System data management using garbage collection and logs

• US 9,977,612 B1
• Filed: 05/11/2012
• Issued: 05/22/2018
• Est. Priority Date: 05/11/2012
• Status: Active Grant

• Current Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Lo, Jerry, Suryabudi, Dominic S.
• Primary Examiner(s): Lo, Ann J
• Assistant Examiner(s): Villanueva, Leandro R
• Application Number:
  US13/470,206
• Time in Patent Office: 2,202 Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1041 Resource optimization
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/068 Hybrid storage device
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

A data storage system is disclosed that utilizes garbage collection and logs for managing system data. In one embodiment, system data stored in a non-volatile memory is updated based on the character of changes to data stored in a data storage system (e.g., changes caused by host system activity). For example, when changes to stored data are scattered (e.g., changes are made to random memory locations), it may be beneficial to generate and accumulate more logs reflecting changes to the system data. As another example, when changes to stored data are substantially consolidated (e.g., changes are made to consecutive memory locations), it may be beneficial to update system data stored in the non-volatile memory more frequently. Reduction in write amplification, increase in efficiency, and reduction in start-up and initialization time can be attained. Reconstruction time of system data can also be reduced.

Claims

1. In a data storage system comprising a non-volatile memory array and a controller, a method of managing system data, the method comprising:

executing a plurality of storage access commands received from a host system, the plurality of storage access commands being associated with host data, wherein the execution of the plurality of storage access commands causes first system data stored in the non-volatile memory array to become outdated, the first system data being different from the host data;

selectively generating log pages to record changes to the first system data and not the host data, the changes being caused by the execution of the plurality of storage access commands;

storing the log pages in the non-volatile memory array;

determining whether the execution of the plurality of storage access commands causes second system data stored in the non-volatile memory array to become outdated, the first system data and the second system data being stored in the same non-volatile memory pages;

in response to determining that the execution of the plurality of storage access commands causes the second system data to become outdated, updating the first and second system data based on the log pages at a first update frequency so that at least some of the first and second system data becomes current; and

in response to determining that the execution of the plurality of storage access commands does not cause the second system data to become outdated, updating the first and second system data based on the log pages at a second update frequency so that at least some of the first and second system data becomes current, wherein the first update frequency is different than the second update frequency,

wherein the method reduces write amplification of the non-volatile memory array associated with managing the first and second system data, and

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

2. The method of claim 1, wherein one or both of the first and second system data comprises a mapping table that associates a set of logical addresses in the data storage system with a set of physical locations in the non-volatile memory array where the host data is stored.

3. The method of claim 1, wherein selectively generating the log pages comprises:

generating a first set of log pages to record the changes to the first system data caused by the execution of the plurality of storage access commands when it is determined that the execution of the plurality of storage access commands causes the second system data to become outdated; and

generating a second set of log pages to record the changes to the first system data caused by the execution of the plurality of storage access commands when it is determined that the execution of the plurality of storage access commands does not cause the second system data to become outdated.

4. The method of claim 3, wherein:

updating the first and second system data comprises, in response to determining that a first number of log pages in the first set of log pages exceeds a first threshold;

updating at least some of the outdated first and second system data based on at least some log pages in the first set, and

performing garbage collection of the at least some log pages in the first set after changes reflected in the at least some log pages in the first set are applied to the first and second system data; and

updating the first system data comprises, in response to determining that a second number of log pages in the second set of log pages exceeds a second threshold;

updating at least some of the outdated first system data based on at least some log pages in the second set, and

performing garbage collection of the at least some log pages in the second set after changes reflected in the at least some log pages in the second set are applied to the first system data, wherein the first number of log pages is greater than the second number of log pages.

5. The method of claim 4, wherein:

updating at least some of the outdated first and second system data based on at least some log pages in the first set comprises updating the at least some of the outdated first and second system data based on a third number of log pages of the first set that were generated before other log pages of the first set; and

