Storage device selection for database partition replicas

• US 9,053,167 B1
• Filed: 06/19/2013
• Issued: 06/09/2015
• Est. Priority Date: 06/19/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Swift, Bjorn Patrick, Xiao, Wei, Marshall, Stuart Henry Seelye, Stefani, Stefano, Rath, Timothy Andrew, Lutz, David Alan
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US13/922,001
• Time in Patent Office: 720 Days
• Field of Search: 707600-899
• 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 storage nodes. The selection of the storage nodes (or storage devices thereof) on which to store the partition replicas may be performed by administrative components that are responsible for partition management and resource allocation for respective groups of storage nodes (e.g., based on a global view of resource capacity or usage), or the selection of particular storage devices of a storage node may be determined by the storage node itself (e.g., based on a local view of resource capacity or usage). Placement policies applied at the administrative layer or storage layer may be based on the percentage or amount of provisioned, reserved, or available storage or IOPS capacity on each storage device, and particular placements (or subsequent operations to move partition replicas) may result in an overall resource utilization that is well balanced.

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 one or more partitions, and wherein to maintain the data in the one or more partitions, the distributed database service is configured to store two or more replicas of each of the one or more partitions on respective storage devices or logical storage volumes of respective ones of the plurality of storage nodes;

wherein an administrative component of the distributed database service is configured to;

store metadata about each of the plurality of storage nodes, wherein the metadata about each storage node comprises an indication of an amount of provisioned throughput capacity or an amount of available throughput capacity for the storage node;

determine that a given one of the plurality of storage nodes is a potential host for a particular partition replica; and

in response to said determining, initiate storage of the particular partition replica on the given storage node;

wherein to determine that the given storage node is a potential host for a particular partition replica, the administrative component is configured to;

receive an indication from the given storage node that the given storage node has sufficient storage capacity to host the particular partition replica; and

determine that the given storage node is a potential host for a particular partition replica based, at least in part, on the received indication and the stored metadata.

2. The system of claim 1, wherein to determine that the given storage node is a potential host for a particular partition replica, the administrative component is further configured to:

send a message to the given storage node, wherein the message specifies an amount of storage capacity associated with the particular partition replica; and

receive a reply message from the given storage node indicating that the given storage node is able to host the particular partition replica.

3. The system of claim 2, wherein the message comprises an indication of a current amount of throughput capacity required for the particular partition replica or a projected amount of throughput capacity for the particular partition replica.

4. The system of claim 2, wherein the message comprises an indication of a current amount of storage capacity required for the particular partition replica or a projected amount of storage capacity for the particular partition replica.

5. The system of claim 2,

wherein the message comprises a reservation request specifying a request to reserve sufficient resource capacity to store the particular partition replica on the given storage node;

and

wherein the reply message comprises an acknowledgement that the requested resource capacity has been reserved for the particular partition replica by the given storage node.

6. A method, comprising:

performing by one or more computers;

storing metadata about one or more storage nodes of a distributed data storage system, wherein the distributed data storage system stores data in one or more partitions on respective storage devices or logical storage volumes of the one or more storage nodes, and wherein the metadata about each storage node comprises an indication of an amount of provisioned throughput capacity or an amount of available throughput capacity for the storage node;

determining that a given one of the one or more storage nodes is a potential host for a particular partition; and

in response to said determining, initiate storage of the particular partition on the given storage node;

wherein said determining comprises receiving an indication from the given storage node that the given storage node has sufficient storage capacity to host the particular partition; and

wherein said determining is based, at least in part, on the received indication and the stored metadata.

7. The method of claim 6, wherein said determining further comprises sending a message to the given storage node indicating an intent to store the particular partition on the storage node, wherein the message comprises an indication of a current amount of storage capacity required by the particular partition replica or a projected amount of storage capacity for the particular partition replica.

8. The method of claim 7, wherein said determining further comprises receiving a reply message from the given storage node, wherein the reply message comprises an identifier of a storage device or logical storage volume having sufficient storage capacity to host the particular partition.

9. The method of claim 6, further comprising, prior to said determining:

querying each of the one or more storage nodes to obtain resource capacity information or resource usage information for the storage node;

