Snapshot lineage preservation for representation-based partitions

• US 10,452,453 B1
• Filed: 02/22/2018
• Issued: 10/22/2019
• Est. Priority Date: 02/22/2018
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Kumar, Sandeep, Singh, Ankit, Verma, Varun
• Primary Examiner(s): Bui, Jonathan A
• Application Number:
  US15/902,950
• Time in Patent Office: 607 Days
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 2201/81 Threshold
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0674 Disk device
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources

Abstract

A router of a block-level data storage service receives a request to generate a snapshot of a block device. The router, based on routing metadata for the block-level data storage service, identifies active metadata that indicates a first cell that may maintain the block device and alternate metadata that indicates a second cell that may maintain the block device. Based on a first state of the block device in the first cell, a second state of the block device in the second cell, and a predetermined set of rules defining operations corresponding to outcomes associated with the first state and the second state, the router determines which of the first cell and the second cell authoritatively maintains the block device. The router transmits the request to the appropriate cell in accordance with the predetermined set of rules.

Claims

1. A computer-implemented method, comprising:

determining, based at least in part on a request to generate a snapshot of a block device, routing metadata comprising first metadata and second metadata, the first metadata corresponding to a first cell corresponding to a first set of hosts that store data content of the block device and the second metadata corresponding to a second cell corresponding to a second set of hosts that store the data content of the block device;

transmitting a second request to the first set of hosts and to the second set of hosts to cause the first set of hosts to generate a first response and to cause the second set of hosts to generate a second response, the first response corresponding to a first state of the block device and the second response corresponding to a second state of the block device;

determining, based at least in part on the first state, the second state, and a predetermined set of rules defining operations corresponding to a plurality of outcomes associated with the first state and the second state whereby the plurality of outcomes corresponds to preservation of a lineage of snapshots for block devices in the first set of hosts and the second set of hosts, a set of the operations, wherein the set of operations are performable to identify a cell, from the first cell and the second cell, corresponding to a set of hosts, from the first set of hosts and the second set of hosts, that store the data content of the block device;

performing a subset of the set of the operations to identify the cell, wherein the subset of the set of the operations corresponds to at least one outcome from the plurality of outcomes;

causing the set of hosts to generate the snapshot of the block device in the cell; and

updating the first state and the second state based at least in part on an outcome of generating the snapshot.

2. The computer-implemented method of claim 1, wherein:

the first state corresponds to the data content of the block device being stored in the set of hosts of the cell;

the second state corresponds to the data content of the block device being migrated from the second cell to the set of hosts of the cell; and

the at least one outcome is that the data content of the block device is stored in the set of hosts of the cell.

3. The computer-implemented method of claim 1, wherein:

the first state corresponds to the data content of the block device being absent from the set of hosts of the cell;

the second state corresponds to the data content of the block device being stored in the second set of hosts of the second cell in a pre-create migrated state, the pre-create migrated state corresponding to the block device being unavailable to generation of snapshots of the block device to prevent generation of corrupt snapshots of the block device; and

the at least one outcome is that the request to generate the snapshot is to be transmitted to the set of hosts of the cell.

4. The computer-implemented method of claim 1, wherein:

the first state corresponds to the data content of the block device being stored in the set of hosts of the cell;

the second state corresponds to the data content of the block device being absent from the second set of hosts of the second cell; and

the at least one outcome is that the data content of the block device is stored in the set of hosts of the cell.

5. A system, comprising:

one or more processors; and

memory that stores computer-executable instructions that, as a result of being executed, cause the system to;

determine, based at least in part on meta data corresponding to a resource, a first location of the resource and a second location of the resource, the first location and the second location being distinct;

determine a first state of the resource in the first location and a second state of the resource in the second location;

identify, based at least in part on the first state, the second state, and a predetermined set of rules defining operations corresponding to a plurality of outcomes associated with the first state and the second state whereby the plurality of outcomes corresponds to preservation of a lineage of snapshots for resources in the first location and the second location, an authoritative location of the resource; and

transmit a request to a set of hosts of the authoritative location of the resource to perform, using the resource, an operation.

6. The system of claim 5, wherein the computer-executable instructions that, as a result of being executed, cause the system to determine the first state of the resource in the first location and the second state of the resource in the second location further cause the one or more processors to transmit a request to a first set of hosts of the first location and to a second set of hosts of the second location to cause the first set of hosts to generate a first response and to cause the second set of hosts to generate a second response, the first response corresponding to the first state and the second response corresponding to the second state of the resource.

7. The system of claim 6, wherein:

the first response is a first tuple comprising a first set of Boolean values corresponding to the first state; and

the second response is a second tuple comprising a second set of Boolean values corresponding to the second state.

