Adaptive Optimization

OVERVIEW

  • The computer industry is reaching a consensus that important systems should be self-managing and self-optimizing. Such systems reduce the need for human intervention and keep their performance at near-optimal levels despite changes in the business environment. Currently, the industry standard approach to policy-based management is to use built-in rules that specify what needs to be done when certain conditions arise. These rules suggest actions for certain prespecified situations, but since they are conceived heuristically and the environment is constantly changing, such built-in rules cannot be expected to always achieve a near-optimal level of performance and sometimes can perform very poorly.

    The main idea of this project is that instead of hand-crafting rules that specify actions the system should take, human administrators should instead specify the optimization goal (performance objective), which the system then automatically tries to achieve. This approach greatly increases the ease of system management, makes systems more adaptable to changes in the business environment and increases the productivity of existing resources because the system can use them more efficiently.

    If the problem of interest is that of dynamically adapting system's parameters so to maximize a certain objective function, then the adaptation problem can be solved using gradient-based optimization of tunable parameters. An example of this methodology is presented in Modeling, Analysis and Throughput Optimization of a Generational Garbage Collector. A more recent example of this methodology applied at Oracle is the joint work with RAC and Database Cloud teams, for whom we designed a gradient-based algorithm for dynamically redistributing the incoming requests among the database instances. This algorithm is guaranteed to converge to the minimal average response time for all requests. Another example of this methodology being used at Oracle is dynamic adjustment of the number of shared DB servers based on the workload changes so as to keep the DB throughput at the maximal level.

    If multiple constraints are presents, then it is possible to optimize the objective function using the Linear Programming methodology if both the objective function and the constraints are linear in the tunable parameters. If nonlinearities are present, then randomized search algorithms (such as Simulated Annealing or Genetic Algorithms) might be used instead. This idea was used in our collaboration with the Retail GBU, which sells to its clients (large chain stores such as Wallgreens) software for periodically recomputing prices for some items in each store (based on the most recent sales rates for all items) so as to keep maximizing the desired objective function such as revenue, profit margin, etc. Together with Kresimir Mihic, we have developed a randomized search algorithm for solving this problem.

    If the future state of the system depends both on the current state and on the most recent action, then the problem can be solved using the Reinforcement Learning (RL) methodology. The following publications describe how this methodology can be applied to optimizing various policies in a cloud data center:

PUBLICATIONS