Range query capacity allocation

• US 9,330,158 B1
• Filed: 05/20/2013
• Issued: 05/03/2016
• Est. Priority Date: 05/20/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Xiao, Wei, Filipe, Miguel Mascarenhas, Swift, Bjorn Patrick, Muniswamy-Reddy, Kiran-Kumar, Marshall, Stuart Henry Seelye, Rath, Timothy Andrew, Blackman, Rande A.
• Primary Examiner(s): Liu, Hexing
• Application Number:
  US13/898,201
• Time in Patent Office: 1,079 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

Distributed database management systems may perform range queries over the leading portion of a primary key. Non-random distribution of data may improve performance related to the processing of range queries, but may tend to cause workload to be concentrated on particular partitions. Groups of partitions may be expanded and collapsed based on detection of disproportionate workload. Disproportionate write workload may be distributed among a group of partitions that can subsequently be queried using a federated approach. Disproportionate read workload may be distributed among a group of read-only replicated partitions.

Claims

1. A storage and retrieval system comprising:

a first computing node comprising a first one or more storage devices, the first one or more storage devices configured to store thereon a first plurality of items corresponding to a first range of a table;

a second computing node comprising a second one or more storage devices, the second one or more storage devices configured to store thereon a second plurality of items corresponding to a second range of the table; and

one or more memories having stored thereon computer-readable instructions that, upon execution, cause the system at least to;

receive information indicative of a first amount of work performed by the first computing node, the first amount of work based at least in part on storing one or more of the first plurality of items corresponding to the first range on the first computing node;

receive information indicative of a second amount of work performed by the second computing node, the second amount of work based at least in part on storing one or more of the second plurality of items corresponding to the second range on the second computing node; and

configure the system, in response to determining that the first amount of work is greater than the second amount of work, to process a first subset of a plurality of requests to store items in the first range on the first computing node and a second subset of the plurality of requests to store items in the first range on a third computing node.

2. The system of claim 1, further comprising one or more memories having stored thereon computer-readable instructions that, upon execution, cause the system at least to:

determine to stop processing requests on the third computing node based at least in part on a third amount of work performed by the third computing node.

3. The system of claim 2, further comprising one or more memories having stored thereon computer-readable instructions that, upon execution, cause the system at least to:

replicate the item by storing a version of the item on the first computing node.

4. The system of claim 1, further comprising one or more memories having stored thereon computer-readable instructions that, upon execution, cause the system at least to:

receive a second request to retrieve a subset of the first plurality of items corresponding to the first range; and

form a result by combining a first one or more items of the subset of the first plurality of items stored on the first computing node with a second one or more items of the subset of the first plurality of items stored on the third computing node, the result corresponding to the second request.

5. The system of claim 1, further comprising one or more memories having stored thereon computer-readable instructions that, upon execution, cause the system at least to:

selecting, based at least in part on one of random selection or round-robin selection, the third computing node for processing a request of the plurality of requests to store items in the first range.

6. A computer-implemented method for storing and retrieving data, the method comprising:

receiving, by a computer, information indicative of a first amount of work performed by a first computing node, the first amount of work based at least in part on storing a first plurality of items on the first computing node, the plurality of items corresponding to a first range of a table;

receiving, by the computer, information indicative of a second amount of work performed on one or more additional computing nodes, the amount of work based at least in part on storing a second plurality of items corresponding to a second range of the table on the one or more additional computing nodes; and

determining to process at least a first request to add an item to the first range of the table by storing the item on a third computing node instead of the first computing node, the determining based at least in part on the first amount of work being greater than the second amount of work.

7. The method of claim 6, further comprising:

determining to stop processing requests on the third computing node, based at least in part on a third amount of work performed by the third computing node.

8. The method of claim 7, further comprising:

replicating the item by storing a version of the item on the first computing node.

9. The method of claim 6, further comprising:

receiving a second request to retrieve a subset of the first plurality of items; and

forming a result by combining a first one or more items stored on the first computing node with a second one or more items stored on the third computing node, the result corresponding to the request to retrieve the subset of the first plurality of items.

10. The method of claim 6, further comprising:

determining to store the item on the third computing node based at least in part on a metadata catalog.

11. The method of claim 6, further comprising:

selecting the third computing node to store the item, the selecting based at least in part on one of random selection or round-robin selection.

12. The method of claim 6, further comprising determining to retrieve the item from the third computing node based at least in part on information indicative of a probability of the third computing node containing the item.

13. The method of claim 6, wherein the first range corresponds to one of time, numerical order, alphabetical order, or ordinal position.

14. The method of claim 6, wherein the determining is based at least in part on a version of the first item being stored on the first computing node.

15. A non-transitory computer-readable storage medium having stored thereon instructions that, upon execution by a computing device, cause the computing device at least to:

receive information indicative of a first amount of work performed by a first computing node, the first amount of work based at least in part on storing a first plurality of items on the first computing node, the plurality of items corresponding to a first range of a table;

receive information indicative of a second amount of work performed on one or more additional computing nodes, the amount of work based at least in part on storing a second plurality of items corresponding to a second range of the table on the one or more additional computing nodes; and

determine, based at least in part on the first amount of work being greater than the second amount of work, to process at least a first request to add an item to the first range of the table by storing the item on a third computing node.

16. The computer-readable medium of claim 15, having stored thereon further instructions that, upon execution by the computing device, cause the computing device at least to:

determine to stop processing requests on the third computing node, based at least in part on a third amount of work performed by the third computing node.

17. The computer-readable medium of claim 15, having stored thereon further instructions that, upon execution by the computing device, cause the computing device at least to:

cause the item to be replicated on the first computing node.

18. The computer-readable medium of claim 15, having stored thereon further instructions that, upon execution by the computing device, cause the computing device at least to:

add an entry corresponding to the third computing node to a metadata catalog.

19. The computer-readable medium of claim 15, wherein the information indicative of the first amount of work is based at least in part on a forecasted amount of work.

20. The computer-readable medium of claim 15, wherein the information indicative of the first amount of work and the information indicative of the second amount of work correspond to an essentially equivalent period of time.