# US 2006/0155946 A1 · Method for taking snapshots of data

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2006/0155946 A1
- Document ID: US20060155946A1
- Status: Published application
- Kind: A1
- Application number: 11/033,343
- Filed: 2005-01-10
- Published: 2006-07-13
- Earliest claimed: 2005-01-10
- Assignees: Hewlett-Packard Development Company, L.P.
- Inventors: Minwen Ji
- Web page: https://patentgrep.com/patent/US20060155946A1

## CPC

- G06F 3/065: {Replication mechanisms}
- G06F 3/0617: {in relation to availability}
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/0689: {Disk arrays, e.g. RAID, JBOD}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 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.

### Claim 5 (depends on 4)

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.

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 4)

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.

### Claim 8 (depends on 7)

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

### Claim 9 (depends on 4)

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.

### Claim 10 (depends on 9)

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

### Claim 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.

### Claim 12 (depends on 11)

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.

### Claim 13 (depends on 12)

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.

### Claim 14 (depends on 11)

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.

### Claim 15 (depends on 11)

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

### Claim 16 (depends on 11)

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

### Claim 17 (depends on 11)

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.

### Claim 18 (depends on 11)

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.

### Claim 19 (depends on 18)

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

### Claim 20 (depends on 19)

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.

### Claim 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.

### Claim 22 (depends on 21)

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.

### Claim 23 (depends on 22)

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.

### Claim 24 (depends on 21)

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.

### Claim 25 (depends on 21)

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

### Claim 26 (depends on 21)

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

### Claim 27 (depends on 21)

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.

### Claim 28 (depends on 21)

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.

### Claim 29 (depends on 28)

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.

### Claim 30 (depends on 28)

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.

### Claim 31 (depends on 28)

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.

### Claim 32 (depends on 28)

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.

### Claim 33 (depends on 32)

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.

### Claim 34 (depends on 32)

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.

### Claim 35 (depends on 34)

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.

### Claim 36 (depends on 35)

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.

### Claim 37 (depends on 21)

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.

### Claim 38 (depends on 21)

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.

### Claim 39 (depends on 37)

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

### Claim 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.
