Storing and reconstructing mapping table data in a data storage system

• US 8,984,247 B1
• Filed: 05/10/2012
• Issued: 03/17/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 N
• Application Number:
  US13/468,999
• Time in Patent Office: 1,041 Days
• Field of Search: 711/165
• US Class Current: 711/165
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric 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/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/225 Hybrid cache memory, e.g. having both volatile and non-volatile portions
• CPC Class Codes: G06F 2212/313 In storage device
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: G06F 2212/7207 management of metadata or control data

Abstract

A data storage subsystem is disclosed that implements a process for storing and/or reconstructing system data, such as a system mapping table. In certain embodiments, table pages and log pages are systematically copied, or flushed, to non-volatile memory in an interleaving manner according to a fixed ratio of log pages to table pages, thereby facilitating coherency of data. Full and/or partial reconstruction of a table may be performed within a bounded number of operations based on the size of the table, the ratio implemented, and/or other characteristics.

Claims

1. A non-volatile storage system comprising:

a non-volatile memory array configured to store data;

a volatile memory; and

a controller configured to;

copy an initial mapping table page of a first set of pages of a logical-to-physical mapping table stored in the volatile memory to the non-volatile memory array;

copy an initial log page of a first set of log pages stored in the volatile memory to the non-volatile memory array in contiguous order with respect to the first set of mapping table pages, wherein the log pages indicate changes to one or more pages of the mapping table;

determine, after the initial mapping table and log pages are copied, whether a predetermined ratio between the first set of mapping table pages and the first set of log pages has been met;

if the predetermined ratio has not been met, continue to copy one or more subsequent mapping table pages and/or one or more subsequent log pages until the predetermined ratio is met;

continue to copy one or more subsequent sets of mapping table pages and one or more subsequent sets of log pages in a contiguous and interleaving configuration according to the predetermined ratio; and

reconstruct the mapping table using a bounded number of read operations based on the copied mapping table pages and log pages.

2. A method of storing mapping table information in a non-volatile storage medium, the method comprising:

storing an initial mapping table page of a first set of pages of a logical-to-physical mapping table in the non-volatile storage medium;

storing an initial log page of a first set of log pages in contiguous order with respect to the first set of mapping table pages, wherein the log pages indicate changes to one or more pages of the mapping table;

determining, after the initial mapping table and log pages are stored, whether a predetermined ratio between the first set of mapping table pages and the first set of log pages has been met;

if the predetermined ratio has not been met, continuing to store one or more subsequent mapping table pages and/or one or more subsequent log pages until the predetermined ratio is met; and

continuing to store one or more subsequent sets of mapping table pages and one or more subsequent sets of log pages in a contiguous and interleaving configuration according to the predetermined ratio,

wherein the stored mapping table pages and log pages are used to reconstruct the mapping table using a bounded number of read operations.

3. The method of claim 2, wherein the first set of mapping table pages has a first predetermined number of pages, and wherein the first predetermined number is a number between one and four.

4. The method of claim 2, wherein the first set of mapping table pages has a first predetermined number of pages, and wherein the first predetermined number is one.

5. The method of claim 2, wherein the first set of mapping table pages has a first predetermined number of pages, and wherein the first set of log pages has a second predetermined number of pages, and wherein the second predetermined number is thirty-two.

6. The method of claim 2, wherein the one or more subsequent sets of mapping table pages comprise a second set of mapping table pages stored in contiguous order with respect to the first set of log pages and wherein the one or more subsequent sets of log pages comprise a second set of log pages stored in contiguous order with respect to the second set of mapping table pages, wherein each of the first and second sets of mapping table pages has a first predetermined number of pages, wherein each of the first and second sets of log pages has a second predetermined number of pages.

7. A method of recovering a logical-to-physical mapping table including a predetermined number of pages of table data in a non-volatile storage system, the method comprising:

loading into a volatile memory a most recently updated version of an initial table data page of a first set of pages of table data;

loading an initial log page of a first set of log pages into the volatile memory from a contiguously ordered physical position in the non-volatile storage system with respect to the first set of table data pages;

determining, after the initial table data and log pages are loaded, whether a predetermined ratio between the first set of table data pages and the first set of log pages has been met;

if the predetermined ratio has not been met, continuing to load one or more subsequent table data pages and/or one or more subsequent log pages until the predetermined ratio is met; and

continuing to load one or more subsequent sets of table data pages and one or more subsequent sets of log pages in a contiguous and interleaving configuration according to the predetermined ratio,

wherein the loaded table data pages and log pages are used to reconstruct the mapping table using a bounded number of read operations.

8. The method of claim 7, wherein the first set of table data pages has a first predetermined number of pages, wherein the first set of log pages has a second predetermined number of pages, and wherein the ratio of the first predetermined number to the second predetermined number represents the predetermined ratio.

9. The method of claim 7, wherein the first set of table data pages has a first predetermined number of pages, and wherein the first predetermined number is one.

10. The method of claim 7, wherein the first set of table data pages has a first predetermined number of pages, and wherein the first predetermined number is a number between one and four.

11. The method of claim 7, wherein the one or more subsequent sets of table data pages comprise a second set of table data pages that is distinct from the first set of table data pages loaded into the volatile memory, wherein the first set of table data pages and the second set of table data pages are the same size.

12. A non-volatile storage device comprising:

a logical-to-physical address mapping table including a plurality of pages of mapping data, wherein the plurality of mapping data pages comprise an initial mapping data page;

a plurality of log pages, the log pages indicating changes in one or more of the plurality of pages of mapping data, wherein the plurality of log pages comprise an initial log page; and

a controller configured to copy the initial mapping data page and the initial log page in a volatile memory, wherein the controller is further configured to determine, after the initial mapping data and log pages are copied, whether a predetermined ratio between the plurality of mapping data pages and the plurality of log pages has been met, wherein, if the predetermined ratio has not been met, the controller is further configured to continue to copy one or more subsequent mapping data pages and/or one or more subsequent log pages until the predetermined ratio is met,

wherein the controller is further configured to continue to copy one or more subsequent sets of mapping data pages and one or more subsequent sets of log pages in a contiguous and interleaving configuration according to the predetermined ratio, and wherein the controller is further configured to reconstruct the mapping table using a bounded number of read operations based on the copied mapping data pages and log pages.

13. The non-volatile storage device of claim 12, wherein the predetermined ratio is between sixteen and thirty-two.

14. The non-volatile storage device of claim 12, wherein the predetermined ratio is between four and sixteen.

15. A method of recovering at least part of a logical-to-physical mapping table including a predetermined number of pages of table data in a non-volatile storage device, the method comprising:

receiving a command from a host system to reconstruct one or more desired pages of the mapping table;

in response to receiving the command;

loading an initial mapping table page of the one or more desired mapping table pages from the non-volatile storage device;

loading an initial log page of one or more log pages from the non-volatile storage device that were recorded in the non-volatile storage device subsequently to at least one of the one or more desired mapping table pages, the log pages indicating changes to be made to the mapping table;

determining, after the initial mapping table and log pages are loaded, whether a predetermined ratio between the mapping table pages and the log pages has been met;

if the predetermined ratio has not been met, continuing to load one or more subsequent mapping table pages and/or one or more subsequent log pages until the predetermined ratio is met; and

continuing to load one or more subsequent sets of mapping table pages and one or more subsequent sets of log pages in a contiguous and interleaving configuration according to the predetermined ratio,

wherein the loaded mapping table pages and log pages are used to reconstruct the mapping table using a bounded number of read operations,

updating the one or more desired mapping table pages in view of the one or more log pages.