Method for taking snapshots of data

• US 20060155946A1
• Filed: 01/10/2005
• Published: 07/13/2006
• Est. Priority Date: 01/10/2005
• 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: Ji, Minwen
• Granted Patent: US 7,363,444 B2
• Time in Patent Office: Days
• US Class Current: 711/162
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A method for taking snapshots of data. In an embodiment, a first map data structure is obtained that records locations for a plurality of data blocks. A second map data structure is formed that is initially empty of locations, the second map data structure representing the snapshot after the snapshot is started. Writes on data that arrive before the snapshot starts are applied to the first map, and writes that arrive after the snapshot starts are applied to the second map.

Claims

1. A method of taking a snapshot of data comprising:

obtaining a first map data structure that records locations for a plurality of data blocks;

forming a second map data structure that is initially empty of locations, the second map data structure representing the snapshot after the snapshot is started; and

applying a write on data to the first map if the write arrives before the snapshot is started, and otherwise to the second map if the write arrives after the snapshot is started.

2. The method according to claim 1, the first map data structure initially being identified as a current map for a volume and the second map data structure initially being identified as a tentative map data structure for the volume and further comprising committing the snapshot by identifying the second map data structure as the current map for the volume and identifying the first map data structure as a snapshot map for the volume.

3. The method according to claim 1, further comprising overwriting the data for a write applied to the second map data structure in place without updating the second map data structure when the data is updated again.

4. A method of taking a snapshot of data comprising:

obtaining a first map data structure that specifies a relationship of logical addresses to physical addresses for a plurality of data blocks of a volume, the first map data structure initially being identified as a current map for the volume;

forming a second map data structure that is initially empty, the second map data structure initially being identified as a tentative map data structure for the volume; and

committing the snapshot by identifying the second map data structure as the current map for the volume and identifying the first map data structure as a snapshot map for the volume.

5. The method according to claim 4, further comprising inserting a new physical address into the second data structure when a data block of the plurality is updated by a new version of the data, the new version of the data being stored at the new physical address.

6. The method according to claim 5, further comprising overwriting the new version of the data in place without updating the second data structure when the data block is updated again.

7. The method according to claim 4, further comprising taking one or more additional snapshots by repeating said steps of forming a and committing for each additional snapshot.

8. The method according to claim 7, wherein a write operation is directed to a newest map that was created before the write operation arrives.

9. The method according to claim 4, wherein the volume is distributed among a plurality of storage devices and wherein said steps of forming and committing are performed at sufficient ones of the plurality of the storage devices that the snapshot can be reconstructed.

10. The method according to claim 9, wherein the volume is distributed and replicated among the plurality of storage devices.

11. A method of taking a snapshot of a data distributed among a plurality of data storage devices, the plurality of data storage devices redundantly storing the data and each having a map data structure that specifies a relationship of logical addresses to physical addresses for a plurality of blocks of the data, the method comprising:

forming new map data structures by at least a quorum of the storage devices, each new map data structure initially being empty of physical addresses and initially being identified as a tentative map data structure; and

committing the snapshot by at least a quorum of the storage devices by identifying the map data structures as snapshot maps for the data and identifying the new map data structures as current maps for the data.

12. The method according to claim 11, further comprising inserting a new physical address into the new data structures when a data block is updated by a new version of the data, the new version of the data being stored at the new physical address.

13. The method according to claim 12, further comprising overwriting the new version of the data in place without updating the new data structure when the data block is updated again.

14. The method according to claim 11, further comprising taking one or more additional snapshots by repeating said steps of forming a and committing for each additional snapshot.

15. The method according to claim 11, wherein the data is replicated.

16. The method according to claim 11, wherein the data is erasure coded.

17. The method according to claim 11, the plurality of data storage devices being a group of devices designated for redundantly storing at least a portion of a data volume and wherein one or more additional groups of storage devices are each designated for storing a corresponding portion of the data volume and the quorum comprising a quorum of each of the groups of the devices.

18. The method according to claim 11, said forming comprising sending a first command and wherein each storage device that successfully forms its new map data structure in response to the first command returns an affirmative response.

19. The method according to claim 18, said committing being performed in response to receiving affirmative responses from the quorum.

