|
|
Adaptive Optimization
- The computer industry is reaching a consensus that large scale systems should be self-managing and self-optimizing. Otherwise, too many human experts would be needed to manage them, and their performance will still be inadequate because of the constant and unpredictable 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 take actions that aim to improve the situation, but since they are specified 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 optimally.
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 the Sun Labs technical report 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.
Sometimes there are no clear tunable knobs in the system, and hence a heuristic algorithm for gradually improving the desired objective function over time is all we can hope for. An example of such a domain is management of the database buffer cache, where the goal is to come up with an algorithm for deciding which cache blocks to evict when a cache miss occurs and a new data block needs to be stored in the cache. Working jointly with Garret Swart, we developed a new cache replacement algorithm that outperformed by a large margin in our simulations all existing algorithms we could find in the literature in the complex scenario when data blocks were distributed among multiple devices with different access latencies. Two patent applications were submitted for this work and the paper Analytical Cache Replacement for Large Caches and Multiple Block Containers was submitted to an external conference. We are also currently evaluating the benefit of using ideas from this cache replacement work in other areas of the Oracle DB.
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. A recent application of these ideas at Oracle is 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 an intern 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. Some examples of how this methodology was applied to real problems can be found in the following Sun Labs technical reports:
|
- Analytical Cache Replacement for Large Caches and Multiple Block Containers
- David Vengerov, Garret Swart, Conference Publication, (2011)
- Adaptive Data-Aware Utility-Based Scheduling in Resource-Constrained Systems
- David Vengerov, Lykomidis Mastroleon, Declan Murphy, Nick Bambos, Article, (2010)
- A Reinforcement Learning Framework for Utility-Based Scheduling in Resource-Constrained Systems
- David Vengerov, Article, (2009)
- Adaptive Optimization of the Sun Java Real-Time System Garbage Collector
- Qian Zhu, David Vengerov, Technical Report, (2009)
- Dynamic Adaptation of User Migration Policies in Distributed Virtual Environments
- David Vengerov, Technical Report, (2009)
- Modeling, Analysis and Throughput Optimization of a Generational Garbage Collector
- David Vengerov, Technical Report, (2009)
- A Reinforcement Learning Framework for Online Data Migration in Hierarchical Storage Systems
- David Vengerov, Article, (2008)
- A Gradient-Based Reinforcement Learning Approach to Dynamic Pricing in Partially-Observable Environments
- David Vengerov, Technical Report, (2007)
- A Reinforcement Learning Approach to Dynamic Resource Allocation.
- David Vengerov, Article, (2007)
- Adaptive Data-Aware Utility-Based Scheduling in Resource-Constrained Systems
- David Vengerov, Lykomidis Mastroleon, Declan Murphy, Nick Bambos, Technical Report, (2007)
- Comprehensive Multivariate Extrapolation Modeling of Multiprocessor Cache Miss Rates
- David Vengerov, Article, (2007)
- Dynamic Tuning of Online Data Migration Policies in Hierarchical Storage Systems using Reinforcement Learning*
- David Vengerov, Technical Report, (2006)
- Reinforcement Learning Approach to Dynamic Resource Allocation, A
- David Vengerov, Technical Report, (2005)
- Reinforcement Learning Framework for Utility-Based Scheduling in Resource-Constrained Systems, A
- David Vengerov, Technical Report, (2005)
|
|
|
Oracle Labs