System and method for providing high availability data

• US 20070282915A1
• Filed: 08/22/2006
• Published: 12/06/2007
• 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 S., Sivasubramanian, Swaminathan, deCandia, Giuseppe, Hastorun, Deniz, Lakshman, Avinash, Pilchin, Alex, Rosero, Ivan D.
• Granted Patent: US 7,925,624 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/219 Managing data history or versioning querying versioned data G06F16/2474; querying temporal data G06F16/2477
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2455 Query execution
• 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 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064

Abstract

An embodiment relates to a computer-implemented data processing system and method for storing a data set at a plurality of data centers. The data centers and hosts within the data centers may, for example, be organized according to a multi-tiered ring arrangement. A hashing arrangement may be used to implement the ring arrangement to select the data centers and hosts where the writing and reading of the data sets occurs. Version histories may also be written and read at the hosts and may be used to evaluate causal relationships between the data sets after the reading occurs.

Claims

1. A computer-implemented data storage system comprising:

mapping logic configured to map responsibility for storing a plurality of data sets to a plurality of data centers and to a plurality of hosts within the plurality of data centers;

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 within a first subset of the plurality of data centers, the data set being one of the plurality of data sets;

data set retrieval logic configured to read a second plurality of copies of the data set at a second subset of the plurality of hosts within a second subset of the plurality of data centers; and

data set comparison logic configured to evaluate causal relationships between the second copies of the data set.

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

3. The system of claim 2, 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.

4. The system of claim 3, wherein each of the plurality of data centers has multiple positions within the hash range, such that the individual data centers have responsibility for storing subsets of the plurality of data sets within multiple different portions of the hash range.

5. The system of claim 4, wherein each of the data centers has multiple positions within the hash range, such that the individual data centers have responsibility for storing subsets of the plurality of data sets within multiple different portions of the hash range.

6. The system of claim 4, wherein the hash value is a first hash value, wherein the hash function is a first hash function, wherein the hash range is a first hash range, and wherein the mapping logic comprises logic configured to generate a second hash value based on a second hash function.

7. The system of claim 6, wherein each of the data centers has multiple positions within the second hash range, such that the individual data centers have responsibility for storing subsets of the plurality of data sets within multiple different portions of the second hash range.

8. The system of claim 1, further comprising lease logic configured to update other copies of the data set after expiration of a data lease.

9. The system of claim 1, further comprising message filters respectively associated with each of the data centers and configured to modulate network traffic between the data centers.

10. The system of claim 1, wherein the data set retrieval logic is configured to pre-fetch the second copies of the data set.

11. The system of claim 1, wherein the data set comparison logic is configured to evaluate the causal relationships based on version histories stored in association with each of the second copies of the data set.

12. The system of claim 11, wherein the version histories comprise respective hash histories.

13. The system of claim 11, wherein the version histories comprise respective vector clocks.

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

15. The system of claim 1, wherein the first subset of the plurality of data centers and the second subset of the plurality of data centers are the same, and wherein the first subset of the plurality of hosts and the second subset of the plurality of hosts are the same.

16. A computer-implemented data processing method comprising:

generating a hash value based on a hash key and a hash function, the hash key being associated with a data set and being applied as input to the hash function;

writing a first plurality of copies of the data set at a first subset of a plurality of data centers, including writing a version history for each of the first copies of the data set, the first subset of the plurality of data centers being selected to write the data set based on the hash value;

reading a second plurality of copies of the data set at a second subset of the plurality of data centers, including reading a version history for each of the second copies of the data set;

comparing the version histories of each of the second copies of the data set; and

evaluating causal relationships between the second copies of the data set based on the version histories of each of the second copies of the data set.

17. The method of claim 16, 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.

18. The method of claim 17, wherein each of the data centers has multiple positions within the hash range, such that each of the data centers has responsibility for storing subsets of the plurality of data sets within multiple different portions of the hash range.

19. The method of claim 16, wherein the first subset of the plurality of data centers and the second subset of the plurality of data centers are the same, and wherein the first subset of the plurality of hosts and the second subset of the plurality of hosts are the same.

20. The method of claim 16, wherein the second subset of the plurality of data centers has at least one data center not in common with the first subset of the plurality of data centers.

21. The method of claim 20, wherein the writing is performed in accordance with a preference list, the preference list providing a ranking of data centers at which copies of the data set are to be stored.

22. The method of claim 21, further comprising migrating one of the copies of the data set from a first data center to a second data center after the second data center becomes available, the second data center being higher on the preference list than the first data center, the second data center on the preference list being the data center not in common with the first plurality of data centers.

23. The method of claim 22, wherein the preference list ranks data centers in a third plurality of data centers which cooperate to implement a data storage system, the first and second pluralities of data centers being subsets of the third plurality of data centers.

24. The method of claim 23, further comprising dynamically migrating more recent copies of the data set to data centers that rank higher on the preference list, causing eventual consistency of the data set at a set of data centers at the top of the preference list.

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

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

