Physical incremental backup using snapshots

• US 20040163009A1
• Filed: 11/03/2003
• Published: 08/19/2004
• Est. Priority Date: 06/22/2000
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Wrenn, Richard F., Thiel, David W., Goldstein, Andrew C.
• Granted Patent: US 7,197,665 B2
• Time in Patent Office: Days
• US Class Current: 714/6
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data

Abstract

A backup apparatus and method suitable for protecting the data volume in a computer system function by acquiring a base state snapshot and a sequential series of data volume snapshots, the apparatus concurrently generating succedent and precedent lists of snapshot differences which are used to create succedent and precedent backups respectively. The data volume is restored by overwriting the base state data with data blocks identified in one or more succedent backups. File recovery is accomplished by overwriting data from a current snapshot with one or more precedent backups.

Claims

1. A method of protecting computer data, said method comprising the steps of:

acquiring a first state snapshot S₁ of a first data volume consistent state at a time t₁;

acquiring a second state snapshot S₂ of a second data volume consistent state at a time t₂>

t₁;

generating a first precedent snapshot difference list S₂₁ comprising an identification of data blocks of said first state snapshot S₁ differing from data blocks in said second state snapshot S₂; and

creating a first precedent backup B₂₁ by copying from said first state snapshot S₁ data blocks identified in said first precedent snapshot difference list S₂₁, said first precedent backup B₂₁ further comprising said first precedent snapshot difference list S₂₁.

2. The method of claim 1 further comprising the step of storing said first precedent backup B₂₁ in an offline memory means.

3. The method of claim 2 wherein said offline memory means comprises at least one member from the group consisting of magnetic tape and optical disk.

4. The method of claim 1 further comprising the step of deleting said first state snapshot S₁ following said step of generating a first precedent snapshot difference list S₂₁.

5. The method of claim 2 further comprising the steps of:

retrieving said first precedent backup B₂₁;

recovering said first precedent snapshot difference list S₂₁ from said first precedent backup B₂₁; and

restoring said first state snapshot S₁ by overwriting at least a portion of said second state snapshot S₂ with the contents of said first precedent backup B₂₁.

6. The method of claim 1 further comprising the steps of:

acquiring a third state snapshot S₃ of a third data volume consistent state at a time t₃>

t₂;

generating a second precedent snapshot difference list S₃₂ comprising an identification of data blocks of said second state snapshot S₂ differing from data blocks in said third state snapshot S₃; and

creating a second precedent backup B₃₂ by copying from said second state snapshot S₂ data blocks identified in said second precedent snapshot difference list S₃₂, said second precedent backup B₃₂ further comprising said second precedent snapshot difference list S₃₂.

7. The method of claim 6 further comprising the step of storing said second precedent backup B₃₂ in an offline memory means.

8. The method of claim 6 further comprising the step of deleting said second state snapshot S₂ following said step of generating a second precedent snapshot difference list S₃₂.

9. The method of claim 6 further comprising the steps of:

recovering said second precedent snapshot difference list S₃₂ from said second precedent backup B₃₂; and

restoring said second state snapshot S₂ by overwriting at least a portion of said third state snapshot S₃ with the contents of said second precedent backup B₃₂.

10. The method of claim 6 further comprising the steps of:

generating a concatenated precedent snapshot difference list S₃₁ comprising an identification of said data blocks of said second state snapshot S₂ differing from data blocks in said third state snapshot S₃ and an identification of said data blocks of said first state snapshot S₁ differing from data blocks in said second state snapshot S₂;

creating a concatenated backup B₃₁ by copying all said blocks in said first precedent backup B₂₁ and copying all blocks in said second precedent backup B₃₂ not present in said first precedent backup B₂₁;

copying said first precedent snapshot difference list S₂₁ and said second precedent snapshot difference list S₃₂ into said concatenated backup B₃₁; and

storing said concatenated backup B₃₁ in an offline memory means.

11. The method of claim 10 further comprising the steps of:

retrieving said concatenated backup B₃₁;

recovering said concatenated precedent snapshot difference list S₃₁ from said concatenated backup B₃₁; and

