Managing operational throughput for shared resources

• US 8,694,400 B1
• Filed: 09/14/2010
• Issued: 04/08/2014
• Est. Priority Date: 09/14/2010
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Certain, Tate Andrew, Jain, Sachin, Marshall, Bradley E., Maniscalco, Nicholas J., Sivasubramanian, Swaminathan, Garman, Matthew S.
• Primary Examiner(s): Weisberger, Richard C
• Application Number:
  US12/882,082
• Time in Patent Office: 1,302 Days
• Field of Search: 705 35- 45, 370/229, 709/223
• US Class Current: 705/35
• CPC Class Codes: G06Q 30/00 Commerce
• CPC Class Codes: G06Q 30/08 Auctions
• CPC Class Codes: G06Q 40/06 Asset management; Financial planning or analysis
• CPC Class Codes: G06T 15/20 Perspective computation
• CPC Class Codes: H04L 15/16 with keyboard co-operating with code discs

Abstract

Usage of shared resources can be managed by enabling users to obtain different types of guarantees at different times for various types and/or levels of resource capacity. A user can select to have an amount or rate of capacity dedicated to that user. A user can also select reserved capacity for at least a portion of the requests, tasks, or program execution for that user, where the user has priority to that capacity but other users can utilize the excess capacity during other periods. Users can alternatively specify to use the excess capacity or other variable, non-guaranteed capacity. The capacity can be for any appropriate functional aspect of a resource, such as computational capacity, throughput, latency, bandwidth, and storage. Users can submit bids for various types and combinations of excess capacity, and winning bids can receive dedicated use of the excess capacity for at least a period of time.

Claims

1. A computer-implemented method of managing shared resources, comprising:

under control of one or more computer systems configured with executable instructions,

receiving an instance request associated with a user, the instance request specifying a bid price and a minimum rate of I/O operations to be used in invoking resource capacity for a user;

determining whether available resource capacity exists to fulfill the instance request with the minimum rate of I/O operations and whether the bid price at least meets a current market price for the available capacity;

if the available capacity exists and the bid price at least meets the current price, comparing the bid price to any competing bid price for the available resource capacity; and

if the instance request meets at least one selection criterion, based at least in part upon the bid price, causing the instance request to be fulfilled using the available capacity.

2. The computer-implemented method of claim 1, wherein the instance request is fulfilled using dedicated or reserved capacity if a user associated with the instance request has available dedicated or reserved capacity.

3. The computer-implemented method of claim 1, wherein the available capacity is excess capacity of at least one resource type, the excess capacity capable of being unused dedicated or reserved capacity.

4. The computer-implemented method of claim 1, wherein the instance request further specifies at least one other category of resource capacity to be used in fulfilling the instance request.

5. The computer-implemented method of claim 4, wherein the instance request includes at least one additional bid price based at least in part upon meeting a level of resource capacity for the at least one other category of resource capacity.

6. The computer-implemented method of claim 4, wherein the at least one other category of resource capacity includes at least one of compute capacity, storage capacity, bandwidth, or latency.

7. The computer-implemented method of claim 1, wherein the instance request does meet at least one selection criterion, and further comprising:

attempting to fulfill the instance request using available variable on-demand capacity; and

if the instance request is unable to be fulfilled using available variable on-demand capacity, denying the instance request.

8. The computer-implemented method of claim 1, further comprising:

if the instance request is being fulfilled using the available capacity, determining after at least one period of time whether the instance request still meets at least one selection criterion, based at least in part upon the current market price; and

if the instance request no longer meets at least one selection criterion, terminating fulfillment of the instance request using the available capacity.

9. The computer-implemented method of claim 1, further comprising:

if the instance request is being fulfilled using the available capacity, determining after at least one period of time whether another user associated with the available capacity has a separate instance request to be fulfilled using the available capacity; and

if the other user associated with the available capacity has a separate instance request to be fulfilled using the available capacity, terminating fulfillment of the instance request using the available capacity.

10. The computer-implemented method of claim 9, wherein fulfillment of the instance request using the available capacity is terminated, and further comprising:

