Block allocation based on server utilization

Patent metadata

Field	Value
Publication number	US-10469571-B2
Application number	US-201715783857-A
Country	US
Kind code	B2
Filing date	Oct 13, 2017
Priority date	Sep 29, 2014
Publication date	Nov 5, 2019
Grant date	Nov 5, 2019

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 machine-shards. The replicated state machine-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 usable in block allocation operations.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
determining a state change of a replicated state machine comprising a set of shards;
generating a consensus message to enable the set of shards to establish a current state of the replicated state machine based at least in part on the state change;
inserting, into the consensus message, message utilization information associated with a first computer system of one or more computer systems participating in the replicated state machine;
providing the consensus message to a second computer system of the one or more computer systems participating in the replicated state machine; and
in response to receiving the consensus message, causing the second computer system to obtain, from the consensus message, utilization information determine a utilization rate for the first computer system based at least in part on the utilization information.

2. The computer-implemented method of claim 1 , wherein the computer-implemented method further includes causing the second computer system to calculate a utilization rate of the replicated state machine based at least in part on additional utilization information obtained from additional consensus messages received from at least one other computer system of the one or more computer systems.

3. The computer-implemented method of claim 2 , wherein the computer-implemented method further includes causing the second computer system to allocate a block of the replicated state machine to a customer based at least in part on the utilization rate of the replicated state machine.

4. The computer-implemented method of claim 2 , wherein the second computer system causes the calculated utilization rate to decay at a rate over an interval of time.

5. The computer-implemented method of claim 1 , wherein the computer-implemented method further includes:
obtaining a request from a customer to al locate a block to the customer;
determining a set of utilization rates associated with a set of replicated state machines of which the replicated state machine is a member; and
selecting a particular replicated state machine of the set of replicated state machines based at least in part on a particular utilization rate of the set of utilization rates associated with the particular replicated state machine.

6. The computer-implemented method of claim 5 , wherein the computer-implemented method further includes transmitting a response to the customer indicating the block has been allocated to the particular replicated state machine.

7. The computer-implemented method of claim 6 , wherein the computer-implemented method further includes:
allocating the block to the customer as a result of selecting the particular replicated state machine; and
generating another consensus message including utilization information associated with resource utilization of the computer system as a result of allocating the block to the customer.

8. A system, comprising:
one or more processors; and
memory that stores computer-executable instructions that, upon execution by the one or more processors, cause the system to:
generate a first consensus message to enable a set of shards to establish a current state of a replicated state machine based at least in part on a state change of the system;
determine first utilization information associated with the system to include in the first consensus message;
provide the first consensus message, including the utilization information, to at least one other system participating in the replicated state machine;
obtain second utilization information from a second consensus message from a second system hosting a shard of the set of shards; and
determine a utilization rate for the shard based at least in part on the second utilization information.

9. The system of claim 8 , wherein the utilization information is selected from disk input output rate, disk bandwidth, disk capacity, network bandwidth, network capacity, processor capacity, processor utilization, memory capacity, and memory utilization of the system.

10. The system of claim 8 , wherein the system implements a second shard of the set of shards and the second shard is a member of the replicated state machine.

11. The system of claim 8 , wherein the memory further includes computer executable instructions that, upon execution, cause the one or more processors to obtain third utilization information from a third consensus message obtained from a third system hosting a third shard of the set of shards.

12. The system of claim 11 , wherein the memory further includes computer executable instructions that, upon execution, cause the one or more processors to:
obtain a request to allocate a block of the system;
determine a utilization rate for the replicated state machine based at least in part on the first utilization information, the second utilization information, and the third utilization information; and
select the system based at least in part on the utilization rate for the replicated state machine.

13. The system of claim 12 , wherein the memory further includes computer executable instructions that, upon execution, cause the one or more processors to:
allocate the block in response to the request; and
generate a third consensus message as a result of allocating the block, where the third consensus message includes updated resource utilization information of the system as a result of allocating the block.

14. A non-transitory computer-readable storage medium storing thereon executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to at least:
determine a state change of a replicated state machine, the replicated state machine including a set of shards of which the computer system is a member;
generate a consensus message to indicating a current state of the replicated state machine based at least in part on the state change;
insert, into the consensus message, message utilization information of the computer system; and
provide the consensus message to a second computer system participating in the replicated state machine and executing at least one shard of the set of shards, the consensus message, upon receipt by the second computer system, causing the second computer system to obtain, from the consensus message, the utilization information to determine a utilization rate for the computer system based at least in part on the utilization information.

15. The non-transitory computer-readable storage medium of claim 14 , wherein the instructions further comprise instructions that, upon execution by the one or more processors, cause the computer system to receive a second consensus message from the second computer systems, the second consensus message including second utilization information.

16. The non-transitory computer-readable storage medium of claim 15 , wherein the instructions further comprise instructions that, upon execution by the one or more processors, cause the computer system to determine to allocate a block of data to the replicated state machine such that allocation of the block of data causes the computer system to minimize a maximum utilization rate of set of shards based at least in part on the second utilization information.

17. The non-transitory computer-readable storage medium of claim 15 , wherein the instructions further comprise instructions that, upon execution by the one or more processors, cause the computer system to calculate a utilization rate based at least in part on the second utilization.

Assignees

• Amazon Tech Inc

Inventors

• Frasca Michael Robert
• Frigo Matteo
• Strauss Jacob A

Classifications

• H04L43/0876

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

• H04L67/1008 Primary

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

• H04L67/1095

  Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes · 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

• G06F16/27

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