restoring said first state snapshot S₁ by overwriting at least a portion of said third state snapshot S₃ with the contents of said concatenated backup B₃₁.

12. The method of claim 10 further comprising the steps of:

acquiring a fourth state snapshot S₄ of a fourth data volume consistent state at a time t₄>

t₃;

generating a third precedent snapshot difference list S₄₃ comprising an identification of data blocks of said third state snapshot S₃ differing from data blocks in said fourth state snapshot S₄;

creating a third precedent backup B₄₃ by copying from said third state snapshot S₃ data blocks identified in said third precedent snapshot difference list S₄₃, said third precedent backup B₄₃ further comprising said third precedent snapshot difference list S₄₃,

generating a concatenated precedent snapshot difference list S₄₂ comprising an identification of said data blocks of said third state snapshot S₃ differing from data blocks in said fourth state snapshot S₄ and an identification of said data blocks of said second state snapshot S₂ differing from data blocks in said third state snapshot S₃;

creating a concatenated backup B₄₂ by copying all said blocks in said second precedent backup B₃₂ and copying all blocks in said third precedent backup B₄₃ not present in said second precedent backup B₃₂, and copying said second and third precedent difference lists S₃₂ and S₄₃ into said concatenated backup B₄₂; and

creating a concatenated backup B₄₁ by copying all said blocks in said first precedent backup B₂₁ and copying all blocks in said concatenated backup B₄₂ not present in said first precedent backup B₂₁, and copying first, second, and third precedent difference lists S₂₁, S₃₂ and S₄₃, into said concatenated backup B₄₁.

13. The method of claim 12 further comprising the steps of:

retrieving said concatenated backup B₄₁;

recovering said concatenated precedent snapshot difference list S₄₁ from said concatenated backup B₄₁; and

restoring said first state snapshot S₁ by overwriting at least a portion of said fourth state snapshot S₄ with the contents of said concatenated backup B₄₁.

14. A method of protecting computer data, said method comprising the steps of:

acquiring a base state snapshot S₀ of a data volume base state at a time t₀;

creating a base state backup B₀ of said base state snapshot S₀;

acquiring a first state snapshot S₁ of a first data volume consistent state at a time t₁>

t₀;

generating a first succedent snapshot difference list S₀₁ comprising an identification of data blocks of said first state snapshot S₁ differing from data blocks in said base state snapshot S₀;

creating a first succedent backup B₀₁ by copying from said first state snapshot S₁ data blocks identified in said first succedent snapshot difference list S₀₁, and copying said first succedent snapshot difference list S₀₁; and

deleting at least a portion of said first state snapshot S₁.

15. The method of claim 14 further comprising the step of storing said base state backup B₀ and said first succedent backup B₀ in an offline memory means.

16. The method of claim 15 further comprising the steps of:

retrieving said base state backup B₀ and said first succedent backup B₀₁;

recovering said base state snapshot S₀ and said first succedent snapshot difference list S₀₁ from said base state backup B₀ and said first succedent backup B₀₁, respectively; and

restoring said first state snapshot S₁ by overwriting said base state snapshot S₀ with said first succedent backup B₀₁.

17. The method of claim 14 further comprising the steps of:

acquiring a second state snapshot S₂ of a second data volume consistent state at a time t₂>

t₁;

generating a second succedent snapshot difference list S₁₂ comprising an identification of data blocks of said second state snapshot S₂ differing from data blocks in said first state snapshot S₁;

creating a second succedent backup B₁₂ by copying from said second state snapshot S₂ data blocks identified in said second succedent snapshot difference list S₁₂, and copying said second succedent snapshot difference list S₁₂; and

deleting at least a portion of said second state snapshot S₂.

18. A method of protecting computer data, said method comprising the steps of:

acquiring a base state snapshot S₀ of a data volume base state at a time to;

acquiring a first state snapshot S₁ of a first data volume consistent state at a time t₁>

t₀;

acquiring a second state snapshot S₂ of a second data volume consistent state at a time t₂>

t₁;

generating a first succedent snapshot difference list S₀₁ comprising an identification of data blocks of said first state snapshot S₀ differing from data blocks in said base state snapshot S₀;