27. A computer-implemented data processing method comprising:

mapping responsibility for storing a plurality of data sets at a plurality of a data centers;

storing copies of a data set at a subset of the plurality of data centers, including writing a version history for each of the copies of the data set; and

evaluating causal relationships between copies of the data set based on the version histories for the second copies of the data set.

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

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

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

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

32. The method of claim 31, wherein the preference list is generated based on a hash function.

33. The method of claim 32, 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.

34. The method of claim 33, wherein the hash fuiction has a hash range comprising a range of output values for the hash function, the hash value being within the hash range.

35. The method of claim 34, wherein the hash function maps the responsibility for storing the plurality of data sets to the plurality of data centers.

36. The method of claim 35, wherein the subset of the plurality of data centers are selected to store the data set based on the hash value and based on whether other data centers are unavailable.

37. The method of claim 36, wherein each of the data centers has multiple positions within the hash range, such that the individual data centers have responsibility for storing subsets of the plurality of data sets within multiple different portions of the hash range.

38. The system of claim 37, wherein the hash value is a first hash value, wherein the hash function is a first hash function, wherein the hash range is a first hash range, and wherein the mapping logic comprises logic configured to generate a second hash value based on a second hash function.

39. The system of claim 38, wherein each of the plurality of data centers comprises a plurality of hosts, wherein each of the plurality of hosts has multiple positions within the second hash range, such that the individual hosts have responsibility for storing subsets of the plurality of data sets within multiple different portions of the second hash range.

40. The method of claim 27, wherein the storing is performed in accordance with a preference list, the preference list providing a ranking of data centers at which copies of the data set are to be stored.

41. The method of claim 37, further comprising migrating one of the copies of the data set from a first data center to a second data center after the second data center becomes available, the second data center being higher on the preference list than the first data center.

42. The method of claim 27, wherein the plurality of data centers implement a network services system accessible to users by way of a network.

43. The method of claim 42, wherein the network services system provides a website accessible to the users.

44. The method of claim 43, wherein the website is a merchant website.

45. The method of claim 44, wherein the data set comprises shopping cart data for a shopping cart for one of the users.

46. The method of claim 27, wherein evaluating causal relationships between the second copies of the data set comprises determining that the second copies of the data set comprise conflicting copies.

47. The method of claim 46, further comprising providing the conflicting copies of the data set to a client process for reconciliation.

48. A computer accessible medium whose contents direct a computing system to:

generate a hash value based on a hash key and a hash function, the hash key being associated with a data set and being applied as input to the hash function;

store copies of a data set at a plurality of data centers, the plurality of data centers being selected based on the hash value; and

evaluate causal relationships between copies of the data set retrieved from different ones of the plurality of data centers.

49. A computer accessible medium whose contents direct a computing system to:

generate a hash value based on a hash key and a hash function, the hash key being associated with a data set and being applied as input to the hash function, the hash function having 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, the hash function mapping responsibility for storing the plurality of data sets to a plurality of data centers;

generate a version history for the data set including causality information describing which data centers are associated with particular previous versions of the data set;

store first copies of the data set and the version history at a first subset of the plurality of data centers responsive to a write request, the first subset of the plurality of data centers being selected to store the data set based on the hash value;

read second copies of the data set at a second subset of the plurality of data centers responsive to a read request, including reading a version history for each of the second copies of the data set, the second subset of the plurality of data centers having at least one data center not in common with the first subset of the plurality of data centers;

compare the version histories of each of the second copies of the data set; and

evaluate causal relationships between the second copies of the data set based on the version histories of each of the second copies of the data set.

50. The computer accessible medium of claim 49, wherein the version histories each comprise a vector clock, and wherein the contents further direct the computing system to generate the vector clock written for each of the first copies of the data set, including copy a prior version of the vector clock associated with a prior version of the data set and increment a counter of the vector clock.

51. The computer accessible medium of claim 50, wherein the vector clocks each comprise a plurality of counters, each of the plurality of counters being associated with different data centers that have written prior versions of the data set.

52. The computer accessible medium of claim 51 wherein, to evaluate the causal relationships, the vector clocks are compared and two of the copies of the data set are determined to be causally related if one vector clock has less than-or-equal counters for all of the nodes in the other clock.

53. The computer accessible medium of claim 49, wherein the writing is performed in accordance with a preference list.

54. The computer accessible medium of claim 49, wherein the preference list is generated based on the hash.

55. A computer-implemented data processing method comprising:

mapping responsibility for storing a plurality of data sets at a plurality of a data centers using first and second hash functions, the first hash function mapping responsibility for storing the plurality of data sets at selected ones of the plurality of data centers, and the second hash function mapping responsibility for storing the plurality of data sets at selected ones of a plurality of hosts within the selected data centers;

storing copies of a data set at a subset of the plurality of data centers, including writing a version history for each of the copies of the data set; and

evaluating causal relationships between copies of the data set based on the version histories for the second copies of the data set.