Methods, devices and systems for physical-to-logical mapping in solid state drives

Patent metadata

Field	Value
Publication number	US-9268682-B2
Application number	US-201213645822-A
Country	US
Kind code	B2
Filing date	Oct 5, 2012
Priority date	Oct 5, 2012
Publication date	Feb 23, 2016
Grant date	Feb 23, 2016

Abstract

A data storage device comprises a plurality of non-volatile memory devices storing physical pages, each stored at a predetermined physical location. A controller may be coupled to the memory devices and configured to access data stored in a plurality of logical pages (L-Pages), each associated with an L-Page number that enables the controller to logically reference data stored in the physical pages. A volatile memory may comprise a logical-to-physical address translation map that enables the controller to determine a physical location, within the physical pages, of data stored in each L-Page. The controller may be configured to maintain, in the memory devices, journals defining physical-to-logical correspondences, each journal covering a predetermined range of physical pages and comprising a plurality of entries that associate one or more physical pages to each L-Page. The controller may read the journals upon startup and rebuild the address translation map from the read journals.

First claim

The invention claimed is:

1. A data storage device, comprising:
a plurality of non-volatile memory devices, each configured to store a plurality of physical pages, each of the plurality of physical pages being stored at a predetermined physical location within the plurality of non-volatile devices;
a volatile memory comprising a logical-to-physical address translation map configured to enable a controller to determine a physical location, within one or more physical pages, of the data stored in a plurality of logical pages (L-Pages); and
the controller coupled to the plurality of non-volatile memory devices and configured to program data to and read data from the plurality of non-volatile memory devices, the data being stored in the plurality of logical pages (L-Pages), each of the plurality of L-Pages being associated with an L-Page number that is configured to enable the controller to logically reference data stored in the one or more of the physical pages using the logical-to-physical address translation map, wherein an entry in the logical-to-physical address translation map includes an association between an L-page number and at least one of a length of the L-page or a size of error correcting code bits to be applied to the entry in the logical-to-physical address translation map,
wherein the controller is configured to maintain, in the plurality of non-volatile memory devices, a plurality of journals defining physical-to-logical correspondences, each of the plurality of journals being associated with a journal number, each journal covering a pre-determined range of physical pages and comprising a plurality of journal entries, each entry being configured to associate one or more physical pages to each L-Page, wherein the controller is configured to read the plurality of journals upon startup and rebuild the logical-to-physical address translation map stored in the volatile memory from the read plurality of journals.

2. The data storage device of claim 1 , wherein the controller is further configured to, upon an update to one of the plurality of L-Pages, create a new entry in one of the plurality of journals.

3. The data storage device of claim 2 , wherein write operations to the non-volatile memory devices to maintain a power-safe copy of translation data are configured to be triggered by newly created journal entries instead of saving at least portions of the logical-to-physical address translation map, such that write amplification is reduced.

4. The data storage device of claim 2 , wherein the new entry indicates a physical location, within a physical page, of a start of the updated L-Page.

5. The data storage device of claim 2 , wherein the controller is further configured to update a free space accounting by an amount corresponding to a length of the L-Page prior to being updated.

6. The data storage device of claim 2 , wherein the controller is further configured to update the logical-to-physical address translation map with the physical location, within one or more physical pages, of the data referenced by the L-Page number of the updated L-Page.

7. The data storage device of claim 1 , wherein at least one of the plurality of L-Pages is unaligned with physical page boundaries.

8. The data storage device of claim 1 , wherein the physical pages are implemented as Error Correcting Code (ECC) pages (E-Pages) and wherein the plurality of devices comprises a plurality of flash memory blocks, each flash memory block comprising a plurality of flash memory pages (F-Pages), each of the F-Pages comprising a plurality of the E-Pages, each of the plurality of E-Pages being stored at a predetermined physical location within the plurality of devices.

9. The data storage device of claim 1 , further comprising a plurality of super blocks (S-Blocks), each comprising one or more flash memory blocks per device and wherein each of the plurality of journal entries is configured to associate one or more of the physical pages of the S-Block to each L-Page.

10. The data storage device of claim 9 , wherein the controller is further configured to garbage collect by at least:
selecting one of the plurality of S-Blocks to garbage collect;
comparing each entry in a journal for the selected S-Block to entries in the logical-to-physical address translation map and designating entries that match as valid and entries that do not match as invalid;
reading the L-Pages corresponding to the valid entries;
writing the read L-Pages to respective physical addresses within the plurality of non-volatile memory devices;
updating the logical-to-physical address translation map for the valid entries to point to the respective physical addresses; and
generating new journal entries for the entries for which the logical-to-physical address translation map was updated.

11. The data storage device of claim 10 , wherein selecting comprises weighing free space and program erase (PE) count in determining which S-Block to select.

12. The data storage device of claim 9 , wherein the controller is further configured to garbage collect by at least:
selecting one of the plurality of S-Blocks to garbage collect;
reading the physical pages of the selected S-Block;
comparing L-Page numbers in the read physical pages of the selected S-Block to entries in the logical-to-physical translation map and designating entries that match as valid and entries that do not match as invalid;
writing the L-Pages corresponding to the valid entries to respective physical addresses within the plurality of non-volatile memory devices;
updating the logical-to-physical address translation map for the valid entries to point to the respective physical addresses; and
generating new journal entries for the entries for which the logical-to-physical address translation map was updated.

13. The data storage device of claim 1 , wherein each journal number comprises a predetermined number of most significant bits of an address of a first physical page covered by the journal.

14. The data storage device of claim 1 , wherein each of the plurality of journal entries comprises:
an L-Page number, and
a physical address location.

15. The data storage device of claim 1 , wherein each of the plurality of journal entries comprises:
an L-Page number;
a physical address location of a physical page, and
an L-Page size.

16. The data storage device of claim 1 , wherein each of the plurality of journal entries comprises:
a predetermined number of least significant bits of an address of a physical page that includes a start of an L-Page;
an address;
an L-Page size; and
an offset into the physical page.

17. The data storage device of claim 1 , wherein the plurality of L-Pages are configured to be compressed and to vary in size, and wherein the plurality of journal numbers are configured to reference a greater number of L-Pages of smaller size or a lesser number of L-Pages of greater size.

18. The data storage device of claim 1 , wherein the controller is further configured to read the plurality of journals upon startup in a predetermined sequential order and rebuild the logical-to-physical address translation map stored in volatile memory based upon the sequentially read plurality of journals.

19. The data storage device of claim 1 , wherein the controller is further configured to build a journal map based on the plurality of journals.

20. The data storage device of claim 1 , wherein the controller is further configured to:
read the plurality of journals upon startup in a predetermin

Assignees

• Western Digital Tech Inc
• Skyera Llc

Inventors

• Tomlin Andrew J
• Mullendore Rodney N
• Jones Justin
• Danilak Radoslav

Classifications

• G06F2212/7201

  Logical to physical mapping or translation of blocks or pages · CPC title

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title