generating a first precedent snapshot difference list S₂₁ comprising an identification of data blocks of said first state snapshot S₁ differing from data blocks in said second state snapshot S₂;

creating a first composite backup C₀₁₂ by copying from said first state snapshot S₁ data blocks identified in first succedent snapshot difference list S₀₁ and copying from said first state snapshot S₁ data blocks identified in said first precedent snapshot difference list S₂₁ and

copying said first succedent snapshot difference list S₀₁ and said first precedent snapshot difference list S₂₁ into said first composite backup C₀₁₂.

19. The method of claim 18 further comprising the step of storing said first composite backup C₀₁₂ in an offline memory means.

20. The method of claim 19 further comprising the steps of:

retrieving said first composite backup C₀₁₂;

recovering said first precedent snapshot difference list S₂₁; and

restoring said first state snapshot S₁ by overwriting at least a portion of said second state snapshot S₂ with at least a portion of the contents of said first composite backup C₀₁₂.

21. The method of claim 18 further comprising the steps of:

acquiring a third state snapshot S₃ of a third data volume consistent state at a time t₃>

t₂;

generating a second succedent snapshot difference list S₁₂ comprising an identification of data blocks of said second state snapshot S₂ differing from data blocks in said first state snapshot S₁;

generating a second precedent snapshot difference list S₃₂ comprising an identification of data blocks of said second state snapshot S₂ differing from data blocks in said third state snapshot S₃;

creating a second composite backup C₁₂₃ by copying from said second state snapshot S₂ data blocks identified in second succedent snapshot difference list S₁₂ and copying from said second state snapshot S₂ data blocks identified in said second precedent snapshot difference list S₃₂ and

copying said second succedent snapshot difference list S₁₂ and said second precedent snapshot difference list S₃₂ into said second composite backup C₁₂₃.

22. The method of claim 21 further comprising the step of storing said second composite backup C₁₂₃ in an offline memory means.

23. The method of claim 18 further comprising the steps of:

acquiring a plurality of third through n^th state snapshots S₃ through S_n, of third through n^th data volume consistent states at respective times t₃<

. . . t_j . . . ≦

t_n;

generating second through (n−

1)^th succedent snapshot difference lists S₁₂ through S<sub>(n−

2)(n−

l)</sub> respectively, a (j−

1)^th succedent snapshot difference list S<sub>(j−

2)(j−

1)</sub> comprising an identification of data blocks of a (j−

1)^th state snapshot S<sub>(j−

1)</sub> differing from data blocks in a (j−

2)^th state snapshot S<sub>(j−

2)</sub>;

generating second through (n−

1)^th precedent snapshot difference lists S₃₂ through S<sub>(n)(n−

1)</sub> respectively, a (j−

1)^th precedent snapshot difference list S<sub>(j)(j−

1)</sub> comprising an identification of data blocks of a (j−

1)^th state snapshot S<sub>(j−

1)</sub> differing from data blocks in a j^th state snapshot S_j;

creating second through (n−

1)^th composite backups C₁₂₃ through C<sub>(n−

2)(n−

1)(n)</sub>, wherein a (j−

1)^th composite backup C<sub>(j−

2)(j−

1)(j)</sub> is created by copying from said (j−

1)^th state snapshot S<sub>(j−

1)</sub> data blocks identified in said (j−

1)^th succedent snapshot difference list S<sub>(j−

2)(j−

1)</sub> and copying from said (j−

1)^th state snapshot S<sub>(j−

1)</sub> data blocks identified in said (j−

1)^th precedent snapshot difference list S<sub>(j)(j−

1)</sub> and

copying said succedent snapshot difference lists S₁₂ through S<sub>(n−

2)(n−

1)</sub> and said precedent snapshot difference lists S₃₂ through S<sub>(n)(n−

1)</sub> into said respective composite backups C₁₂₃ through C<sub>(n−

2)(n−

1)(n)</sub>.

24. The method of claim 23 further comprising the step of storing one or more of said second through (n−

1)^th composite backups C₁₂₃ through C<sub>(n−

2)(n−

1)(n)</sub> in an offline memory means.