receiving resource capacity information or resource usage information from each of the one or more storage nodes; and

storing the resource capacity information or resource usage information received from each of the one or more storage nodes as the metadata about the one or more storage nodes.

10. The method of claim 6, wherein the metadata about each storage node further comprises an indication of an amount or percentage of provisioned storage capacity, an amount or percentage of reserved storage capacity, or an amount or percentage of available storage capacity on the storage node.

11. The method of claim 6, wherein the metadata about each storage node further comprises heat information for the storage node or an indication of bursting activity on the storage node.

12. The method of claim 6, wherein the metadata about each storage node comprises an indication of an amount or percentage of provisioned throughput capacity, an amount or percentage of reserved throughput capacity, an amount or percentage of available throughput capacity, an amount or percentage of provisioned storage capacity, an amount or percentage of reserved storage capacity, or an amount or percentage of available storage capacity for each of a plurality of storage devices or logical storage volumes on the storage node.

13. The method of claim 6,

wherein the method further comprises generating a multi-dimensional representation of resource capacity or resource usage for at least some of the one or more storage nodes based, as least in part, on the stored metadata;

and

wherein said determining is based, at least in part, on the multi-dimensional representation.

14. The method of claim 13,

wherein the multi-dimensional representation comprises an indication of a target resource utilization;

and

wherein said determining comprises determining that storing the particular partition on the given storage node will move a representation of a storage device or logical storage volume of the given storage node in the multi-dimensional representation closer to the indication of the target resource utilization.

15. The method of claim 6, wherein said determining further comprises, prior to said receiving:

selecting a set of storage nodes at random, wherein the randomly selected set of storage nodes comprises the given storage node;

determining that storage nodes in a subset of the randomly selected set of storage nodes have sufficient available throughput capacity for hosting the particular partition, wherein the subset comprises the given storage node; and

querying the given storage node to determine whether the given storage node has sufficient storage capacity to host the particular partition.

16. The method of claim 6, wherein said determining is performed in response to receiving a request to store the particular partition, and wherein the request to store the particular partition is part of an operation to create a table, an operation to divide a table into two or more partitions, an operation to replicate a partition, an operation to move a partition, an operation to split a partition, or an operation to move resource utilization in the distributed data storage system toward a target resource utilization.

17. 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, by a given one of a plurality of storage nodes of a distributed data storage system that has sufficient available throughput capacity for hosting a particular data partition, a request to reserve resource capacity for hosting the particular data partition, wherein the request comprises an indication of a current amount of storage capacity required by the particular partition or a projected amount of storage capacity for the particular partition, and wherein the distributed data storage system stores data in one or more partitions on respective storage devices or logical storage volumes on respective ones of the plurality of storage nodes; and

determining, by the given storage node, that a storage device or logical storage volume of the given storage node has sufficient available storage capacity for hosting the particular data partition;

reserving, by the given storage node, the storage device or logical storage volume for hosting the particular data partition; and

returning, by the given storage node, an acknowledgement that resource capacity has been reserved for hosting the particular data partition;

wherein said determining is based, at least in part, on the indication in the request and on resource related metadata for one or more storage devices or logical storage volumes of the given storage node that is stored locally on the given storage node.

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

wherein the resource related metadata that is stored locally on the given storage node comprises metadata indicating which, if any, of the one or more storage devices or logical storage volumes have available storage capacity falling within each of a plurality of available storage capacity ranges;

and

wherein said determining comprises determining that the storage device or logical volume has an amount of available storage capacity within highest storage capacity range.

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

wherein the request to reserve resource capacity for hosting the particular data partition is received from the administrative component of the distributed data storage system;

and

wherein said returning comprises returning the acknowledgement to the administrative component of the distributed data storage system.

20. The non-transitory, computer-readable storage medium of claim 17,

wherein the resource related metadata that is stored locally on the given storage node comprises metadata indicating the amount of available throughput capacity for the given storage node;

when executed on the one or more computers, the program instructions further cause the one or more computers to perform, prior to said receiving, sending the metadata indicating the amount of available throughput capacity for the given storage node to an administrative component of the distributed data storage system.