Low Level Object Version Tracking Using Non-Volatile Memory Write Generations

• US 20140236911A1
• Filed: 04/28/2014
• Published: 08/21/2014
• 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, Carryl M.
• Granted Patent: US 9,183,236 B2
• Time in Patent Office: Days
• US Class Current: 707/695
• 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;

in response to the request, determining, via an object table, whether one or more versions of the data object exist in memory;

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

reading at least one of the one or more versions of the data object from the respective location into volatile memory.

2. The method of claim 1, wherein the object table comprises multiple records and each record includes a version number, a reference to an object list, and an object index.

3. The method of claim 2, 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 2, 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 an object table, whether one or more versions of the data object exist in the memory comprises determining whether one 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 an object table, whether one or more versions of the data object exist in the memory includes determining that each of the one or more versions is not listed on a dead-version list.

8. The method of claim 1, further comprising:

determining a current version number for the data object;

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

wherein reading the at least one of the one 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 one or more versions of the data object exist in the non-volatile memory;

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

read at least one of the one or more versions of the data object from the respective location into volatile memory.

11. The system of claim 10, wherein the object table comprises multiple records and each record includes a version number, a reference to an object list, and an object index.

12. The system of claim 11, 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 11, 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 an object table, whether one or more versions of the data object exist in the non-volatile memory comprises determining whether one 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 an object table, whether one or more versions of the data object exist in the non-volatile memory includes determining that each of the one or more versions is not 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;

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

wherein reading the at least one of the one 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.