25. The method of claim 23 further comprising the step of deleting said third through (n−

1)^th state snapshots S₃ through S<sub>n−

1</sub>.

26. The method of claim 23 further comprising the steps of:

assigning a unique identifier to each said state snapshot S_j for each said composite backup C<sub>(j−

2)(j−

1)(j)</sub>, identifying said state snapshots S<sub>(j−

2)</sub> and S_j as difference snapshots and said (j−

1)^th state snapshot S<sub>(j−

1)</sub> as a content snapshot;

for each said composite backup C<sub>(j−

2)(j−

1)(j)</sub>, copying the unique identifiers of said state snapshots S<sub>(j−

2)</sub>, S<sub>(j−

1)</sub>, and S_j into said (j−

1)^th composite backup C<sub>(j−

2)(j−

l)(j)</sub>.

27. The method of claim 26 further comprising the steps of:

retrieving said (j−

1)^th composite backup C<sub>(j−

2)(j−

1)(j)</sub>;

recovering said (j−

1)^th precedent snapshot difference list S<sub>(j)(j−

1)</sub> from said (j−

1)^th composite backup C<sub>(j−

2)(j−

1)(j)</sub>; and

restoring said (j−

1)^th state snapshot S<sub>j−

1</sub> by overwriting at least a portion of said j^th state snapshot S_j with the contents of said (j−

1)^th composite backup C<sub>(j−

2)(j−

l)(j)</sub>.

28. The method of claim 26 further comprising the step of comparing the unique identifier of said j^th snapshot S_j to the unique identifiers of the difference snapshots of said (j−

1)^th composite backup C<sub>(j−

2)(j−

1)(j).</sub>

29. The method of claim 26 further comprising the step of assigning the unique identifier of the content snapshot of said (j−

1)^th composite backup C<sub>(j−

2)(j−

1)(j)</sub> to be the unique identifier of said restored (j−

1)^th state snapshot S<sub>(j−

1)</sub>.

30. The method of claim 23 further comprising the steps of:

creating a (j−

1)^th precedent backup B<sub>(j−

1)(j−

2)</sub> by copying from said (j−

1)^th state snapshot S<sub>(j−

1)</sub> data blocks identified in said (j−

1)^th precedent snapshot difference list S<sub>(j)(j−

1)</sub>, said (j−

1)^th precedent backup B<sub>(j)(j−

1)</sub> further comprising said (j−

1)^th precedent snapshot difference list S<sub>(j)(j−

1)</sub>;

creating a (j−

2)^th precedent backup B<sub>(j−

1)(j−

2)</sub> by copying from said (j−

2)^th state snapshot S<sub>(j−

2)</sub> data blocks identified in said (j−

2)^th precedent snapshot difference list S<sub>(j−

1)(j−

2)</sub>, said (j−

2)^th precedent backup B<sub>(j−

1)(j−

2)</sub> further comprising said (j−

2)^th precedent snapshot difference list S<sub>(j−

1)(j−

2)</sub>; and

creating a first concatenated precedent backup B<sub>(j)(j−

2)</sub> from said (j−

1)^th precedent backup B<sub>(j)(j−

1)</sub> and said (j−

2) ^th precedent backup B<sub>(j−

l)(j−

2)</sub> by copying all blocks in said (j−

2)^th precedent backup B<sub>(j−

1)(j−

2)</sub> and by also copying all blocks in said (j−

1)^th precedent backup B<sub>(j)(j−

1)</sub> not present in said (j−

2)^th precedent backup B<sub>(j−

1)(j−

2)</sub> and by copying said precedent difference lists S<sub>(j−

1)(j−

2)</sub> and S<sub>(j)(j−

1)</sub> from said precedent backups B<sub>(j−

1)(j−

2)</sub> and B<sub>(j)(j−

1)</sub> into said concatenated precedent backup B<sub>(j)(j−

2)</sub>.

31. The method of claim 30 further comprising the steps of:

