Tuning software execution environments using Bayesian models

• US 10,257,275 B1
• Filed: 10/26/2015
• Issued: 04/09/2019
• Est. Priority Date: 10/26/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Dirac, Leo Parker, Jenatton, Rodolphe
• Primary Examiner(s): Vu, Viet D
• Application Number:
  US14/923,237
• Time in Patent Office: 1,261 Days
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

An optimizer for a software execution environment determines an objective function and permitted settings for various tunable parameters of the environment. To represent the execution environment, the optimizer generates a Bayesian optimization model employing Gaussian process priors. The optimizer implements a plurality of iterations of execution of the model, interleaved with observation collection intervals. During a given observation collection interval, tunable parameter settings suggested by the previous model execution iteration are used in the execution environment, and the observations collected during the interval are used as inputs for the next model execution iteration. When an optimization goal is attained, the tunable settings that led to achieving the goal are stored.

Claims

1. A system, comprising:

one or more computing devices of an optimization service implemented at a provider network;

wherein the one or more computing devices are configured to;

identify, as a candidate for performance optimization, an execution environment comprising one or more software components, wherein the execution environment has a plurality of tunable parameters, and wherein at least one software component of the one or more software components is instantiated at a particular computing resource of the provider network;

receive, based at least in part on input via a programmatic interface from a client on whose behalf the execution environment is configured, (a) a definition of an objective function that specifies a non-linear transformation of one or more execution results produced by the one or more software components to produce one or more objective function values to be optimized, and (b) a respective plurality of permissible settings for at least a first tunable parameter and a second tunable parameter of the plurality of tunable parameters;

generate, corresponding to the execution environment, a Bayesian model using Gaussian process priors, wherein input to the Bayesian model includes the one or more objective function values and output of the Bayesian model includes settings for at least the first and second tunable parameters;

perform a plurality of iterations of execution of the Bayesian model, including a first iteration and a second iteration, wherein input model parameters for the second iteration are determined based at least in part on an evaluation of the objective function over a set of execution results obtained from the execution environment, wherein the set of execution results are obtained using settings indicated for at least the first and second tunable parameters in output model parameters produced by the first iteration; and

in response to a determination that an optimization goal corresponding to the execution environment has been attained according to the objective function, store settings of at least the first and second tunable parameters which correspond to attainment of the optimization goal.

2. The system as recited in claim 1, wherein the one or more software components include a first application, wherein the first application implements a web service interface to receive client requests generated outside the provider network, wherein the one or more computing devices are configured to:

select a start time and an end time of a first observation collection interval of the first application corresponding to the first iteration of execution of the Bayesian model, wherein the input model parameters for the second iteration are based at least in part on execution results obtained from the first application during the first observation collection interval, and wherein the first application remains online during a time period which begins prior to the start time and ends later than the end time.

3. The system as recited in claim 1, wherein the one or more software components include a first application which is executed in batch mode, wherein a data set of a first batch iteration of the first application differs from a data set of a second batch iteration of the first application, wherein the one or more computing devices are configured to:

collect a first set of execution results corresponding to the first batch iteration of the first application;

generate input model parameters for the first iteration of execution of the Bayesian model based at least in part on the first set of execution results;

modify a setting of the first tuning parameter setting prior to the second batch iteration of the first application, based at least in part on output parameters of the first iteration of execution of the Bayesian model;

collect a second set of execution results corresponding to the second batch iteration of the first application; and

generate input model parameters for the second iteration of execution of the Bayesian model based at least in part on the second set of execution results.

4. The system as recited in claim 1, wherein the one or more computing devices are configured to:

receive, from the client via the programmatic interface, an indication of a conditional relationship between the first tunable parameter and a third tunable parameter of the plurality of tunable parameters; and

determine a covariance function of the Gaussian process based at least in part on the conditional relationship.

5. The system as recited in claim 1, wherein the one or more computing devices are configured to:

