System data management using garbage collection and hybrid self mapping

• US 8,966,205 B1
• Filed: 05/10/2012
• Issued: 02/24/2015
• Est. Priority Date: 05/10/2012
• Status: Active Grant

• Current Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Lo, Jerry, Adi, Frederick H.
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): Wong, Nanci
• Application Number:
  US13/468,946
• Time in Patent Office: 1,020 Days
• Field of Search: 711/165
• US Class Current: 711/165
• 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 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7204 Capacity control, e.g. partitioning, end-of-life degradation
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control

Abstract

A data storage system is disclosed that utilizes garbage collection and hybrid self-mapping for managing system data. In one embodiment, a system data region having an amount of valid system data that is below a threshold is freed. Write amplification associated with managing and storing system data can be reduced at least in part because only valid system data can be copied during garbage collection of the selected region. Mapping information associating system data with physical locations in non-volatile storage where system data is stored can be generated, which can reduce system data reconstruction time during start-up of the data storage system. Increase in efficiency and reduction in startup and initialization time can be attained.

Claims

1. In a data storage system comprising a non-volatile memory array and a controller, a method of managing a mapping table comprising a plurality of table pages associating logical addresses with physical locations in the non-volatile memory array where data is stored, the method comprising:

storing a first set of table pages in a first region of the non-volatile memory array;

storing a second set of table pages in a second region of the non-volatile memory array, wherein the first and second regions are configured to achieve concurrent execution of storage access operations;

executing a plurality of storage access operations;

determining whether certain pages of the first and second sets of table pages have become invalid as a result of executing the storage access operations;

determining the number of remaining valid table pages existing at least in the first set of table pages;

generating a mapping page that includes information indicating the determined number of remaining valid table pages in each of the first and second regions, wherein the determined number of remaining valid table pages is included in a header of the mapping page; and

if the number of the remaining valid table pages satisfies a threshold;

copying the valid table pages of the first set to a third region of the non-volatile memory array; and

freeing the first region,

wherein, by delaying the copying of mapping table pages until the number of the remaining valid tables pages satisfies the threshold, the number of table pages copied is reduced, and

wherein the method is performed under the control of the controller.

2. The method of claim 1, wherein the non-volatile memory array further comprises a plurality of additional regions, and wherein the method further comprises:

determining a region that includes the smallest number of valid table pages of any region of the non-volatile memory array where table pages are stored;

copying the valid table pages of the determined region to a third region of the non-volatile memory array; and

freeing the determined region.

3. The method of claim 1, wherein executing the storage access operations comprises executing write data operations, each write data operation comprising a logical address in the data storage system and a data unit.

4. The method of claim 3, further comprising at least partially in response to executing each of the write data operations:

invalidating a first table page indicating an existing association between the logical address corresponding to a write data operation and a physical location in the non-volatile memory array; and

storing, in a second table page, a new association between the logical address and another physical location in the non-volatile memory array where the data unit corresponding to the write data operation is written, wherein the second table page is a replacement for the first table page.

5. The method of claim 1, wherein the mapping page additionally includes information indicating non-volatile memory array locations in which at least some of the plurality of table pages are stored, and wherein the mapping page reduces a time needed for reconstruction of at least a part of the mapping table.

6. The method of claim 5, further comprising storing the mapping page in the non-volatile memory array if the number of the remaining valid table pages satisfies the threshold.

7. The method of claim 5, further comprising generating an updated mapping page that reflects one or more of:

changes to the locations where table pages are stored due to the copying of the table pages to other non-volatile memory array regions and changes to the locations where table pages are stored due to the table pages becoming invalid as a result of executing the storage access operations.

8. The method of claim 5, further comprising reconstructing the mapping table by:

using the mapping page, locating in the non-volatile memory array a table page; and

loading the located table page from the non-volatile memory array to a volatile memory.

9. The method of claim 1, wherein logs configured to track changes to the table pages are not generated.

10. The method of claim 1, wherein the first region comprises a first superblock and the second region comprises a second superblock.

25. The method of claim 1, wherein the mapping page is stored in the third region along with the copied valid table pages.

11. A data storage system comprising:

a non-volatile memory array configured to store data and a mapping table comprising a plurality of table pages associating logical addresses with physical locations in the non-volatile memory array where data is stored; and

