Block allocation based on server utilization

Patent metadata

Field	Value
Publication number	US-9794331-B1
Application number	US-201414500435-A
Country	US
Kind code	B1
Filing date	Sep 29, 2014
Priority date	Sep 29, 2014
Publication date	Oct 17, 2017
Grant date	Oct 17, 2017

Abstract

A computing resource service provider may operate a data storage service configured to provide data storage for one or more customers of the computing resource service provider. The data storage service may store customer data in one or more replicated state machines, where the replicated state machines comprise a plurality of replicated state machines-shards. The replicated state machines-shards may cause the computer system hosting the replicated state machine-shard to transmit a consensus message to other computer system. The consensus message may include utilization information corresponding to the other computer system. The utilization information may be used to calculate a utilization rate for the replicated state machine useable in block allocation operations.

First claim

What is claimed is:

1. A system, comprising:
a set of computing devices including at least a first computing device and a second computing device that:
generates a consensus message in accordance with a consensus protocol to establish a state of a replicated state machine across a set of replicated state machine-shards corresponding to the replicated state machine by at least:
determining state information of the replicated state machine to provide to the set of replicated state machine-shards; and
obtaining resource utilization information from the first computing device, the first computing device participating in the replicated state machine;

determines the second computing device is hosting a replicated state machine-shard of the set of replicated state machine-shards;
provides the second computing device with the generated consensus message based at least in part on the determination; and
calculates a utilization rate of the replicated state machine based at least in part on the obtained resource utilization information contained in the consensus message.

2. The system of claim 1 , wherein calculating the utilization rate of the replicated state machine further include calculating the utilization rate based at least in part on a history of the replicated state machine, the history comprising resource utilization information obtained from at least one previous consensus message.

3. The system of claim 1 , wherein the system further determines a set of utilization rates corresponding to a set of replicated state machines based at least in part on resource utilization information obtained from a set of consensus messages provided by at least a subset of the set of computing devices.

4. The system of claim 3 , wherein the system further:
provides the determined set of utilization rates to a customer; and
receives, from the customer, a selection of a particular replicated state machine of the set of replicated state machines, the selection causing the particular replicated state machine to indicate allocation of a block to the customer.

5. The system of claim 1 , wherein the system is further calculates another utilization rate based at least in part on another consensus message received from another computing device.

6. The system of claim 1 , wherein the replicated state machine stores information about a block storage device.

7. The system of claim 6 , wherein the information indicates block allocations of the block storage device.

8. A computer-implemented method, comprising:
generating a consensus message in accordance with a consensus protocol to establish a state of a replicated state machine across a set of replicated state machine-shards corresponding to the replicated state machine by at least:
determining state information of the replicated state machine to provide to the set of replicated state machine-shards; and
obtaining resource utilization information from a first computing device, the first computing device participating in the replicated state machine;

determining the second computing device is hosting a replicated state machine-shard of the set of replicated state machine-shards;
providing the second computing device with the generated consensus message based at least in part on the determination to cause the second computing device to calculate a utilization rate of the replicated state machine based at least in part on the obtained resource utilization information contained in the consensus message.

9. The computer-implemented method of claim 8 , wherein calculating the utilization rate of the replicated state machine further include calculating the utilization rate based at least in part on a history of the replicated state machine, where the history comprising resource utilization information obtained from at least one previous consensus message.

10. The computer-implemented method of claim 8 , further comprising determining a set of utilization rates corresponding to a set of replicated state machines based at least in part on resource utilization information obtained from a set of consensus messages provided by at least a subset of a set of computing devices that replicate at least respective portions of the replicated state machine.

11. The computer-implemented method of claim 10 , further comprising:
providing the determined set of utilization rates to a customer; and
receiving, from the customer, a selection of a particular replicated state machine of the set of replicated state machines, the selection causing the particular replicated state machine to indicate allocation of a block to the customer.

12. The computer-implemented method of claim 8 , further comprising calculating another utilization rate based at least in part on another consensus message received from another computing device.

13. The computer-implemented method of claim 8 , wherein the replicated state machine stores information about a block storage device.

14. The computer-implemented method of claim 13 , wherein the information indicates block allocations of the block storage device.

15. A non-transitory computer-readable storage medium having stored thereon instructions that, if executed by one or more processors of a first computing device, cause the first computing device to:
generate a consensus message in accordance with a consensus protocol to establish a state of a replicated state machine across a set of replicated state machine-shards corresponding to the replicated state machine by at least:
determining state information of the replicated state machine to provide to the set of replicated state machine-shards; and
obtaining resource utilization information from the first computing device, the first computing device participating in the replicated state machine;

determine the second computing device is hosting a replicated state machine-shard of the set of replicated state machine-shards;
provide the second computing device with the generated consensus message based at least in part on the determination to cause the second computing device to calculate a utilization rate of the replicated state machine based at least in part on the obtained resource utilization information contained in the consensus message.

16. The non-transitory computer-readable storage medium of claim 15 , wherein calculating the utilization rate of the replicated state machine further include calculating the utilization rate based at least in part on a history of the replicated state machine, where the history comprises resource utilization information obtained from at least one previous consensus message.

17. The non-transitory computer-readable storage medium of claim 15 , wherein the instructions further cause the first computing device to determine a set of utilization rates corresponding to a set of replicated state machines based at least in part on resource utilization information obtained from a set of consensus messages provided by at least a subset of the set of computing devices.

18. The non-transitory computer-readable storage medium of claim 17 , wherein the instructions further cause the first computing device to:
provide the determined set of utilization rates to a customer; and
receive, from the customer, a selection of a particular replicated state machine of the set of replicated state machines, the selection causing the particular replicated state machine indicate allocation of a block to the customer.

19. The non-transitory computer-readable storage medium of claim 15 , wherein the replicated state machine stores

Assignees

• Amazon Tech Inc

Inventors

• Frasca Michael Robert
• Frigo Matteo
• Strauss Jacob A

Classifications

• H04L67/1095

  Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes · CPC title

• H04L43/0876

  Network utilisation, e.g. volume of load or congestion level · CPC title

• H04L67/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] · CPC title

• H04L67/1008 Primary

  based on parameters of servers, e.g. available memory or workload (monitoring of computer activity G06F11/30) · CPC title

• G06F16/27

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title