Data replication framework

• US 9,449,065 B1
• Filed: 12/28/2010
• Issued: 09/20/2016
• Est. Priority Date: 12/28/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: O'Neill, Brian S., Parakh, Vishal, Holgers, Tobias L., Shivaprakash, Archit
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Cheung, Hubert
• Application Number:
  US12/980,153
• Time in Patent Office: 2,093 Days
• Field of Search: 707/610
• US Class Current: 1/1
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation

Abstract

Generally described, the present disclosure is directed to an eventually consistent replicated data store that uses, for its underlying storage, a computer software library that provides a high-performance embedded database for data. The replicated data store employs a plurality of hosts interconnected to one another, allowing for writes to any host and full awareness of membership across all hosts. With the data replication framework disclosed herein, various modes are allowed to be built up on top of the core system.

Claims

1. A computing system for dynamic membership enabling data replication, the computing system comprising:

a plurality of hosts, wherein;

individual hosts include a data store and a member store, and

the plurality of hosts replicate data from a data store with at least one additional host of the plurality of hosts utilizing locally stored availability information;

a membership module configured to;

maintain availability information regarding availability of each of the plurality of hosts in a member store,

identify an unavailable host among the plurality of hosts,

attempt to reconnect with the unavailable host for a threshold period of time, and

update the availability information to indicate that the unavailable host is permanently unavailable based on unsuccessful subsequent attempts to connect to the unavailable host for the threshold period of time,

wherein one or more of the plurality of hosts indicated as available in the updated availability information ignore availability information received from the permanently unavailable host, wherein the availability information received from the permanently unavailable host relates to availability of one or more of the plurality of hosts, and

wherein the permanently unavailable host is enabled to receive the updated availability information from the one or more of the plurality of hosts indicated as available in the updated availability information;

a server registry configured to replicate the updated availability information from the membership module to the data store of individual hosts; and

a membership agent in communication with the member store,

wherein the server registry notifies the membership agent of host membership state changes, and

wherein the membership agent replicates a common version of the updated availability information to the plurality of hosts, and wherein individual ones of the plurality of hosts replicate data with another available host based on the common version of the updated availability information.

2. The computing system of claim 1, wherein a host membership state change comprises at least one of a change from an available state to an unavailable state or a change from an unavailable state to an available state.

3. The computing system of claim 1, wherein the availability state of individual hosts is accessible to a new host from any one of the plurality of hosts.

4. The computing system of claim 1, wherein the membership agent is configured to first attempt to reconnect with the unavailable host within one second.

5. The computing system of claim 1, wherein the membership agent is configured to attempt to reconnect with the unavailable host within increasingly longer subsequent time delays.

6. The computing system of claim 5, wherein the subsequent time delays increase up to two minutes.

7. A method for enabling data replication for a plurality of hosts, the method comprising:

maintaining, at a member store, availability information related to availability of a plurality of hosts;

monitoring availability states of the plurality of hosts;

replicating the availability information to a data store associated with individual hosts;

identifying an unavailable host among the plurality of hosts;

attempting to reconnect with the unavailable host for a threshold period of time;

updating the availability information to indicate that the unavailable host is permanently unavailable based on unsuccessful subsequent attempts to connect to the unavailable host for the threshold period of time,

wherein one or more of the plurality of hosts indicated as available in the updated availability information ignore availability information received from the permanently unavailable host, wherein the availability information received from the permanently unavailable host relates to availability of one or more of the plurality of hosts, and

wherein the permanently unavailable host is enabled to receive the updated availability information from the one or more of the plurality of hosts indicated as available in the updated availability information;

receiving an indication of host membership state change; and

replicating a common version of the updated availability information across the plurality of hosts, wherein an individual one of the plurality of hosts replicates data with another available host based on the common version of the updated availability information.

8. The method of claim 7, wherein individual hosts are assigned a unique member identity.

9. The method of claim 8, wherein the unique member identity is stored in the member store.

10. The method of claim 8, wherein the unique member identity of a permanently unavailable host is stored in the member store for one year.

11. The method of claim 10, wherein the permanently unavailable host is assigned a new unique member identity if the host becomes available.

12. The method of claim 7 further comprising replicating the common version of the updated availability information to the permanently unavailable host based on a successful attempt to reconnect with the permanently unavailable host.

13. A non-transitory computer-readable medium containing computer-executable instructions for enabling data replication among a plurality of hosts, the computer-executable instructions comprising instructions that, when executed by a processor, cause the processor to:

maintain, at a member store, availability information related to a plurality of hosts, wherein individual hosts of the plurality of hosts each comprise a data store, wherein the availability information comprises an availability state of individual hosts of the plurality of hosts;

monitor availability states of the plurality of hosts;

replicate the availability information to the data store of individual hosts;

identify an unavailable host among the plurality of hosts;

attempt to reconnect with the unavailable host;

attempt to reconnect with the unavailable host again with time delays after a first unsuccessful attempt;

update the availability information to indicate that the unavailable host is permanently unavailable based on unsuccessful attempts to connect to the unavailable host for a threshold period of time,

wherein one or more of the plurality of hosts indicated as available in the updated availability information ignore availability information received from the permanently unavailable host, wherein the availability information received from the permanently unavailable host relates to availability of one or more of the plurality of hosts, and

wherein the permanently unavailable host is enabled to receive the updated availability information from the one or more of the plurality of hosts indicated as available in the updated availability information;

receive an indication of host membership state change; and

replicate a common version of the updated availability information across member stores of the plurality of hosts, wherein an individual one of the plurality of hosts is configured to replicate data with another host based on the common version of the updated availability information.

14. The non-transitory computer-readable medium of claim 13, wherein the time delays are determined based on a previous time delay.

15. The non-transitory computer-readable medium of claim 14, wherein the time delays are multiples of a previous time delay.

16. The non-transitory computer-readable medium of claim 13, wherein the threshold period of time is 20 hours.

17. The non-transitory computer-readable medium of claim 13 wherein the instructions further cause the processor to declare the permanently unavailable host available based on a successful attempt to reconnect.

18. The non-transitory computer-readable medium of claim 17 wherein the instructions further cause the processor to replicate the common version of the updated availability information to the permanently unavailable host based on a successful attempt to reconnect with the permanently unavailable host.