MANAGING ALLOCATION OF COMPUTING CAPACITY

• US 20130311650A1
• Filed: 07/19/2013
• Published: 11/21/2013
• Est. Priority Date: 02/28/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Brandwine, Eric Jason, Gupta, Diwakar, Greenfield, James Alfred Gordon
• Granted Patent: US 8,667,499 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: H04L 43/04 Processing captured monitoring data, e.g. for logfile generation

Abstract

Systems and methods are described for managing requests for computing capacity from a provider of computing resources. The computing resources may include program execution capabilities, data storage or management capabilities, network bandwidth, etc. In some implementations, user requests are probabilistically denied or granted while some computing resources are still available. By denying some requests or granting only some, the rate of computing resource usage can be reduced, thus preserving some capacity for a longer period of time. In one embodiment, the capacity can be provided to clients based on client priority, provided to clients with reserved resources, provided to clients probabilistically, sold on a spot market, or allocated in some other fashion.

Claims

1. A computing system configured to manage execution of programs for users, the system comprising:

a capacity request manager component that is configured to manage requests for execution of programs for users of a program execution service having a plurality of computing nodes, at least some of the plurality of computing nodes comprising physical computing systems, the capacity request manager component configured to;

access a request from a user of the program execution service for a specified amount of computing capacity of the program execution service;

determine if sufficient available capacity exists in the program execution service to fulfill the request for the specified amount of computing capacity;

deny the request if insufficient available capacity exists on the program execution service;

grant the request if available capacity on the program execution service is above a first threshold; and

probabilistically grant the request if the available capacity is below the first threshold, wherein a probability of granting the request is based at least in part on available capacity and a probability function that is used to determine the probability of granting the request, such that at least some of the requests are denied based at least in part on the probability function, even if available capacity exists;

wherein one or more of the plurality of computing nodes sufficient to provide the specified amount of computing capacity of the program execution service is allocated to the user if the request from the user is granted.

2. The system of claim 1, wherein the probability of granting the request increases when the available capacity increases or decreases when the available capacity decreases.

3. The system of claim 1, wherein the user is a customer of the program execution service and is associated with an account at the program execution service.

4. The system of claim 1, wherein the capacity manager is configured to deny a request if the available capacity is below a second threshold, wherein the second threshold is associated with a desired reserve capacity for the program execution service.

5. The system of claim 4, wherein the desired reserve capacity is sufficient to fulfill outstanding capacity guarantees provided by the program execution service for a particular usage period.

6. The system of claim 1, wherein the capacity request manager component is configured to grant the request for the specified amount of computing capacity if the capacity request manager component determines the program execution service has sufficient current computing capacity to satisfy the request for the specified amount of computing capacity.

7. The system of claim 1, wherein the request includes a requested usage period when the specified amount of computing capacity is desired.

8. A computer-implemented method for managing requests for computing capacity provided by a program execution service, the method comprising:

under control of a program execution service that provides a plurality of computing nodes that are each configurable to execute one or more programs of multiple users of the program execution service, at least some of the plurality of computing nodes comprising physical computing systems,

receiving from a user of the program execution service a request to provide a computing resource associated with one or more of the plurality of computing nodes;

determining availability of the requested computing resource on the plurality of computing nodes; and

probabilistically granting the request if the determined availability is below a first threshold, wherein a probability of granting the request is based at least in part on the availability of the requested computing resource and a probability function that is used to determine the probability of granting the request, such that at least some requests to the program execution service are denied based at least in part on the probability function, even if available resource exists.

9. The method of claim 8, further comprising granting the request if the determined availability of the requested resource is above the first threshold.

10. The method of claim 8, wherein granting the request comprises instantiating a virtual machine instance on the program execution service.

11. The method of claim 8, wherein the computing resource comprises at least one of processing capacity, memory capacity, network bandwidth or an IP address.

12. The method of claim 8, further comprising providing a notice to the user that the requested resource is unavailable.

13. The method of claim 8, wherein the request includes a requested period of time having an initial time in the future when availability of the computing resource is desired and an expiration time when availability of the computing resource is desired to end.

14. The method of claim 8, wherein probabilistically granting the request comprises using a probability function to determine whether to grant the request.

15. The method of claim 14, wherein the probability function provides a grant probability, wherein at least over a range of availability of the requested computing resource, the grant probability decreases as the availability of the requested computing resource decreases.

16. The method of claim 15, wherein the probability function comprises a linear function.

17. The method of claim 8, wherein probabilistically granting the request comprises determining a priority for the request, wherein different priorities correspond to different probabilities that the request is granted.

18. A non-transitory computer-readable medium having stored thereon instructions that, when executed by a computer system, cause the computer system to perform operations comprising:

receiving a plurality of computing resource requests for respective amounts of computing resources of a program execution service;

determining that sufficient computing resources are available on the program execution service to fulfill the respective computing resource requests; and

based at least in part on the determination, probabilistically denying at least some of the requests and granting at least some of the requests, wherein a probability function is used to determine a probability of granting at least some of the requests, such that at least some of the requests are denied based at least in part on the probability function, even if available resource exists.

19. The computer-readable medium of claim 18, wherein denying at least some of the requests comprises statistically determining a denial probability and utilizing the denial probability to determine whether to deny a request.

20. The computer-readable medium of claim 18, wherein granting at least some of the requests comprises statistically determining a grant probability and utilizing the grant probability to determine whether to grant a request.