System, method and computer program product for managing data

• US 7,664,766 B2
• Filed: 09/12/2006
• Issued: 02/16/2010
• Est. Priority Date: 09/12/2006
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Laden, Guy, Factor, Michael, Ta-Shma, Paula, Fienblit, Shachar
• Primary Examiner(s): Robinson; Greta L
• Assistant Examiner(s): Wilcox; James J
• Application Number:
  US11/531,130
• Publication Number:
  US 20080065669A1
• Time in Patent Office: 1,253 Days
• Field of Search: None
• US Class Current: 1/1
• 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 computer-implemented method for managing data, comprising the steps of:

under control of instructions residing in a computer-readable storage medium performing respective data update operations comprising writing updated data into a storage unit, the storage unit comprising a continuous data protection system (CDP) for maintaining multiple versions of the updated data;

establishing first entries in a first data structure that describe the update operations, the first entries comprising a timestamp that indicates an update time of the update operations, and being indexed by a key comprising a logical block address;

establishing second entries in a second data structure comprising a table, each second entry having a start time, an end time, a revert-to time, and a time interval that is defined by the start time and end time, the second entries including parent entries and child entries, wherein for each of the child entries, the revert-to time thereof falls within the time interval of its parent entry, each second entry corresponding to a set of update operations occurring during the time interval thereof, the second entries including an initial parent entry;

defining an initial sequence of update operations that defines a first evolution of the updated data over time, wherein the update time thereof occurs during the time interval of the initial parent entry;

responsively to a reversion request to update the initial sequence beginning at a given point in time, adding an initial child entry to the table, wherein the revert-to time thereof is set at the given point and falls within the time interval of the initial parent entry;

reverting the initial sequence to a reverted sequence of update operations by recursively scanning the first data structure, wherein update times in the reverted sequence occur during a first reverted time interval beginning at the start time of the initial parent entry and ending at the revert-to time of the initial child entry or during a second reverted time interval beginning at the start time of the initial child entry;

defining a relevancy window of time wherein it is possible to establish a new child entry in the table, wherein the revert-to time thereof falls in the relevancy window;

determining data accessibility in the storage unit by identifying first update operations, wherein update times thereof fall within the relevancy window and identifying second update operations in the reverted sequence; and

designating the undated data of the first update operations and the second update operations as accessible data;

deleting the undated data other than the accessible data from the storage unit; and

accessing updated data in the reverted sequence in the storage unit.

2. The computer-implemented method according to claim 1, wherein establishing first entries in the first data structure comprises establishing B-tree entries as nodes of a B-tree.

3. The computer-implemented method according to claim 1, wherein accessing updated data comprises:

accepting a lookup request having a lookup timestamp to access a portion of the updated data that is associated with a given key; and

referencing ones of the first entries having update operations occurring within the time interval of the initial parent entry or the time interval of the initial child entry to identify valid updated data at the lookup timestamp.

4. The computer-implemented method according to claim 1, wherein detecting data accessibility includes a coarse analysis that comprises identifying an end portion of the time interval of one of the second entries, wherein the end portion is outside the relevancy window, the one second entry, and wherein the end portion begins at the latest revert-to time of child entries of the one second entry.

5. The computer-implemented method according to claim 4, further comprising performing a fine analysis that comprises scanning at least a subset of the first entries to associate combinations of a particular key with the one second entry and to recursively scan descendant child entries of the one second entry.

6. The computer-implemented method according to claim 1, further comprising the step of:

identifying ones of the second entries wherein the time interval thereof is outside the relevancy window and which lack child entries; and

deleting the identified second entries from the table, and deleting from the storage unit the updated data indicated by ones of the first entries that correspond to the identified second entries.

7. The computer-implemented method according to claim 1, wherein the storage unit comprises a plurality of storage modules that are adapted to store the multiple versions, wherein defining the initial sequence comprises:

maintaining a forward data structure indicative of ones of the multiple versions required to be transferred from a first one of the storage modules to a second one of the storage modules;