creating a (j−

3)^th precedent backup B<sub>(j−

2)(j−

3)</sub> by copying from said (j−

3)^th state snapshot S<sub>(j−

3)</sub> data blocks identified in said (j−

3)^th precedent snapshot difference list S<sub>(j−

2)(j−

3)</sub>, said (j−

3)^th precedent backup B<sub>(j−

2)(j−

3)</sub> further comprising said (j−

3)^th precedent snapshot difference list S<sub>(j−

2)(j−

3)</sub>; and

creating a second concatenated precedent backup B<sub>(j)(j−

3)</sub> from said first concatenated precedent backup B<sub>(j)(j−

2)</sub> and said (j−

3)^th precedent backup B<sub>(j−

2)(j−

3)</sub> by copying all blocks in said (j−

3)^th precedent backup B<sub>(j−

2)(j−

3)</sub> and by also copying all blocks in said first concatenated precedent backup B<sub>(j)(j−

2)</sub> not present in said (j−

3)^th precedent backup B<sub>(j−

2)(j−

3)</sub>, and by copying said precedent difference lists S<sub>(j−

2)(j−

3)</sub>, S<sub>(j−

1)(j−

2)</sub>, and S<sub>(j)(j−

1)</sub> from said precedent backup B<sub>(j−

2)(j−

3)</sub> and said concatenated precedent backup B<sub>(j)(j−

2)</sub> into said concatenated precedent backup B<sub>(j)(j−

3)</sub>.

32. The method of claim 31 further comprising the steps of:

retrieving a concatenated precedent backup B_(h)(g), where g<

h≦

n; and

restoring a g^th state snapshot S_g by overwriting an h^th state snapshot S_h with said concatenated precedent backup B_(h)(g).

33. The method of claim 23 further comprising the steps of:

creating a (j−

1)^th succedent backup B<sub>(j−

2)(j−

1)</sub> by copying from said (j−

1)^th state snapshot S<sub>(j−

1)</sub> data blocks identified in said (j−

1)^th succedent snapshot difference list S<sub>(j−

2)(j−

1)</sub>, said (j−

1)^th succedent backup B<sub>(j−

2)(j−

1)</sub> further comprising said (j−

1)^th succedent snapshot difference list S<sub>(j−

2)(j−

)</sub>;

creating a j^th succedent backup B<sub>(j−

1)(j)</sub> by copying from said j^th state snapshot S_j data blocks identified in said j^th succedent snapshot difference list S<sub>(j−

1)(j)</sub>, said j^th succedent backup j^th further comprising said j^th succedent snapshot difference list S<sub>(j−

1)(j)</sub>; and

creating a first concatenated succedent backup B<sub>(j−

2)(j)</sub> from said j^th succedent backup B<sub>(j−

1)(j)</sub> and said (j−

1)^th succedent backup B<sub>(j−

2)(j−

1)</sub> by copying all blocks in said j^th succedent backup B<sub>(j−

1)(j)</sub>, and by also copying all blocks in said (j−

1)^th succedent backup B<sub>(j−

2)(j−

1)</sub> not present in said j^th succedent backup B<sub>(j−

1)(j)</sub>, and by copying said difference lists S<sub>(j−

1)(j)</sub> and S<sub>(j−

2)(j−

1)</sub>.

34. The method of claim 33 further comprising the steps of:

creating a (j−

2)^th succedent backup B<sub>(j−

3)(j−

2)</sub> by copying from said (j−

2)^th state snapshot S<sub>(j−

2)</sub> data blocks identified in said (j−

2)^th succedent snapshot difference list S<sub>(j−

3)(j−

2)</sub>, said (j−

2)^th succedent backup B<sub>(j−

3)(j−

2)</sub> further comprising said (j−

2)^th succedent snapshot difference list S<sub>(j−

3)(j−

2)</sub>; and

creating a second concatenated succedent backup B<sub>(j−

3)(j)</sub> from said first concatenated succedent backup B<sub>(j−

2)(j)</sub> and said (j−

2)^th succedent backup B<sub>(j−

3)(j−

2)</sub> by copying all blocks in said first concatenated succedent backup B<sub>(j−

2)(j)</sub> and by also copying all blocks in said (j−

2)^th succedent backup B<sub>(j−

3)(j−

2)</sub> not present in said first concatenated succedent backup B<sub>(j−

2)(j)</sub>, and copying said difference lists S<sub>(j−

1)(j)</sub>, S<sub>(j−

2)(j−

1)</sub>, and S<sub>(j−

3)(j−

2)</sub> from said first concatenated succedent backup B<sub>(j−

2)(j)</sub> and said (j−

2)^th succedent backup B<sub>(j−

3)(j−

2)</sub>.

