Time and space efficient technique for creating virtual volume copies

• US 7,886,119 B1
• Filed: 02/27/2007
• Issued: 02/08/2011
• Est. Priority Date: 09/06/2002
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: 3PAR Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Cameron, George R., Huang, Hueichian
• Primary Examiner(s): Chery; Mardochee
• Application Number:
  US11/679,728
• Time in Patent Office: 1,442 Days
• Field of Search: 711/162, 711/114
• US Class Current: 711/162
• CPC Class Codes: G06F 11/1458 Management of the backup or restore process
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A chain of snapshots includes a more recent snapshot with a data block copied from a base volume, a less recent snapshot with a skip-pointer that leads to the data block in said more recent snapshot, and one or more intermediate snapshots between the more recent snapshot and the less recent snapshot in the chain of snapshots.

Claims

1. A non-transitory computer-readable storage medium encoded with an executable program for generating skip-pointers in a chain of snapshots descending from a parent, wherein the program causes a processor to perform the following:

receiving a write request to a data block in the parent;

determining if the write request is a first write request to the data block in the parent;

when the write request is the first write request to the data block in the parent;

copying the data block from the parent to a most recent snapshot in the chain of snapshots;

writing a skip-pointer in at least one of the other snapshots in the chain of snapshots, the skip-pointer leading to the data block in the most recent snapshot;

writing the data block in the parent;

when the write request is not the first write request to the data block, only writing the data block in the parent.

2. The non-transitory computer-readable storage medium of claim 1, wherein the parent is a base volume.

3. The non-transitory computer-readable storage medium of claim 1, wherein the parent is a read-write snapshot that can be written by a user.

4. The non-transitory computer-readable storage medium of claim 1, wherein the skip-pointer leads to an address table in the most recent snapshot and the address table at least partially represents an address of the data block.

5. The non-transitory computer-readable storage medium of claim 1, wherein the skip-pointer directly leads to the data block in the most recent snapshot.

6. The non-transitory computer-readable storage medium of claim 1, wherein the program further causes the processor to perform the following:

reading the data block from the at least one of the other snapshots, comprising;

searching for the data block in the at least one of the other snapshots;

finding the skip-pointer in the at least one of the other snapshots;

following the skip-pointer to the data block in the most recent snapshot; and

reading the data block from the most recent snapshot.

7. The non-transitory computer-readable storage medium of claim 1, wherein the skip-pointer leads to the most recent snapshot.

8. A non-transitory computer-readable storage medium encoded with an executable program for generating skip-pointers in a chain of snapshots, wherein the program causes a processor to perform the following:

searching for a data block in a selected snapshot in the chain of snapshots;

when the data block is not found in the selected snapshot, searching for the data block in more recent snapshots in the chain of snapshots;

when the data block is found in one of the more recent snapshots, writing a skip-pointer in the selected snapshot that leads to the data block in the one of the more recent snapshots, wherein one or more intermediate snapshots are between the selected snapshot and the one of the more recent snapshots; and

reading the data block from the one of the more recent snapshots.

9. The non-transitory computer-readable storage medium of claim 8, wherein the skip-pointer leads to the one of the more recent snapshots.

10. The non-transitory computer-readable storage medium of claim 8, wherein the skip-pointer leads to an address table in the one of the more recent snapshots and the address table at least partially represents an address of the data block.

11. The non-transitory computer-readable storage medium of claim 8, wherein the skip-pointer directly leads to the data block in the one of the more recent snapshots.

12. The non-transitory computer-readable storage medium of claim 8, wherein the program further causes the processor to perform the following:

searching again for the data block in the selected snapshot;

finding the skip-pointer in the selected snapshot;

following the skip-pointer to the data block in the one of the more recent snapshots; and

reading the data block from the one of the more recent snapshots.

13. The non-transitory computer-readable storage medium of claim 8, wherein the program further causes the processor to perform the following, when the data block is found in one of the more recent snapshots:

writing the skip-pointer in at least one of the one or more intermediate snapshots in the chain of snapshots between the selected snapshot and the one of the more recent snapshots.

14. The non-transitory computer-readable storage medium of claim 13, wherein the program further causes the processor to perform the following:

searching for the data block in the one of the one or more intermediate snapshots;

finding the skip-pointer in the one of the one or more intermediate snapshots;