updating at least some of the outdated first system data based on at least some log pages in the second set comprises updating the at least some of the outdated first system data based on a fourth number of log pages of the second set that were generated before other log pages of the second set, wherein the third number is the same as the fourth number.

6. The method of claim 1, wherein:

execution of the plurality of storage access commands causes the second system data to become outdated when the plurality of storage access commands are directed to consecutive logical addresses in the data storage system; and

execution of the plurality of storage access commands does not cause the second system data to become outdated when the plurality of storage access commands are directed to nonconsecutive logical addresses in the data storage system.

7. The method of claim 1, further comprising performing garbage collection of a set of log pages after changes reflected in the set of log pages are applied to at least one of the first or second system data.

8. The method of claim 1, wherein:

no log pages are generated when it is determined that the execution of the plurality of storage access commands causes the second system data to become outdated; and

the first update frequency is greater than the second update frequency.

9. The method of claim 1, further comprising consolidating the changes recorded in the log pages into at least one new log page and updating at least one of the first or second system data based on the at least one new log page.

10. The method of claim 1, wherein the log pages are interleaved with memory pages storing the first system data.

11. The method of claim 1, wherein the first system data and the second system data correspond to consecutive logical memory addresses.

12. The method of claim 1, further comprising, in response to determining that execution of one or more storage access commands causes the second system data to become outdated:

updating a portion of at least one of the first or second system data stored in the non-volatile memory array without utilizing any log pages; and

generating metadata utilized to invalidate one or more log pages that comprise outdated changes associated with the portion of at least one of the first or second system data.

13. A data storage system comprising:

a non-volatile memory array configured to store host data and system data; and

a controller configured to;

execute a plurality of storage access commands received from a host system, the plurality of storage access commands being associated with host data, wherein the execution of the plurality of storage access commands causes first system data stored in the non-volatile memory array to become outdated, the first system data being different from the host data;

selectively generate log pages to record changes to the first system data and not the host data, the changes being caused by the execution of the plurality of storage access commands;

store the log pages in the non-volatile memory array;

determine whether the execution of the plurality of storage access commands causes second system data stored in the non-volatile memory array to become outdated, the first system data and the second system data being stored in the same non-volatile memory pages;

in response to determining that the execution of the plurality of storage access commands causes the second system data to become outdated, update the first and second system data based on the log pages at a first update frequency so that at least some of the first and second system data becomes current; and

in response to determining that the execution of the plurality of storage access commands does not cause the second system data to become outdated, update the first and second system data based on the log pages at a second update frequency so that at least some of the first and second system data becomes current, wherein the first update frequency is different than the second update frequency.

14. The data storage system of claim 13, wherein one or both of the first and second system data comprises a mapping table that associates a set of logical addresses in the data storage system with a set of physical locations in the non-volatile memory array where the host data is stored.

15. The data storage system of claim 13, wherein the controller is configured to selectively generate log pages by:

generating a first set of log pages to record the changes to the first system data caused by the execution of the plurality of storage access commands when it is determined that the execution of the plurality of storage access commands causes the second system data to become outdated; and

generating a second set of log pages to record the changes to the first system data caused by the execution of the plurality of storage access commands when it is determined that the execution of the plurality of storage access commands does not cause the second system data to become outdated.

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

update the first and second system data by, in response to determining that a first number of log pages in the first set of log pages exceeds a first threshold;

updating at least some of the outdated first and second system data based on at least some log pages in the first set, and

performing garbage collection of the at least some log pages in the first set after changes reflected in the at least some log pages in the first set are applied to the first and second system data; and

update the first system data by, in response to determining that a second number of log pages in the second set of log pages exceeds a second threshold;

updating at least some of the outdated first system data based on at least some log pages in the second set, and

performing garbage collection of the at least some log pages in the second set after changes reflected in the at least some log pages in the second set are applied to the first system data, wherein the first number of log pages is greater than the second number of log pages.

17. The data storage system of claim 16, wherein the controller is configured to:

update at least some of the outdated first and second system data based on at least some log pages in the first set by updating the at least some of the outdated first and second system data based on a third number of log pages of the first set that were generated before other log pages of the first set; and

