Write updates sorting during BKOPS idle
A data storage device includes a memory device and a controller coupled to the memory device. The controller is configured to store data mappings in an uLayer, where the uLayer includes a plurality of mSet updates, and where the uLayer is organized into a sorted section and an unsorted section, sort one or more of the plurality of mSet updates of the uLayer, and provide, to a host device, data stored in the memory device corresponding to a most recent update of a data mapping by ignoring non-recent updates for a read command associated with an mSet group of the sorted section.
1. A data storage device, comprising:
a memory device; and
a controller coupled to the memory device, the controller configured to:
store data mappings in an uLayer, wherein the uLayer includes a plurality of mSet updates, and wherein the uLayer is organized into a sorted section and an unsorted section;
sort one or more of the plurality of mSet updates of the uLayer, wherein the uLayer is a linked list of data mapping updates, and wherein an mSet includes a plurality of logical block address (LBA) to physical block address (PBA) mappings; and
provide, to a ho st device, data stored in the memory device corresponding to a most recent update of a data mapping by ignoring non-recent updates for a read command associated with an mSet group of the sorted section, wherein the controller is further configured to:
receive a first update for a first mSet;
store the first update for the first mSet in the unsorted section;
receive a second update for a second mSet;
store the second update for the second mSet in the unsorted section, wherein the second update is stored adjacent to the first update;
receive a third update for the first mSet; and
store the third update for the first mSet in the unsorted section, wherein the third update is adjacent to the second update, wherein the controller is further configured to:
determine that the first mSet is associated with a first mSet group of the sorted section; and
determine that the second mSet is associated with a second mSet group of the sorted section, wherein the controller is further configured to:
copy the first update and the third update from the unsorted section to the first mSet group while maintaining chronological order for the first mSet group; and
copy the second update from the unsorted section to the second mSet group while maintaining chronological order for the second mSet group.
2. The data storage device of claim 1 , wherein the controller is further configured to erase the first update, the second update, and the third update from the unsorted section upon completion of the copying.
3. A data storage device, comprising:
a memory device; and
a controller coupled to the memory device, the controller configured to:
receive a read command for data stored in the memory device;
search an uLayer corresponding to the read command for a data mapping, wherein the uLayer includes a plurality of mSet updates, and wherein the uLayer is organized into a sorted section and an unsorted section, wherein the uLayer is a linked list of data mapping updates, and wherein an mSet includes a plurality of logical block address (LBA) to physical block address (PBA) mappings; and
retrieve first data stored in the memory device corresponding to a most recent update of the data mapping corresponding to the read command by ignoring non-recent updates for a read command associated with an mSet group of the sorted section, wherein the controller is further configured to:
determine that there is another most recent update of the data mapping corresponding to the read command in the unsorted section; and
retrieve second data stored in the memory device corresponding to the another most recent update of the data mapping for the read command located in another mSet of the unsorted section.
4. The data storage device of claim 3 , wherein the controller is further configured to:
determine whether the first data or the second data is the most recent update; and
provide, to a host device, either the first data or the second data based on the determining.
5. The data storage device of claim 3 , wherein the plurality of mSets of the sorted section is sorted by mSet group and by chronological order, and wherein the plurality of mSets of the unsorted section is stored in chronological order by arrival time.
6. A data storage device, comprising:
a memory device; and
a controller coupled to the memory device, the controller configured to:
receive a read command for data stored in the memory device;
search an uLayer corresponding to the read command for a data mapping, wherein the uLayer includes a plurality of mSet updates, and wherein the uLayer is organized into a sorted section and an unsorted section, wherein the uLayer is a linked list of data mapping updates, and wherein an mSet includes a plurality of logical block address (LBA) to physical block address (PBA) mappings; and
retrieve first data stored in the memory device corresponding to a most recent update of the data mapping corresponding to the read command by ignoring non-recent updates for a read command associated with an mSet group of the sorted section, wherein the controller is further configured to sort the unsorted section into the sorted section, while maintaining chronological order per mSet group of the sorted section, during idle time or background operations occurring.
7. The data storage device of claim 6 , wherein the controller is further configured to:
determine that a first update corresponds to a first data mapping and a second update corresponds to a the first data mapping;
determine whether the first update or the second update is a most recent update; and
ignore either the first update or the second update based on the determining.
8. The data storage device of claim 7 , wherein the controller is further configured to keep track of the ignored update in an outdated list, and wherein the outdated list is used for block reuse operations.
9. A data storage device, comprising:
memory means; and
a controller coupled to the memory means, the controller configured to:
store data mappings in an uLayer, wherein the uLayer includes a plurality of mSet updates, and wherein the uLayer is organized into a sorted section and an unsorted section, wherein the uLayer is a linked list of data mapping updates, and wherein an mSet includes a plurality of logical block address (LBA) to physical block address (PBA) mappings, wherein the controller is further configured to search the sorted section fora most recent update of a data mapping corresponding to data stored in the memory means, wherein the controller is further configured to:
search the unsorted section for a most recent update of the data mapping prior to searching the sorted section; and
either:
provide the data mapping when the most recent update is present in the unsorted section; or
search the sorted section for the most recent update of the data mapping, wherein, when the most recent update is not in the sorted section or the unsorted section, the controller is further configured to load the data mapping from the memory means.
10. The data storage device of claim 9 , wherein the searching is completed in binary search and skips non-relevant updates.