Predictive governing of dynamic modification of program execution capacity

• US 8,346,921 B1
• Filed: 11/19/2010
• Issued: 01/01/2013
• Est. Priority Date: 11/19/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Goodspeed, Joshua M., Zhang, Zhuo, Subramanian, Swaminathan, Siddiqui, Muhammad Ali
• Primary Examiner(s): Etienne, Ario
• Assistant Examiner(s): SALL, EL HADJI MALICK
• Application Number:
  US12/950,630
• Time in Patent Office: 774 Days
• Field of Search: 709/200, 709/203, 709/218, 709/220, 709/223, 709/224, 709/246, 718/102, 714/47.1
• US Class Current: 709/224
• CPC Class Codes: G06F 2209/5019 Workload prediction
• CPC Class Codes: G06F 2209/508 Monitor
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Techniques are described for managing program execution capacity or other capacity of computing-related hardware resources used to execute software programs, such as for a group of computing nodes that is in use executing one or more programs for a user. Dynamic modifications to the program execution capacity of the group may include adding or removing computing nodes, such as in response to automated determinations that previously specified triggers are currently satisfied, and may be automatically governed at particular times based on automatically generated predictions of program execution capacity that will be used at those times by the group, such as to verify that requested dynamic execution capacity modifications at a time are within the predicted execution capacity values for that time. 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 automatically governing dynamic modification of program execution capacity, the method comprising:

receiving information from a first user of a program execution service that specifies an initial quantity of computing nodes to provide program execution capacity for use in executing an indicated software program for the first user and that specifies one or more capacity modification triggers for use in later initiating automated modifications to the program execution capacity during the executing of the indicated software program, wherein each of the capacity modification triggers includes one or more criteria for use in determining if the capacity modification trigger is satisfied and includes a specified computing node quantity change, wherein the receiving of the information is performed by one or more computing systems that are configured to provide the program execution service, and wherein the program execution service has a plurality of computing nodes that are configurable to execute programs of the users of the program execution service;

automatically generating predictions of future execution capacity that will be used for the executing of the indicated software program for the first user, wherein the automatic generating of the predictions of the future execution capacity includes obtaining historical time-series data indicating prior quantities of computing nodes used to provide program execution capacity at multiple times during multiple prior executions of the indicated software program and includes generating predicted time-series data for multiple future times based on the obtained historical time-series data, and wherein the generating of the predicted time-series data for the multiple future times is performed by the one or more configured computing systems and includes determining for each of the multiple future times a range of authorized computing node quantities for that future time that has a lower bound of the range and an upper bound of the range;

after the automatic generating of the predictions of the future execution capacity, automatically determining a group of multiple of the plurality of computing nodes for use in executing the indicated software program for the first user, wherein the multiple computing nodes of the group are of the initial quantity specified by the first user, and automatically providing the multiple computing nodes of the group at a first time for use in providing the program execution capacity for the executing of the indicated software program by the first user; and

automatically managing the computing nodes of the group during the executing of the indicated software program at each of one or more of the multiple future times, wherein the automatic managing is performed by the one or more configured computing systems and includes;

automatically determining that one of the specified capacity modification triggers is currently satisfied at the future time;

automatically determining a new quantity of computing nodes of the group that would result if the specified computing node quantity change for the one satisfied specified capacity modification trigger is performed;

automatically determining if the new quantity of computing nodes is authorized based on being within the determined range of authorized computing node quantities for the future time from the generated predicted time-series data;

if it is automatically determined that the new quantity of computing nodes is authorized, automatically providing the new quantity of the computing nodes in the group for the first user at the future time by performing the specified computing node quantity change for the one satisfied specified capacity modification trigger; and

if it is not automatically determined that the new quantity of computing nodes is authorized, automatically selecting an altered quantity of computing nodes that is within the range of authorized computing node quantities for the future time, and automatically providing the altered quantity of the computing nodes in the group for the first user at the future time.

2. The method of claim 1 wherein the managing of the computing nodes of the group during the executing of the indicated software program includes automatically monitoring the computing nodes of the group to determine performance characteristics from operation of those computing nodes, wherein the automatic determining that one of the specified capacity modification triggers is currently satisfied at each of the one or more future times is based on the determined performance characteristics, wherein the program execution service is a fee-based network-accessible service and the first user is one of multiple users of the program execution service, and wherein the first user pays a first fee for the providing of the multiple computing nodes of the group at the first time and pays a distinct second fee for providing of a modified quantity of computing nodes of the group at a later second time.

