Managing use of program execution capacity

• US 8,249,904 B1
• Filed: 12/12/2008
• Issued: 08/21/2012
• Est. Priority Date: 12/12/2008
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: DeSantis, Peter N., Garman, Matthew S., Ward, Charles L., Greenfield, James Alfred Gordon, Jassy, Andrew R.
• Primary Examiner(s): Zeender, Ryan
• Assistant Examiner(s): Roman, Denisse Ortiz
• Application Number:
  US12/334,022
• Time in Patent Office: 1,348 Days
• Field of Search: None
• US Class Current: 705/7.12
• CPC Class Codes: G06F 15/173 using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
• CPC Class Codes: G06F 2209/5014 Reservation
• CPC Class Codes: G06F 2209/509 Offload
• CPC Class Codes: G06F 9/5088 involving task migration
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

Techniques are described for managing execution of programs. In some situations, program execution is managed for multiple users using excess program execution capacity of one or more computing systems. In some such situations, excess or otherwise unused program execution capacity may be made available to execute programs on a temporary basis, such that the programs executing using the excess program execution capacity may be terminated at any time if other preferred use for the excess program execution capacity arises. The excess program execution capacity may in some situations be provided in conjunction with other dedicated program execution capacity that is allocated to particular users, such as to use unused dedicated capacity of some users as excess capacity for other users. In some situations, the techniques are used in conjunction with a fee-based program execution service that executes multiple programs on behalf of multiple users of the service.

Claims

1. A computer-implemented method for a program execution service to manage execution of programs for users, the method comprising:

after receiving a request from a first user of the program execution service to reserve a computing node to provide guaranteed availability for the first user to execute one or more programs, allocating, by one or more configured computing systems of the program execution service, one of a plurality of computing nodes provided by the program execution service to be reserved for guaranteed use by the first user;

in response to a request from the first user, initiating, by the one or more configured computing systems, execution at a first time of a first program on the allocated one computing node reserved for the first user;

receiving, by the one or more configured computing systems, a request to execute a second program of a second user on a computing node of the program execution service in a non-guaranteed manner such that the non-guaranteed execution of the second program may be terminated by the program execution service at any time;

monitoring, by the one or more configured computing systems, the execution of the first program on the allocated one computing node reserved for the first user and determining that the allocated one computing node is not currently executing any programs for the first user at a second time after the first time;

initiating, by the one or more configured computing systems, the non-guaranteed execution of the second program at the second time on the allocated one computing node on behalf of the second user; and

after receiving a request from the first user at a third time after the second time to execute one or more indicated programs on the allocated one computing node reserved for the first user,

determining to terminate execution of the second program on the allocated one computing node;

terminating execution of the second program on the allocated one computing node; and

initiating execution of the one or more indicated programs on the allocated one computing node on behalf of the first user.

2. The method of claim 1 wherein the program execution service is a fee-based service such that the first user pays a first fee for the allocating of the one computing node for reserved use by the first user and such that the second user pays a second fee for the non-guaranteed execution of the second program on the allocated one computing node, the second fee being less than the first fee, and wherein at least a portion of the second fee is provided to the first user for use of the allocated one computing node in executing the second program on behalf of the second user.

3. The method of claim 2 wherein the first user is part of a first group of multiple users to whom multiple of the plurality of computing nodes are allocated for priority access, wherein the second fee paid by the second user is based at least in part on an amount bid by the second user as part of the received request to execute the second program of the second user, wherein one or more other users also place bids as part of received requests for non-guaranteed execution of programs on behalf of the one or more other users, wherein the initiating of the non-guaranteed execution of the second program on the allocated one computing node includes selecting the received request from the second user before the received requests from the one or more other users based at least in part on the amount bid by the second user being higher than the bids placed by the one or more other users, and wherein the received requests of at least one of the one or more other users is not satisfied based at least in part on none of the multiple allocated computing nodes being available to execute the programs on behalf of the at least one other users.

4. A computer-implemented method for a program execution service to manage execution of programs for users, the method comprising:

allocating, by one or more configured computing systems of a program execution service, one or more computing nodes of the program execution service to a first user of the program execution service to provide the first user with priority access to the allocated computing nodes;

