Methods and infrastructure for performing repetitive data protection and a corresponding restore of data

• US 8,572,040 B2
• Filed: 04/27/2007
• Issued: 10/29/2013
• Est. Priority Date: 04/28/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation, ServiceNow Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Prause, Thomas, Augenstein, Oliver
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): HARPER, ELIYAH STONE
• Application Number:
  US11/741,163
• Publication Number:
  US 20070260645A1
• Time in Patent Office: 2,377 Days
• Field of Search: 707/104.1, 707/100, 707/10, 707/3
• US Class Current: 707/648
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence

Abstract

The present invention provides methods and an infrastructure for performing repetitive data protection and a corresponding restore of data for block oriented data objects comprising several indexed segments. For implementing the invention, timestamps t_k are set by a timer k. Only the first data modification of a segment is recorded, after a timestamp t_k has been set, by storing the old data contents of said segment together with the segment index j and said timestamp t_k as undo-log block in a first journal j₀, before overwriting said segment with the modified new data. Besides, said undo-log blocks are transmitted to N journals j_i for storing redundant undo-log information, with N>1 and i=0, . . . , N−1. According to the present invention for each journal j_i journal-specific timestamps t_k/i are generated, so that each journal j_i is written for a different set of timestamps t_k/i.

Claims

1. A method for performing repetitive data protection for data stored in a block oriented data object comprising several indexed segments, the method comprising:

setting a set of timestamps t_k for a first undo-log journal j₀ by a timer k;

recording each first data modification of a segment that occurs after a timestamp t_k has been set by storing old data contents of said segment together with a segment index j and a timestamp t_k as an undo-log block in the first undo-log journal j₀ before overwriting said segment with modified new data such that the first undo-log journal j₀ comprises sequential undo-log blocks corresponding to each timestamp t_k;

transmitting an undo-log block to one or more additional undo-log journals j_i based on a timestamp t_k and storing redundant undo-log information in the one or more additional undo-log journals, the redundant undo-log information comprising a subset of undo-log blocks from the first undo-log journal j₀, such that each additional undo-log journal comprises sequential undo-log blocks written for a different set of timestamps t_k/i, a granularity of timestamps and corresponding undo-log blocks in an additional undo-log journal decreasing such that each additional undo-log journal comprises fewer undo-log blocks than a previous undo-log journal; and

restoring data contents of the segment from a state of the data contents at a start time to a state of the data contents at a target time using a sequence of undo-log blocks from two or more undo-log journals, the two or more undo-log journals selected from the first undo-log journal j₀ and the one or more additional undo-log journals j_i, each undo-log block in the sequence selected from one of the two or more undo-log journals with a coarsest available granularity for the undo-log block such that the undo-log blocks in the sequence are selected from each of the two or more undo-log journals.

2. The method of claim 1, wherein each set of timestamps t_k/i represents a different time graining and wherein the density of timestamps t_k/i decreases with increasing i.

3. The method of claim 1, wherein the timer k is incremented on request.

4. The method of claim 1, wherein said journal-specific timestamps t_k are generated based on the timestamp values t_k set by said timer k.

5. The method of claim 4, wherein said journal-specific timestamps t_k/i are defined as the 2ⁱ-th timestamps t_k.

6. The method of claim 5, wherein said journal-specific timestamps t_k/i is incremented only if the ratio of the amount of data written to journal j_i with timestamp t_k/i over the total number of modifications including those undo-log blocks not written to journal j_i during that period gets lower than a predefined ratio for journal j_i.

7. The method of claim 5, wherein said journal-specific timestamps t_k/i for journal j_i (i>

0) is incremented if a recovery point in journal j<sub>i−

1</sub> was set and the ratio of the amount of data written to journal j<sub>i−

1</sub> since last recovery point in journal j_i over the amount of data written to journal j_i since last recovery point in journal j_i exceeds a predefined ratio.

8. The method of claim 1, characterized in that an offset-table is updated regularly for each timestamp t_k/i, wherein said offset-table comprises for each timestamp t_k/i the offset-position for writing to corresponding journal j_i after said timestamp t_k/i.

9. The method of claim 1, wherein said journals j_i are stored on sequential storage media.

