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

• US 20120259863A1
• Filed: 04/11/2011
• Published: 10/11/2012
• 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 M.
• Granted Patent: US 8,874,515 B2
• Time in Patent Office: Days
• US Class Current: 707/747
• 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

Data versioning in a non-volatile memory. An object key associated with a data object is created. An index into an object table is generated using the object key. A version number is stored in conjunction with the data object stored in the non-volatile memory. In an object linked-list, the object key and the location information of the data object in the non-volatile memory are stored. A record associated with the data object is created in an object table. The record includes an index, a reference to the object linked-list, and the version number. The index is generated based on the object key.

Claims

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

creating an object key associated with a data object;

generating an index into an object table using the object key;

storing a version number in conjunction with the data object stored in the non-volatile memory;

entering, in an object linked-list, the object key and the location information of the data object in the non-volatile memory; and

creating a record associated with the data object in an object table, the record including an index, a reference to the object linked-list, and the version number;

wherein the index is generated based on the object key.

2. The method of claim 1, wherein the version number is determined by a program requesting the data object or storing the data object in the non-volatile memory.

3. The method of claim 1, further comprising assigning a current version number (CVN) associated with a container of the data object as a default version number.

4. The method of claim 3, wherein version numbers associated with the container include a minimum active version number (MVN) and a next version number (NVN).

5. The method of claim 1, wherein the object table includes multiple version numbers associated with a data object.

6. The method of claim 1, further comprising hashing the object key to produce a syndrome and using the syndrome instead of the object key.

7. The method of claim 1, further comprising scanning the object linked-list to find a match in response to a request for the data object with a specified version number, wherein a match condition includes the version number in the object table being less than or equal to the specified version number, and not belonging to a dead-version list.

8. The method of claim 1, further comprising incrementing a current version number (CVN) in response to a snapshot request, wherein the incremented CVN is used by other applications concurrently using the data object.

9. The method of claim 1, further comprising assigning monotonically increasing version numbers to a series of consecutive updates of the data object.

10. The method of claim 9, further comprising maintaining a list of data items associated with each version of the data object.

11. The method of claim 9, further comprising storing commit and abort records associated with each version of the data object.

12. The method of claim 11, further comprising using the stored commit and abort records to restore the non-volatile memory to a consistent state after a system interruption.

13. A system for providing data versioning, the system comprising:

non-volatile memory to store a data object; and

a non-volatile memory controller configured to;

create an object key associated with a data object;

generate an index into an object table using the object key;

store a version number in conjunction with the data object stored in the non-volatile memory;

enter, in an object linked-list, the object key and the location information of the data object in the non-volatile memory; and

create a record associated with the data object in an object table, the record including an index, a reference to the object linked-list, and the version number;

wherein the index is generated based on the object key.

14. The system of claim 13, wherein the non-volatile memory controller is further configured to assign a current version number (CVN) associated with a container of the data object as a default version number for the data object.

15. The system of claim 13, wherein the non-volatile memory controller is further configured to hash the object key to produce a syndrome and use the syndrome instead of the object key.

16. The system of claim 13, wherein the non-volatile memory controller is further configured to scan the object linked-list to find a match, in response to a request for the data object with a specified version number, wherein a match condition includes the version number in the object table being less than or equal to the specified version number, and not belonging to a dead-version list.

17. The system of claim 13, wherein the non-volatile memory controller is further configured to increment a current version number (CVN), in response to a snapshot request, wherein the incremented CVN is used by other applications concurrently using the data object.

18. The system of claim 13, wherein the non-volatile memory controller is further configured to assign monotonically increasing version numbers to a series of consecutive updates of the data object.

19. The system of claim 13, wherein the non-volatile memory controller is further configured to:

maintain a list of data items associated with each version of the data object; and

store commit and abort records associated with each version of the data object.

20. The system of claim 13, wherein the non-volatile memory controller is further configured to use the stored commit and abort records to restore the non-volatile memory to a consistent state after a system interruption.