Data replication framework

• US 9,734,199 B1
• Filed: 10/04/2013
• Issued: 08/15/2017
• 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., Kuznetsova, Olga I., Shivaprakash, Archit, Long, Jason Shijia
• Primary Examiner(s): Yen, Syling
• Application Number:
  US14/046,775
• Time in Patent Office: 1,411 Days
• Field of Search: 707706, 707713-719, 707721, 707722, 707736, 707758, 707782, 707999004-999006
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/2453 Query optimisation
• 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 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning

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 comprising:

a plurality of hosts comprising one or more computing devices, the plurality of hosts configured to receive queries for data, the plurality of hosts associated with an ordered list of available hosts from the plurality of hosts, the list comprising an index; and

a router configured to;

receive an individual request for data, wherein the individual request for data comprises a request key;

route the individual request for data to at least one of the available hosts based on a comparison between the request key and at least one divider key of a plurality of divider keys associated with a divider, wherein routing the individual request comprises;

determining that the request key is equal to the at least one divider key of the plurality of divider keys, wherein the request key and the at least one divider key each correspond to an index value in an ordered index; and

in response to determining that the request key is equal to the at least one divider key;

determine, based at least in part on the index value of the at least one divider key, a probability list of an ordered set of hosts associated with the divider, wherein a probability for individual hosts is defined based on a number of times the divider key is assigned to individual hosts and a number of times the divider key is assigned to the plurality of hosts, and

route the individual request to a host of the ordered subset of hosts based at least in part on the probability list of the ordered subset of hosts.

2. The computing system of claim 1, wherein the request key is configured to indicate a type of request.

3. The computing system of claim 1, wherein the individual request comprises a comparator configured to compare request keys.

4. The computing system of claim 1 further comprising a key store configured to generate the dividers.

5. The computing system of claim 4, wherein the key store is further configured to detect a change in a number of hosts and, upon detection, to regenerate the list of dividers.

6. The computing system of claim 4 wherein the router is further configured to route the request keys to the key store.

7. The computing system of claim 1, wherein the request key is generated based on a determined distribution of queries for data.

8. The computing system of claim 7, wherein the determined distribution of queries for data is based on an analysis of frequencies of queries for data across the plurality of hosts.

9. The computing system of claim 8, wherein the requests for data comprise a data index.

10. The computing system of claim 9, wherein the data index comprises at least one of a product identity index, a customer identity index and a review identity request.

11. A method of dynamically routing requests of data across a plurality of hosts, the method comprising:

receiving at least one request for data, the at least one request including a request key;

comparing the request key with keys associated with a list of dividers, wherein the request key and each of the keys associated with the list of dividers correspond to index values in an ordered index;

routing the at least one request for data to a host based on the comparison, wherein routing the at least one request for data includes;

determining whether the request key is less than or equal to at least one divider key of a plurality of divider keys of an individual divider, wherein the individual divider is associated with an ordered set of hosts;

in response to determining that the request key is less than the at least one divider key associated with the individual divider, routing the at least one request to a host ordered first in the ordered set of hosts; and

in response to determining that the request key is equal to the at least one divider key;

determining a probability list of the ordered set of hosts based at least in part on the index value of the at least one divider key associated with the individual divider, wherein a probability for individual hosts is defined based on a number of times the divider key is assigned to individual hosts and a number of times the divider key is assigned to the plurality of hosts; and

routing the at least one request to a host of the ordered set of hosts based at least in part on the probability list of the ordered set of hosts,

wherein the method is performed on a computing device comprising a hardware processor and memory.

12. The method of claim 11, wherein the request key is configured to indicate a type of request.

13. The method of claim 11 further comprising generating the dividers.

14. The method of claim 13 further comprising regenerating the dividers at a predetermined frequency.

15. The method of claim 13, wherein generating the dividers is based on a determined distribution of queries for data.

16. The method of claim 15, wherein the determined distribution of queries for data is based on an analysis of frequencies of queries for data across the plurality of hosts.

17. The method of claim 11, wherein the requests for data comprise a data index.

18. The method of claim 11, wherein the data index comprises at least one of a product identity index, a customer identity index and a review identity request.

19. A nontransitory computer-readable medium having computer-executable instructions stored thereon that, in response to execution by one or more processors of a computing device, cause the computing device to perform actions for dynamically routing requests of data across a plurality of hosts, the actions comprising:

receiving at least one request for data, the at least one request including a request key;

comparing the request key with at least one divider key of a plurality of divider keys associated with a list of dividers, wherein the request key and each of the key associated with the list of dividers correspond to index values in an ordered index;

routing the at least one request for data to a host based on the comparison, wherein routing the at least one request for data includes;

determining whether the request key is less than or equal to at least one divider key of an individual divider, wherein the individual divider is associated with an ordered set of hosts;

in response to determining that the request key is less than the at least one divider key associated with the individual divider, routing the at least one request to a host ordered first in the ordered set of hosts; and

in response to determining that the request key is equal to the at least one divider key associated with an individual divider;

determining a probability list of the ordered set of hosts based at least in part on the index value of the at least one divider key associated with the individual divider, wherein a probability for individual hosts is defined based on a number of times the divider key is assigned to individual hosts and a number of times the divider key is assigned to the plurality of hosts; and

routing the at least one request to a host of the ordered set of hosts based at least in part on the probability list of the ordered set of hosts.

20. The non-transitory computer-readable medium of claim 19 wherein the actions further comprise regenerating the dividers at a predetermined frequency.