10. A method for restoring data of a block oriented data object comprising several indexed segments by using undo-log information generated and stored as described by:

setting a set of timestamps t_k for a first undo-log journal j₀ by a timer k;

recording each first data modification of a segment that occurs after a timestamp t_k has been set by storing old data contents of said segment together with a segment index j and a timestamp t_k as an undo-log block in the first undo-log journal j₀ before overwriting said segment with modified new data such that the first undo-log journal j₀ comprises sequential undo-log blocks corresponding to each timestamp t_k;

transmitting an undo-log block to one or more additional undo-log journals j_i based on a timestamp t_k and storing redundant undo-log information in the one or more additional undo-log journals, the redundant undo-log information comprising a subset of undo-log blocks from the first undo-log journal, such that each additional undo-log journal comprises sequential undo-log blocks written for a different set of timestamps t_k/i, a granularity of timestamps and corresponding undo-log blocks in an additional undo-log journal decreasing such that each additional undo-log journal comprises fewer undo-log blocks than a previous undo-log journal, wherein each undo-log journal j_i represents a different time graining of undo-log information and wherein the density of the corresponding timestamps t_k/i decreases with increasing i; and

restoring data contents of the segment to a state before a timestamp t using a sequence of undo-log blocks each selected from an undo-log journal with a coarsest available granularity for the undo-log block such that the undo-log blocks in the sequence are selected from multiple undo-log journals, the restoring comprising,

reading a last undo-log journal j_N-1, the last undo-log journal j_N-1 having the fewest number of undo-log blocks relative to the first undo-log journal j₀ and the other additional undo-log journals j_i, starting from the first undo-log block comprising a first timestamp t_k/N-1 which is the same as or occurs after a time for undo-log journal j_N-1 which corresponds to timestamp t, till the end of undo-log journal j_N-1,

reading the next journal j_i in decreasing order starting from the first undo-log block, comprising the first timestamp t_k/i which is the same as or occurs after the time for undo-log journal j_i which corresponds to timestamp t, till the undo-log block comprising the first timestamp t_k/i which is the same as or occurs after the first timestamp for undo-log journal j_i which corresponds to the timestamp t_k/i+1 of undo-log journal j_i+1 having been read of the preceding undo-log journal j_i+1;

repeating the preceding step of reading for all next journals j<sub>i−

1</sub> such that the data stored in an undo-log block read from an undo-log journal is only written to the corresponding segment of the data object, if said segment has not been re-written before, initiated by an undo-log block read before from the same undo-log journal.

11. The method of claim 10, wherein a restore table is generated for each currently read journal and listing the indexes j of those segments which have already been re-written with said journal.

12. The method of claim 10, wherein in case of an error when reading journal j_N-1, journal j_N-2 is read starting from the first undo-log block comprising the first timestamp t_k/N-2 which is the same as or occurs after timestamp t, until the end of journal j_N-2, and wherein the preceding step of reading is repeated for all next journals j_i−

1 according to claim 10.

13. The method of claim 10, wherein in case of an error when reading journal j_i with N−

1>

i>

0, the next journal j<sub>i−

1</sub> in decreasing order is read starting from the first undo-log block, comprising the first timestamp t<sub>k/i−

1</sub> which is the same as or occurs after timestamp t, till the undo-log block comprising the first timestamp t<sub>k/i−

1</sub> which is the same as or occurs after the first timestamp t_k/i+1 having been read of the preceding journal j_i+1 and wherein the preceding step of reading is repeated for all next journals j<sub>i−

1</sub> according to claim 10.

14. The method of claim 10, wherein the offset-positions of the undo-log blocks to be read first in each journal j_i, are identified by means of an offset-table comprising for each timestamp t_k/i the offset-position for writing to the corresponding journal j_i after said timestamp t_k/i.

15. A method for restoring data of a block oriented data object comprising several indexed segments by using undo-log information generated and stored as described by:

setting a set of timestamps t_k for a first undo-log journal j₀ by a timer k;

recording each first data modification of a segment that occurs after a timestamp t_k has been set by storing old data contents of said segment together with a segment index j and a timestamp t_k as an undo-log block in the first undo-log journal j₀ before overwriting said segment with modified new data such that the first undo-log journal j₀ comprises sequential undo-log blocks corresponding to each timestamp t_k;