20. The method according to claim 19, said committing comprising sending a second command and said committing is performed by the storage devices in response to the second command.

21. A method of taking a snapshot of a data distributed among a plurality of data storage devices, the plurality of data storage devices redundantly storing the data and each having a map data structure that specifies a relationship of logical addresses to physical addresses for a plurality of blocks of the data, the method comprising:

sending a first command to the plurality of storage devices instructing the snapshot of the data to be prepared;

receiving any affirmative responses from the plurality of storage devices, each affirmative response indicating that the corresponding storage device is able to form a new map data structure, the new map data structure initially being empty of physical addresses; and

sending a second command to the plurality storage devices, the second command instructing the snapshot to be committed if a quorum of affirmative responses is received and the second command instructing the snapshot to be aborted if a quorum of affirmative responses is not received.

22. The method according to claim 21, further comprising inserting a new physical address into the new data structures when a data block is updated by a new version of the data, the new version of the data being stored at the new physical address.

23. The method according to claim 22, further comprising overwriting the new version of the data in place without updating the new data structure when the data block is updated again.

24. The method according to claim 21, further comprising taking one or more additional snapshots by repeating said steps of sending the first command, receiving any responses and sending the second command for each additional snapshot.

25. The method according to claim 21, wherein the data is replicated.

26. The method according to claim 21, wherein the data is erasure coded.

27. The method according to claim 21, the plurality of data storage devices being a group of devices designated for redundantly storing at least a portion of a data volume and wherein one or more additional groups of storage devices are each designated for storing a corresponding portion of the data volume and the quorum comprising a quorum of each of the groups of the devices.

28. The method according to claim 21, the map data structure for each storage device initially being identified as a current map for the data and the new map data structure for each storage device initially being identified as a tentative map data structure.

29. The method according to claim 28, wherein in response to being instructed to commit the snapshot, each storage device identifies its map data structure as the snapshot map for the data and identifies the new map data structure as its current map for the data.

30. The method according to claim 28, wherein write operations are directed to the tentative map for the data after the first command is received and before the snapshot is committed or aborted and, otherwise, the write operations are directed to the current map for the data.

31. The method according to claim 28, wherein in response to being instructed to abort the snapshot, each storage device merges any write operations in its tentative map for the data into its current map for the data and deletes or ignores its tentative map.

32. The method according to claim 28, wherein a timestamp for the snapshot is associated with the first command and each storage device has information that indicates the last time that a snapshot was started on the volume and the last time that any data corresponding to the current map was updated or prepared for update.

33. The method according to claim 32, wherein each storage device receiving the first command determines from the timestamp and the information whether data corresponding to the current map was updated or prepared for update after a time indicated by the timestamp.

34. The method according to claim 32, wherein if the data corresponding to the current map was updated or prepared for update after a time indicated by the timestamp at a storage device, the storage device does not return an affirmative response to the first command.

35. The method according to claim 34, the value of the timestamp for a retried snapshot after an abort is determined by adding to a present time an adjustment period in response to one or more attempted snapshots being aborted.

36. The method according to claim 35, wherein the adjustment period is at least the difference in time between the timestamp of an aborted snapshot and last time that any data corresponding to the current map was updated or prepared for update.

37. The method according to claim 21, the plurality of data storage devices being a group of devices designated for redundantly storing at least a portion of a data volume and wherein one or more additional groups of storage devices are each designated for storing a corresponding portion of the data volume and the snapshot being determined valid or invalid from information obtained from quorum of the groups of the storage devices.

38. The method according to claim 21, the plurality of data storage devices being a group of devices designated for redundantly storing at least a portion of a data volume and wherein one or more additional groups of storage devices are each designated for storing a corresponding portion of the data volume and the snapshot being determined valid or invalid from information obtained from only one group of the storage devices.

39. The method according to claim 37, further comprising recovering the snapshot if the snapshot is determined invalid.

40. A computer readable media comprising computer code for implementing a method of taking a snapshot of data, the method comprising the steps of:

obtaining a first map data structure that records locations for a plurality of data blocks;

forming a second map data structure that is initially empty of locations, the second map data structure representing the snapshot after the snapshot is started; and

applying a write on data to the first map if the write arrives before the snapshot is started, and otherwise to the second map if the write arrives after the snapshot is started.