System and method for providing high availability data

• US 11,288,002 B2
• Filed: 12/28/2015
• Issued: 03/29/2022
• Est. Priority Date: 03/31/2006
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Vosshall, Peter Sven, Decandia, Giuseppe, Hastorun, Deniz, Lakshman, Avinash, Pilchin, Alex, Rosero, Ivan D.
• Primary Examiner(s): Thomas, Ashish
• Assistant Examiner(s): Ohba, Mellissa M.
• Application Number:
  US14/981,370
• Publication Number:
  US 20160110110A1
• Time in Patent Office: 2,283 Days
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

A computer-implemented data processing system and method writes a first plurality of copies of a data set at a first plurality of hosts and reads a second plurality of copies of the data set at a second plurality of hosts. The first and second pluralities of copies may be overlapping and the first and second pluralities of hosts may be overlapping. A hashing function may be used to select the first and second pluralities of hosts. Version histories for each of the first copies of the data set may also be written at the first plurality of hosts and read at the second plurality of hosts. The version histories for the second copies of the data set may be compared and causal between the second copies of the data set may be evaluated based on the version histories for the second copies of the data set.

Claims

1. A system, comprising:

a distributed data store comprising a plurality of computing devices comprising respective hardware processors and memory and configured to implement a plurality storage hosts that store a plurality of data sets for the distributed data store, wherein individual ones of the storage hosts are assigned to a plurality of different hash value ranges of a set of hash values mapped to different ones of the data sets;

the distributed data store, configured to;

receive an access request over a network for one of the data sets stored in the distributed data store from a client of the distributed data store, wherein the access request identifies a key associated with the data set, wherein the access request is a request to perform a write operation to modify data in the data set;

generate a hash value for the data set based, at least in part, on the identified key according to a hash function for identifying storage hosts that store versions of the data sets;

identify a first storage host of the storage hosts that stores a first version of the data set to service the access request that is assigned to a first hash value range of the hash value ranges that includes the hash value for the data set;

from a second hash value range of the hash value ranges that is determined to be successive to the first hash value range in an order for selecting hosts from the hash value ranges, select a second storage host of the storage hosts that stores a second version of the data set, wherein the second storage host is assigned to the second hash value range;

direct the access request to the data set to be performed at both the first storage host and the second storage host before returning a response for the access request over the network to the client; and

wherein the selection of the second storage host of the storage hosts that stores the second version of the data set is performed as part of an identification of a number of storage hosts including the second storage host such that the write operation is successfully completed in satisfaction of a write quorum requirement before returning the response.

2. The system of claim 1, wherein a number of hash value ranges assigned to one of the storage hosts is different than another number of hash value ranges assigned to another one of the storage hosts.

3. The system of claim 1, wherein to select the second storage host of the storage hosts that stores the second version of the data set, the distributed data store is configured to exclude from consideration those hash value ranges successive to the first hash value range that are also assigned to the first storage host.

4. The system of claim 1, wherein the distributed system is further configured to:

receive an access request for another one of the data sets stored in the distributed data store, wherein the access request identifies another key associated with the other data set;

generate another hash value for the other data set based, at least in part, on the identified other key according to the hash function for identifying storage hosts that store versions of the data sets;

identify the first storage host that stores a first version of the other data set to service the access request, wherein the first storage host is assigned to a third hash value range of the hash value ranges that includes the other hash value for the other data set, wherein the third hash value range is different than the first hash value range;

from fourth hash value range that is successive to the third hash value range, select a third storage host of the storage hosts that stores a second version of the other data set, wherein the third storage host is assigned to the fourth hash value range, wherein the third storage host is different than the second storage host; and

perform the access request to the other data set at the first storage host and the third storage hosts.

5. The system of claim 4, wherein the access request for another one of the data sets is a request to perform a read operation to read data in the other one of the data sets, and wherein the selection of the third storage host of the storage hosts that stores the second version of the other one of the data sets is performed as part of an identification of a number of storage hosts including the third storage host such that the read operation is successfully completed in satisfaction of a read quorum requirement before returning a response to the access request for another one of the data sets.

6. A method, comprising:

performing, by a plurality of computing devices;

maintaining plurality of data sets at a plurality of storage hosts implemented as part of a distributed data store, wherein individual ones of the storage hosts are assigned to a plurality of different hash value ranges of a set of hash values mapped to different ones of the data sets;

receiving an access request for one of the data sets stored in the distributed data store from a client of the distributed data store over a network, wherein the access request identifies a key associated with the data set, wherein the access request is a request to perform a write operation to modify data in the data set;

generating a hash value for the data set based, at least in part, on the identified key according to a hash function for identifying storage hosts that store versions of the data sets;

identifying a first storage host of the storage hosts that stores a version of the data set to service the access request that is assigned to a first hash value range of the hash value ranges that includes the hash value for the data set;

from a second hash value range of the hash value ranges that is determined to be successive to the first hash value range in an order for selecting hosts from the hash value ranges, selecting a second storage host of the storage hosts that stores a second version of the data set, wherein the second storage host is assigned to the second hash value range;

