Time and space efficient technique for creating virtual volume copies

• US 7,743,031 B1
• Filed: 09/04/2003
• Issued: 06/22/2010
• 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): ALAM, SHAHID AL
• Application Number:
  US10/655,951
• Time in Patent Office: 2,483 Days
• Field of Search: 707/10, 707/100, 707/101, 707/102, 707/200, 707/201, 707/202
• US Class Current: 707/649
• 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 snapshot tree structure includes a base volume storing a current user data at a current time, a first read-only snapshot descending from the base volume, and a second read-only snapshot descending from the first read-only snapshot. The first read-only snapshot is created at a first time earlier than the current time. The first read-only snapshot stores a first data of the base volume at the first time before the first data is modified in the base volume. The second read-only snapshot is created at a second time earlier than the first time. The second read-only snapshot stores a second data of the base volume at the second time before the second data is modified in the base volume.

Claims

1. A non-transitory computer readable medium for a data storage device encoded with a snapshot tree structure and code for managing the snapshot tree structure to provide point-in-time backups of a base volume, wherein:

the snapshot tree structure comprises;

a first branch, comprising;

the base volume storing a current user data;

a first read-only snapshot descending from the base volume, the first read-only snapshot being created at a first time, the first read-only snapshot storing a first data of the base volume at the first time before the first data is modified in the base volume; and

a second read-only snapshot descending from the first read-only snapshot, the second read-only snapshot being created at a second time earlier than the first time, the second read-only snapshot storing a second data of the base volume at the second time before the second data is modified in the base volume; and

the code comprises instructions to retrieve data from the snapshot tree structure and transmitting the retrieved data to a host device.

2. The non-transitory computer readable medium of claim 1, wherein the snapshot tree structure further comprises:

a second branch, comprising a first read-write snapshot descending from one of the first and the second read-only snapshots.

3. The non-transitory computer readable medium of claim 2, wherein the second branch further comprises a third read-only snapshot descending from the first read-write snapshot, the third read-only snapshot being created at a third time, the third read-only snapshot storing a third data of the first read-write snapshot at the third time before the third data is modified in the first read-write snapshot.

4. The non-transitory computer readable medium of claim 3, wherein the snapshot tree structure further comprises:

a third branch, comprising a second read-write snapshot descending from the third read-only snapshot.

5. The non-transitory computer readable medium of claim 1, wherein the third branch further comprises a fourth read-only snapshot descending from the second read-write snapshot, the fourth read-only snapshot being created at a fourth time, the fourth read-only snapshot storing a fourth data of the second read-write snapshot at the fourth time before the fourth data is modified in the second read read-write snapshot.

6. A method for a data storage device to store snapshots that provide point-in-time backups of a base volume using a snapshot tree structure, the method comprising:

creating a first branch, comprising;

creating the base volume storing a current user data;

creating a first read-only snapshot descending from the base volume, the first read-only snapshot being created at a first time;

storing in the first read-only snapshot a first data of the base volume at the first time before the first data is modified in the base volume;

creating a second read-only snapshot descending from the base volume, the second read-only snapshot being created at a second time later than the first time;

storing in the second read-only snapshot a second data of the base volume at the second time before the second data is modified in the base volume; and

inserting the second read-only snapshot between the base volume and the first read-only snapshot, wherein the first read-only snapshot now descends from the second read-only snapshot; and

retrieving data from the snapshot tree structure and transmitting the retrieved data to a host device.

7. The method of claim 6, further comprising:

creating a second branch, comprising creating a first read-write snapshot descending from one of the first and the second read-only snapshots.

8. The method of claim 7, wherein said creating a second branch further comprises creating a third read-only snapshot descending from the first read-write snapshot, the third read-only snapshot being created at a third time, the third read-only snapshot storing a third data of the first read-write snapshot at the third time before the third data is modified in the first read-write snapshot.

9. The method of claim 8, further comprising:

creating a third branch, comprising creating a second read-write snapshot descending from the third read-only snapshot.

10. The method of claim 9, wherein said creating a third branch further comprises creating a fourth read-only snapshot descending from the second read-write snapshot, the fourth read-only snapshot being created at a fourth time, the fourth read-only snapshot storing a fourth data of the second read-write snapshot at the fourth time before the fourth data is modified in the second read read-write snapshot.

11. A method for a data storage device to retrieve a point-in-time backup of a base volume by reading a value of a data block from a snapshot tree structure having the base volume, a first snapshot descending from the base volume, and a second snapshot descending from the first snapshot, the method comprising:

searching for the data block in the second snapshot;

if the data block is not found in the second snapshot;

following a link in the second snapshot to the first snapshot; and

searching for the data block in the first snapshot; and

transmitting the data block to a host device after the data block is found.

12. The method of claim 11, wherein the first and the second snapshots are read-only snapshots.

13. The method of claim 11, wherein the first snapshot is a read-only snapshot and the second snapshot is a read-write snapshot.

14. The method of claim 11, further comprising:

if the data block is not found in the first snapshot;

following another link in the first snapshot to the base volume; and

reading the data block from the base volume.