Snapshots in distributed storage systems

• US 20080183973A1
• Filed: 01/31/2007
• Published: 07/31/2008
• Est. Priority Date: 01/31/2007
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Aguilera, Marcos K., Veitch, Alistair, Spence, Susan
• Granted Patent: US 8,935,206 B2
• Time in Patent Office: Days
• US Class Current: 711/147
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 11/182 based on mutual exchange of the output between redundant processing components
• 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

Abstract

Embodiments include methods, apparatus, and systems for snapshots in distributed storage systems. One method of software execution includes using a version tree to determine what data blocks are shared between various storage nodes in the version tree in order to create a clone or a snapshot of a storage volume in a distributed storage system that uses quorum-based replication.

Claims

1. ) A method of software execution, comprising:

generating one of a clone or a snapshot in a distributed storage system that utilizes quorum-based replication by updating a version tree and incrementing a version number at a quorum of storage nodes in the distributed storage system.

2. ) The method of claim 1 further comprising:

propagating data with a timestamp to the quorum of storage nodes;

comparing timestamps received from the quorum of storage nodes to determine which of the storage nodes has current data.

3. ) The method of claim 1 further comprising:

announcing a timestamp to the quorum of storage nodes before propagating data to the storage nodes;

storing the timestamp at each of the quorum of storage nodes to determine a current version of data.

4. ) The method of claim 1 further comprising, incrementing a version number associated with a writable volume each time the writable volume receives a new snapshot.

5. ) The method of claim 1 further comprising, ensuring branching consistency by verifying whether a version number assigned to a write is equal to a version number from the quorum of storage nodes.

6. ) The method of claim 1 further comprising:

updating the version tree;

broadcasting an update to all storage nodes;

waiting for the quorum of storage nodes to acknowledge the update in order to successfully complete generation of the clone or the snapshot.

7. ) The method of claim 1 further comprising:

writing data back to the quorum of storage nodes;

including an updated timestamp with the data to prevent conflicting consecutive reads of the data from the quorum of storage nodes.

8. ) A computer readable medium having instructions for causing a computer to execute a method, comprising:

using a version tree to determine what data blocks are shared between various storage nodes in the version tree in order to create a clone or a snapshot of a storage volume in a distributed storage system that uses quorum-based replication.

9. ) The computer readable medium of claim 8 further comprising, rejecting data at one of the storage nodes if a timestamp associated with the data is older than an announced timestamp from a coordinator to a quorum of the storage nodes.

10. ) The computer readable medium of claim 8 further comprising, cloning plural different volumes in the version tree such that the cloning appears to take place at a single point-in-time.

11. ) The computer readable medium of claim 8 further comprising:

requesting the clone or the snapshot at time T1;

completing the clone or the snapshot at time T2, wherein T2>

T1;

capturing a global state of storage at a single point-in-time between T1 and T2.

12. ) The computer readable medium of claim 8 further comprising, requesting the storage nodes to return a most recent timestamp associated with data to determine which of the storage nodes has a current version of the data.

13. ) The computer readable medium of claim 8 further comprising:

defining a sharing list of a storage block as a set of all storage volumes that share the storage block;

splitting the sharing list such that a volume being written and all children in the sharing list share newly written contents.

14. ) The computer readable medium of claim 8 further comprising, associating a version number with a writable volume in the version tree, wherein the version number is incremented when a new snapshot of the volume is taken.

15. ) The computer readable medium of claim 8 further comprising, deleting a volume in the version tree by (1) removing the volume from a sharing list, (2) marking a storage node of the volume as deleted to update the version tree, and (3) removing the volume if all children of the storage node are marked as being deleted.

16. ) A computer system, comprising:

a memory for storing an algorithm; and

a processor for executing the algorithm to;

create a clone or snapshot in a distributed storage system that utilizes quorum-based replication by (1) updating a version tree, (2) broadcasting an update to storage nodes in the distributed storage system, and (3) waiting for a quorum of the storage nodes to acknowledge the update before successfully completing the clone or the snapshot.

17. ) The computer system of claim 16, wherein the processor further executes the algorithm to associate a version number with a writable volume in the version tree, wherein the version number is incremented when a new snapshot of the volume is taken.

18. ) The computer system of claim 16, wherein the processor further executes the algorithm to propagate data with timestamps to the storage nodes and compare timestamps received from the storage nodes to determine a current version of data.

19. ) The computer system of claim 16, wherein the processor further executes the algorithm to:

update a first variable when a storage node delivers a message with a new version to other storage nodes; and

update a second variable when the storage node receives confirmation from a quorum of the other storage nodes that received the message.

20. ) The computer system of claim 16, wherein the processor further executes the algorithm to clone plural different volumes such that the clones appear to be created at a single point-in-time throughout the distributed storage system.