directing the access request to the data set to be performed at both the first storage host and the second storage host before returning a response for the access request to the client over the network; and

wherein the selection of the second storage host of the storage hosts that stores the second version of the data set is performed as part of an identification of a number of storage hosts including the second storage host such that the write operation is successfully completed in satisfaction of a write quorum requirement before returning the response.

7. The method of claim 6, wherein a number of hash value ranges assigned to one of the storage hosts is different than another number of hash value ranges assigned to another one of the storage hosts.

8. The method of claim 6, wherein said selecting the second storage host of the storage hosts that stores the second version of the data set comprises excluding from consideration those successive hash value ranges assigned to the initial storage host.

9. The method of claim 6, further comprising:

receiving an access request for another one of the data sets stored in the distributed data store, wherein the access request identifies another key associated with the other data set;

generating another hash value for the other data set based, at least in part, on the identified other key according to the hash function for identifying storage hosts that store versions of the data sets;

identifying the first storage host that stores a first version of the other data set to service the access request that is assigned to a third hash value range of the hash value ranges that includes the other hash value for the other data set, wherein the

of the other data set, wherein the third storage host is different than the second storage host; and

performing the access request to the other data set at the first storage host and the third storage host.

10. The method of claim 9, wherein the access request for another one of the data sets is a request to perform a read operation to read data in the other one of the data sets, and wherein said selecting of the third storage host of the storage hosts that stores the second version of the other one of the data sets is performed as part of an identification of a number of storage hosts including the third storage host such that the read operation is successfully completed in satisfaction of a read quorum requirement before returning a response to the access request for another one of the data sets.

11. The method of claim 6, wherein the different hash value ranges are assigned to the storage hosts according to respective preference lists of storage hosts for accessing the data sets.

12. A non-transitory, computer-readable storage medium, storing program instructions that when executed by a plurality of computing devices cause the plurality of computing devices to implement:

maintaining plurality of data sets at a plurality of storage hosts implemented as part of a distributed data store, wherein individual ones of the storage hosts are assigned to a plurality of different hash value ranges of a set of hash values mapped to different ones of the data sets;

receiving an access request for one of the data sets stored in the distributed data store from a client of the distributed data store over a network, wherein the access request identifies a key associated with the data set, wherein the access request is a request to perform a write operation to modify data in the data set;

generating a hash value for the data set based, at least in part, on the identified key according to a hash function for identifying storage hosts that store versions of the data sets;

identifying a first storage host of the storage hosts that stores a first version of the data set to service the access request that is assigned to a first hash value range of the hash value ranges that includes the hash value for the data set;

from a second hash value range of the hash value ranges that is determined to be successive to the first hash value range in an order for selecting hosts from the hash value ranges, selecting a second storage host of the storage hosts that stores a second version of the data set, wherein the second storage host is assigned to the second hash value range;

directing the access request to the data set to be performed at both the first storage host and the second storage host before returning a response for the access request to the client over the network; and

wherein the selection of the second storage host of the storage hosts that stores the second version of the data set is performed as part of an identification of a number of storage hosts including the second storage host such that the write operation is successfully completed in satisfaction of a write quorum requirement before returning the response.

13. The non-transitory, computer-readable storage medium of claim 12, further comprising additional program instructions to assign a different number of hash value ranges to one of the storage hosts than another number of hash value ranges assigned to another one of the storage hosts.

14. The non-transitory, computer-readable storage medium of claim 12, wherein, in said selecting the second storage host of the storage hosts that stores the second version of the data set, the program instructions cause the plurality of computing devices to implement excluding from consideration those successive hash value ranges assigned to the initial storage host.

15. The non-transitory, computer-readable storage medium of claim 12, further comprising additional program instructions that cause the plurality of computing devices to further implement:

receiving an access request for another one of the data sets stored in the distributed data store, wherein the access request identifies another key associated with the other data set;

generating another hash value for the other data set based, at least in part, on the identified other key according to the hash function for identifying storage hosts that store versions of the data sets;

identifying the first storage host that stores a first version of the other data set to service the access request that is assigned to a third hash value range of the hash value ranges that includes the other hash value for the other data set, wherein the of the other data set, wherein the third storage host is different than the second storage host; and

performing the access request to the other data set at the first storage host and the third storage host.

16. The non-transitory, computer-readable storage medium of claim 15, wherein the access request for another one of the data sets is a request to perform a read operation to read data in the other one of the data sets, and wherein said selecting of the third storage host of the storage hosts that stores the second version of the other one of the data sets is performed as part of an identification of a number of storage hosts including the third storage host such that the read operation is successfully completed in satisfaction of a read quorum requirement before returning a response to the access request for another one of the data sets.

17. The non-transitory, computer-readable storage medium of claim 12, storing additional program instructions to assign the different hash value ranges to the storage hosts according to respective preference lists of storage hosts for accessing the data sets.