maintaining a backward data structure indicative of whether a most recently updated one of the multiple versions resides in the first one or the second one of the storage modules;

responsively to information in the forward data structure and the backward data structure transferring a selected one of the multiple versions from the first one to the second one of the storage modules; and

refreshing the first data structure by updating the key of a corresponding one of the first entries to reflect the update time corresponding to the selected one of the multiple versions.

8. A computer software product for managing data, including a computer-readable storage medium in which computer program instructions are stored, which instructions, when executed by a computer, cause the computer to perform a method comprising the steps of:

performing respective data update operations comprising writing updated data into a storage unit, the storage unit comprising a continuous data protection system (CDP) for maintaining multiple versions of the updated data;

establishing first entries in a first data structure that describe the update operations, the first entries comprising a timestamp that indicates an update time of the update operations, and being indexed by a key comprising a logical block address;

establishing second entries in a second data structure comprising a table, each second entry having a start time, an end time, a revert-to time, and a time interval that is defined by the start time and end time, the second entries including parent entries and child entries, wherein for each of the child entries, the revert-to time thereof falls within the time interval of its parent entry, each second entry corresponding to a set of update operations occurring during the time interval thereof, the second entries including an initial parent entry;

defining an initial sequence of update operations that defines a first evolution of the updated data over time, wherein the update time thereof occurs during the time interval of the initial parent entry;

responsively to a reversion request to update the initial sequence beginning at a given point in time, adding an initial child entry to the table, wherein the revert-to time thereof is set at the given point and falls within the time interval of the initial parent entry;

reverting the initial sequence to a reverted sequence of update operations by recursively scanning the first data structure, wherein update times in the reverted sequence occur during a first reverted time interval beginning at the start time of the initial parent entry and ending at the revert-to time of the initial child entry or during a second reverted time interval beginning at the start time of the initial child entry;

defining a relevancy window of time wherein it is possible to establish a new child entry in the table, wherein the revert-to time thereof falls in the relevancy window;

determining data accessibility in the storage unit by identifying first update operations, wherein update times thereof fall within the relevancy window and identifying second update operations in the reverted sequence; and

designating the undated data of the first update operations and the second update operations as accessible data;

deleting the updated data other than the accessible data from the storage unit; and

accessing updated data in the reverted sequence in the storage unit.

9. The computer software product according to claim 8, wherein establishing first entries in the first data structure comprises establishing B-tree entries as nodes of a B-tree.

10. The computer software product according to claim 8, wherein accessing updated data comprises:

accepting a lookup request having a lookup timestamp to access a portion of the updated data that is associated with a given key; and

referencing ones of the first entries having update operations occurring within the time interval of the initial parent entry or the time interval of the initial child entry to identify valid updated data at the lookup timestamp.

11. The computer software product according to claim 8, wherein detecting data accessibility includes a coarse analysis that comprises identifying an end portion of the time interval of one of the second entries, wherein the end portion is outside the relevancy window, the one second entry, and wherein the end portion begins at the latest revert-to time of child entries of the one second entry.

12. The computer software product according to claim 11, wherein the instructions further cause the computer to perform a fine analysis that comprises scanning at least a subset of the first entries to associate combinations of a particular key with the one second entry and to recursively scan descendant child entries of the one second entry.

13. The computer software product according to claim 8, wherein the instructions cause the computer to perform the additional steps of:

identifying ones of the second entries wherein the time interval thereof is outside the relevancy window and which lack child entries; and

deleting the identified second entries from the table, and deleting from the storage unit the updated data indicated by ones of the first entries that correspond to the identified second entries.

14. The computer software product according to claim 8, wherein the storage unit comprises a plurality of storage modules that are adapted to store the multiple versions, wherein defining the initial sequence comprises:

maintaining a forward data structure indicative of ones of the multiple versions required to be transferred from a first one of the storage modules to a second one of the storage modules;

maintaining a backward data structure indicative of whether a most recently updated one of the multiple versions resides in the first one or the second one of the storage modules;

responsively to information in the forward data structure and the backward data structure transferring a selected one of the multiple versions from the first one to the second one of the storage modules; and

