Managing a Data Structure

• US 20120096052A1
• Filed: 10/18/2010
• Published: 04/19/2012
• Est. Priority Date: 10/18/2010
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: TOLIA, Niraj, BINKERT, Nathan, TURNER, Yoshio, CHANG, Jichuan
• Granted Patent: US 8,762,425 B2
• Time in Patent Office: Days
• US Class Current: 707/806
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors

Abstract

In a method for managing a data structure in a memory, an accessor to access a version of the data structure is determined, in which the accessor includes a version number and a fat pointer, in which the version number corresponds to the most recent version of the data structure, and wherein the fat pointer is configured to enable for multiple versions of a linked-data structure to be maintained.

Claims

1. A method for managing a data structure in a memory, said method comprising:

determining, using at least one processor, an accessor to access a version of the data structure, wherein the accessor includes a version number and a fat pointer, wherein the version number corresponds to the most recent version of the data structure, and wherein the fat pointer is configured to enable for multiple versions of a linked-data structure to be maintained.

2. The method according to claim 1, further comprising:

determining the fat pointer associated with the accessor, wherein the fat pointer comprises a collection of version number and pointer tuples corresponding to at least one node extending from a root of the data structure; and

storing the accessor and the fat pointer.

3. The method according to claim 2, wherein determining the fat pointer further comprises generating the fat pointer to include a plurality of identification sets, wherein each of the identification sets includes a version number and a pointer tuple corresponding to the at least one node.

4. The method according to claim 3, wherein a plurality of the identification sets include pointers that correspond to the same at least one node.

5. The method according to claim 3, wherein generating the fat pointer further comprises generating the fat pointer such that each of the version numbers contained in the plurality of identification sets comprises at least a most recent version number and a new version number, wherein the new version is greater than the version number of the accessor.

6. The method according to claim 5, wherein the new version number represents an ongoing update that has not yet been committed to the memory, said method further comprising:

committing an update of the data structure, wherein the committing of the update causes the pointer in a common tuple with the new version number to overwrite previous pointers; and

updating the pointer and version of the accessor in response to the update of the data structure being committed to the memory.

7. The method according to claim 1, wherein the data structure is a linked-data structure.

8. The method according to claim 7, further comprising:

implementing the fat pointer to update the data structure.

9. The method according to claim 8, wherein implementing the fat pointer to update the data structure further comprises:

using the accessor to determine the current version and a new version number that would be committed for an upcoming update;

implementing an updating function, wherein the updating function uses the current version to determine the least recent pointer in the fat pointer;

overwriting the least recent pointer with the new version number;

updating the accessor with the new version number; and

implementing a flush command to propagate the updates to the memory.

10. The method according to claim 1, wherein the memory comprises a non-volatile byte addressable memory.

11. An apparatus for managing a data structure in a memory, said apparatus comprising:

a memory storing one or more modules configured to determine an accessor to access a version of the data structure, wherein the accessor includes a version number and a fat pointer, wherein the version number corresponds to the most recent version of the data structure, and wherein the fat pointer is configured to enable for multiple versions of a linked-data structure to be maintained; and

a processor configured to execute the one or more modules.

12. The apparatus according to claim 11, wherein the one or more modules are further configured to determine the fat pointer associated with the accessor, wherein the fat pointer comprises a collection of version number and pointer tuples corresponding to at least one node extending from a root of the data structure, and to store the accessor and the fat pointer.

13. The apparatus according to claim 12, wherein the one or more modules are further configured to generate the fat pointer to include a plurality of identification sets, wherein each of the identification sets includes a version number and pointer tuple corresponding to the at least one node.

14. The apparatus according to claim 13, wherein the one or more modules are further configured to generate the fat pointer such that each of the version numbers contained in the plurality of identification sets comprises at least a most recent version number and a new version number, wherein the new version is greater than the version number of the accessor.

15. The apparatus according to claim 14, wherein the new version number represents an ongoing update that has not yet been committed to the memory and wherein the one or more modules are further configured to commit an update of the data structure, wherein the committing of the update causes the pointer in a common tuple with the new version number to overwrite previous pointers and to update the pointer and version of the accessor in response to the update of the data structure being committed to the memory.

16. The apparatus according to claim 11, wherein the data structure is a linked-data structure.

17. The apparatus according to claim 16, wherein the one or more modules are further configured to implement the fat pointer to update the data structure.

18. The apparatus according to claim 13, wherein the one or more modules are further configured to use the accessor to determine the current version and a new version number that would be committed for an upcoming update, to implement an updating function, wherein the updating function uses the current version to determine the least recent pointer in the fat pointer, to overwrite the least recent pointer with the new version number, to update the accessor with the new version number, and to implement a flush command to propagate the update to the memory.

19. A computer readable storage medium on which is embedded one or more computer programs, said one or more computer programs implementing a method for managing a data structure in a memory, said one or more computer programs comprising a set of instructions to:

determine an accessor to access a version of the data structure, wherein the accessor includes a version number and a fat pointer, wherein the version number corresponds to the most recent version of the data structure, and wherein the fat pointer is configured to enable for multiple versions of a linked-data structure to be maintained.

20. The computer readable storage medium according to claim 19, said one or more computer programs further comprising a set of instructions to:

determining the fat pointer associated with the accessor, wherein the fat pointer comprises a collection of version number and pointer tuples corresponding to at least one node extending from a root of the data structure.