Scheduling of splits and moves of database partitions

• US 9,489,443 B1
• Filed: 05/24/2013
• Issued: 11/08/2016
• Est. Priority Date: 05/24/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Muniswamy-Reddy, Kiran-Kumar, Xiao, Wei, Stefani, Stefano, Huang, Xianglong, Ng, Clarence Wing Yin, Vasanth, Jai
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Tessema, Aida
• Application Number:
  US13/902,419
• Time in Patent Office: 1,264 Days
• Field of Search: None
• US Class Current: 1/1
• 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/278 Data partitioning, e.g. horizontal or vertical partitioning

Abstract

A system that implements a data storage service may store data in multiple replicated partitions on respective computing nodes on behalf of clients. A storage node may, based on the amount of provisioned resources on a given storage device or logical volume, identify candidate partition management operations to be performed, and may send information about the operations to a central partition management scheduler. The scheduler may apply a global prioritization scheme to determine an order in which to perform the candidate operations. The order may be based on whether the operations include partition splits or partition moves, whether they aim to reduce provisioned storage capacity or reduce throughput capacity on a storage device or logical volume, whether they conflict with each other, whether the total number of partitions (or replicas thereof) involved in partition management at any given time exceeds a pre-determined limit, or whether they were requested by clients.

Claims

1. A system, comprising:

one or more processors;

a memory coupled to the one or more processors; and

a plurality of storage nodes, each of which comprises one or more storage devices or logical storage volumes;

wherein the memory stores program instructions that when executed by the one or more processors cause the one or more processors to implement a distributed database service;

wherein the distributed database service maintains data in two or more partitions, and wherein to maintain the data in the two or more partitions, the distributed database service is configured to store two or more replicas of each of the two or more partitions on respective storage devices or logical storage volumes of respective ones of the plurality of storage nodes;

wherein multiple storage nodes of the plurality of storage nodes are configured to;

identify one or more candidate partition management operations to be performed on the storage node, wherein each of the candidate partition management operations comprises a split operation targeting a partition replica that is stored on a storage device or logical volume of the storage node or a move operation targeting one or more partition replicas that are stored on a storage device or logical volume of the storage node; and

send information about each of the one or more candidate partition management operations to a central partition management scheduler of the distributed database service, wherein for each of the candidate partition management operations, the information comprises an indication of whether the candidate partition management operation comprises a split operation or a move operation, an indication of a number of replicas to be affected by the candidate partition management operation, or an indication of an amount of a resource that is provisioned for replicas affected by the candidate partition management operation; and

wherein the central partition management scheduler of the distributed database service is configured to;

receive the information about the one or more candidate partition management operations from the multiple storage nodes; and

apply a global prioritization across the candidate partition management operations to be performed on the multiple storage nodes, wherein to apply the global prioritization the central partition management scheduler is configured to determine an order in which at least some of the candidate partition management operations across the multiple nodes are to be performed based, at least in part, on the received information.

2. The system of claim 1, wherein to determine an order, the central partition management scheduler is configured to prioritize candidate partition management operations for which the received information indicates that the operation comprises a split operation over any candidate partition management operations for which the received information indicates that the operation comprises a move operation.

3. The system of claim 1,

wherein for each of the candidate partition management operations for which the received information indicates that the operation comprises a move operation, the received information further indicates whether the one or more partition replicas are to be moved to reduce the amount of provisioned storage capacity on a storage device or logical volume of the storage node or to reduce an amount of provisioned throughput capacity on a storage device or logical volume of the storage node;

and

wherein to determine an order, the central partition management scheduler is configured to prioritize candidate partition management operations for which the received information indicates that the operation comprises a move operation to reduce the amount of provisioned storage capacity on a storage device or logical volume over any candidate partition management operations for which the received information indicates that the operation comprises a move operation to reduce an amount of provisioned throughput capacity on a storage device or logical volume.

4. The system of claim 1, wherein to identify the one or more candidate partition management operations, each of the multiple storage nodes is configured to:

determine one or more measurements of storage capacity utilization or throughput capacity utilization on the one or more storage devices or logical storage volumes of the storage node;

determine, based at least in part on the determined measurements, that one or more partition replicas should be moved from a given one of the storage devices or logical storage volumes to one or more different storage devices or logical storage volumes to reduce the storage capacity utilization or the throughput capacity utilization on the given one of the storage devices or logical storage volumes;

apply two or more algorithms to the one or more measurements to identify the one or more partition replicas that should be moved, each of which yields a respective partition management solution; and

identify one of the partition management solutions as a candidate partition management operation.

5. The system of claim 1,

wherein the central partition management scheduler is further configured to send a query to the each of the multiple storage nodes;

