# US 2017/0286476 A1 · System and method for providing high availability data

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0286476 A1
- Document ID: US20170286476A1
- Status: Published application
- Kind: A1
- Application number: 15/620,638
- Filed: 2017-06-12
- Published: 2017-10-05
- Earliest claimed: 2006-03-31
- Assignees: Amazon Technologies, Inc.
- Applicants: Amazon Technologies, Inc.
- Inventors: Peter S. Vosshall; Swaminathan Sivasubramanian; Giuspeppe deCandia; Deniz Hastorun; Avinash Lakshman; Alex Pilchin; Ivan D. Rosero
- Web page: https://patentgrep.com/patent/US20170286476A1

## CPC

- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/219: {Managing data history or versioning (querying versioned data G06F16/2474; querying temporal data G06F16/2477)}
- G06F 16/2255: {Hash tables}
- G06F 16/2455: Query execution
- G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
- G06F 11/2097: {maintaining the standby controller/processing unit updated (initialisation or re-synchronisation thereof G06F11/1658 and subgroups)}
- G06F 2201/82: Solving problems relating to consistency
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 1

A computer-implemented data storage system comprising:
mapping logic executed by a processor operative to execute instructions stored in memory, the mapping logic configured to map responsibility for storing a plurality of data sets to a plurality of data centers, wherein the plurality of data centers include a plurality of hosts for maintaining parts of the data sets;
data set replication logic executed by a processor operative to execute instructions stored in memory, the 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;
data set retrieval logic executed by a processor operative to execute instructions stored in memory, the 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 executed by a processor operative to execute instructions stored in memory, the data set comparison logic configured to:
evaluate causal relationships between elements of the second plurality of copies of the data set to provide a single copy of the data set, the evaluation of causal relationships including at least an determination of causal relationships between elements in the second plurality of copies of the data set that are not causal ancestors of other elements in the second plurality of copies of the data set; and
cause reconciliation between at least two copies of the second plurality of copies, wherein respective elements of the at least two copies are determined not to be causal ancestors of one another.

### Claim 2 (depends on 1)

The computer-implemented data storage system of claim 1, wherein at least one member in the first subset of data centers and the second subset of data centers are different.

### Claim 3 (depends on 1)

The computer-implemented data storage system of claim 1, wherein the data set comparison logic is further configured to cause generation of the single copy of the data set based, at least in part, on the reconciliation between the at least two copies.

### Claim 4 (depends on 1)

The computer-implemented data storage system of claim 1, wherein the reconciliation is based at least in part on data versioning information.

### Claim 5 (depends on 1)

The computer-implemented data storage system of claim 1, wherein the reconciliation includes applying a default ordering on copies in the second plurality of copies of the data set.

### Claim 6 (depends on 5)

The computer-implemented data storage system of claim 5, wherein the default ordering includes partial ordering.

### Claim 7 (depends on 5)

The computer-implemented data storage system of claim 5, wherein the default ordering is based at least in part on changes identified in data versioning information.

### Claim 8 (depends on 1)

The computer-implemented data storage system of claim 1, wherein the reconciliation includes merging copies in the second plurality of copies.

### Claim 9 (depends on 8)

The computer-implemented data storage system of claim 8, wherein merging copies in the second plurality of copies of the data set is based at least in part on changes identified in data versioning information.

### Claim 10 (depends on 1)

The computer-implemented data storage system of claim 1, wherein the first subset of the first subset of the plurality of hosts within the plurality of data centers comprises a set of one or more hosts in the first subset of the plurality of hosts within each data center of the first subset of the plurality of data centers.

### Claim 11 (depends on 1)

The computer-implemented data storage system of claim 1, wherein reading a second plurality of copies of a data set at the second subset of the plurality of hosts within the first subset of the plurality of data centers includes reading data from a second ordered sequence of hosts.

### Claim 12

A computer-implemented method comprising:
obtaining a data set;
writing a first plurality of copies of the data set at a first plurality of hosts within a first subset of a plurality of data centers;
reading a second plurality of copies of the data set at a second plurality of hosts within a second subset of the plurality of data centers;
evaluating causal relationships between elements of the second plurality of copies of the data set, wherein evaluating causal relationships comprises at least determining causal relationships between elements in the second plurality of copies of the data set that are not causal ancestors of other elements in the second plurality of copies of the data set;
reconciling between at least two copies of the second plurality of copies, wherein the at least two copies comprise respective elements that are determined not to be causal ancestors of one another; and
determining a single copy of the data set from the second plurality of copies of the data set based, at least in part, on the reconciling between the at least two copies.

### Claim 13 (depends on 12)

The computer-implemented method of claim 12, wherein evaluating causal relationships is based at least in part on data versioning information.

### Claim 14 (depends on 12)

The computer-implemented method of claim 12, wherein evaluating causal relationships includes applying a default ordering on copies in the second plurality of copies of the data set.

### Claim 15 (depends on 12)

The computer-implemented method of claim 12, wherein determining a single copy of the data set includes merging copies in the second plurality of copies.

### Claim 16 (depends on 12)

The computer-implemented method of claim 12, wherein at least one member in the first subset of data centers and the second subset of data centers are different.

### Claim 17 (depends on 12)

The computer-implemented method of claim 12, wherein writing the first plurality of copies of the data set at the first plurality of hosts within the first subset of the plurality of data centers includes writing data to a first ordered sequence of hosts.

### Claim 18 (depends on 17)

The computer-implemented method of claim 17, wherein reading the second plurality of copies of a data set at the second plurality of hosts within the second subset of the plurality of data centers includes reading data from a second ordered sequence of hosts.

### Claim 19

A computer-readable medium containing computer-executable instructions, wherein the computer-executable instructions, when executed by a processor, cause the processor to:
read a plurality of copies of a data set at a plurality of hosts within a subset of a plurality of data centers;
evaluate causal relationships between elements of the plurality of copies of the data set, wherein evaluating causal relationships comprises at least evaluating causal relationships between elements in the second plurality of copies of the data set that are not causal ancestors of other elements in the plurality of copies of the data set; and
determine a single copy of the data set from the plurality of copies of the data set based on the evaluated causal relationships between the elements of the plurality of copies of the data set.

### Claim 20 (depends on 19)

The computer-readable medium of claim 19, wherein evaluating causal relationships further comprises applying partial ordering on copies in the plurality of copies of the data set.
