Predicting long-term computing resource usage

• US 8,499,066 B1
• Filed: 12/06/2010
• Issued: 07/30/2013
• Est. Priority Date: 11/19/2010
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Zhang, Zhuo, Subramanian, Swaminathan, Siddiqui, Muhammad Ali
• Primary Examiner(s): CHEN, ALAN S
• Application Number:
  US12/961,285
• Time in Patent Office: 967 Days
• Field of Search: None
• US Class Current: 709/223
• CPC Class Codes: G06F 2209/5019 Workload prediction
• CPC Class Codes: G06F 9/06 using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: H04L 47/823 Prediction of resource usage
• CPC Class Codes: H04L 47/83 based on usage prediction

Abstract

Techniques are described for performing automated predictions of program execution capacity or other capacity of computing-related hardware resources that will be used to execute software programs in the future, such as for a group of computing nodes that execute one or more programs for a user. The predictions that are performed may in at least some situations be based on historical data regarding corresponding prior actual usage of execution-related capacity (e.g., for one or more prior years), and may include long-term predictions for particular future time periods that are multiple months or years into the future. In addition, the predictions of the execution-related capacity for particular future time periods may be used in various manners, including to manage execution-related capacity at or before those future time periods, such as to prepare sufficient execution-related capacity to be available at those future time periods.

Claims

1. A computer-implemented method comprising:

receiving, by one or more configured computing systems, historical data about prior execution of one or more indicated software programs during a prior interval of time including a plurality of months;

analyzing, by the one or more configured computing systems, the historical data to determine multiple day-of-week average program execution capacities used during the prior interval time and to determine multiple month-of-year average program execution capacities used during the prior interval time;

identifying, by the one or more configured computing systems, a future event that is expected to occur during a future interval of time including a plurality of months and that is expected to influence program execution capacity that will be used by the indicated software programs during a subset of the future interval of time, the identifying being based at least in part on information distinct form the received historical data;

generating, by the one or more configured computing systems, predictions of future program execution capacity that will be used for execution of the indicated software programs during multiple individual future days of the future interval of time, the generating of the predictions including determining the predicted future program execution capacity for individual future days based in part on one of the multiple determined day-of-week average program execution capacities and based in part on one of the multiple determined month-of-year average program execution capacities, the generating of the predictions further including adjusting the determined predicted future program execution capacity for at least one of the multiple individual future days to reflect the influence of the identified future event; and

initiating, by the one or more configured computing systems, use of the generated predictions to control program execution capacity that is available for the execution of the indicated software programs during the at least one future day.

2. The method of claim 1 wherein the historical data is based on prior execution of the indicated software programs during the prior interval of time by a group of multiple computing nodes, and wherein the initiating of use of the generated predictions of the future program execution capacities includes, for the at least one future day, altering the computing nodes that are part of the group for that future day to reflect the generated prediction of the future program execution capacity for that future day.

3. The method of claim 2 wherein the one or more configured computing systems provide a program execution service, wherein the multiple computing nodes of the group are a subset of a plurality of computing nodes of the program execution service, and wherein the altering of the computing nodes that are part of the group is performed by the program execution service and includes at least one of adding one or more additional computing nodes to the group or of removing one or more existing computing nodes from the group.

4. The method of claim 2 wherein the historical data includes an amount of actual program execution capacity that was provided for the prior execution of the indicated software programs by the group of multiple computing nodes during a plurality of distinct prior days, wherein the amounts of actual program execution capacity that were provided by the group of multiple computing nodes during the prior interval of time include at least one of a quantity of computing nodes that are in the group for the plurality of distinct prior days, a quantity of pages of information that are supplied to requesters during the plurality of distinct prior days, or a quantity of received requests that are handled during the plurality of distinct prior days, and wherein the altering of the computing nodes that are part of the group for the at least one future day includes at least one of acquiring one or more additional computing nodes to be added to the group before the at least one future day or provisioning one or more additional computing nodes to be available for the group for the at least one future day.

5. The method of claim 1 wherein the prior interval of time further includes a plurality of years, wherein the analyzing of the historical data further includes estimating one or more yearly average program execution capacity growth values based at least in part on the received historical data, and wherein the generating of the predictions includes adjusting the determined predicted future program execution capacity for the at least one future day based on at least one of the one or more estimated yearly average program execution capacity growth values.

