Method for taking snapshots of data
First Claim
Patent Images
1. 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;
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 for the volume;
taking one or more additional snapshots by repeating said steps of forming and committing for each additional snapshot, each snapshot being completed upon being committed and the snapshots being linked such that each snapshot is linked to a next most-recent snapshot; and
performing writes to data blocks of the volume while taking the one or more additional snapshots by writing a data block to a new physical location and updating the map identified as the current map at the time of the write with a physical address of the data block being written, wherein each committed snapshot only contains values corresponding to the physical addresses of the data blocks of the volume that were written to while the map data structure for the snapshot was identified as the current map.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
37 Claims
-
1. 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; 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 for the volume; taking one or more additional snapshots by repeating said steps of forming and committing for each additional snapshot, each snapshot being completed upon being committed and the snapshots being linked such that each snapshot is linked to a next most-recent snapshot; and performing writes to data blocks of the volume while taking the one or more additional snapshots by writing a data block to a new physical location and updating the map identified as the current map at the time of the write with a physical address of the data block being written, wherein each committed snapshot only contains values corresponding to the physical addresses of the data blocks of the volume that were written to while the map data structure for the snapshot was identified as the current map. - View Dependent Claims (2, 3, 4, 34)
-
-
5. 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 but not necessarily all 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 but not necessarily all 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. - View Dependent Claims (6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. 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 of storage devices, the second command instructing the snapshot to be committed if a quorum of affirmative responses is received, but not necessarily a response from each of the plurality of storage devices being received, and the second command instructing the snapshot to be aborted if the quorum of affirmative responses is not received. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 31, 32, 33, 35, 36)
-
-
27. A method of taking a snapshot of 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 and the map data structure for each storage device initially being identified as a current map for the data, the method comprising:
-
sending a first command to the plurality of storage devices instructing the snapshot of the data to be prepared, 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 and 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; 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 the new map data structure for each storage device initially being identified as a tentative map data structure; and sending a second command to the plurality of storage devices, the second command instructing the snapshot to be committed if a quorum of affirmative responses is received, but not necessarily a response from each of the plurality of storage devices being received, and the second command instructing the snapshot to be aborted if the quorum of affirmative responses is not received. - View Dependent Claims (28, 29, 30)
-
-
37. 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 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; 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 for the volume; taking one or more additional snapshots by repeating said steps of forming and committing for each additional snapshot, each snapshot being completed upon being committed and the snapshots being linked such that each snapshot is linked to a next most-recent snapshot, and performing writes to data blocks of the volume while taking the one or more additional snapshots by writing a data block to a new physical location and updating the map identified as the current map at the time of the write with a physical address of the data block being written, wherein each committed snapshot only contains values corresponding to the physical addresses of the data blocks of the volume that were written to while the map data structure for the snapshot was identified as the current map.
-
Specification