a controller configured to;

store a first set of table pages in a first region of the non-volatile memory array;

store a second set of table pages in a second region of the non-volatile memory array, wherein the first and second regions are configured to achieve concurrent execution of storage access operations;

execute a plurality of storage access operations;

determine whether certain pages of the first and second sets of table pages have become invalid as a result of executing the storage access operations;

determine the number of remaining valid table pages existing at least in the first set of table pages;

generate a mapping page that includes information indicating the determined number of remaining valid table pages in each of the first and second regions, wherein the determined number of remaining valid table pages is included in a header of the mapping page; and

if the number of the remaining valid table pages satisfies a threshold;

copy the valid table pages of the first set to a third region of the non-volatile memory array; and

free the first region.

12. The data storage system of claim 11, wherein the non-volatile memory array further comprises a plurality of additional regions, and wherein the controller is further configured to:

determine a region that includes the smallest number of valid table pages of any region of the non-volatile memory array where table pages are stored;

copy the valid table pages of the determined region to a third region of the non-volatile memory array; and

free the determined region.

13. The data storage system of claim 11, wherein the storage access operations comprise write data operations, each write data operation comprising a logical address in the data storage system and a data unit.

14. The data storage system of claim 13, wherein, at least partially in response to executing each of the write data operations, the controller is further configured to:

invalidate a first table page indicating an existing association between the logical address corresponding to a write data operation and a physical location in the non-volatile memory array; and

store, in a second table page, a new association between the logical address and another physical location in the non-volatile memory array where the data unit corresponding to the write data operation is written, wherein the second table page is a replacement for the first table page.

15. The data storage system of claim 11, wherein the mapping page additionally includes information indicating non-volatile memory array locations in which at least some of the plurality of table pages are stored, wherein the mapping page reduces a time needed for reconstruction of at least a part of the mapping table.

16. The data storage system of claim 15, wherein the controller is further configured to store the mapping page in the non-volatile memory array if the number of the remaining valid table pages satisfies the threshold.

17. The data storage system of claim 15, wherein the controller is further configured to generate an updated mapping page that reflects one or more of:

changes to the locations where table pages are stored due to the copying of the table pages to other non-volatile memory array regions and changes to the locations where table pages are stored due to the table pages becoming invalid as a result of executing the storage access operations.

18. The data storage system of claim 15, wherein the controller is further configured to:

using the mapping page, locate in the non-volatile memory array a table page; and

load the located table page from the non-volatile memory array to a volatile memory.

19. The data storage system of claim 11, wherein the controller is configured to not generate logs configured to track changes to the table pages.

20. The data storage system of claim 11, wherein the first region comprises a first superblock and the second region comprises a second superblock.

21. In a data storage system comprising a non-volatile memory array and a controller, a method of managing system data stored in a plurality of non-volatile memory array pages, the method comprising:

storing a first set of system data pages of a first region of the non-volatile memory array;

storing a second set of system data pages of a second region of the non-volatile memory array, wherein the first and second regions are configured to achieve concurrent execution of storage access operations;

executing a plurality of storage access operations;

determining whether at least some pages of the first and second sets of system data pages have become invalid as a result of executing the storage access operations;

determining the number of remaining valid system data pages existing at least in the first set of system data pages;

generating a mapping page that includes information indicating the determined number of remaining valid table pages in each of the first and second regions, wherein the determined number of remaining valid table pages is included in a header of the mapping page; and

if the number of the remaining valid system data pages satisfies a threshold;

copying the valid system data pages of the first set to a third region of the non-volatile memory array; and

freeing the first region,

wherein the method is performed under the control of the controller.

22. The method of claim 21, wherein the non-volatile memory array further comprises a plurality of additional regions, and wherein the method further comprises:

determining a region that includes the smallest amount of valid system data pages of any region of the non-volatile memory array where system data is stored;

copying the valid system data pages of the determined region to a third region of the non-volatile memory array; and

freeing the determined region.

23. The method of claim 21, further comprising generating mapping information indicating non-volatile memory array locations in which at least some of the plurality of pages storing system data are located, wherein the mapping information reduces a time needed for reconstruction of at least a part of the system data.

24. The method of claim 21, wherein the system data comprises a logical to physical address mapping table.