refreshing the first data structure by updating the key of a corresponding one of the first entries to reflect the update time corresponding to the selected one of the multiple versions.

15. A data processing system for managing data, comprising:

a controller;

a memory accessible by the controller;

a storage unit accessible by the controller, the storage unit comprising a continuous data protection system (CDP) for maintaining multiple versions of data being managed, wherein the controller is operative to perform the steps of;

performing respective data update operations comprising writing updated data into the storage unit;

establishing first entries in a first data structure that describe the update operations, the first entries comprising a timestamp that indicates an update time of the update operations, and being indexed by a key comprising a logical block address;

establishing second entries in a second data structure comprising a table, each second entry having a start time, an end time, a revert-to time, and a time interval that is defined by the start time and end time, the second entries including parent entries and child entries, wherein for each of the child entries, the revert-to time thereof falls within the time interval of its parent entry, each second entry corresponding to a set of update operations occurring during the time interval thereof, the second entries including an initial parent entry;

defining an initial sequence of update operations that defines a first evolution of the updated data over time, wherein the update time thereof occurs during the time interval of the initial parent entry;

responsively to a reversion request to update the initial sequence beginning at a given point in time, adding an initial child entry to the table, wherein the revert-to time thereof is set at the given point and falls within the time interval of the initial parent entry;

reverting the initial sequence to a reverted sequence of update operations by recursively scanning the first data structure, wherein update times in the reverted sequence occur during a first reverted time interval beginning at the start time of the initial parent entry and ending at the revert-to time of the initial child entry or during a second reverted time interval beginning at the start time of the initial child entry;

defining a relevancy window of time wherein it is possible to establish a new child entry in the table, wherein the revert-to time thereof falls in the relevancy window;

determining data accessibility in the storage unit by identifying first update operations, wherein update times thereof fall within the relevancy window and identifying second update operations in the reverted sequence; and

designating the undated data of the first update operations and the second update operations as accessible data;

deleting the undated data other than the accessible data from the storage unit; and

accessing updated data in the reverted sequence in the storage unit.

16. The data processing system according to claim 15, wherein establishing first entries in the first data structure comprises establishing B-tree entries as nodes of a B-tree.

17. The data processing system according to claim 15, wherein accessing updated data comprises:

accepting a lookup request having a lookup timestamp to access a portion of the updated data that is associated with a given key; and

referencing ones of the first entries having update operations occurring within the time interval of the initial parent entry or the time interval of the initial child entry to identify valid updated data at the lookup timestamp.

18. The data processing system according to claim 15, wherein detecting data accessibility includes a coarse analysis that comprises identifying an end portion of the time interval of one of the second entries, wherein the end portion is outside the relevancy window, the one second entry, and wherein the end portion begins at the latest revert-to time of child entries of the one second entry.

19. The data processing system according to claim 18, wherein the controller is operative to perform a fine analysis that comprises scanning at least a subset of the first entries to associate combinations of a particular key with the one second entry and to recursively scan descendant child entries of the one second entry.

20. The data processing system according to claim 15, wherein the controller is operative to perform the additional steps of:

identifying ones of the second entries wherein the time interval thereof is outside the relevancy window and which lack child entries; and

deleting the identified second entries from the table, and deleting from the storage unit the updated data indicated by ones of the first entries that correspond to the identified second entries.

21. The data processing system according to claim 15, wherein the storage unit comprises a plurality of storage modules that are adapted to store the multiple versions, wherein defining the initial sequence comprises:

maintaining a forward data structure indicative of ones of the multiple versions required to be transferred from a first one of the storage modules to a second one of the storage modules;

maintaining a backward data structure indicative of whether a most recently updated one of the multiple versions resides in the first one or the second one of the storage modules;

responsively to information in the forward data structure and the backward data structure transferring a selected one of the multiple versions from the first one to the second one of the storage modules; and

refreshing the first data structure by updating the key of a corresponding one of the first entries to reflect the update time corresponding to the selected one of the multiple versions.