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

• US 8,874,515 B2
• Filed: 04/11/2011
• Issued: 10/28/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, Darryl M.
• Primary Examiner(s): Spieler, William
• Application Number:
  US13/084,464
• Publication Number:
  US 20120259863A1
• Time in Patent Office: 1,296 Days
• Field of Search: 707/638
• US Class Current: 707/638
• 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:

obtaining a first object key that uniquely identifies a first data object stored in the non-volatile memory, and obtaining an index for the first data object generated based on a hash of the first object key, wherein the first data object is assigned a first version number;

entering, in an object list, the first object key and location information of the first data object stored in the non-volatile memory, wherein the object list contains entries for all data objects having the first version number;

creating, in an object table, a record associated with the first data object, wherein the object table is distinct from the object list, and the record includes the index for the first data object, a reference to the object list, and the first version number;

subsequent to entering the first object key and location information of the first data object in the first object list, assigning a second version number to the first data object;

after assigning the second version number to the first data object, obtaining a second object key that uniquely identifies a second data object stored in the non-volatile memory, and obtaining an index for the second data object generated based on a hash of the second object key, wherein the second data object is assigned the first version number; and

entering, in the object list, the second object key and location information of the second data object stored in the non-volatile memory.

2. The method of claim 1, wherein the first version number is generated by an application storing the respective data object in the non-volatile memory.

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

4. The method of claim 3, wherein the container of the first data object is further assigned a minimum active version number (MVN) and a next version number (NVN) based on the CVN.

5. The method of claim 3, further comprising incrementing the CVN in response to a snapshot request, wherein the incremented CVN is used by other applications concurrently using the first data object.

6. The method of claim 1, wherein the object table includes two or more records associated with the first data object, wherein each record of the two or more records associated with the first data object includes a distinct version number.

7. The method of claim 1, further comprising scanning the object table and the object list to find a match in response to a request for the first data object with a specified version number, wherein a match condition includes:

a match between the first object key and the first data object;

the version number in the object table being less than or equal to the specified version number; and

the version number in the object table not belonging to a dead-version list.

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

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

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

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

12. The method of claim 1, wherein the index for the first data object is a masked syndrome of the object key.

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

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

a non-volatile memory controller configured to;

obtain a first object key that uniquely identifies a first data object of the one or more data objects stored in the non-volatile memory, and obtain an index for the first data object generated based on a hash of the first object key, wherein the first data object is assigned a first version number;

enter, in an object list, the first object key and location information of the first data object stored in the non-volatile memory, wherein the object list contains entries for all data objects having the first version number;

create, in an object table, a record associated with the first data object, wherein the object table is distinct from the object list, and the record includes the index for the first data object, a reference to the object list, and the first version number;

subsequent to entering the first object key and location information of the first data object in the first object list, assign a second version number to the first data object;

after assigning the second version number to the first data object, obtain a second object key that uniquely identifies a second data object stored in the non-volatile memory, and obtain an index for the second data object generated based on a hash of the second object key, wherein the second data object is assigned the first version number; and

enter, in the object list, the second object key and location information of the second data object stored in the non-volatile memory.

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

15. The system of claim 14, wherein the non-volatile memory controller is further configured to increment the CVN, in response to a snapshot request, wherein the incremented CVN is used by other applications concurrently using the first data object.

16. The system of claim 13, wherein the non-volatile memory controller is further configured to scan the object table and the object list to find a match, in response to a request for the first data object with a specified version number, wherein a match condition includes:

a match between the first object key and the first data object;

the version number in the object table being less than or equal to the specified version number; and

the version number in the object table not belonging to a dead-version list.

17. 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 first data object.

18. The system of claim 13, wherein the non-volatile memory controller is further configured to store commit and abort records associated with each version of the first data object.

19. The system of claim 18, 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.

20. 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 first data object.

21. The system of claim 13, wherein the object table includes two or more records associated with the first data object, wherein each record of the two or more records associated with the first data object includes a distinct version number.

22. The system of claim 13, wherein the index for the first data object is a masked syndrome of the object key.