Method and system for forward reference logging in a persistent datastore

• US 9,703,816 B2
• Filed: 12/19/2013
• Issued: 07/11/2017
• Est. Priority Date: 11/19/2013
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: George, Johann, Olbrich, Aaron
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Perez-Arroyo, Raquel
• Application Number:
  US14/135,400
• Publication Number:
  US 20150142860A1
• Time in Patent Office: 1,300 Days
• Field of Search: 707812
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: G06F 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 3/0611 in relation to response time
• 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/0643 Management of files
• 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/0688 Non-volatile semiconductor memory arrays

Abstract

The embodiments described herein are methods and systems to enhance the reliability and performance of a persistent datastore (e.g., non-volatile memory such as flash memory). The method includes generating a log entry associated with first write data. The method also includes generating a first record including the log entry, the first write data, and pointer to a second record different from the first record. The method further includes performing a single write operation that includes writing the first record to the persistent datastore.

Claims

1. A method of recovering persisted data, comprising:

at an electronic system with one or more processors and memory;

generating a first log entry associated with first write data to be stored in a persistent data store, wherein the first log entry includes information sufficient to replay a transaction corresponding to the first write data;

generating a forward reference identifier for a second record of a plurality of sequential records that is different from a first record of the plurality of sequential records, wherein each respective record of the plurality of sequential records includes a respective log entry, write data that was not yet stored in the persistent data store when said log entry was generated, a respective reference identifier for the respective record, a forward reference identifier for a next record in the sequence, and a pointer to a next record in the sequence;

generating the first record including the first log entry, the first write data, the forward reference identifier for the second record, and a pointer to the second record;

performing a single write operation that includes writing the first record to the persistent datastore, wherein;

the pointer to the second record is a pointer to a location in the persistent data store allocated for writing the second record prior to writing the first record and the second record to the persistent datastore, and

the forward reference identifier for the second record is different from the pointer to the second record; and

performing a recovery operation that includes;

reading the first log entry;

using the pointer to the second record to read a second log entry;

determining whether the forward reference identifier for the second record matches a second reference identifier in the second record;

in accordance with a determination that the forward reference identifier for the second record matches the second reference identifier in the second record, replaying a transaction associated with the second log entry; and

in accordance with a determination that the forward reference identifier for the second record does not match the second reference identifier in the second record, stopping the recovery operation.

2. The method of claim 1, wherein the first log entry includes a logical address of the first record or of the first write data.

3. The method of claim 1, further comprising:

generating a reference identifier for the first record; and

wherein the first record further includes the reference identifier for the first record.

4. The method of claim 1, wherein the first log entry includes information corresponding to an update of the persistent datastore corresponding to the first write data.

5. The method of claim 1, further comprising:

batching a plurality of log entries into a log entry collection, the log entry collection including a last respective log entry associated with a last record; and

performing a second write operation that includes writing a log stream portion to a log stream in the persistent datastore, the log stream portion includes the log entry collection and, separate from the log entry collection, a pointer to a next record following the last record.

6. The method of claim 5, wherein the plurality of log entries in the log entry collection are sequentially written to the log stream in the persistent datastore.

7. The method of claim 1, further comprising:

batching a plurality of log entries into a log entry collection, the log entry collection including a last respective log entry associated with a last record; and

performing a second write operation that includes writing a log stream portion to a log stream in the persistent datastore, the log stream portion includes the log entry collection and a plurality of pointers, wherein;

each of the plurality of pointers is associated with one of a plurality of record sets, wherein at least one record set of the plurality of record sets has a different size from at least one other record set of the plurality of record sets; and

one of the plurality of pointers is associated with a next record following the last record.

8. The method of claim 7, wherein each of the log entries in the log entry collection corresponds to one of the plurality of different record sizes.

9. The method of claim 1, further comprising:

generating a third record including a log entry indicating that the third record represents a deletion of the first write data, a tombstone corresponding to the deleted first write data, and a forward reference identifier associated with a fourth record; and

performing a third write operation that includes writing the third record to the persistent datastore.

10. An electronic system, comprising:

one or more processors; and

memory storing one or more programs to be executed by the one or more processors, the one or more programs comprising instructions for;

generating a first log entry associated with first write data to be stored in a persistent data store, wherein the first log entry includes information sufficient to replay a transaction associated with the first write data;