6. The method of claim 5 wherein the received historical data includes actual prior time-series data, wherein the generated predictions of the future program execution capacities for the multiple future days include predicted time-series data, and wherein the determining of the multiple day-of-week average program execution capacities and the determining of the multiple average month-of-year program execution capacities is performed for multiple days-of-week values and multiple months-of-year values and includes at least one of computing an average variation for at least one of the days-of-week values or of computing an average variation for at least one of the months-of-year values.

7. The method of claim 5 wherein the generated predicted future program execution capacity for the at least one future day is an expected future program execution capacity value for the at least one future day, and wherein the generating of the prediction for the multiple future days further includes generating a range of predicted future program execution capacity values for the at least one future day that includes the expected future program execution capacity value and that has at least one of an upper bound or a lower bound.

8. The method of claim 7 wherein the generated range of predicted future program execution capacity values for the multiple future days includes determining at least one of an uncertainty level in the expected future program execution capacity value for the at least one future day and of a confidence interval for the expected future program execution capacity value for the at least one future day.

9. The method of claim 1 wherein the influence of the identified future event includes an expected amount of adjustment of the future program execution capacity that will be used during the multiple individual future days, and wherein the identified future event includes at least one of a future holiday that is expected to affect the execution of the indicated software programs, a scheduled advertising campaign that is expected to affect the execution of the indicated software programs, or a planned change in future availability of an item or of functionality that will be available via the execution of the indicated software programs.

10. A non-transitory computer-readable medium whose contents configure a computing system to perform a method, the method comprising:

analyzing historical data about prior execution of one or more programs during a prior time interval to determine multiple average execution capacities used during the prior time interval that are specific to one of multiple time period categories, at least one of the multiple time period categories including multiple of a plurality of distinct prior time periods during the prior time interval;

identifying a future event that is expected to occur during a future time interval, the identifying of the future event being based at least in part on information distinct from the analyzed historical data;

generating, for at least one of multiple future time periods, a prediction of future execution capacity that will be used for execution of the one or more programs during that future time period, the multiple future time periods being distinct time periods during the future time interval, the generating of the prediction including determining the predicted future execution capacity for that future time period based in part on at least one of the multiple determined average execution capacities that are specific to one or more of the multiple time period categories to which that future time period corresponds;

for the at least one of the multiple future time periods, adjusting the predicted future execution capacity based at least in part on the identifying of the future event; and

initiating use of the generated prediction for the at least one future time period to affect execution capacity that is available for the execution of the one or more programs during the at least one future time period.

11. The non-transitory computer-readable medium of claim 10 wherein the historical data indicates an amount of execution capacity that was used for the prior execution of the one or more programs during the multiple distinct prior time periods, and wherein the amounts of execution capacity used for the prior execution of the one or more programs are amounts of actual program execution capacity that was provided by a group of multiple computing nodes during multiple months prior to the analyzing of the historical data, the amounts of the actual program execution capacity being measured using at least one of a quantity of computing nodes that are in the group for one of the plurality of distinct prior time periods, of a quantity of pages of information that are supplied to requesters during one of the plurality of distinct prior time periods, or of a quantity of received requests that are handled during one of the plurality of distinct prior time periods.

12. The non-transitory computer-readable medium of claim 11 wherein the plurality of distinct prior time periods during the prior time interval are individual days, wherein the multiple future time periods are individual days, and wherein at least one of the multiple time period categories corresponds to a day-of-week or a month-of-year.

13. The non-transitory computer-readable medium of claim 10 wherein the historical data indicates an amount of execution capacity that was used for the prior execution of the one or more programs during each of the plurality of distinct prior time periods, and wherein the indicated amount of execution capacity used for the prior execution of the one or more programs during at least one of the plurality of distinct prior time periods includes a quantity of at least one type of hardware resource that is used by a group of multiple computing nodes to execute the one or more programs during that prior time period.

14. The non-transitory computer-readable medium of claim 13 wherein the one type of hardware resource includes at least one of volatile memory, non-volatile data storage, network bandwidth, non-network communication bandwidth, or CPU instruction execution capabilities.

15. The non-transitory computer-readable medium of claim 10 wherein the prior execution of the one or more programs during the prior time interval is performed by a group of multiple computing nodes that are a subset of a plurality of computing nodes provided by a program execution service, and wherein the initiating of use of the generated predictions of the future execution capacities for the multiple future time periods includes, under control of the program execution service and for at least one of the multiple future time periods, altering the computing nodes that are part of the group for that future time period to reflect the predicted future execution capacity for that future time period.

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