35. An apparatus suitable for protecting the data volume in a computer system, said apparatus comprising:

means for acquiring a sequence of state snapshots S₀, . . . , S_j, . . . , S_n of the data volume, each said state snapshot acquired at a respective time t₀<

. . . t_j . . . <

t_n;

means for generating a (j−

1)^th precedent snapshot difference list S<sub>(j)(j−

1)</sub> comprising a list of one or more data blocks of said j^th state snapshot S_j identified as differing from data blocks of said (j−

1)^th state snapshot S<sub>(j−

1)</sub>;

means for copying from said (j−

1)^th state snapshot S<sub>j−

1</sub> all the data blocks listed in said (j−

1)^th precedent snapshot difference list S<sub>(j)(j−

1)</sub> into a (j−

1)^th precedent backup B<sub>(j)(j−

1)</sub> and

means for copying said precedent snapshot difference list S<sub>(j)(j−

1)</sub>.

36. The apparatus of claim 35 further comprising means for storing said (j−

1)^th precedent backup B<sub>(j)(j−

1)</sub> in an offline memory means.

37. The apparatus of claim 36 further comprising:

means for retrieving said (j−

1)^th precedent backup B<sub>(j)(j−

1)</sub>;

means for recovering said (j−

1)^th precedent snapshot difference list S<sub>(j)(j−

1)</sub> from said (j−

1)^th precedent backup B<sub>(j)(j−

1); and</sub>

means for overwriting at least a portion of said j^th state snapshot S_j with at least a portion of the contents of said (j−

1)^th precedent backup B<sub>(j)(j−

1)</sub>.

38. The apparatus of claim 37 further comprising:

means for generating a (j−

1)^th succedent snapshot difference list S<sub>(j−

2)(j−

1)</sub> comprising a list of one or more data blocks of said (j−

1)^th state snapshot S<sub>(j−

1)</sub> identified as differing from data blocks of said (j−

2)^th state snapshot S<sub>(j−

2)</sub>; and

means for copying from said (j−

1)^th state snapshot S<sub>(j−

1)</sub> all the data blocks listed in said (j−

1)^th succedent snapshot difference list S<sub>(j−

2)(j−

1)</sub> into said (j−

1)^th precedent backup B<sub>(j)(j−

1)</sub>; and

means for copying said (j−

1)^th succedent snapshot difference list S<sub>(j−

2)(j−

1).</sub>

39. The apparatus of claim 38 further comprising:

means for recovering said (j−

1)^th succedent snapshot difference list S<sub>(j−

2)(j−

1)</sub> from said (j−

1)^th precedent backup B<sub>(j)(j−

1)</sub>; and

means for overwriting at least a portion of said (j−

2)^th state snapshot S<sub>(j−

2)</sub>with at least a portion of the contents of said (j−

1)^th precedent backup B<sub>(j)(j−

1)</sub>.

40. The apparatus of claim 35 further comprising:

means for concatenating an (h−

1)^th precedent backup B<sub>(h)(h−

1)</sub> with an (h−

2)^th precedent backup B<sub>(h−

1)(h−

2)</sub> through a g^th precedent backup B_(g+1)(g), where g<

h, into a concatenated precedent backup B_(h)(g); and

means for storing said concatenated precedent backup B_(h)(g) in an offline memory means.

41. The apparatus of claim 38 further comprising:

means for concatenating a (g+1)^th succedent backup B_(g)(g+1) with a (g+2)^th succedent backup B_(g+1)(g+2) through an h^th succedent backup B<sub>(h−

1)(h)</sub>, where g<

h, into a concatenated succedent backup B_(g)(h); and

means for storing said concatenated succedent backup B_(g)(h) in an offline memory means.