8. The system of claim 5, wherein:

the first state of the resource in the first location corresponds to the resource being migrated from the first location to the second location;

the second state of the resource in the second location corresponds to the resource being located in the second location; and

the authoritative location is the second location.

9. The system of claim 5, wherein:

the first state of the resource in the first location corresponds to the resource being located in the first location in a pre-create migrated state, whereby the resource being in the pre-create migrated state results in the resource being unavailable to prevent generation of corrupt snapshots of the resource;

the second state of the resource in the second location corresponds to the resource being located in the second location; and

the authoritative location is the second location.

10. The system of claim 5, wherein the operation includes generating a snapshot of the resource in the authoritative location.

11. The system of claim 5, wherein:

the first state of the resource in the first location corresponds to the resource being located in the first location;

the second state of the resource in the second location corresponds to the resource being absent from the second location; and

the authoritative location is the first location.

12. The system of claim 5, wherein:

the first location is a first cell corresponding to a first set of hosts that store data content of the resource; and

the second location is a second cell corresponding to a second set of hosts that store the data content of the resource.

13. A non-transitory computer-readable storage medium having stored storing thereon executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to at least:

determine, based at least in part on a request to perform an operation on a resource, a first location of the resource and a second location of the resource;

process responses from the first location and the second location to determine a first state of the resource and a second state of the resource;

determine, based at least in part on the first state, the second state, and a predetermined set of rules defining operations corresponding to a plurality of outcomes associated with the first state and the second state whereby the plurality of outcomes corresponds to preservation of a lineage of snapshots for resources in the first location and the second location, if the resource is stored in the first location or in the second location, resulting in a determination; and

perform a set of operations in accordance with the determination.

14. The non-transitory computer-readable storage medium of claim 13, wherein the responses from the first location and the second location comprise a set of tuples, whereby the set of tuples include at least:

a first tuple comprising a first set of Boolean values corresponding to the first state; and

a second tuple comprising a second set of Boolean values corresponding to the second state.

15. The non-transitory computer-readable storage medium of claim 13, wherein the instructions that cause the computer system to determine the first location of the resource and the second location of the resource, further cause the computer system to identify routing metadata comprising first metadata and second metadata, the first metadata corresponding to the first location and the second metadata corresponding to the second location.

16. The non-transitory computer-readable storage medium of claim 13, wherein:

the first state corresponds to the resource being absent from the first location;

the second state corresponds to the resource being migrated from the second location to the first location;

the determination is that second responses are to be obtained from the first location and the second location to determine a new first state of the resource and a new second state of the resource; and

the instructions that cause the computer system to perform the set of operations in accordance with the determination further cause the computer system to transmit a second request to the first location and to the second location to obtain the new first state of the resource and the new second state of the resource.

17. The non-transitory computer-readable storage medium of claim 13, wherein:

the first state corresponds to the resource being located in the first location;

the second state corresponds to the resource being located in the second location;

the determination is that metadata of the resource within a location is to indicate that the resource is full; and

the instructions that cause the computer system to perform the set of operations in accordance with the determination further cause the computer system to;

select the location from the first location and the second location; and

cause metadata of the resource within the location to indicate that the resource is full.

18. The non-transitory computer-readable storage medium of claim 13, wherein the instructions that cause the computer system to determine the first location of the resource and the second location of the resource further cause the computer system to:

identify a first merit attribute value of the first location;

identify a second merit attribute value of the second location, whereby the second merit attribute value is greater than the first merit attribute value;

transmit a first request to the first location to identify the first state, the first request specifying creation of the resource in the first location in a pre-create migrated state if the resource is absent from the first location, the pre-create migrated state corresponding to the resource being in a pre-create migrated state, whereby the resource being in the pre-create migrated state results in the resource being unavailable to prevent generation of corrupt snapshots of the resource; and

transmit a second request to the second location to identify the second state.

19. The non-transitory computer-readable storage medium of claim 13, wherein:

the first state corresponds to the resource being absent from the first location;

the second state corresponds to the resource being located in the second location;

the determination is that the second location is to be utilized for processing of requests associated with the resource; and

the instructions that cause the computer system to perform the set of operations in accordance with the determination further cause the computer system to transmit the request to perform the operation on the resource to the second location.

20. The non-transitory computer-readable storage medium of claim 13, wherein:

the first state corresponds to the resource being migrated from the first location to the second location;

the second state corresponds to the resource being migrated from the second location to the first location;

the determination is that second responses are to be obtained from the first location and the second location to determine a new first state of the resource and a new second state of the resource; and

the instructions that cause the computer system to perform the set of operations in accordance with the determination further cause the computer system to transmit a second request to the first location and to the second location to obtain the new first state of the resource and the new second state of the resource.