17. A system, 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;

receive historical data that represents an amount of prior execution capacity for one or more programs for each of a plurality of distinct prior days during a prior interval of time;

automatically analyze the historical data to determine multiple average execution capacities for the prior interval time, each of the multiple determined average execution capacities being specific to one of multiple categories that each includes multiple of the plurality of distinct prior days;

identify a future event that is expected to occur during a future interval of time and that is expected to influence execution capacity that will be used by the one or more programs during at least a subset of the future interval of time;

at a first time, automatically generate for each of multiple future days a prediction of future execution capacity that will be used for execution of the one or more programs during that future day, the multiple future days being distinct days during the future interval of time and being after the first time, the automatic generating of the prediction for each of the multiple future days including determining the predicted future execution capacity for that future day based in part on at least one of the multiple determined average execution capacities that are specific to one or more of the multiple categories to which that future day corresponds, the determining of the predicted future execution capacity for each of at least one of the multiple future days including adjusting that predicted future execution capacity for that future day to reflect the influence of the identified future event based on that future day being part of the at least subset of the future interval of time; and

initiate use of the generated predictions of the future execution capacities for the multiple future day to affect execution capacity that is available for the execution of the one or more programs during those multiple future days.

18. The system of claim 17 wherein the prior interval of time includes multiple prior months before the first time, wherein the future interval of time includes multiple future months after the first time, and wherein the multiple categories each correspond to at least one of a day-of-week and of a month-of-year.

19. The system of claim 18 wherein the historical data is based on prior execution by a group of multiple computing nodes of the one or more programs during the prior interval of time, and wherein the amounts of execution capacity used for the prior execution of the one or more programs during the plurality of distinct prior days are tracked amounts of actual program execution capacity that was provided by the group of multiple computing nodes on those prior days.

20. The system of claim 17 wherein the historical data is received from a remote client on whose behalf the generating of the predictions of the future execution capacities for the multiple future days is performed, and wherein the initiating of use of the generated predictions of the future execution capacities for the multiple future days includes supplying the generated predictions of the future execution capacities for the multiple future days to the remote client to enable the remote client to control the execution capacity that is available for the execution of the one or more programs during those multiple future days.

21. The system of claim 20 wherein the identifying of the future event includes receiving information from the remote client about the at least subset of the future interval of time for the future event and about an amount of the influence on the execution capacity that will be used by the one or more programs during the at least subset of the future interval of time.

22. The system of claim 17 wherein the historical data is generated without the one or more programs being executed during the prior interval of time.

23. The system of claim 17 wherein the system includes 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 historical data is based on prior execution of the one or more programs during the prior interval of time by a group of multiple computing nodes that are a subset of the plurality of computing nodes, and wherein the initiating of use of the generated predictions of the future execution capacities for the multiple future days includes, for each of one or more of those multiple future days, altering the computing nodes that are part of the group for that future day to reflect the generated prediction of the future execution capacity for that future day.

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

25. The system of claim 17 wherein the one or more modules consist of one or more means for:

receiving historical data that represents an amount of prior execution capacity for one or more programs for each of a plurality of distinct prior days during a prior interval of time;

automatically analyzing the historical data to determine multiple average execution capacities for the prior interval time, each of the multiple determined average execution capacities being specific to one of multiple categories that each includes multiple of the plurality of distinct prior days;

identifying a future event that is expected to occur during a future interval of time and that is expected to influence execution capacity that will be used by the one or more programs during at least a subset of the future interval of time;

at a first time, automatically generating for each of multiple future days a prediction of future execution capacity that will be used for execution of the one or more programs during that future day, the multiple future days being distinct days during the future interval of time and being after the first time, the automatic generating of the prediction for each of the multiple future days including determining the predicted future execution capacity for that future day based in part on at least one of the multiple determined average execution capacities that are specific to one or more of the multiple categories to which that future day corresponds, the determining of the predicted future execution capacity for each of at least one of the multiple future days including adjusting that predicted future execution capacity for that future day to reflect the influence of the identified future event based on that future day being part of the at least subset of the future interval of time; and

initiating use of the generated predictions of the future execution capacities for the multiple future day to affect execution capacity that is available for the execution of the one or more programs during those multiple future days.