Optimizing for infrastructure diversity constraints in resource placement

• US 10,505,862 B1
• Filed: 02/18/2015
• Issued: 12/10/2019
• Est. Priority Date: 02/18/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Dhoolam, Surya Prakash, Greenwood, Christopher Magee, Flaherty, Mitchell Gannon, Lakshmikanth, Nishant Satya
• Primary Examiner(s): Lazaro, David R
• Assistant Examiner(s): Chang, Julian
• Application Number:
  US14/625,535
• Time in Patent Office: 1,756 Days
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/781 Centralised allocation of resources

Abstract

A distributed system may implement optimizing for infrastructure diversity in resource placement. A placement request for a resource to be placed at one of multiple resource hosts respectively implemented at infrastructure units may be received. An evaluation of utilization data for the multiple resource hosts may be performed with regard to an infrastructure diversity constraint for placing resources at the infrastructure units. A selection of a resource host may be made based on the evaluation of the utilization data according to the infrastructure diversity constraint. In some embodiments to select the resource host, the effect of placing the resource on candidate resource hosts on an infrastructure-diverse capacity metric may be determined to score the candidate resource hosts. The resource may be placed at the selected resource host.

Claims

1. A distributed system, comprising:

one or more computing devices that include one or more central processing units, the one or more computing devices configured to implement a plurality of different resource hosts at respective infrastructure units of a plurality of infrastructure units of the distributed system; and

a resource placement manager implemented via one or more central processing units, configured to;

receive a request to place a resource at one of the plurality of different resource hosts;

in response the receipt of the request;

obtain utilization data of the plurality of different resource hosts;

evaluate the utilization data according to an infrastructure diversity constraint to determine respective effects of placing the resource at different ones of the resource hosts upon an ability of the resource hosts to accept subsequent placement of a different resource and one or more other resources associated with the different resource while satisfying the infrastructure diversity constraint for the different resource and the one or more other resources with regard to the plurality of infrastructure units;

based, at least in part, on the evaluation of the utilization data according to the infrastructure diversity constraint, select one resource host of the distributed system to place the resource, wherein the selected resource host has available capacity to receive the resource for placement and is selected at least in part to permit satisfaction of the diversity constraint with regard to the plurality of infrastructure units for the resource, and wherein the selected resource host is selected at least in part to permit satisfaction of the infrastructure diversity constraint with regard to the plurality of infrastructure units for another resource that is to be subsequently placed at one of the plurality of resource hosts; and

direct placement of the resource at the selected resource host.

2. The system of claim 1,

wherein to evaluate the utilization data of the plurality of different resource hosts according to the infrastructure diversity constraint, the resource placement manager is configured to calculate an infrastructure-diverse resource capacity metric for the plurality of different resource hosts;

wherein to select the one resource host of the distributed system to place the resource, the resource placement manager is configured to;

identify a plurality of candidate hosts from among the plurality of different resource hosts for placing the resource;

generate respective scores for different ones of the plurality of candidate hosts according to an effect of resource placement at the respective candidate host on the infrastructure-diverse resource capacity metric for the plurality of different resource hosts; and

determine the selected resource host for placing the resource based, at least in part, on the respective scores for the plurality of candidate hosts.

3. The system of claim 1, wherein the resource placement manager is further configured to:

respectively aggregate the utilization data according to the plurality of infrastructure units; and

wherein the evaluation is performed upon the aggregate utilization data for the plurality of infrastructure units.

4. The system of claim 1, wherein the distributed system is implemented as part of a network-based block-based storage service, wherein the resource is a data volume maintained for a client of the network-based block-based storage service.

5. A method, comprising:

performing, by one or more computing devices;

receiving a request to place a resource at one of a plurality of different resource hosts of a distributed system, wherein the plurality of different resource hosts are respectively implemented at an infrastructure unit of a plurality of infrastructure units of the distributed system;

in response to receiving the request;

evaluating utilization data of the plurality of different resource hosts according to an infrastructure diversity constraint to determine respective effects of placing the resource at different ones of the resource hosts upon an ability of the resource hosts to accept subsequent placement of a different resource and one or more other resources associated with the different resource while satisfying the infrastructure diversity constraint for the different resource and the one or more other resources with regard to the plurality of infrastructure units;

based, at least in part, on the respective effects of placing the resource at the different ones of the resource hosts, selecting one resource host of the distributed system to place the resource, wherein the selected resource host has available capacity to receive the resource for placement and is selected at least in part to permit satisfaction of the diversity constraint with regard to the plurality of infrastructure units for the resource, and wherein the selected resource host is selected at least in part to permit satisfaction of the infrastructure diversity constraint with regard to the plurality of infrastructure units for another resource that is to be subsequently placed at one of the plurality of resource hosts; and

placing the resource at the selected resource host.

6. The method of claim 5,

wherein evaluating the utilization data of the plurality of different resource hosts according to the infrastructure diversity constraint comprises calculating an infrastructure-diverse resource capacity metric for the plurality of different resource hosts;

