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

• US 9,268,682 B2
• Filed: 10/05/2012
• Issued: 02/23/2016
• Est. Priority Date: 10/05/2012
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Skyera, LLC (Western Digital Corporation), Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Tomlin, Andrew J., Mullendore, Rodney N., Jones, Justin, Danilak, Radoslav
• Primary Examiner(s): Cygiel, Gary W
• Application Number:
  US13/645,822
• Publication Number:
  US 20140101369A1
• Time in Patent Office: 1,236 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages

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.

Claims

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 predetermined sequential order;

build a map of the journals stored in the non-volatile memory devices based upon the sequentially read plurality of journals, and

store the built map of the journals in the volatile memory.

21. The data storage of device of claim 1, wherein, among journal entries associated with a given L-Page, only a last-in-time updated journal entry associated with the given L-Page is valid.

22. The data storage device of claim 1, wherein the controller is further configured to maintain a system journal map of the plurality of journals in the volatile memory, each entry in the system journal map pointing to a location in the non-volatile memory devices where one of the plurality of journals is stored.

23. A method of controlling a data storage device comprising a volatile memory and a plurality of non-volatile memory devices, each of the plurality of non-volatile devices being 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, the method comprising:

storing data in a 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 a controller to logically reference data stored in one or more of the physical pages;

maintaining a logical-to-physical address translation map in the volatile memory, the translation map being configured to enable determination of a physical location, within one or more of the physical pages, of the data stored in each L-Page, 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;

maintaining a plurality of journals defining physical-to-logical correspondences in the plurality of non-volatile memory devices, each of the plurality of journals being associated with a journal number, each journal covering a pre-determined range of physical pages and each comprising a plurality of journal entries, each entry being configured to associate one or more physical pages to each L-Page; and

reading the plurality of journals upon startup and rebuilding the logical-to-physical address translation map stored in volatile memory based upon the read entries in the plurality of journals.

24. The method of claim 23, further comprising creating a new entry in one of the plurality of journals upon an update to one of the plurality of L-Pages.

25. The method of claim 24, further comprising triggering write operations to the non-volatile memory devices to maintain a power-safe copy of translation data based on newly created journal entries instead of saving at least portions of the logical-to-physical address translation map, such that a write amplification is reduced.

26. The method of claim 24, wherein the new entry indicates a physical location, within a physical page, of a start of the updated L-Page.

27. The method of claim 24, further comprising updating a free space accounting by an amount corresponding to a length of the L-Page prior to being updated.

28. The method of claim 23, wherein storing comprises storing at least one of the plurality of L-Pages at a location that is unaligned with physical page boundaries.

29. The method of claim 23, 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.

30. The method of claim 23, further comprising updating 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.

31. The method of claim 23, wherein the plurality of devices comprises 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 associated one or more of the physical pages of the S-Block to each L-Page.

32. The method of claim 31, further comprising:

selecting an S-Block 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.

33. The method of claim 32, wherein selecting comprises weighing free space and program erase (PE) count in determining which S-Block to select.

34. The method of claim 33, wherein the journal number comprises a predetermined number of most significant bits of an address of a first physical page covered by the journal.

35. The method of claim 31, further comprising

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 address 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.

36. The method of claim 23, wherein each of the plurality of journal entries comprises:

an L-Page number, and

a physical address location.

37. The method of claim 23, 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.

38. The method of claim 23, 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.

39. The method of claim 23, further comprising selectively compressing the plurality of L-Pages such that the plurality of L-Pages vary in size and wherein the plurality of journals are configured to reference a greater number of L-Pages of smaller size or a lesser number of L-Pages of greater size.

40. The method of claim 23, wherein reading the plurality of journals upon startup and rebuilding the logical-to-physical address translation map comprises reading the plurality of journals upon startup in a predetermined sequential order and rebuilding the logical-to-physical address translation map stored in volatile memory based upon the read plurality of journals.

41. The method of claim 23, wherein the controller is further configured to build a journal map based on the plurality of journals.

42. The method of claim 23, further comprising:

reading the plurality of journals upon startup in a predetermined sequential order;

building a map of the journals stored in the non-volatile memory devices based upon the sequentially read plurality of journals, and

storing the built map of the journals in the volatile memory.

43. The method of claim 23 wherein, among journal entries associated with a given L-Page, only a last-in-time updated journal entry associated with the given L-Page is valid.

44. The method of claim 23, further comprising maintaining a system journal map of the plurality of journals in the volatile memory, each entry in the system journal map pointing to a location in the non-volatile memory devices where one of the plurality of journals is stored.

45. A data storage device controller, comprising:

a processor configured to couple to a volatile memory and to a plurality of non-volatile memory devices, each of the plurality of non-volatile memory devices being configured to store a plurality of physical pages at a predetermined physical location within the plurality of non-volatile memory devices, the processor being further configured to program data to and read data from the plurality of non-volatile memory devices, the data being stored in a 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 processor to logically reference data stored in one or more of the physical pages, the volatile memory being configured to store a logical-to-physical address translation map configured to enable the processor to determine a physical location, within one or more physical pages, of the data stored in each L-Page,

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 processor 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 processor is further 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.