determining, by the one or more configured computing systems, a group including at least one computing node of the program execution service to satisfy a request to execute a program for a second user, the at least one computing node of the determined group including one of the allocated computing nodes;

initiating, by the one or more configured computing systems, execution of the program of the second user on the at least one computing node of the determined group; and

after receiving an indication to execute one or more programs of the first user,

determining, by the one or more configured computing systems, to terminate execution of the program of the second user on the included one allocated computing node;

terminating, by the one or more configured computing systems, execution of the program of the second user on the included one allocated computing node; and

making the included one allocated computing node available, by the one or more configured computing systems, to execute the one or more programs of the first user based at least in part on the terminating.

5. The method of claim 4 wherein the received indication to execute the one or more programs of the first user is based on a request from the first user to execute an indicated program on the allocated computing nodes, and wherein the method further comprises, after the terminating of the execution of the program of the second user on the one allocated computing node, executing the indicated program of the first user on the one allocated computing node.

6. The method of claim 4 wherein the one or more computing nodes are allocated to the first user to provide the first user with the priority access to the allocated computing nodes during a specified period of time, wherein the priority access of the first user to the allocated computing nodes is dedicated access such that a request by the first user to execute a program on the allocated computing nodes during the specified period of time is guaranteed to be satisfied, wherein the one allocated computing node is not executing a program for the first user at a time of the determining of the group of one or more computing nodes, and wherein the execution of the program of the second user on the one or more computing nodes of the determined group is performed in a non-guaranteed manner such that the execution of the program of the second user is allowed to be terminated at any time.

7. The method of claim 6 wherein the allocated computing nodes and the at least one computing nodes of the determined group are a subset of a plurality of computing nodes provided by the program execution service, wherein some of the plurality of computing nodes are not allocated to give dedicated access to users of the program execution service and are maintained to dynamically satisfy at least some other requests from users for immediate execution of programs, such that the other requests for immediate execution are not guaranteed to be satisfied and such that execution of programs for satisfied requests using the some computing nodes are not subject to termination, and wherein the method further comprises receiving other requests from other users for immediate execution of indicated programs and satisfying at least some of the received other requests by initiating execution of the indicated programs on the some computing nodes.

8. The method of claim 4 wherein the program execution service is a fee-based service such that the first user pays one or more first fees for the priority access to the allocated computing nodes and such that the second user pays a second fee for execution of the program of the second user, the second fee being less than the one or more first fees based at least in part on the execution of the program of the second user not having priority access.

9. The method of claim 4 wherein the request to execute the program of the second user reflects that the execution of the program of the second user is time-sensitive, and wherein the program execution service is a fee-based service such that the first user pays one or more first fees for the priority access to the allocated computing nodes and such that the second user pays a second fee for execution of the program of the second user, the second fee being more than the one or more first fees based at least in part on the execution of the program of the second user being time-sensitive.

10. The method of claim 4 wherein the received request to execute the program of the second user includes a bid amount specified by the second user to be paid to the program execution service by the second user for executing the program on behalf of the second user on a specified quantity of computing nodes.

11. The method of claim 10 wherein at least some of the bid amount is provided to the first user based at least in part on use of the one allocated computing nodes for executing the program of the second user.

12. The method of claim 4 wherein the one or more computing nodes are allocated to the first user for a specified period of time, wherein the received request to execute the program of the second user is an indicated acceptance by the second user of a prior offer by the first user to allow others to use the one or more allocated computing nodes of the first user for a subset of the specified period of time, wherein the determining of the group of computing nodes includes selecting the one allocated computing node based on the indicated acceptance of the prior offer, and wherein the terminating of the execution of the program of the second user occurs after the subset of the specified period of time is complete.

13. The method of claim 4 wherein the one or more computing nodes are allocated to the first user for a specified period of time, wherein a third user of the program execution service is given priority access to one or more other computing nodes of the program execution service that are allocated to the third user for the specified period of time, the one or more other computing nodes being distinct from the one or more computing nodes allocated to the first user and from the at least one computing nodes of the determined group, and wherein the method further comprises:

receiving a request from a fourth user of the program execution service to execute a program of the fourth user using the one or more other computing nodes allocated to the third user; and