3. A computer-implemented method for automatically governing dynamic modification of program execution capacity, the method comprising:

receiving information that specifies an initial amount of program execution capacity for a first user of a program execution service to use in executing one or more software programs and that specifies one or more capacity modification triggers for use in later initiating modifications to the program execution capacity for the first user during the executing of the one or more software programs, wherein the receiving of the information is performed by one or more computing systems that are configured to provide the program execution service, and wherein the program execution service has a plurality of computing nodes that are configurable to execute programs of multiple users;

automatically generating predictions of future execution capacity that will be used for the executing of the one or more software programs for the first user at each of multiple future times, wherein the automatic generating of the predictions of the future execution capacity is performed by the one or more configured computing systems and includes determining for each of the multiple future times a range of authorized execution capacity amounts for that future time that has a lower bound of the range and an upper bound of the range; and

automatically providing the program execution capacity for the first user for use in the executing of the one or more software programs, wherein the automatic providing of the program execution capacity is performed by the one or more configured computing systems and includes, at a first time, using a group of multiple of the plurality of computing nodes for the first user to provide the initial amount of program execution capacity and includes, at one of the multiple future times that is after the first time and is during the executing of the one or more software programs, automatically governing the program execution capacity based on the generated predictions by;

automatically determining that one or more of the specified capacity modification triggers are satisfied, wherein the one or more satisfied specified capacity modification triggers correspond to an indicated modification to the program execution capacity for the first user that would produce a resulting new amount of the program execution capacity if the indicated modification is performed;

automatically determining if the new amount of the program execution capacity is approved for the first user, wherein the new amount of the program execution capacity is determined to be approved if the new amount is within the range of authorized execution capacity amounts for the one future time; and

automatically providing the new amount of the program execution capacity for the first user only if it is automatically determined that the new amount of the program execution capacity is approved for the first user, wherein the providing of the new amount of the program execution capacity includes performing the indicated modification to the program execution capacity for the first user at the one future time by modifying the computing nodes included in the group for the first user.

4. The method of claim 3 wherein the provided program execution capacity is measured based on a quantity of computing nodes that are part of the group, wherein the indicated modification to the program execution capacity reflects an indicated quantity change in the quantity of computing nodes that are part of the group, wherein the automatic determining if the new amount of the program execution capacity is approved for the first user includes automatically determining that the new amount is approved, and wherein the modifying of the computing nodes included in the group for the first user includes modifying the quantity of the computing nodes that are part of the group by performing at least one of adding one or more new computing nodes to the group and of removing at least one of the computing nodes from the group.

5. The method of claim 3 wherein the automatic providing of the program execution capacity for the first user further includes, if it is not automatically determined that the new amount of the program execution capacity is approved for the first user, automatically providing an altered amount of the program execution capacity for the first user at the one future time that is distinct from the new amount and that is within the range of authorized execution capacity amounts for the one future time, the automatic providing of the altered amount of the program execution capacity for the first user including performing an alternative modification to the program execution capacity for the first user at the one future time that is distinct from the indicated modification.

6. The method of claim 5 wherein the automatic determining if the new amount of the program execution capacity is approved for the first user includes automatically determining that the new amount is not approved based on the new amount being larger than the upper bound of the range for the one future time, wherein the provided altered amount of the program execution capacity is automatically selected to be the upper bound of the range for the one future time, and wherein the performed alternative modification to the program execution capacity includes adding one or more additional computing nodes to the group for the first user to reach the provided altered amount of the program execution capacity.

7. The method of claim 5 wherein the automatic determining if the new amount of the program execution capacity is approved for the first user includes automatically determining that the new amount is not approved based on the new amount being smaller than the lower bound of the range for the one future time, wherein the provided altered amount of the program execution capacity is automatically selected to be the lower bound of the range for the one future time, and wherein the performed alternative modification to the program execution capacity includes removing one or more computing nodes from the group for the first user to reach the provided altered amount of the program execution capacity.

8. The method of claim 3 wherein the automatic providing of the program execution capacity for the first user further includes, if it is not automatically determined that the new amount of the program execution capacity is approved for the first user, automatically notifying the first user that the indicated modification based on the satisfied one or more specified capacity modification triggers is not approved.

