Methods, devices and systems for hardware-based garbage collection in solid state drives

• US 9,489,296 B1
• Filed: 10/17/2012
• Issued: 11/08/2016
• Est. Priority Date: 10/17/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
• Primary Examiner(s): Yi, David X
• Assistant Examiner(s): Grullon, Francisco
• Application Number:
  US13/654,288
• Time in Patent Office: 1,483 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0638 Combination of memories, e.g. ROM and RAM such as to permit replacement or supplementing of words in one module by words in another module address formation of the next microinstruction G06F9/26; masking faults in memories by using spares or by reconfiguring G11C29/70
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 2212/1008 Correctness of operation, e.g. memory ordering
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/205 Hybrid memory, e.g. using both volatile and non-volatile memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7209 Validity control, e.g. using flags, time stamps or sequence numbers
• CPC Class Codes: G06F 2212/7211 Wear leveling

Abstract

A data storage device may comprise non-volatile memory devices, each configured to store a plurality of physical pages, a controller and a first volatile memory configured to store a logical-to-physical address translation map that enables the controller to determine a physical location of logical pages. The controller may maintain, in the memory devices, a plurality of journals defining physical-to-logical page correspondences, each entry of which associating one or more physical pages to a logical page. Garbage collection may be carried out by reading entries of the journals; determining a validity of each logical page referenced by the read entries through a comparison with a corresponding entry in the map, the logical pages referenced by the read entries being stored in first physical pages; writing logical pages determined to be valid to second physical pages and updating the map accordingly; and designating at least the first physical pages as free space.

Claims

1. A solid state drive controller, comprising:

a processor configured to couple to a plurality of non-volatile memory devices, each configured to store a plurality of physical pages; and

a first volatile memory configured to store a logical-to-physical address translation map configured to enable the controller to determine a physical location of logical pages stored within one or more of the plurality of physical pages;

wherein the processor is further configured to;

maintain, in the plurality of non-volatile memory devices, a plurality of journals defining physical-to-logical page correspondences and comprising a plurality of journal entries, each entry associating one or more physical pages to a logical page, at least one of the plurality of journals containing last-in-time updates to logical pages and stale entries that no longer point to valid logical pages,

wherein each of the plurality of journals covers a predetermined physical region of the non-volatile memory, the predetermined physical region comprising a predetermined range of the plurality of physical pages, and each of the plurality of journals comprises an identification number based on address information of a physical page covered by the journal;

create a journal entry directly into one of the plurality of journals each time a logical page in the logical-to-physical address translation map is updated; and

perform garbage collection, wherein garbage collection comprises;

reading entries of at least one of the plurality of journals;

determining a validity of each logical page referenced by the read entries through a comparison with a corresponding entry in the address translation map, wherein the logical pages referenced by the read entries are stored in first physical pages;

writing logical pages determined to be valid to second physical pages and updating the address translation map accordingly; and

designating at least the first physical pages as free space.

2. The solid state drive controller of claim 1, wherein the processor is further configured to:

before updating the address translation map, determine whether the address translation map has been updated to invalidate the logical pages previously determined to be valid,

for logical pages that have not been invalidated, update the address translation map to reflect locations in the second physical pages; and

for logical pages that have been invalidated, do not update the address translation map to reflect locations in the second physical pages.

3. The solid state drive controller of claim 2, wherein at least one of the logical pages written to the second physical pages has been invalidated.

4. The solid state drive controller of claim 1, wherein the processor is further configured to:

before writing the logical pages determined to be valid to the second physical pages and updating the address translation map,

determine whether the address translation map has been updated to invalidate the logical pages previously determined to be valid,

for logical pages that have not been invalidated, write to the second physical pages and update the address translation map to reflect locations in the second physical pages; and

for logical pages that have been invalidated, do not write to the second physical pages and do not update the address translation map for the logical pages that have been invalidated.

5. The solid state drive controller of claim 1, wherein the processor is further configured to generate at least one new journal comprising entries associating the second physical pages to the valid logical pages.

6. The solid state drive controller of claim 5, wherein the processor is further configured to write the generated journal to a second volatile memory.

