BLOCK ALLOCATION BASED ON SERVER UTILIZATION

• US 20180041572A1
• Filed: 10/13/2017
• Published: 02/08/2018
• 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.
• Granted Patent: US 10,469,571 B2
• Time in Patent Office: Days
• 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 utilization information associated with a computer system of one or more computer systems participating in the replicated state machine; and

providing the consensus message to another computer system of the one or more computer systems participating in the replicated state machine.

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

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

4. The computer-implemented method of claim 2, wherein the other 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:

receiving a request from a customer to allocate 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 non-transitory computer-readable storage medium having stored 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:

receive a message from another computer system, the message including resource utilization information of the other computer system;

receive a request to allocate a block of data; and

allocate the block of data by at least;

determining a set of replicated state machines capable of allocating the block of data;

calculating a utilization rate for at least a subset of the set of replicated state machines based at least in part on resource utilization information included in the message; and

determining a particular replicated state machine of the set of replicated state machines based at least in part on the calculated utilization rates.

9. The non-transitory computer-readable storage medium of claim 8, wherein the instructions that cause the computer system to calculate the utilization rate for at least the subset of the set of replicated state machines further include instructions that cause the computer system to determine the set of replicated state machines based at least in part on one or more replicated state machines hosted by the computer system.

10. The non-transitory computer-readable storage medium of claim 8, wherein the instructions that cause the computer system to determine the particular replicated state machine further include instructions that cause the computer system to determine the particular replicated state machine such that allocation of the block causes the computer system to minimize a maximum utilization rate of the utilization rates of the set of replicated state machines.

11. The non-transitory computer-readable storage medium of claim 8, wherein the instructions that cause the computer system to calculate the utilization rate for at least the subset of the set of replicated state machines further include instructions that cause the computer system to calculate the utilization rate by at least multiplying a disk capacity of the other computer system by a first constant and multiplying a network bandwidth of the other computer system by a second constant, where the first constant and the second constant are selected such that the utilization rate is skewed toward the disk capacity or the network bandwidth.

12. The non-transitory computer-readable storage medium of claim 8, wherein the instructions further comprise instructions that, if executed by the one or more processors, cause the computer system to query one or more other computer systems for the set of replicated state machines capable of block allocation and utilization rates associated with the set of replicated state machines, where the one or more other computer systems host at least one replicated state machine of the set of replicated state machines.

13. The non-transitory computer-readable storage medium of claim 8, wherein the instructions that cause the computer system to calculate the utilization rate for at least the subset of the set of replicated state machines further include instructions that cause the computer system to calculate the utilization rate based at least in part on a set of previously received messages including resource utilization information of the other computer system.

14. The non-transitory computer-readable storage medium of claim 13, wherein the instructions that cause the computer system to calculate the utilization rate of at least the subset of the set of replicated state machines further include instructions that cause the computer system to discount resource utilization information of the other computer system obtained from at least a portion of the set of previously received messages based at least in part on the portion of the set of previously received messages being received before an interval of time.

15. A system, comprising:

one or more processors; and

memory that stores computer-executable instructions that, if executed, cause the one or more processors to;

generate a 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 utilization information associated with the system to include in the consensus message; and

provide the consensus message to at least one other system participating in the replicated state machine.

16. The system of claim 15, 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.

17. The system of claim 15, wherein the system implements a shard of the set of shards and the shard is a member of the replicated state machine.

18. The system of claim 15, wherein the memory further includes computer-executable instructions that, if executed, cause the one or more processors to obtain additional utilization information from a second consensus message obtained from the at least one other system.

19. The system of claim 18, wherein the memory further includes computer-executable instructions that, if executed, cause the one or more processors to:

receive a request to allocate a block of the system;

determine a utilization rate based at least in part on the utilization information and the additional utilization information; and

select the system based at least in part on the utilization rate.

20. The system of claim 19, wherein the memory further includes computer-executable instructions that, if executed, 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.