9. The method of claim 8 wherein the automatic determining if the new amount of the program execution capacity is approved for the first user includes automatically determining that the new amount is not approved, and wherein the method further comprises, if approval of the new amount is received from the first user in response to the notifying, automatically determining that the new amount of the program execution capacity is approved for the first user, and automatically providing the new amount of the program execution capacity for the first user.

10. The method of claim 3 wherein the automatic generating of the predictions of the future execution capacity includes obtaining historical data indicating prior program execution capacity that was used during multiple prior executions of the one or more software programs, and includes performing the generating of the predictions of the future execution capacity at a prior time before the first time based at least in part on the obtained historical data.

11. The method of claim 3 wherein the obtained historical data includes actual time-series data, wherein the generated predictions of the future execution capacity for the multiple future times include predicted time-series data, wherein the performing of the generating of the predictions includes calculating a day-of-week average of program execution capacity used from the obtained historical data and includes computing an average monthly variation of program execution capacity used from the obtained historical data and includes estimating a year-to-year growth in program execution capacity based at least in part on the obtained historical data, and wherein the method further comprises, after the generating of the predictions of the future execution capacity at the prior time and during the executing of the one or more software programs before the first time, automatically updating the generated predictions of the future execution capacity for at least some of the multiple future times based at least in part on information obtained from the executing of the one or more software programs, the at least some future times including the one future time.

12. The method of claim 3 wherein the range of authorized execution capacity amounts determined for each of the multiple future times is a range of computing node quantities and includes a predicted average computing node quantity within the range, and wherein the method further comprises, before the one future time and during the executing of the one or more software programs:

automatically determining that the predicted average computing node quantity within the range for the one future time is larger than a current quantity of the computing nodes in the group; and

automatically initiating provisioning one or more computing nodes to enable the provisioned one or more computing nodes to be available to be added to the group and used for the executing of the one or more software programs at the one future time.

13. The method of claim 3 wherein each of the specified capacity modification triggers includes one or more criteria for use in determining if the capacity modification trigger is satisfied and includes a specified type of modification to the program execution capacity that is to be requested if the capacity modification trigger is satisfied, wherein the method further comprises monitoring the computing nodes of the group to determine current values for one or more types of performance characteristics of those computing nodes related to the executing of the one or more software programs, wherein the one or more criteria of each of at least one of the specified capacity modification triggers are based on one or more specified values for at least one of the one or more performance characteristic types, and wherein the automatic governing of the program execution capacity further includes automatically assessing whether the specified capacity modification triggers are satisfied for each of the multiple future times based at least in part on the monitoring.

14. The method of claim 3 wherein the received information is provided by the first user and includes one or more criteria for use in determining whether to authorize modifications to the program execution capacity for the first user, the one or more criteria being distinct from the specified one or more capacity modification triggers, and wherein the new amount of the program execution capacity is automatically determined to be approved for the first user only if the included one or more criteria are further automatically determined to be satisfied by the indicated modification to the program execution capacity.

15. The method of claim 3 wherein the program execution service is a fee-based network-accessible service that is remote from the multiple users and uses virtualization technology such that the plurality of computing nodes include multiple virtual machines hosted by one or more physical computing systems, wherein the modifying of the computing nodes included in the group for the first user includes automatically provisioning at least one new computing node to be added to the group for the first user and automatically initiating execution of the one or more software programs on the at least one new computing nodes, wherein the first user pays one or more fees for the automatic governing of the program execution capacity based on the generated predictions of the future execution capacity that will be used for the executing of the one or more software programs for the first user, and wherein the method further comprises automatically generating predictions of future execution capacity for each of one or more of the multiple users distinct from the first user and automatically providing execution capacity to each of the one or more users that is governed in accordance with the generated predictions of the future execution capacity for that user.

16. A non-transitory computer-readable medium whose contents configure a computing system to automatically govern dynamic modification of execution capacity, by performing a method comprising:

automatically providing execution capacity for use in executing a software program, wherein the automatic providing of the program execution capacity includes using a group of multiple computing nodes at a first time to provide an initial amount of execution capacity;

