System, Method and Computer Program Product for Managing Data

• US 20080065669A1
• Filed: 09/12/2006
• Published: 03/13/2008
• Est. Priority Date: 09/12/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Laden, Guy, Fienblit, Shachar, Factor, Michael, Ta-Shma, Paula
• Granted Patent: US 7,664,766 B2
• Time in Patent Office: Days
• US Class Current: 707/101
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method and computer readable product for managing data, the method includes: providing a first data structure representative of insert or update operations to entries identified by keys and providing a second data structure representative of branch creation operations wherein the second data structure stores branch identifiers and branch timing information; receiving a request to lookup a version of data at a read timestamp; scanning the first and the second data structures to locate that version of data; and receiving a request to create a branch that starts by a version of data at a requested timestamp and updating the second data structure accordingly.

Claims

1. A method for managing data, the method comprises:

providing a first data structure representative of insert or update operations to entries identified by keys and providing a second data structure representative of branch creation operations wherein the second data structure stores branch identifiers and branch timing information;

receiving a request to lookup a version of data at a read timestamp;

scanning the first and the second data structures to locate that version of data;

receiving a request to create a branch that starts by a version of data at a requested timestamp; and

updating the second data structure accordingly.

2. The method according to claim 1 wherein the first data structure is a BTree.

3. The method according to claim 1 wherein the method comprises receiving a request to update a value associated with a given key and updating the first data structure.

4. The method according to claim 3 wherein the updating is performed by adding a new entry with the given key and associated data and the current timestamp.

5. The method according to claim 1 wherein the key is a logical block address.

6. The method according to claim 1 wherein the request to create a branch is a revert operation and wherein the certain time stamp is a revert-to time.

7. The method according to claim 1 wherein the looking for a branch comprises scanning branch timing information.

8. The method according to claim 1 wherein the method comprises refreshing the first and second data structures in response to a data storage policy.

9. The method according to claim 8 wherein the refreshing comprises performing a coarse analysis of entries of the second data structure.

10. The method according to claim 8 wherein the refreshing comprises performing a fine analysis of entries of the first and second data structures.

11. The method according to claim 8 wherein the refreshing is responsive to at least one relevancy window.

12. The method according to claim 8 wherein the refreshing is responsive to at least one data storage granularity.

13. The method according to claim 8 wherein the refreshing is responsive to multiple data storage granularities that are responsive to a time lapse from a current point in time.

14. The method according to claim 8 wherein the refershing is responsive to a relationship between an entry of the first data structure and between a subset of entries of the first data structure.

15. The method according to claim 8 wherein the refreshing is responsive to a relationship between an entry of the first data structure and between entries of the first data structure.

16. The method according to claim 1 wherein the branch timing information comprises a branch start time, a branch end time and the requested time stamp.

17. A computer program product wherein the computer readable program when executed on a computer further cause the computer to:

provide a first data structure representative of write or insert operations to locations identified by keys and to provide a second data structure representative of branch creation operation operations;

wherein the second data structure stores branch identifiers and branch timing information;

receive a request to lookup a version of data at a read timestamp;

scan the first and the second data structures to locate that version of data;

receive a request to create a branch that starts by a version of data at a requested timestamp and update the second data structure accordingly.

18. The computer program product according to claim 17 wherein the computer readable program when executed on a computer further cause the computer to receive a request to write data and to update the first data structure.

19. The computer program product according to claim 17 wherein the key is a logical block address.

20. The computer program product according to claim 17 wherein the request to create a branch is a revert operation and wherein the certain time stamp is a revert-to time.

21. The computer program product according to claim 17 wherein the computer readable program when executed on a computer further cause the computer to scan branch timing information.

22. The computer program product according to claim 17 wherein the computer readable program when executed on a computer further cause the computer to refresh the first and second data structures in response to a data storage policy.

23. The computer program product according to claim 22 wherein the computer readable program when executed on a computer further cause the computer to perform a coarse analysis of entries of the second data structure.

24. The computer program product according to claim 22 wherein the computer readable program when executed on a computer further cause the computer to performe a fine analysis of entries of the first data structure.

25. The computer program product according to claim 22 wherein the computer readable program when executed on a computer further cause the computer to the refresh the first and second data structures in response to at least one relevancy window.

26. The computer program product according to claim 22 wherein the computer readable program when executed on a computer further cause the computer to the refresh the first and second data structures in response to at least one data storage granularity.

27. The computer program product according to claim 17 wherein the computer readable program when executed on a computer further cause the computer to provide a second data structure that comprises branch information and branch timing information.

28. A method of providing a service to a customer over a network, the service comprising:

receiving, over a network, a request to lookup a version of data at a read timestamp;

scanning a first data structure and a second data structure to locate that version of data;

wherein the first data structure is representative of insert or update operations to entries identified by keys and the second data structure is representative of branch creation operations and the second data structure stores branch identifiers and branch timing information;

providing the version of data at the read timestamp;

receiving, over a network, a request to create a branch that starts by a version of data at a requested timestamp; and

updating the second data structure accordingly.

29. The method according to claim 28 wherein the first data structure is a BTree.

30. The method according to claim 28 wherein the method comprises receiving, over a network, a request to update a value associated with a given key and updating the first data structure.

31. The method according to claim 30 wherein the updating is performed by adding a new entry with the given key and associated data and the current timestamp.

32. The method according to claim 28 wherein the key is a logical block address.

33. The method according to claim 28 wherein the request to create a branch is a revert operation and wherein the certain time stamp is a revert-to time.