Efficient and reliable virtual volume mapping

• US 7,191,304 B1
• Filed: 09/04/2003
• Issued: 03/13/2007
• Est. Priority Date: 09/06/2002
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: 3pardata Incorporated
• Inventors: Cameron, George R., Huang, Hueichian
• Primary Examiner(s): LANE, JOHN A
• Application Number:
  US10/655,963
• Time in Patent Office: 1,286 Days
• Field of Search: 711/162, 711/202, 707/204, 707/205
• US Class Current: 711/202
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1456 Hardware arrangements for backup
• CPC Class Codes: G06F 11/2064 while ensuring consistency
• CPC Class Codes: G06F 11/2089 Redundant storage control functionality
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

A snapshot tree structure includes a base volume storing a current user data, a first snapshot descending from the base volume, and a second snapshot descending from the first snapshot, wherein the second snapshot was created prior to the first snapshot. The first snapshot includes a first table corresponding to first portions of block addresses, a second table corresponding to second portions of the block addresses, and a third table to third portions of the block addresses. The first table includes an entry with a pointer to the second table. The second table includes an entry with a pointer to the third table. The third table includes an entry with a pointer to a data of the base volume before the data is modified in the base volume.

Claims

1. A snapshot tree structure, comprising:

a base volume storing a current user data;

a first snapshot descending from the base volume, the first snapshot being created at a first time, the first snapshot comprising;

a first table comprising a first plurality of entries corresponding to first portions of block addresses;

a second table comprising a second plurality of entries corresponding to second portions of the block addresses;

a third table comprising a third plurality of entries corresponding to third portions of the block addresses;

wherein;

one of the first plurality of entries contains a pointer to the second table;

one of the second plurality of entries contains a pointer to the third table;

one of the third plurality of entries contains a pointer to a data of the base volume at the first time before the data is modified in the base volume;

a second snapshot descending from the first snapshot, the second snapshot being created at a second time earlier than the first time.

2. The snapshot tree structure of claim 1, wherein the second snapshot comprises:

another first table comprising the first plurality of entries corresponding to the first portions of the block addresses;

another second table comprising another second plurality of entries corresponding to second portions of the block addresses;

another third table comprising another third plurality of entries corresponding to third portions of the block addresses;

wherein;

one of the first plurality of entries in said another first table contains a pointer to said another second table;

one of said another second plurality of entries in said another second table contains a pointer to said another third table;

one of said another third plurality of entries in said another third table contains a pointer to another data of the base volume at the second time before said another data is modified in the base volume.

3. The snapshot tree structure of claim 2, wherein the first and the second snapshots are read-only snapshots.

4. The snapshot tree structure of claim 2, wherein the first snapshot is a read-only snapshot and the second snapshot is a read-write snapshot.

5. A method for creating a snapshot tree structure, comprising:

creating a base volume;

at a first time, creating a first snapshot descending from the base volume, said creating a first snapshot comprising;

creating a first table comprising a first plurality of entries corresponding to first portions of block addresses;

after said creating a first snapshot, receiving a write to a data block in the base volume at a block address;

in response to said receiving a write, copying an original value of the data block to the first snapshot, comprising;

creating a second table comprising a second plurality of entries corresponding to second portions of block addresses;

writing one of the first plurality of entries corresponding to a first portion of the block address with a pointer leading to the second table;

creating a third table comprising a third plurality of entries corresponding to third portions of block addresses;

writing one of the second plurality of entries corresponding to a second portion of the block address with a pointer leading to the third table;

writing the original value of the data block to a new data block;

writing one of the third plurality of entries corresponding to a third portion of the block address with a pointer leading to the new data block;

writing a new value in the data block in the base volume;

at a second time after the first time, creating a second snapshot descending from the base volume, said creating a second snapshot comprising;

creating another first table comprising the first plurality of entries corresponding to the first portions of block addresses;

inserting the second snapshot between the base volume and the first snapshot, wherein the first snapshot now descends from the second snapshot.

6. The method of claim 5, further comprising, after said creating a second snapshot:

receiving another write to another data block in the base volume, said another data block having another block address;

in response to said receiving another write, copying another original value of said another data block to the second snapshot, comprising;

creating another second table comprising another second plurality of entries corresponding to second portions of the block addresses;

writing, in said another first table, one of the first plurality of entries corresponding to a first address portion of said another data block with a pointer leading to said another second table;

creating another third table comprising another third plurality of entries corresponding to third portions of block addresses;

writing, in said another second table, one of said another second plurality of entries corresponding to a second address portion of said another data block with a pointer leading to said another third table;

writing said another original value of said another data block to another new data block;

writing, in said another third table, one of said another third plurality of entries corresponding to a third address portion of said another data block with a pointer leading to said another new data block;

writing another new value in said another data block in the base volume.

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