automatically obtaining predictions of future execution capacity that will be used for the executing of the software program at each of one or more future times after the first time, wherein the automatic obtaining is performed by the configured computing system, wherein the obtained predictions include a determined lower execution capacity amount and a determined upper execution capacity amount for each of the one or more future times, and wherein the upper execution capacity amount at each of the one or more future times is larger than the lower execution capacity amount at that future time; and

during the executing of the software program, automatically using the obtained predictions to govern the provided execution capacity by;

obtaining an indication of a requested modification to the provided execution capacity for use in the executing of the software program that would produce a resulting new amount of the execution capacity if the requested modification is performed;

automatically determining if the new amount of the execution capacity is approved for the executing of the software program, wherein the new amount of the execution capacity is determined to be approved if the new amount is within a range from the determined lower execution capacity amount for one of the future times to the determined upper execution capacity amount for the one future time; and

automatically providing the new amount of the execution capacity only if it is automatically determined that the new amount of the execution capacity is approved for the executing of the software program, wherein the providing of the new amount of the execution capacity includes performing at the one future time the requested modification to the execution capacity for use in the executing of the software program by modifying the computing nodes included in the group.

17. The non-transitory computer-readable medium of claim 16 wherein the configured computing system is part of one or more computing systems that provide a program execution service having a plurality of computing nodes configurable to execute programs of users of the program execution service, wherein the multiple computing nodes of the group are a subset of the plurality of computing nodes, wherein the automatic providing of the execution capacity is performed by the one or more computing systems in response to configuration information supplied by a first user of the program execution service before the automatic providing of the execution capacity, and wherein the obtaining of the indication of the requested modification to the provided execution capacity is based on an automated determination by the one or more computing systems that a capacity modification trigger is satisfied at the one future time, the capacity modification trigger being specified by the first user as part of the configuration information for use in later initiating modifications to the provided execution capacity, the requested modification being associated with the satisfied capacity modification trigger.

18. The non-transitory computer-readable medium of claim 17 wherein the automatic obtaining of the predictions of the future execution capacity includes automatically generating the predictions of the future execution capacity for the executing of the software program for each of multiple future times after the first time, the automatic generating of the predictions being performed before the first time by the one or more computing systems, the generated predictions for each of the multiple future times including a range of authorized execution capacity amounts for that future time that has a lower bound of the range and an upper bound of the range, the lower bound of the range for the one future time being the determined lower execution capacity amount for the one future time and the upper bound of the range for the one future time being the determined upper execution capacity amount for the one future time.

19. The non-transitory computer-readable medium of claim 16 wherein the automatic obtaining of the predictions of the future execution capacity includes automatically generating by the configured computing system before the first time the predictions of the future execution capacity for the executing of the software program, the generated predictions for the one future time including a range of authorized execution capacity amounts for the one future time that has a lower bound of the range and an upper bound of the range, the lower bound of the range being the determined lower execution capacity amount for the one future time and the upper bound of the range being the determined upper execution capacity amount for the one future time, and wherein the automatic providing of the execution capacity and the automatic using of the obtained predictions to govern the provided execution capacity is performed by one or more other computing systems that provide a program execution service having a plurality of computing nodes configurable to execute programs of users of the program execution service.

20. The non-transitory computer-readable medium of claim 16 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.

21. A system configured to automatically govern dynamic modification of execution capacity, comprising:

one or more processors; and

one or more modules that are configured to, when executed by at least one of the one or more processors, manage execution capacity by;

automatically obtaining predictions of future resource usage capacity that will be used by a first user at each of one or more future times for executing one or more software programs, wherein the one or more future times are after a first time, wherein the obtained predictions include a determined lower resource usage capacity amount and a determined upper resource usage capacity amount for each of the one or more future times, and wherein the upper resource usage capacity amount at each of the one or more future times is larger than the lower resource usage capacity amount at that future time;

automatically providing resource usage capacity at the first time for use by the first user in executing at least one of the one or more software programs, wherein the providing of the resource usage capacity includes using a group of multiple computing nodes to provide an initial amount of resource usage capacity; and

automatically using the obtained predictions to govern the provided resource usage capacity after the first time by;

obtaining an indication of a requested modification to the provided resource usage capacity for the first user that would produce a resulting new amount of the resource usage capacity if the requested modification is performed;