attempting to fulfill the instance request using available variable on-demand capacity, the available variable on-demand capacity capable of having no guaranteed rate of I/O operations.

11. The computer-implemented method of claim 9, wherein terminating the fulfillment of the instance request includes at least one of destroying a volume associated with the instance request, deactivating an instance associated with the request, taking at least one snapshot of a volume associated with the instance request and storing the snapshot for subsequent retrieval, or changing the fulfillment of the instance request to an uncommitted level of fulfillment.

12. The computer-implemented method of claim 1, wherein the instance request is associated with at least one program, fulfilling of the instance request comprising executing the at least one program using the available capacity.

13. The computer-implemented method of claim 1, wherein a bid price for the request is not considered if at least one specified level for at least one resource type for fulfilling the instance request is not available using the available capacity.

14. The computer-implemented method of claim 1, further comprising:

periodically adjusting the market price based at least in part upon a target capacity usage, the adjusted market price causing more or fewer requests to meet at least one selection criterion.

15. The computer-implemented method of claim 1, further comprising:

for fulfilling instance requests in excess of a capacity limit for the available capacity, attempting to fulfill the excess instance requests using an uncommitted type of capacity.

16. The computer-implemented method of claim 1, further comprising:

periodically receiving adjusted bid prices for the instance request during fulfilling, the adjusted bid prices being submitted to ensure that the instance request is fulfilled using the available capacity even in the presence of an adjusting market price and new competing bids.

17. The computer-implemented method of claim 1, wherein the instance request is received from a customer as a Web services request through an application programming interface (API) of a control plane.

28. The computer-implemented method of claim 1, wherein the instance request further specifies a type of resource capacity, and further comprising:

if the type of capacity is a dedicated capacity type and dedicated capacity for the user with at least the rate of I/O operations is available, generating an instance for the user using the dedicated capacity;

if the type of capacity is a reserved capacity type and reserved capacity for the user with at least the rate of I/O operations is available, generating an instance for the user using the reserved capacity;

if the type of capacity is an excess capacity type;

determining whether a bid price is a winning bid price, the winning bid price being greater than other pending bids for the same excess capacity and being at least equal to the current market price; and

if the bid price is the winning bid price and excess capacity for the user with at least the rate of I/O operations is available, generating an instance for the user using the excess capacity for at least a minimum period of time; and

if the type of capacity is a variable capacity type and variable capacity is available, generating an instance for the user using the variable capacity, the variable capacity capable of having less than the rate of I/O operations specified for the instance request.

29. The computer-implemented method of claim 28, further comprising:

if the dedicated capacity with the rate of I/O operations is not available for the instance request specifying the dedicated capacity type, changing the type of capacity specified by the instance request to one of an excess capacity type or a variable capacity type;

if the reserved capacity with the rate of I/O operations is not available for the instance request specifying the reserved capacity type, changing the type of capacity specified by the instance request to one of an excess capacity type or a variable capacity type;

if the excess capacity with the rate of I/O operations is not available for the instance request specifying the excess capacity type, changing the type of capacity specified by the instance request to a variable capacity type; and

if the variable capacity is not available for the instance request specifying the variable capacity type, denying the instance request.

30. The computer-implemented method of claim 28, further comprising:

if the instance request is being fulfilled using the excess capacity and the excess capacity becomes no longer available, moving an instance corresponding to the request to variable capacity if available.

31. The computer-implemented method of claim 1, further comprising:

receiving a reservation request from the user to utilize the resource capacity prior to receiving the instance request associated with the user;

enabling the user to purchase dedicated capacity for fulfilling at least a portion of the instance request if dedicated capacity is available with the specified rate of I/O operations, the dedicated capacity being available at any time for use by the user;

enabling the user to purchase reserved capacity for fulfilling at least a portion of the instance request if reserved capacity is available with the specified rate of I/O operations, the user being given priority to use the reserved capacity over other users; and

if a user is unable to purchase dedicated or reserved capacity, in response to a subsequent instance request;