transmitting an undo-log block to one or more additional undo-log journals j_i based on a timestamp t_k storing redundant undo-log information in the one or more additional undo-log journals, the redundant undo-log information comprising a subset of undo-log blocks from the first undo-log journal, such that each additional undo-log journal comprises sequential undo-log blocks written for a different set of timestamps t_k/i, a granularity of timestamps and corresponding undo-log blocks in an additional undo-log journal decreasing such that each additional undo-log journal comprises fewer undo-log blocks than a previous undo-log journal, wherein each undo-log journal j_i represents a different time graining of undo-log information, wherein the density of the corresponding timestamps t_k/i decreases with increasing i; and

restoring data contents of the segment to a state before a timestamp t using a sequence of undo-log blocks each selected from an undo-log journal with a coarsest available granularity for the undo-log block such that the undo-log blocks in the sequence are selected from multiple undo-log journals, the restoring comprising;

reading the first undo-log journal j₀, the first undo-log journal j₀ having the highest number of undo-log blocks relative to the additional undo-log journals j_i starting from a first undo-log block, comprising a first timestamp t_k/i which is the same as or occurs after timestamp t, till the first undo-log block comprising a timestamp t_k/i which is the same as or occurs after a first timestamp t_k/i+1 of a next undo-log journal j_i+1, with timestamp t_k/i+1 which is the same as or occurs after timestamp t;

repeating the preceding step of reading for all next undo-log journals j_i+1 with i=1, . . . , N−

2;

reading a last undo-log journal j_N-1 starting from the first undo-log block comprising the first timestamp t_k/N-1 which is the same as or occurs after timestamp t, till the end of undo-log journal j_N-1, such that the data stored in an undo-log block read from an undo-log journal is only written to the corresponding segment of the data object, if said segment has not been re-written before, initiated by an undo-log block read before from the same undo-log journal.

16. The method of claim 15, wherein a restore table is generated for each restore procedure listing the indexes j of those segments which have already been re-written.

17. The method of claim 15, wherein in case of an error, when reading journal j_i with 0<

i<

=N−

1,

journal j_i is removed;

all journals j_i+k+1 are renamed to be j_i+k with and all corresponding timestamps are renamed accordingly; and

reading continues with journal j<sub>i−

1</sub>.

18. The method of claim 15, wherein the offset-positions of the undo-log blocks to be read first in each journal j_i, are identified by means of an offset-table comprising for each timestamp t_k/i the offset-position for writing to the corresponding journal j_i after said timestamp t_k/i.

19. A method for performing repetitive data protection for data stored in a block oriented data object comprising several indexed segments, the method comprising:

setting a different granularity of timestamps for each of a plurality of undo-log journals such that the granularity of the timestamps decreases for each undo-log journal between a first undo-log journal and a last undo-log journal;

recording, for each undo-log journal from the plurality of undo-log journals, each first data modification of a segment that occurs after a timestamp for the undo-log journal by storing old data contents of the segment, a segment index of the segment, and the timestamp as an undo-log block in the undo-log journal such that each undo-log journal from the plurality of undo-log journals comprises sequential undo-log blocks corresponding to the granularity of timestamps for the undo-log journal, each undo-log journal between the first undo-log journal and the last undo-log journal comprising fewer undo-log blocks than a previous undo-log journal based on the different granularity of timestamps for each undo-log journal; and

restoring data contents of the segment from a state of the data contents at a start time to a state of the data contents at a target time using a sequence of undo-log blocks from two or more of the plurality of undo-log journals, the undo-log blocks in the sequence selected from one of the two or more undo-log journals with a coarsest available granularity for the undo-log block such that the undo-log blocks in the sequence are selected from each of the two or more undo-log journals.

20. The method of claim 19, wherein the target time is prior to the start time and the sequence of undo-log blocks begins with undo-log blocks from the last journal and ends with undo-log blocks from the first journal.

21. The method of claim 19, wherein the start time is prior to the target time and the sequence of undo-log blocks begins with undo-log blocks from the first journal and ends with undo-log blocks from the last journal.