System data storage mechanism providing coherency and segmented data loading

• US 9,170,932 B1
• Filed: 05/22/2012
• Issued: 10/27/2015
• Est. Priority Date: 05/22/2012
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Lo, Jerry, Suryabudi, Dominic S., Phan, Lan D.
• Primary Examiner(s): Tseng, Cheng-Yuan
• Assistant Examiner(s): PUCHE, TAHILBA O
• Application Number:
  US13/478,036
• Time in Patent Office: 1,253 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1458 Management of the backup or restore process
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays

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 are systematically copied, or flushed, to non-volatile memory in a progressive manner, according to a fixed ratio of flushed table pages per table update trigger, thereby facilitating write and/or load efficiency. Full 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 configured to store data;

a volatile memory; and

a controller configured to progressively flush a system table stored in y table pages in the volatile memory to the non-volatile memory at least in part by;

receiving a command from a host system that indicates that a first page of the system table is to be updated;

updating content of the first page in response to receiving the command; and

in response to receiving the command, flushing both the updated first page and a set of x additional pages of the system table to the non-volatile memory, wherein content of the set of additional pages is not updated in response to receiving the command;

wherein flushing the set of x additional pages guarantees that the system table can be reconstructed using a number z or fewer read operations, wherein z=y·

((x+1)/x).

2. In a data storage system, a method of progressively flushing system table information to non-volatile memory, the method comprising:

receiving a first command from a host system that indicates that a first page of a system table stored in y pages in a volatile memory of the data storage system is to be updated, wherein y is a number greater than one;

in response to receiving the first command;

updating the first page in the volatile memory; and

flushing both the updated first page and a first set of x additional pages of the system table to the non-volatile memory, wherein the content of the first set of additional pages is not updated in response to receiving the first command;

wherein flushing the first set of x additional pages guarantees that the system table can be reconstructed using a number z or fewer read operations, wherein z=y·

((x+1)/x);

wherein the method is performed under the control of a controller of the data storage system.

3. The method of claim 2, wherein x=1.

4. The method of claim 2, wherein x=2.

5. The method of claim 2, wherein x=3.

6. The method of claim 2, wherein x is greater than 3.

7. The method of claim 2, further comprising:

receiving a second command from the host system that indicates that a second page of the system table is to be updated;

in response to receiving the second command;

updating the second page in the volatile memory; and

flushing both the updated second page and a second set of x additional pages of the system table to the non-volatile memory, wherein the content of the second set of pages is not updated in response to receiving the second command;

wherein flushing the updated first page and the first set of additional pages is performed prior to receiving the second command, and wherein the first set of additional pages is different from the second set of additional pages.

8. The method of claim 2, wherein flushing the first set of additional pages is performed after flushing the updated first page, but prior to flushing any subsequently updated table pages to the non-volatile memory.

9. In a data storage system, a method of recovering a system table having y table pages, the method comprising:

reading a set of z table pages from a non-volatile memory to a volatile memory, wherein z is a number greater than y, but less than or equal to 2y, wherein the set of z table pages comprises at least one copy of each of the y table pages; and

locating within the set of z table pages a most up-to-date version of each of the y table pages of the system table;

copying the most up-to-date versions of each of the y table pages to a volatile memory, thereby generating an up-to-date version of the system table in the volatile memory;

wherein the set of z table pages comprises z table pages that were most recently flushed to the non-volatile memory;

wherein the method allows for recovering the system table using a limited number z or fewer read operations;

wherein z is less than or equal to y*((x+1)1/x), wherein x is an integer value; and

wherein the method is performed under the control of a controller of the data storage system.

10. The method of claim 9, wherein locating the most up-to-date version of each page of the system table comprises:

reading each of the z table pages in order from a most-recently stored page to a least-recently stored page; and

for each of the z pages, determining whether a more up-to-date version of the page was previously read, wherein when it is determined that a more up-to-date version of the page was not previously read, the up-to-date version of the system table is updated to include the page.

11. The method of claim 9, wherein x=1.

12. The method of claim 9, wherein x=2.

13. The method of claim 9, wherein x=3.

14. The method of claim 9, wherein x is greater than 3.

15. The method of claim 9, wherein the set of z table pages are divided into segments and the reading and locating are performed in order according to individual segments.

16. The method of claim 15, wherein a segment containing an address in a host data access request is processed on demand to service the host data access request.