and

wherein at least one of identifying the one or more candidate partition management operations or sending information about each of the one or more candidate partition management operations is performed in response to the query.

6. A method, comprising:

performing by one or more computers;

obtaining, from a plurality of storage nodes of a distributed data storage system, information about each of a plurality of candidate partition management operations to be performed on the plurality of storage nodes of the distributed data storage system, wherein the distributed data storage system stores data in two or more partitions on respective storage devices or logical storage volumes of the plurality of storage nodes, and wherein for each of the candidate partition management operations, the information comprises an indication of a partition management operation type, wherein the partition management operation type specifies whether the candidate partition management operation comprises a split type operation or a move type operation;

applying a global prioritization across the plurality of candidate partition management operations to be performed on the plurality of storage nodes, wherein said applying the global prioritization comprises determining an order in which to perform the plurality of candidate partition management operations across the plurality of storage nodes based, at least in part, on the partition management operation types of the plurality of candidate partition management operations.

7. The method of claim 6, wherein said obtaining comprises receiving the information from the plurality of storage nodes.

8. The method of claim 6, wherein said obtaining comprises scanning a database table or data structure in which the information about each of the plurality of candidate partition management operations is stored.

9. The method of claim 6, wherein said determining comprises selecting a first candidate partition management operation to be performed based, at least in part, on the partition management operation type for the first candidate partition management operation.

10. The method of claim 9, wherein said determining further comprises:

determining that a pre-determined constraint limiting performance of additional partition management operations has not been met; and

in response to determining that the pre-determined constraint limiting performance of additional partition management operations has not been met, selecting a second candidate partition management operation to be performed while the first candidate partition management operation is in progress.

11. The method of claim 6, wherein said obtaining comprises:

receiving information indicating storage capacity utilization or throughput capacity utilization on one or more storage devices or logical storage volumes of each of the plurality of storage nodes; and

identifying a plurality of candidate partition management operations to be performed on the plurality of storage nodes based, at least in part, on the information indicating storage capacity utilization or throughput capacity utilization.

12. The method of claim 6, wherein said determining an order in which to perform the plurality of candidate partition management operations is based, at least in part, on a number of partitions affected by at least some of the plurality of candidate partition management operations.

13. The method of claim 6, wherein said determining an order in which to perform the plurality of candidate partition management operations is based, at least in part, on an amount of provisioned resources affected by at least some of the plurality of candidate partition management operations.

14. The method of claim 6, wherein said determining an order in which to perform the plurality of candidate partition management operations is based, at least in part, on determining that a given one of the plurality of candidate partition management operations does not conflict with any partition management operations that are in progress.

15. A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:

receiving, from a plurality of storage nodes, information about each of a plurality of candidate partition management operations to be performed on the plurality of storage nodes on which database partitions are stored on one or more storage devices or logical storage volumes based, at least in part, on the received information; and

applying a global prioritization across the plurality of candidate partition management operations to be performed on the plurality of storage nodes, wherein said applying the global prioritization comprises determining an order in which to perform at least some of the candidate partition management operations across the plurality of storage nodes based, at least on part, on a number of partitions affected by the at least some of the candidate partition management operations or on an amount of provisioned resources affected by at least some of the candidate partition management operations.

16. The non-transitory, computer-readable storage medium of claim 15, wherein said determining an order comprises identifying two or more of the plurality of candidate partition management operations that can be performed substantially concurrently.

17. The non-transitory, computer-readable storage medium of claim 15, wherein said determining an order comprises identifying two or more of the plurality of candidate partition management operations to be performed substantially concurrently, wherein the total number of partitions affected by the two or more candidate partition management operations is less than a pre-determined limit on the number of partitions that can be involved in partition management operations at any given time.

18. The non-transitory, computer-readable storage medium of claim 15,

wherein said identifying comprises storing information about each of the plurality of candidate partition management operations in a database table on one of the plurality of storage nodes;

and

wherein said determining an order comprises applying one or more global prioritization policies to the information about each of the plurality of candidate partition management operations in a database table.

19. The non-transitory, computer-readable storage medium of claim 15, wherein when executed on the one or more computers, the program instructions cause the one or more computers to perform, prior to said receiving, provisioning resource capacity for a database table, wherein said provisioning comprises dividing the provisioned resource capacity among two or more partitions of the database table.

20. The non-transitory, computer-readable storage medium of claim 15, wherein each of the plurality of candidate partition management operations comprises one or more partition moving or partition splitting operations that if performed would reduce a provisioned resource on one of the plurality of storage devices or logical storage volumes on which database partitions are stored by at least a pre-determined target amount.