US 9,053,167 B1Granted

Storage device selection for database partition replicas

AssigneeAmazon Technologies, Inc.

InventorsBjorn Patrick Swift, Wei Xiao, Stuart Henry Seelye Marshall, Stefano Stefani, Timothy Andrew Rath, David Alan Lutz

Life of this patent

Estimating the term…

patentgrep

Loading patent…

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.

Claims20

Dependent claims

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.

12 more elements

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.

5 more elements

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.

4 more elements

Dependencies are inferred from the claim text.