automatically determining if the new amount of the resource usage capacity is approved for the first user, wherein the new amount of the resource usage capacity is determined to be approved if the new amount is within a range from the determined lower resource usage capacity amount for one of the future times to the determined upper resource usage capacity amount for the one future time; and

automatically providing the new amount of the resource usage capacity only if it is automatically determined that the new amount of the resource usage capacity is approved for the first user, wherein the providing of the new amount of the resource usage capacity includes performing the requested modification to the resource usage capacity for the first user by modifying the computing nodes included in the group.

22. The system of claim 21 wherein the system includes one or more computing systems that each includes at least one of the one or more processors and that are configured to provide a program execution service having a plurality of computing nodes configurable to execute programs of users of the program execution service, wherein the multiple computing nodes of the group are a subset of the plurality of computing nodes, wherein the obtained predictions of future resource usage capacity are predictions of future program execution capacity, wherein the determined lower resource usage capacity amount for each of the one or more future times is a determined lower program execution capacity amount for that future time, wherein the determined upper resource usage capacity amount for each of the one or more future times is a determined upper program execution capacity amount for that future time, wherein the automatic providing of the resource usage capacity includes automatically providing program execution capacity and is performed by at least one of the one or more computing systems in response to configuration information supplied by the first user before the automatic providing of the program execution capacity, and wherein the obtaining of the indication of the requested modification is based on an automated determination by the at least one computing systems that a capacity modification trigger is satisfied at the one future time, the capacity modification trigger being specified by the first user as part of the configuration information for use in later initiating modifications to the provided program execution capacity, the requested modification being associated with the satisfied capacity modification trigger.

23. The system of claim 22 wherein the automatic obtaining of the predictions of the future program execution capacity includes automatically generating the predictions of the future program execution capacity for each of multiple future times after the first time and is based on one or more indicated software programs to be executed by the first user using the provided program execution capacity, the automatic generating of the predictions being performed before the first time by at least one of the one or more configured computing systems, the generated predictions for each of the multiple future times including a range of authorized program execution capacity amounts for that future time that has a lower bound of the range and an upper bound of the range, the lower bound of the range for the one future time being the determined lower program execution capacity amount for the one future time and the upper bound of the range for the one future time being the determined upper program execution capacity amount for the one future time.

24. The system of claim 21 wherein the system includes a plurality of hardware resources of one or more types that are available for use in executing software programs of one or more users, wherein the multiple computing nodes of the group are associated with a subset of the plurality of hardware resources, wherein the obtained predictions of future resource usage capacity are predictions of future capacity of usages of hardware resources of the one or more types, wherein the determined lower resource usage capacity amount for each of the one or more future times is a determined lower capacity amount for using hardware resources of the one or more types for that future time, wherein the determined upper resource usage capacity amount for each of the one or more future times is a determined upper capacity amount for using hardware resources of the one or more types for that future time, wherein the automatic providing of the resource usage capacity includes automatically providing capacity for using at least some of the plurality of hardware resources of the one or more types and is performed in response to configuration information supplied by the first user before the automatic providing of the resource usage capacity, and wherein the obtaining of the indication of the requested modification is based on an automated determination by the one or more modules that a capacity modification trigger is satisfied at the one future time, the capacity modification trigger being specified by the first user as part of the configuration information for use in later initiating modifications to the provided resource usage capacity, the requested modification being associated with the satisfied capacity modification trigger.

25. The system of claim 24 wherein the system includes one or more computing systems that each includes at least one of the one or more processors, wherein the automatic obtaining of the predictions of the future resource usage capacity includes automatically generating the predictions of the future resource usage capacity for each of multiple future times after the first time and is based on one or more indicated software programs to be executed by the first user using the provided resource usage capacity, the automatic generating of the predictions being performed before the first time by at least one of the one or more computing systems, the generated predictions for each of the multiple future times including a range of authorized resource usage capacity amounts for that future time that has a lower bound of the range and an upper bound of the range, the lower bound of the range for the one future time being the determined lower resource usage capacity amount for the one future time and the upper bound of the range for the one future time being the determined upper resource usage capacity amount for the one future time.

26. The system of claim 24 wherein the one or more types of the plurality of hardware resources include at least one of volatile memory, non-volatile data storage, network bandwidth, non-network communication bandwidth, and CPU instruction execution capabilities.

27. The system of claim 21 wherein the one or more modules each includes software instructions for execution by the one or more processors.