following the skip-pointer to the data block in the one of the more recent snapshots; and

reading the data block from the one of the more recent snapshots.

15. The non-transitory computer-readable storage medium of claim 8, wherein the program further causes the processor to perform the following, when the data block is not found in any of the more recent snapshots:

writing the skip-pointer in the selected snapshot, the skip-pointer leading to a most recent snapshot in the chain of snapshots.

16. The non-transitory computer-readable storage medium of claim 15, wherein the program further causes the processor to perform the following:

searching again for the data block in the selected snapshot;

finding the skip-pointer in the selected snapshot;

following the skip-pointer to the data block in the most recent snapshot; and

searching for the data block in the most recent snapshot.

17. A method for generating skip-pointers in a chain of snapshots descending from a parent, comprising:

receiving a write request to a data block in the parent;

determining, using a programmed processor, if the write request is a first write request to the data block in the parent;

when the write request is the first write request to the data block in the parent;

copying, using the programmed processor, the data block from the parent to a most recent snapshot in the chain of snapshots;

writing, using the programmed processor, a skip-pointer in at least one of the other snapshots in the chain of snapshots, the skip-pointer leading to the data block in the most recent snapshot;

writing, using the programmed processor, the data block in the parent;

when the write request is not the first write request to the data block, only writing, using the programmed processor, the data block in the parent.

18. The method of claim 17, wherein the parent is a base volume.

19. The method of claim 17, wherein the parent is a read-write snapshot that can be written by a user.

20. The method of claim 17, wherein the skip-pointer leads to an address table in the most recent snapshot and the address table at least partially represents an address of the data block.

21. The method of claim 17, wherein the skip-pointer directly leads to the data block in the most recent snapshot.

22. The method of claim 17, further comprising:

reading the data block from the at least one of the other snapshots, comprising;

searching for the data block in the at least one of the other snapshots;

finding the skip-pointer in the at least one of the other snapshots;

following the skip-pointer to the data block in the most recent snapshot; and

reading the data block from the most recent snapshot.

23. The method of claim 17, wherein the skip-pointer leads to the most recent snapshot.

24. A method for generating skip-pointers in a chain of snapshots, comprising:

searching, using a programmed processor, for a data block in a selected snapshot in the chain of snapshots;

when the data block is not found in the selected snapshot, searching, using the programmed processor, for the data block in more recent snapshots in the chain of snapshots;

when the data block is found in one of the more recent snapshots, writing, using the programmed processor, a skip-pointer in the selected snapshot that leads to the data block in the one of the more recent snapshots, wherein one or more intermediate snapshots are between the selected snapshot and the one of the more recent snapshots; and

reading, using the programmed processor, the data block from the one of the more recent snapshots.

25. The method of claim 24, wherein the skip-pointer leads to the one of the more recent snapshots.

26. The method of claim 24, wherein the skip-pointer leads to an address table in the one of the more recent snapshots and the address table at least partially represents an address of the data block.

27. The method of claim 24, wherein the skip-pointer directly leads to the data block in the one of the more recent snapshots.

28. The method of claim 24, further comprising:

searching again for the data block in the selected snapshot;

finding the skip-pointer in the selected snapshot;

following the skip-pointer to the data block in the one of the more recent snapshots; and

reading the data block from the one of the more recent snapshots.

29. The method of claim 24, further comprising, when the data block is found in one of the more recent snapshots:

writing the skip-pointer in at least one of the one or more intermediate snapshots in the chain of snapshots between the selected snapshot and the one of the more recent snapshots.

30. The method of claim 29, further comprising:

searching for the data block in the one of the one or more intermediate snapshots;

finding the skip-pointer in the one of the one or more intermediate snapshots;

following the skip-pointer to the data block in the one of the more recent snapshots; and

reading the data block from the one of the more recent snapshots.

31. The method of claim 24, further comprising, when the data block is not found in any of the more recent snapshots:

writing the skip-pointer in the selected snapshot, the skip-pointer leading to a most recent snapshot in the chain of snapshots.

32. The method of claim 31, further comprising:

searching again for the data block in the selected snapshot;

finding the skip-pointer in the selected snapshot;

following the skip-pointer to the data block in the most recent snapshot; and

searching for the data block in the most recent snapshot.