determine, based at least in part on an observation validity period associated with the execution environment, that a particular execution result obtained from the execution environment is no longer valid with respect to predicting performance; and

modify, to incorporate an effect of expiration of validity of the particular execution result, one or more parameters of the Bayesian model.

6. A method, comprising:

performing, by a network-accessible optimization tool implemented using one or more computing devices;

identifying, as a candidate for performance optimization, an execution environment comprising one or more software components, wherein the execution environment has a plurality of tunable parameters;

receiving, from a client, (a) a definition of an objective function that specifies a non-linear transformation of one or more execution results produced by the one or more software components to produce as output one or more objective function values to be optimized and (b) a respective plurality of permissible settings for at least a first tunable parameter and a second tunable parameter of the plurality of tunable parameters;

generating, with respect to the execution environment, a Bayesian model employing a Gaussian process, wherein input to the Bayesian model includes the one or more objective function values and output of the Bayesian model includes settings for at least the first and second tunable parameters;

implementing a plurality of iterations of execution of the Bayesian model, including a first iteration and a second iteration, wherein input model parameters for the second iteration are determined based at least in part on an evaluation of the objective function over a set of execution results obtained from the execution environment, wherein the set of execution results is obtained using settings indicated for at least the first and second tunable parameters in output model parameters of the first iteration; and

in response to determining that an optimization goal associated with the execution environment has been attained according to the objective function, storing an indication of settings for at least the first and second tunable parameters which correspond to an attainment of the optimization goal.

7. The method as recited in claim 6, wherein the one or more software components include a first application executing at one or more computing devices of a provider network, wherein the first application implements a programmatic interface to receive client requests, further comprising performing, by the network-accessible optimization tool:

determining a start time and an end time of a first observation collection interval of the first application corresponding to the first iteration of execution of the Bayesian model, wherein the input model parameters for the second iteration of the plurality of iterations are based at least in part on execution results obtained from first application during the first observation collection interval.

8. The method as recited in claim 7, wherein the first application is a distributed application executing at a plurality of computing devices of the provider network, wherein the first tunable parameter comprises a first configuration setting of a particular computing device of the plurality of computing devices, further comprising:

modifying, by the network-accessible optimization tool, the first configuration setting for a second observation collection interval of the first application, without modifying a corresponding configuration setting of another device of the plurality of computing devices for the second observation collection interval.

9. The method as recited in claim 6, wherein the one or more software components include a first application which is executed iteratively in batch mode, wherein a data set of a first batch iteration of the first application differs from a data set of a second batch iteration of the first application, further comprising performing, by the network-accessible optimization tool:

collecting a first set of execution results corresponding to the first batch iteration of the first application;

generating input model parameters for the first iteration of execution of the Bayesian model based at least in part on the first set of execution results; and

modifying the first tuning parameter setting prior to the second batch iteration of the first application, based at least in part on output parameters of the first iteration of execution of the Bayesian model.

10. The method as recited in claim 6, wherein generating the Bayesian model employing a Gaussian process comprise determining a mean and covariance function for the Gaussian process.

11. The method as recited in claim 6, further comprising performing, by the network-accessible optimization tool:

receiving, from the client via a programmatic interface, an indication of at least one permissible setting for the first tunable parameter.

12. The method as recited in claim 6, further comprising performing, by the network-accessible optimization tool:

receiving, from the client via a programmatic interface, an indication of a conditional relationship between the first tunable parameter and a third tunable parameter of the plurality of tunable parameters; and

setting a particular parameter of the Gaussian process based at least in part on the conditional relationship.

13. The method as recited in claim 6, further comprising performing, by the network-accessible optimization tool:

determining, with respect to performance prediction, an observation validity period associated with the execution environment; and

adjusting, prior to a particular iteration of execution the Bayesian model, one or more model parameters of the Bayesian model based at least in part on the observation validity period.

