Low level object version tracking using non-volatile memory write generations

• US 9,183,236 B2
• Filed: 04/28/2014
• Issued: 11/10/2015
• Est. Priority Date: 04/11/2011
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Enterprise IP LLC (Western Digital Corporation)
• Inventors: Bodwin, James M., Dinker, Darpan, Eckhardt, Andrew D., Ouye, Darryl
• Primary Examiner(s): Spieler, William
• Application Number:
  US14/263,945
• Publication Number:
  US 20140236911A1
• Time in Patent Office: 561 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1873 Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files
• CPC Class Codes: G06F 16/219 Managing data history or versioning querying versioned data G06F16/2474; querying temporal data G06F16/2477

Abstract

A method for retrieving versioned data in a non-volatile memory is provided. The method includes: (1) receiving a read request for a data object, (2) in response to the request, determining, via an object table, whether one or more versions of the data object exist in memory, (3) in accordance with a determination that one or more versions exist in memory, obtaining, via the object table, a respective location where each of the one or more versions of the data object are stored, and (4) reading at least one of the one or more versions of the data object from the respective location into volatile memory.

Claims

1. A method for retrieving versioned data in a non-volatile memory, the method comprising:

receiving a read request for a data object; and

in response to the request;

determining, via an object table, whether two or more versions of the data object exist in memory;

in accordance with a determination that two or more versions exist in memory, obtaining, via the object table, a respective location where a particular version of the two or more versions of the data object is stored; and

reading at least the particular version of the two or more versions of the data object from the respective location into volatile memory;

wherein the object table comprises multiple records and each record includes a reference to an object list, a version number distinct from the reference to the object list, and an object index.

2. The method of claim 1, further comprising, in accordance with the determination that two or more versions exist in memory, obtaining, via the object table, a respective storage location for each of the two or more versions of the data object.

3. The method of claim 1, wherein the object index is generated based on a hash of an object key that uniquely identifies the data object.

4. The method of claim 1, wherein the object list includes an object key that uniquely identifies the data object and location information corresponding to the data object.

5. The method of claim 1, wherein the object table includes two or more records corresponding to the data object, wherein each record of the two or more records includes a distinct version number.

6. The method of claim 1, wherein the read request includes a specified version number for the data object;

and

wherein determining, via the object table, whether two or more versions of the data object exist in the memory comprises determining whether two or more versions of the data object, each with corresponding version number less than or equal to the specified version number, exist in the memory.

7. The method of claim 1, wherein determining, via the object table, whether two or more versions of the data object exist in the memory includes determining whether each of the two or more versions is listed on a dead-version list.

8. The method of claim 1, further comprising:

determining a current version number for the data object; and

in accordance with the determination that two or more versions exist in memory, determining whether one of the two or more versions is the current version;

wherein reading at least the particular version of the two or more versions of the data object from the respective location into the volatile memory comprises reading the current version of the data object into the volatile memory.

9. The method of claim 1, further comprising:

receiving a snapshot request; and

in response to a snapshot request, incrementing a current version number for the data object, wherein the incremented current version number is used by applications concurrently using the data object.

10. A system for retrieving versioned data, the system comprising:

non-volatile memory configured to store one or more data objects; and

one or more non-volatile memory controllers configured to;

receive a read request for a data object;

in response to the request;

determine, via an object table, whether two or more versions of the data object exist in the non-volatile memory;

in accordance with a determination that two or more versions exist in the non-volatile memory, obtain, via the object table, a respective location where a particular version of the two or more versions of the data object is stored; and

read at least the particular version of the two or more versions of the data object from the respective location into volatile memory;

wherein the object table comprises multiple records and each record includes a reference to an object list, a version number distinct from the reference to the object list, and an object index.

11. The system of claim 10, wherein the one or more non-volatile memory controllers are further configured to obtain, in accordance with the determination that two or more versions exist in memory, a respective storage location for each of the two or more versions of the data object, via the object table.

12. The system of claim 10, wherein the object index is generated based on a hash of an object key that uniquely identifies the data object.

13. The system of claim 10, wherein the object list includes an object key that uniquely identifies the data object and location information corresponding to the data object.

14. The system of claim 10, wherein the object table includes two or more records corresponding to the data object, wherein each record of the two or more records includes a distinct version number.

15. The system of claim 10, wherein the read request includes a specified version number for the data object;

and

wherein determining, via the object table, whether two or more versions of the data object exist in the non-volatile memory comprises determining whether two or more versions of the data object, each with corresponding version number less than or equal to the specified version number, exist in the non-volatile memory.

16. The system of claim 10, wherein determining, via the object table, whether two or more versions of the data object exist in the non-volatile memory includes determining whether each of the two or more versions is listed on a dead-version list.

17. The system of claim 10, wherein the one or more non-volatile memory controllers are further configured to:

determine a current version number for the data object; and

in accordance with the determination that two or more versions exist in memory, determine whether one of the two or more versions is the current version;

wherein reading at least the particular version of the two or more versions of the data object from the respective location into the volatile memory comprises reading the current version of the data object into the volatile memory.

18. The system of claim 10, wherein the one or more non-volatile memory controllers are further configured to:

receive a snapshot request; and

in response to a snapshot request, increment a current version number for the data object, wherein the incremented current version number is used by applications concurrently using the data object.