wherein selecting the one resource host of the distributed system to place the resource comprises;

identifying a plurality of candidate hosts from among the plurality of different resource hosts for placing the resource;

generating respective scores for different ones of the plurality of candidate hosts according to an effect of resource placement at the respective candidate host on the infrastructure-diverse resource capacity metric for the plurality of different resource hosts; and

determining the selected resource host for placing the resource based, at least in part, on the respective scores for the plurality of candidate hosts.

7. The method of claim 6, wherein generating the respective scores for the plurality of candidate hosts is based, at least in part, on the effect of resource placement upon comparisons of current utilization metrics of the plurality of different resource hosts with capacity metrics for the plurality of different resource hosts.

8. The method of claim 5, further comprising:

collecting the utilization data of the plurality of different resource hosts;

respectively aggregating the utilization data according to the plurality of infrastructure units; and

wherein the evaluation is performed upon the aggregate utilization data for the plurality of infrastructure units.

9. The method of claim 5, wherein the utilization data comprises storage capacity of the plurality of different resource hosts.

10. The method of claim 5, wherein the evaluation of the utilization data of the plurality of different resource hosts according to the infrastructure diversity constraint is based, at least in part, on historic resource placement data for the plurality of different resource hosts.

11. The method of claim 5, wherein the plurality of infrastructure units are a plurality of network routers, wherein the plurality of different resource hosts respectively implemented at the infrastructure unit are respectively connected to a network router of the plurality of network routers, and wherein the infrastructure diversity constraint comprises a requirement that associated resources be placed at different resource hosts connected to two or more different network routers of the plurality of network routers.

12. The method of claim 5, wherein the request to place the resource at one of the plurality of different resource hosts of the distributed system is a request to create a new resource at the distributed system.

13. The method of claim 5, wherein the distributed system is a network-based service, and wherein the resource is placed for a client of the network-based service.

14. A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices cause the one or more computing devices to implement:

receiving a request to place a resource at one of a plurality of different resource hosts of a distributed system, wherein the plurality of different resource hosts are respectively implemented at an infrastructure unit of a plurality of infrastructure units of the distributed system;

in response to receiving the request;

evaluating utilization data of the plurality of different resource hosts according to an infrastructure diversity constraint to determine respective effects of placing the resource at different ones of the resource hosts upon an ability of the resource hosts to accept subsequent placement of a different resource and one or more other resources associated with the different resource while satisfying the infrastructure diversity constraint for the different resource and the one or more other resources with regard to the plurality of infrastructure units;

based, at least in part, on the respective effects of placing the resource at the different ones of the resource hosts, selecting one resource host of the distributed system to place the resource, wherein the selected resource host has available capacity to receive the resource for placement and is selected at least in part to permit satisfaction of the diversity constraint with regard to the plurality of infrastructure units for the resource, and wherein the selected resource host is selected at least in part to permit satisfaction of the infrastructure diversity constraint with regard to the plurality of infrastructure units for another resource that is to be subsequently placed at one of the plurality of resource hosts; and

placing the resource at the selected resource host.

15. The non-transitory, computer-readable storage medium of claim 14,

wherein, in evaluating the utilization data of the plurality of different resource hosts according to the infrastructure diversity constraint, the program instructions cause the one or more computing devices to implement calculating an infrastructure-diverse resource capacity metric for the plurality of different resource hosts;

wherein, in selecting the one resource host of the distributed system to place the resource, the program instructions cause the one or more computing devices to implement;

identifying a plurality of candidate hosts from among the plurality of different resource hosts for placing the resource;

generating respective scores for different ones of the plurality of candidate hosts according to an effect of resource placement at the respective candidate host on the infrastructure-diverse resource capacity metric for the plurality of different resource hosts; and

determining the selected host for placing the resource based, at least in part, on the respective scores for the plurality of candidate hosts.

16. The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions cause the one or more computing devices to further implement:

collecting the utilization data of the plurality of different resource hosts;

respectively aggregating the utilization data according to the plurality of infrastructure units; and

wherein the evaluation is performed upon the aggregate utilization data for the plurality of infrastructure units.

17. The non-transitory, computer-readable storage medium of claim 14, wherein the utilization data comprises throughput capacity of the plurality of different resource hosts.

18. The non-transitory, computer-readable storage medium of claim 14, wherein the plurality of infrastructure units are a plurality of server racks, wherein the plurality of different resource hosts respectively implemented at the infrastructure unit are respectively located at a server rack of the plurality of server racks, and wherein the infrastructure diversity constraint comprises a requirement that associated resources be placed at different resource hosts implemented at two or more different server racks of the plurality of server racks.

19. The non-transitory, computer-readable storage medium of claim 14, wherein the request to place the resource at one of the plurality of different resource hosts of the distributed system is a request to move a resource hosted at another resource host of the distributed system.

20. The non-transitory, computer-readable storage medium of claim 14, wherein the distributed system is a network-based computing service, wherein the resource is a virtual compute instance requested via the network-based computing service for a client of the network-based computing service.