Block allocation based on server utilization

• US 10,469,571 B2
• Filed: 10/13/2017
• Issued: 11/05/2019
• Est. Priority Date: 09/29/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Frasca, Michael Robert, Frigo, Matteo, Strauss, Jacob A.
• Primary Examiner(s): Won, Michael
• Application Number:
  US15/783,857
• Publication Number:
  US 20180041572A1
• Time in Patent Office: 753 Days
• Field of Search: 709223, 709248
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• 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 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/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]

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.

Claims

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.

18. The non-transitory computer-readable storage medium of claim 17, wherein the instructions the cause the computer system to calculate the utilization rate further comprise instructions that, upon execution by the one or more processors, cause the computer system to calculate the utilization rate by at least multiplying a disk capacity of the second computer system by a first constant and multiplying a network bandwidth of the second computer system by a second constant, where the first constant and the second constant are included in the second utilization information and selected such that the utilization rate is skewed toward the disk capacity or the network bandwidth.

19. The non-transitory computer-readable storage medium of claim 17, wherein the instructions that cause the computer system to calculate the utilization rate further include instructions that cause the computer system to calculate the utilization rate based at least in part on the message and a set of previously obtained messages including resource utilization information of the other computer system.

20. 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 query one or more other computer systems executing at least one shard of the set of shard to determine the replicated state machine has sufficient capacity to allocate a block of data.