14. The method as recited in claim 6, wherein the first tunable parameter comprises one or more of:

(a) a garbage collection algorithm to be used for memory management, (b) a size of a memory to be allocated, (c) a networking configuration parameter, (d) a number of nodes to be included in a collection of nodes implementing a distributed application, (e) a database configuration parameter, (f) a hypervisor configuration parameter, or (g) a storage device configuration parameter.

15. The method as recited in claim 6, wherein the execution environment is configured on behalf of a particular client of a network-accessible service, further comprising, performing, by the network-accessible optimization tool;

applying, in the execution environment, the settings indicated for at least the first and second tunable parameters in the output model parameters of the selected iteration, without notifying the particular client that the Bayesian model was used to determine the settings.

16. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors:

receiving, from a client, (a) a definition of an objective function that a non-linear transformation of one or more execution results produced by one or more software components in an execution environment to produce as output one or more objective function values to be optimized and (b) a respective plurality of permissible settings for at least a first tunable parameter and a second tunable parameter of a plurality of tunable parameters of the execution environment;

generate, with respect to the execution environment, a Bayesian model employing a Gaussian process, wherein input to the Bayesian model includes the one or more objective function values and output of the Bayesian model includes settings for at least the first and second tunable parameters;

implement a plurality of iterations of execution of the Bayesian model, including a first iteration and a second iteration, wherein input model parameters for the second iteration are determined based at least in part on an evaluation of the objective function over a set of execution results obtained from the execution environment, wherein the set of execution results is obtained using settings indicated for at least the first and second tunable parameters in output model parameters of the first iteration; and

store an indication of settings indicated for at least the first and second tunable parameters in output model parameters of a selected iteration of the plurality of iterations of execution.

17. The non-transitory computer-accessible storage medium as recited in claim 16, wherein to implement a particular iteration of the plurality of iterations of execution of the Bayesian model, the instructions when executed on the one or more processors:

evaluate an acquisition function which models a relationship between at least some tunable parameters of the plurality of tunable parameters and the objective function, without providing an indication of the acquisition function to a particular client on whose behalf the execution environment is configured, and without receiving an indication of the acquisition function from the particular client.

18. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the one or more software components include a first application executing at one or more computing devices of a provider network, wherein the first application implements a programmatic interface to receive client requests, wherein the instructions when executed on one or more processors:

collect, from the execution environment, respective sets of execution results corresponding to a first observation collection interval of the first application and a second observation collection interval of the first application, wherein the first observation collection interval does not overlap with the second observation collection interval, and wherein the first application remains in operation continuously between a start of the first observation collection interval and an end of the second observation collection interval.

19. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the instructions when executed on the one or more processors:

select, prior to a particular observation collection interval corresponding to the one or more software components, a particular permissible setting for the first tunable parameter based at least in part on one or more of;

(a) a random selection from among the plurality of permissible settings of the first tunable parameter, (b) programmatic input received from the client, or (c) contents of a knowledge base.

20. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the instructions when executed on the one or more processors:

determine a conditional relationship between the first tunable parameter and a third tunable parameter of the plurality of tunable parameters; and

set a particular parameter of the Bayesian model based at least in part on the conditional relationship.

21. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the plurality of iterations of execution of the Bayesian model include a third iteration performed after the first iteration and after the second iteration, wherein the instructions when executed on the one or more processors:

assign a first weight to a particular execution result obtained using the settings indicated for at least the first and second tunable parameters in the output model parameters of the first iteration, wherein the first weight is based at least in part on an amount of time elapsed since the particular execution result was obtained from the execution environment;

assign a different weight to a different execution result obtained using settings indicated for at least the first and second tunable parameters in the output model parameters of the second iteration, wherein the different weight is based at least in part on an amount of time elapsed since the different execution result was obtained from the execution environment; and

determine the input model parameters for the third iteration based at least in part on the first weight and the second weight.