7. The solid state drive controller of claim 6, wherein the processor is further configured to scan the journal written to the second volatile memory for invalid entries through comparison with corresponding entries in the address translation map.

8. The solid state drive controller of claim 7, wherein the processor is further configured to remove any invalid entries from the scanned journal.

9. The solid state drive controller of claim 7, wherein the processor is further configured to write the scanned journal to the non-volatile devices before any other journal is written to the non-volatile devices.

10. The solid state drive controller of claim 1, wherein the processor is further configured to add at least an aggregate size of the first physical pages designated as free space to a running count of free space.

11. The solid state drive controller of claim 1, wherein the plurality of non-volatile memory devices comprise a plurality of superblocks, each comprising one block per die within the devices, and wherein one or more of the plurality of journals are associated with a superblock.

12. The solid state drive controller of claim 11, wherein the entries read as part of the garbage collection are from at least one journal associated with a selected superblock.

13. The solid state drive controller of claim 12, wherein the processor is further configured to choose the selected superblock based at least in part upon a program erase (PE) count of the selected superblock.

14. The solid state drive controller of claim 12, wherein the processor is further configured to choose the selected superblock based at least in part upon an amount of free space therein.

15. The solid state drive controller of claim 11, wherein the second physical pages are associated with a superblock that has been designated as a superblock for storing valid logical pages from garbage collection operations.

16. The solid state drive controller of claim 1, wherein the garbage collection is performed in hardware.

17. A data storage device, comprising:

the plurality of non-volatile memory devices; and

the solid state drive controller of claim 1.

18. A solid state drive controller, comprising:

a processor configured to couple to a plurality of non-volatile memory devices, each configured to store a plurality of physical pages and to;

write data to and read data from the memory devices; and

maintain, in the memory devices, a plurality of journals comprising a plurality of journal entries, each entry associating a physical location in the memory devices to a logical page that is stored in the memory devices, at least one of the plurality of journals containing last-in-time updates to logical pages and stale entries that no longer point to valid logical pages,

wherein each of the plurality of journals covers a predetermined physical region of the non-volatile memory, the predetermined physical region comprising a predetermined range of the plurality of physical pages, and each of the plurality of journals comprises an identification number based on address information of a physical page covered by the journal;

create a journal entry directly into one of the plurality of journals each time a logical page is updated;

a volatile memory configured to store;

a logical-to-physical address translation map configured to enable the processor to determine a physical location of the logical pages within the memory devices; and

a journal translation map configured to enable the processor to determine a physical location of the journals within the memory devices;

wherein the processor is further configured to;

perform garbage collection of a memory block in the memory devices that stores a plurality of journals, the performing including at least, for each journal in the memory block;

determining whether the journal is valid based at least in part on a check with the journal translation map;

when the journal is determined to be valid,

determining validity of one or more entries in the journal through a comparison with a corresponding entry in the address translation map; and

writing valid entries to a new journal and updating the journal translation map accordingly.

19. The solid state drive controller of claim 18, wherein the processor is further configured to designate at least the memory block as free space.

20. A data storage device, comprising:

the plurality of non-volatile memory devices; and

the solid state drive controller of claim 18.

21. A method for controlling a data storage device, the data storage device comprising a plurality of non-volatile memory devices, each being configured to store a plurality of physical pages;

a controller coupled to the plurality of memory devices and configured to program data to and read data from the plurality of memory devices; and

a first volatile memory configured to store a logical-to-physical address translation map configured to enable the controller to determine a physical location of logical pages stored within one or more of the plurality of physical pages, the method comprising;

maintaining, in the plurality of non-volatile memory devices, a plurality of journals defining physical-to-logical page correspondences and comprising a plurality of journal entries, each associating one or more physical pages to a logical page, at least one of the plurality of journals containing last-in-time updates to logical pages and stale entries that no longer point to valid logical pages,

wherein each of the plurality of journals covers a predetermined physical region of the non-volatile memory, the predetermined physical region comprising a predetermined range of the plurality of physical pages, and each of the plurality of journals comprises an identification number based on address information of a physical page covered by the journal;

creating a journal entry directly into one of the plurality of journals each time a logical page in the logical-to-physical address translation map is updated; and