if the third user has provided consent, transferring the priority access to the one or more other allocated computing nodes from the third user to the fourth user to enable the fourth user to receive priority access to the one or more allocated other computing nodes during a remaining portion of the specified period of time.

14. The method of claim 4 wherein the first user is part of a first group of multiple users to whom multiple of a plurality of computing nodes of the program execution service are allocated for priority access, wherein the terminating of the execution of the program of the second user on the one allocated computing node includes saving execution state of the program at a time of the terminating, and wherein the method further comprises, at a second time after the time of the terminating:

determining a second group of computing nodes of the program execution service that are available to execute the program of the second user at the second time, the determined second group including one or more of the multiple allocated computing nodes that are not currently executing programs on behalf of the users of the first group at the second time; and

reinitiating execution of the program of the second user on the computing nodes of the determined second group in such a manner as to restore the saved execution state of the program.

15. The method of claim 14 wherein the program execution service uses virtualization technology such that the plurality of computing nodes include, for each of multiple physical computing systems, multiple virtual machines hosted by the physical computing system that are each able to execute at least one program, wherein the at least one computing nodes of the determined group are each hosted virtual machines, wherein the program of the second user is a virtual machine image, and wherein the saving of the execution state of the program and the reinitiating of the execution of the program are based at least in part on the virtualization technology used by the program execution service.

16. The method of claim 4 wherein inclusion in the determined group of the one allocated computing node is based at least in part on a prior indication from the first user that the one allocated computing node is available for use to execute programs of other users.

17. The method of claim 4 wherein inclusion of the one allocated computing node in the determined group is based at least in part on monitoring execution of programs on the one or more allocated computing nodes to determine which of the one or more allocated computing nodes is not currently executing any program for a user of the program execution service.

18. The method of claim 4 wherein the one or more computing nodes are allocated to the first user for a specified period of time, wherein the first user is part of a first group of multiple users to whom multiple of a plurality of computing nodes of the program execution service are allocated for priority access, and wherein the method further comprises:

receiving multiple other requests from multiple other users of the program execution service, the other users being distinct from the users of the first group and from the second user, each of the other requests including a request to execute a respective program of a respective other user during at least some of the specified period of time;

determining a subgroup of the multiple other requests to execute on computing nodes of the program execution service, the determining of which of the multiple other requests to include in the subgroup being based at least part on a determined priority of each of the other requests, such that each request of the subgroup is determined to be of higher priority than other requests that are not in the subgroup; and

for each of the requests of the subgroup, initiating execution of the respective program of the request on at least one of the multiple allocated computing nodes that is not currently executing programs on behalf of the users of the first group.

19. The method of claim 18 wherein the determined priority of each of the other requests is based on at least one of a monetary bid associated with the other request, of a quantity of computing nodes to use to satisfy the request, and of a time of executing the respective program of the request.

20. The method of claim 4 wherein the program execution service is remote from the first user and from the second user, wherein the program execution service provides one or more Application Programming Interfaces (APIs) for remote computing systems to programmatically interact with the program execution service over one or more networks, and wherein the allocating of the one or more computing nodes to the first user and the receiving by the program execution service of the request to execute the program of the second user are initiated based on programmatic interactions received by the program execution service via the one or more APIs.

21. The method of claim 4 wherein the one or more computing nodes are allocated to the first user for a specified period of time, wherein the second user further has priority access to one or more other computing nodes of the program execution service that are allocated to the second user during the specified period of time, the one or more other computing nodes being distinct from the one or more computing nodes allocated to the first user, and wherein the second user further executes an indicated program during the specified period of time on the one or more other computing nodes allocated to the second user, such that the indicated program executes on the one or more other computing nodes allocated to the second user at a same time that the program of the second user executes on the at least one computing nodes of the determined group.

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

one or more processors; and

a system manager component that is configured to, when executed by at least one of the one or more processors, manage execution of programs for users of a program execution service by;

receiving an indication to execute a first program of a first user using a specified first amount of computing capacity of the program execution service;

initiating execution of the first program of the first user using a group of computing resources of the program execution service that is determined to provide the first amount of computing capacity;

receiving an indication of a second amount of computing capacity of the program execution service for executing a second program of a second user, the second amount of computing capacity being dedicated for executing programs of the second user in accordance with priority access of the second user to the program execution service;