update at least some of the outdated first system data based on at least some log pages in the second set by updating the at least some of the outdated first system data based on a fourth number of log pages of the second set that were generated before other log pages of the second set, wherein the third number is same as the fourth number.

18. The data storage system of claim 13, wherein:

execution of the plurality of storage access commands causes the second system data to become outdated when the plurality of storage access commands are directed to consecutive logical addresses in the data storage system; and

execution of the plurality of storage access commands does not cause the second system data to become outdated when the plurality of storage access commands are directed to nonconsecutive logical addresses in the data storage system.

19. The data storage system of claim 13, wherein the controller is further configured to perform a garbage collection of a set of log pages after changes reflected in the set of log pages are applied to at least one of the first or second system data.

20. The data storage system of claim 13, wherein:

the controller is configured not to generate log pages when the controller determines that the execution of the plurality of storage access commands causes the second system data to become outdated; and

the first update frequency is greater than the second update frequency.

21. The data storage system of claim 13, wherein the log pages are interleaved with memory pages storing the first system data.

22. In a data storage system comprising a non-volatile memory array and a controller, a method of managing system data, the method comprising:

executing a plurality of storage access commands received from a host system, the plurality of storage access commands being associated with host data, wherein the execution of the plurality of storage access commands causes first system data stored in the non-volatile memory array to become outdated, the first system data being different from the host data;

generating log pages to record changes to the first system data and not the host data, the changes being caused by the execution of the plurality of storage access commands;

storing the log pages in the non-volatile memory array;

in response to determining that a number of generated log pages exceeds a first threshold;

determining whether the execution of the plurality of storage access commands causes second system data stored in the non-volatile memory array to become outdated, the first system data and the second system data being stored in the same non-volatile memory pages;

updating the first system data and the second system data stored in the non-volatile memory array based on a set of generated log pages at an update frequency, the update frequency being based on whether the execution of the plurality of storage access commands causes the second system data stored in the non-volatile memory array to become outdated; and

performing garbage collection of the set of generated log pages after changes reflected in the log pages of the set are applied to the at least one of the first system data or the second system data,

wherein the method reduces write amplification of the non-volatile memory array associated with managing the first system data and the second system data, and

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

23. The method of claim 22, wherein log pages in the set of generated log pages comprise log pages that were generated before other generated log pages and the number of log pages in the set equals to a second threshold.

24. The method of claim 22, wherein the first system data comprises a mapping table that associates a set of logical addresses in the data storage system with a set of physical locations in the non-volatile memory array where the host data is stored.

25. The method of claim 22, wherein the log pages are interleaved with memory pages storing the first system data.

26. In a data storage system comprising a non-volatile memory array and a controller, a method of managing system data, the method comprising:

executing a plurality of storage access commands received from a host system, the plurality of storage access commands being associated with host data, wherein the execution of the plurality of storage access commands comprising the host data causes first system data stored in the non-volatile memory array to become outdated, the first system data being different from the host data;

generating a log page to record changes to the first system data and not the host data, the changes being caused by the execution of the plurality of storage access commands;

storing the log page in the non-volatile memory array;

determining whether the execution of the plurality of storage access commands causes second system data stored in the non-volatile memory array to become outdated, the first system data and the second system data being stored in the same non-volatile memory pages;

updating the first system data and the second system data stored in the non-volatile memory array based at least on the log page at an update frequency, the update frequency being based on whether the execution of the plurality of storage access commands causes the second system data stored in the non-volatile memory array to become outdated; and

performing garbage collection of the log page after the changes reflected in the log page are applied to the at least one of the first system data or the second system data,

wherein the method reduces write amplification of the non-volatile memory array associated with managing the first system data and second system data, and

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

27. The method of claim 26, wherein the first system data comprises a mapping table that associates a set of logical addresses in the data storage system with a set of physical locations in the non-volatile memory array where the host data is stored.

28. The method of claim 26, wherein the log page is interposed between memory pages storing the first system data.