performing garbage collection by at least;

reading entries of at least one of the plurality of journals;

determining a validity of each logical page referenced by the read entries through a comparison with a corresponding entry in the address translation map, wherein the logical pages referenced by the read entries are stored in first physical pages;

writing logical pages determined to be valid to second physical pages and updating the address translation map accordingly; and

designating at least the first physical pages as free space.

22. The method of claim 21, further comprising:

before updating the address translation map, determining whether the address translation map has been updated to invalidate the logical pages previously determined to be valid,

for logical pages that have not been invalidated, updating the address translation map to reflect locations in the second physical pages; and

for logical pages that have been invalidated, not updating the address translation map to reflect locations in the second physical pages.

23. The method of claim 22, wherein at least one of the logical pages written to the second physical pages has been invalidated.

24. The method of claim 21, further comprising:

before writing the logical pages determined to be valid to the second physical pages and updating the address translation map, determining whether the address translation map has been updated to invalidate the logical pages previously determined to be valid,

for logical pages that have not been invalidated, writing to the second physical pages and updating the address translation map to reflect locations in the second physical pages; and

for logical pages that have been invalidated, not writing to the second physical pages and not updating the address translation map for the logical pages that have been invalidated.

25. The method of claim 21, further comprising generating at least one new journal comprising entries associating the second physical pages to the valid logical pages.

26. The method of claim 25, further comprising writing the generated journal to a second volatile memory.

27. The method of claim 26, further comprising scanning the journal written to the second volatile memory for invalid entries through comparison with corresponding entries in the address translation map.

28. The method of claim 27, further comprising removing any invalid entries from the scanned journal.

29. The method of claim 27, further comprising writing the scanned journal to the non-volatile memory devices before any other journal is written to the non-volatile memory devices.

30. The method of claim 21, further comprising adding at least an aggregate size of the first physical pages designated as free space to a running count of free space.

31. The method of claim 21, wherein the plurality of non-volatile memory devices comprise a plurality of superblocks, each comprising one block per die within the devices, and wherein one or more of the plurality of journals are associated with a superblock.

32. The method of claim 31, wherein the entries read as part of the garbage collection are from at least one journal associated with a selected superblock.

33. The method of claim 32, further comprising choosing the selected superblock based at least in part upon a program erase (PE) count of the selected superblock.

34. The method of claim 32, further comprising choosing the selected superblock based at least in part upon an amount of free space therein.

35. The method of claim 31, wherein the second physical pages are associated with a superblock that has been designated as a superblock for storing valid logical pages from garbage collection operations.

36. The method of claim 21, further comprising performing the garbage collection in hardware.

37. A method of controlling a data storage device, the data storage device comprising a plurality of non-volatile memory devices each configured to store a plurality of physical pages, a controller and a volatile memory, the controller being coupled to the plurality of memory devices and being configured to write data to and read data from the memory devices, the method comprising the controller:

maintaining, in the memory devices, a plurality of journals comprising a plurality of journal entries, each entry associating a physical location in the memory devices to a logical page that is stored in the memory devices, at least one of the plurality of journals containing last-in-time updates to logical pages and stale entries that no longer point to valid logical pages,

wherein each of the plurality of journals covers a predetermined physical region of the non-volatile memory, the predetermined physical region comprising a predetermined range of the plurality of physical pages, and each of the plurality of journals comprises an identification number based on address information of a physical page covered by the journal;

creating a journal entry directly into one of the plurality of journals each time a logical page is updated;

storing, in the volatile memory, a logical-to-physical address translation map configured to enable the controller to determine a physical location of the logical pages within the memory devices;

storing, in the volatile memory, a journal translation map configured to enable the controller to determine a physical location of the journals within the memory devices;

performing garbage collection of a memory block in the memory devices that stores a plurality of journals, by at least, for each journal in the memory block,

determining whether the journal is valid based at least in part on a check with the journal translation map; and

when the journal is determined to be valid,

determining validity of one or more entries in the journal through a comparison with a corresponding entry in the address translation map; and

writing valid entries to a new journal and updating the address translation map accordingly.

38. The method of claim 37, further comprising designating at least the memory block as free space.