enabling the user to bid on excess capacity for fulfilling at least a portion of the instance request if excess capacity is available with the specified rate of I/O operations at substantially a time of submission of the instance request, the excess capacity being available when the bid price for the user at least meets a market price for the excess capacity, the user being able to utilize the excess capacity for at least a period of time when the bid price meets at least one selection criterion; and

enabling the user to utilize available variable on-demand capacity for fulfilling at least a portion of the instance request if available variable on-demand capacity is available.

32. The computer-implemented method of claim 31, further comprising enabling the user to specify another type of capacity to use to fulfill any instance requests that exceed an amount of capacity specified by the user for at least a portion of the fulfillment.

33. The computer-implemented method of claim 31, further comprising enabling the user to dynamically adjust the bid price for the excess capacity in order to continue fulfillment for the instance request using the excess capacity.

34. The computer-implemented method of claim 31, further comprising enabling the user to submit a plurality of bids for excess capacity, each bid having a bid price based on a combination of levels of capacity for multiple categories of resource capacity.

18. A system for managing shared resources, comprising:

at least one processor; and

memory including instructions that, when executed by the at least one processor, cause the system to;

receive an instance request associated with a user, the instance request specifying a bid price and a minimum rate of I/O operations to be used in invoking resource capacity for a user;

determine whether available resource capacity exists to fulfill the instance request with the minimum rate of I/O operations and whether the bid price at least meets a current market price for the available capacity;

if the available capacity exists and the bid price at least meets the current price, compare the bid price to any competing bid price for the available resource capacity; and

if the request meets at least one selection criterion, based at least in part upon the bid price, cause the instance request to be fulfilled using the available capacity.

19. The system of claim 18, wherein the instance request is fulfilled using dedicated or reserved capacity if a user associated with the instance request has available dedicated or reserved capacity.

20. The system of claim 18, wherein the instance request further specifies at least one other type of resource capacity to be used in fulfilling the instance request.

21. The system of claim 18, wherein the instance request does not meet at least one selection criterion, and wherein the instructions when executed further cause the system to:

attempt to fulfill the instance request using available variable on-demand capacity; and

if the instance request is unable to be fulfilled using available variable on-demand capacity, deny the instance request.

22. The system of claim 18, wherein the instructions when executed further cause the system to:

if the instance request is being fulfilled using the available capacity, determine after at least one period of time whether the instance request still meets at least one selection criterion, based at least in part upon the current market price; and

if the instance request no longer meets at least one selection criterion, terminate fulfillment of the instance request using the available capacity.

23. A computer-readable storage medium including instructions for managing shared resources, the instructions when executed by a processor causing the processor to:

receive an instance request associated with a user, the instance request specifying a bid price and a minimum rate of I/O operations to be used in invoking resource capacity for a user;

determine whether available resource capacity exists to fulfill the instance request with the minimum rate of I/O operations and whether the bid price at least meets a current market price for the available capacity;

if the available capacity exists and the bid price at least meets the current price, compare the bid price to any competing bid price for the available resource capacity; and

if the request meets at least one selection criterion, based at least in part upon the bid price, cause the instance request to be fulfilled using the available capacity.

24. The computer-readable storage medium of claim 23, wherein the instance request is fulfilled using dedicated or reserved capacity if a user associated with the instance request has available dedicated or reserved capacity.

25. The computer-readable storage medium of claim 23, wherein the instance request further specifies at least one other type of resource capacity to be used in fulfilling the instance request.

26. The computer-readable storage medium of claim 23, wherein the instance request does not meet at least one selection criterion, and wherein the instructions when executed further cause the system to:

attempt to fulfill the instance request using available variable on-demand capacity; and

if the instance request is unable to be fulfilled using available variable on-demand capacity, deny the instance request.

27. The computer-readable storage medium of claim 23, wherein the instructions when executed further cause the system to:

if the instance request is being fulfilled using the available capacity, determine after at least one period of time whether the instance request still meets at least one selection criterion, based at least in part upon the current market price; and

if the instance request no longer meets at least one selection criterion, terminate fulfillment of the instance request using the available capacity.