System and method for providing high availability data

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, including at least a first part for identifying one or more data centers for storing the data set and a second part for identifying a location with in the identified data centers, the hash key 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 and on a predetermined location of the first subset of the plurality of data centers;
• obtaining a request to recall a copy of the data set;
• responsive to the request, 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;
• evaluating causal relationships between the second copies of the data set based on at least one of:
• applying a default ordering on copies in the second plurality of copies of the data set that are not causal ancestors of other copies in the second plurality of copies of the data set, wherein the default ordering is based at least in part on changes identified in the version histories;
• merging copies in the second plurality of copies of the data set that are not causal ancestors of other copies in the second plurality of copies of the data set based at least in part on changes identified in the version histories;
• and
• applying a reconciliation algorithm specific to inconsistencies among copies in the second plurality of copies of the data set that are not causal ancestors of other copies in the second plurality of copies of the data set based at least in part on changes identified in the version histories;
• and
• identifying the copy of the data set to recall based on the evaluated causal relationship between the second copies of the data set.

A non-transitory computer readable medium whose contents include computer-executable instruction which 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, on a predetermined location of the first subset of the plurality of data centers in accordance with an attributed low probability of failure independent to a plurality of data centers used in subsequent read requests;
• responsive to a request to provide a single copy of the data set, read second 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, 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, the evaluation of causal relationships including at least one of:
• applying a default ordering on copies in the second plurality of copies of the data set that are not causal ancestors of other copies in the second plurality of copies of the data set, wherein the default ordering is based at least in part on changes identified in the data versioning information;
• merging copies in the second plurality of copies of the data set that are not causal ancestors of other copies in the second plurality of copies of the data set based at least in part on changes identified in the data versioning information;
• and
• applying a reconciliation algorithm specific to inconsistencies among copies in the second plurality of copies of the data set that are not causal ancestors of other copies in the second plurality of copies of the data set based at least in part on changes identified in the data versioning information;
• wherein the first subset of the plurality of hosts for writing the data set and the second subset of the plurality of hosts for reading the data set are independently determined.

A computer-implemented data processing method comprising:

• mapping responsibility for storing a plurality of data sets at a plurality of data centers using first and second hash functions for a multi-part key corresponding to each data set, the first hash function mapping responsibility for storing the plurality of data sets at selected ones of the plurality of data centers and using a first part of the multi-part key as input, 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 and using a second part of the multi-part key as input;
• 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, the evaluation of causal relationships including at least one of:
• applying a default ordering on copies in the second plurality of copies of the data set that are not causal ancestors of other copies in the second plurality of copies of the data set, wherein the default ordering is based at least in part on changes identified in the data versioning information;
• merging copies in the second plurality of copies of the data set that are not causal ancestors of other copies in the second plurality of copies of the data set based at least in part on changes identified in the data versioning information;
• and
• applying a reconciliation algorithm specific to inconsistencies among copies in the second plurality of copies of the data set that are not causal ancestors of other copies in the second plurality of copies of the data set based at least in part on changes identified in the data versioning information.