generating a forward reference identifier for a second record of a plurality of sequential records that is different from a first record of the plurality of sequential records, wherein each respective record of the plurality of sequential records includes a respective log entry, write data that was not yet stored in the persistent data store when said log entry was generated, a respective reference identifier for the respective record, a forward reference identifier for a next record in the sequence, and a pointer to a next record in the sequence;

generating the first record including the first log entry, the first write data, the forward reference identifier for the second record, and a pointer to the second record;

performing a single write operation that includes writing the first record to the persistent datastore, wherein;

the pointer to the second record is a pointer to a location in the persistent data store allocated for writing the second record prior to writing the first record and the second record to the persistent datastore, and

the forward reference identifier for the second record is different from the pointer to the second record; and

performing a recovery operation that includes;

reading the first log entry;

using the pointer to the second record to read a second log entry;

determining whether the forward reference identifier for the second record matches a second reference identifier in the second record;

in accordance with a determination that the forward reference identifier for the second record matches the second reference identifier in the second record, replaying a transaction associated with the second log entry; and

in accordance with a determination that the forward reference identifier for the second record does not match the second reference identifier in the second record, stopping the recovery operation.

11. The electronic system of claim 10, wherein the first log entry includes a logical address of the first record or of the first write data.

12. The electronic system of claim 10, wherein the one or more programs further comprise instructions for:

generating a reference identifier for the first record; and

wherein the first record further includes the reference identifier for the first record.

13. The electronic system of claim 10, wherein the first log entry includes information corresponding to an update of the persistent datastore corresponding to the first write data.

14. The electronic system of claim 10, wherein the one or more programs further comprise instructions for:

batching a plurality of log entries into a log entry collection, the log entry collection including a last respective log entry associated with a last record; and

performing a second write operation that includes writing a log stream portion to a log stream in the persistent datastore, the log stream portion includes the log entry collection and, separate from the log entry collection, a pointer to a next record following the last record.

15. The electronic system of claim 14, wherein the plurality of log entries in the log entry collection are sequentially written to the log stream in the persistent datastore.

16. The electronic system of claim 10, wherein the one or more programs further comprise instructions for:

batching a plurality of log entries into a log entry collection, the log entry collection including a last respective log entry associated with a last record; and

performing a second write operation that includes writing a log stream portion to a log stream in the persistent datastore, the log stream portion includes the log entry collection and a plurality of pointers, wherein;

each of the plurality of pointers is associated with one of a plurality of record sets, wherein at least one record set of the plurality of record sets has a different size from at least one other record set of the plurality of record sets; and

one of the plurality of pointers is associated with a next record following the last record.

17. The electronic system of claim 16, wherein each of the log entries in the log entry collection corresponds to one of the plurality of different record sizes.

18. The electronic system of claim 10, wherein the one or more programs further comprise instructions for:

generating a third record including a log entry indicating that the third record represents a deletion of the first write data, a tombstone corresponding to the deleted first write data, and a forward reference identifier associated with a fourth record; and

performing a third write operation that includes writing the third record to the persistent datastore.

19. A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions, which, when executed by an electronic system with one or more processors, cause the electronic systems to perform operations comprising:

generating a first log entry associated with first write data to be stored in a persistent data store, wherein the first log entry includes information sufficient to replay a transaction associated with the first write data;

generating a forward reference identifier for a second record of a plurality of sequential records that is different from a first record of the plurality of sequential records, wherein each respective record of the plurality of sequential records includes a respective log entry, write data that was not yet stored in the persistent data store when said log entry was generated, a respective reference identifier for the respective record, a forward reference identifier for a next record in the sequence, and a pointer to a next record in the sequence;

generating the first record including the first log entry, the first write data, the forward reference identifier for the second record, and a pointer to the second record;

performing a single write operation that includes writing the first record to the persistent datastore, wherein;

the pointer to the second record is a pointer to a location in the persistent data store allocated for writing the second record prior to writing the first record and the second record to the persistent datastore, and

the forward reference identifier for the second record is different from the pointer to the second record; and

performing a recovery operation that includes;

reading the first log entry;

using the pointer to the second record to read a second log entry;

determining whether the forward reference identifier for the second record matches a second reference identifier in the second record;

in accordance with a determination that the forward reference identifier for the second record matches the second reference identifier in the second record, replaying a transaction associated with the second log entry; and

in accordance with a determination that the forward reference identifier for the second record does not match the second reference identifier in the second record, stopping the recovery operation.