SYSTEM AND METHOD FOR PROVIDING HIGH AVAILABILITY DATA

• US 20160110110A1
• Filed: 12/28/2015
• Published: 04/21/2016
• 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.
• Granted Patent: US 11,288,002 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 computer-implemented data storage system comprising:

host mapping logic configured to map responsibility for storing a plurality of data sets to individual ones of a plurality of hosts which cooperate to implement a data storage system;

data set replication logic configured to write a first plurality of copies of a data set at a first subset of the plurality of hosts, the first subset of the plurality of hosts being selected to write the data set;

data set retrieval logic configured to be responsive to a request to provide a single copy of the data set by reading a second plurality of copies of the data set at a second subset of the plurality of hosts, the second subset of the plurality of hosts having at least one host not in common with the first subset of the plurality of hosts; and

an evaluation component configured to provide a single copy of the data set by reading the second plurality of copies of the data set and reconciling the read data using data versioning information;

wherein the evaluation component is configured to be invoked after the second plurality of copies of the data set is read.

2. The system of claim 1, wherein the host mapping logic is further configured to generate a hash value based on a hash function.

3. The system of claim 1, wherein the data versioning information includes version histories stored in association with each of the second plurality of copies of the data set.

4. The method of claim 3, wherein the version histories each comprise a respective vector clock.

5. The method of claim 4, wherein the version histories each comprise a respective hash history.

6. A computer-implemented data processing method comprising:

writing a first plurality of copies of a data set at a first plurality of hosts, including writing a version history for each of the first plurality of copies of the data set;

responding to a request to provide a single copy of the data set by reading a second plurality of copies of the data set at a second plurality of hosts, including reading a version history for each of the second plurality of copies of the data set, the second plurality of hosts having at least one host not in common with the first plurality of hosts;

reconciling the second plurality of copies of the data set using versioning information; and

providing a single copy of the data set from the reconciled second plurality of copies of the data set.

7. The method of claim 6, wherein the version histories for the first plurality of copies of the data set and for the second plurality of copies of the data set each comprise a respective hash history.

8. The method of claim 6, wherein the version histories for the first plurality of copies of the data set and for the second plurality of copies of the data set each comprise a respective vector clock.

9. The method of claim 8, wherein the vector clocks each comprise a counter that encodes causality information for a data set including a summary of preceding changes.

10. The method of claim 9, wherein the vector clocks each comprise a host identifier that identifies a host that coordinated a write operation.

11. The method of claim 6, wherein the version histories each comprise a vector clock, and wherein the method further comprises generating the vector clock written for each of the first plurality of copies of the data set, including copying a prior version of the vector clock associated with a prior version of the data set and incrementing a counter of the vector clock.

12. The method of claim 11, wherein the vector clocks each comprise a plurality of counters, each of the plurality of counters being associated with different hosts that have written prior versions of the data set.

13. The method of claim 12, wherein reconciling the second plurality of copies of the data set comprises comparing the vector clocks and determining that two of the plurality of copies of the data set are causally related based on one vector clock having less than-or-equal counters for all of the nodes in the other vector clock.

14. The method of claim 12 further comprising truncating the vector clocks.

15. The method of claim 14, wherein truncating the vector clocks includes truncating counters associated with hosts that have not performed a write operation for greater than a predetermined period of time.

16. The method of claim 6, wherein the writing is performed in accordance with a preference list.

17. The method of claim 16, wherein the preference list is generated based on a hash function that maps the data set to the first plurality of hosts based on a data element associated with the data set.

18. The method of claim 17, further comprising generating a hash value based on a hash key and the hash function, the hash key being associated with the data set and being applied as input to the hash function.

19. The method of claim 18, wherein the hash function has a hash range comprising a range of output values for the hash function, the hash value being within the hash range, the data set being one of a plurality of data sets.

20. The method of claim 19, wherein the hash function maps responsibility for storing the plurality of data sets to individual ones of a third plurality of hosts which cooperate to implement a data storage system, the first and second pluralities of hosts being subsets of the third plurality of hosts.

21-42. -42. (canceled)