Data replication framework

• US 8,554,762 B1
• Filed: 12/28/2010
• Issued: 10/08/2013
• 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: Shivaprakash, Archit, Kuznetsova, Olga I., O'Neill, Brian S., Long, Jason Shijia
• Primary Examiner(s): Yen, Syling
• Application Number:
  US12/980,193
• Time in Patent Office: 1,015 Days
• Field of Search: 707/706, 707713-719, 707/721, 707/722, 707/736, 707/758, 707/782, 707999003-999006
• US Class Current: 707/715
• 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 method of dynamically routing requests of data across a plurality of hosts, the method comprising:

analyzing queries for data at a plurality of hosts, wherein individual hosts have a replicated copy of a data store;

determining frequency of queries for data among the plurality of hosts;

determining distribution of queries for data based on the determined frequency of queries for data among the plurality of hosts;

generating an insertion index for data requests based on the determined distribution of queries for data;

generating a list of dividers based on a count of the plurality of hosts, wherein the list of dividers is associated with a comparison key, and wherein the list is regenerated when the count of the plurality of hosts is changed; and

routing data requests based on the insertion index and the list of dividers wherein routing data requests includes;

determining a size of the insertion index and a size of the list of dividers;

comparing the size of the insertion index to the size of the list of dividers;

routing the request to a last host added to the plurality of hosts in response to determining that the size of the insertion index is the same as the size of the list of dividers;

comparing a request key associated with the data request to the comparison key in response to determining that the size of the insertion index is different than the size of the list of dividers;

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

2. The method of claim 1, wherein the queries for data comprise a data index.

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

4. The method of claim 1, wherein the distribution of queries comprises a histogram.

5. The method of claim 1, wherein the data requests are routed to at least one of the plurality of hosts.

6. The method of claim 1 further comprising regenerating the list of dividers at a predetermined frequency.

7. The method of claim 6, wherein the predetermined frequency is 1 second.

8. A computing system for dynamically routing requests of data across a plurality of hosts, the system comprising:

a plurality of hosts configured to receive queries for data, wherein individual hosts have a replicated copy of a data store;

a query analysis component configured to determine a distribution of the queries for data received based on a frequency of queries for data among the plurality of hosts; and

a router configured to route a data request to at least one of the plurality of hosts based on an insertion index of a request key and a list of dividers, wherein the list of dividers is associated with a comparison key and wherein the router routes a data request by;

determining a size of the insertion index and a size of the list of dividers;

comparing the size of the insertion index to the size of the list of dividers;

routing the request to a last host added to the plurality of hosts in response to determining that the size of the insertion index is the same as the size of the list of dividers;

comparing a request key associated with the request for data to the comparison key in response to determining that the size of the insertion index is different than the size of the list of dividers.

9. The computing system of claim 8, wherein the queries 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. The computing system of claim 8 wherein the router is further configured to regenerate the list of dividers periodically.

12. The computing system of claim 8, wherein the router is further configured to detect a change in a number of hosts and, upon detection, to regenerate the list of dividers.

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

analyzing queries for data at a plurality of hosts, wherein individual hosts have a replicated copy of a data store;

determining distribution of queries for data based on a frequency of queries of data among the plurality of hosts; and

routing requests for data based on an insertion index of a request key and a list of dividers, wherein the list of dividers is associated with a comparison key and wherein routing requests includes;

determining a size of the insertion index and a size of the list of dividers;

comparing the size of the insertion index to the size of the list of dividers;

routing the request to a last host added to the plurality of hosts in response to determining that the size of the insertion index is the same as the size of the list of dividers;

comparing a request key associated with the request for data to the comparison key in response to determining that the size of the insertion index is different than the size of the list of dividers;

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

14. The method of claim 13, wherein the queries for data comprise a data index.

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

16. The method of claim 13, wherein the distribution of queries comprises a histogram.

17. The method of claim 13, wherein the requests are routed to at least one of the plurality of hosts.

18. The method of claim 13 further comprising updating the list of dividers at a predetermined frequency.

19. The method of claim 13 further comprising generating keys for data requests based on the determined distribution of queries for data.