determining that at least some of the group of computing resources used for executing the first program of the first user is needed to provide the second amount of computing capacity to execute the second program;

terminating use of the at least some computing resources to execute the first program of the first user; and

initiating execution of the second program of the second user using the at least some computing resources.

23. The computing system of claim 22 wherein the computing resources of the program execution service include a plurality of computing nodes that are each configurable to execute one or more programs for one or more of the users of the program execution service, wherein the second amount of computing capacity that is dedicated for executing programs of the second user includes at least one of the plurality of computing nodes that is reserved for use by the second user in executing programs, wherein the group of computing resources includes one or more of the at least one computing nodes reserved for use by the second user, wherein the received indication to execute the first program is a request by the first user to execute the first program, and wherein the received indication of the second amount of computing capacity to execute the second program is a request by the second user to execute the second program.

24. The computing system of claim 23 wherein the managing of the execution of the programs for the users of the program execution service includes determining the group of the computing resources to provide the first amount of computing capacity, the computing resources of the determined group including a subset of computing cycles of a particular computing node that is currently executing one or more programs for the second user, and wherein the initiating of the execution of the first program includes executing the first program on the particular computing node simultaneously with the currently executing one or more programs of the second user, such that the first program of the first user executes using the subset of the computing cycles of the particular computing node.

25. The computing system of claim 22 wherein the system manager component includes software instructions for execution by the at least one processors of the computing system.

26. The computing system of claim 22 wherein the system manager component consists of a means for performing the managing of the execution of the programs for the users of the program execution service.

27. A non-transitory computer-readable medium whose contents configure a computing system of a program execution service to perform a method for managing execution of programs for users, the method comprising:

allocating one or more computing nodes of the program execution service to a first user of the program execution service to provide the first user with priority access to the allocated computing nodes during a specified period of time;

determining a group including at least one computing node of the program execution service to satisfy a request to execute a program for a second user, the at least one computing node of the determined group including one of the allocated computing nodes;

initiating execution of the program of the second user on the at least one computing node of the determined group; and

after receiving an indication to execute one or more programs of the first user,

determining to terminate execution of the program of the second user on the included one allocated computing node;

terminating execution of the program of the second user on the included one allocated computing node; and

making the included one allocated computing node to be available to execute the one or more programs of the first user.

28. The non-transitory computer-readable medium of claim 27 wherein the received indication to execute the one or more programs of the first user of the first group is based on a request from the first user to execute an indicated program on the allocated computing nodes, and wherein the method further comprises, after the terminating of the execution of the program of the second user on the one allocated computing node, executing the indicated program of the first user on the included one allocated computing node.

29. The non-transitory computer-readable medium of claim 27 wherein the priority access of the first user to the allocated computing nodes is dedicated access such that a request by the first user to execute a program on the allocated computing nodes during the specified period of time is guaranteed to be satisfied, wherein the included one allocated computing node is not executing a program for the first user at a time of the determining of the group of one or more computing nodes, and wherein the execution of the program of the second user on the one or more computing nodes of the determined group is performed in a non-guaranteed manner such that the execution of the program of the second user is allowed to be terminated at any time.

30. The non-transitory computer-readable medium of claim 27 wherein the first user is part of a first group of multiple users to whom multiple of a plurality of computing nodes of the program execution service are allocated for priority access, and wherein the method further comprises:

receiving multiple other requests from multiple other users of the program execution service, the other users being distinct from the users of the first group and from the second user, each of the other requests including a request to execute a respective program of a respective other user during at least some of the specified period of time;

determining a subgroup of the multiple other requests to execute on computing nodes of the program execution service, the determining of which of the multiple other requests to include in the subgroup being based at least part on a determined priority of each of the other requests, such that each request of the subgroup is determined to be of higher priority than other requests that are not in the subgroup; and

for each of the requests of the subgroup, initiating execution of the respective program of the request on at least one of the multiple allocated computing nodes that is not currently executing programs on behalf of the users of the first group.

31. The non-transitory computer-readable medium of claim 27 wherein the computer-readable medium is a memory of the configured computing system that stores the contents, and wherein the contents are instructions that when executed program the configured computing system to perform the method.