Abstract
This study investigates the use of reinforcement learning to guide a generalpurpose cache manager decisions. Cache managers directly impact the overallperformance of computer systems. They govern decisions about which objectsshould be cached, the duration they should be cached for, and decides on whichobjects to evict from the cache if it is full. These three decisions impactboth the cache hit rate and size of the storage that is needed to achieve thatcache hit rate. An optimal cache manager will avoid unnecessary operations,maximise the cache hit rate which results in fewer round trips to a slowerbackend storage system, and minimise the size of storage needed to achieve ahigh hit-rate. This project investigates using reinforcement learning in cache management bydesigning three separate agents for each of the cache manager tasks.Furthermore, the project investigates two advanced reinforcement learningarchitectures for multi-decision problems: a single multi-task agent and amulti-agent. We also introduce a framework to simplify the modelling ofcomputer systems problems as a reinforcement learning task. The frameworkabstracts delayed experiences observations and reward assignment in computersystems while providing a flexible way to scale to multiple agents. Simulation results based on an established database benchmark system showthat reinforcement learning agents can achieve a higher cache hit rate overheuristic driven algorithms while minimising the needed space. They are alsoable to adapt to a changing workload and dynamically adjust their cachingstrategy accordingly. The proposed cache manager model is generic andapplicable to other types of caches, such as file system caches. This projectis the first, to our knowledge, to model cache manager decisions as amulti-task control problem.
Quick Read (beta)
RLCache: Automated Cache Management Using Reinforcement Learning.
Sami Alabed
Girton College
[24pt]
A dissertation submitted to the University of Cambridge
in partial fulfilment of the requirements for the degree of
Master of Philosophy in Advanced Computer Science
University of Cambridge
Computer Laboratory
William Gates Building
15 JJ Thomson Avenue
Cambridge CB3 0FD
United Kingdom
Email: [email protected]
October 10, 2019
Declaration
I Sami Alabed of Girton College, being a candidate for the M.Phil in Advanced Computer Science, hereby declare that this report and the work described in it are my own work, unaided except as may be specified below, and that the report does not contain material that has already been used to any substantial extent for a comparable purpose.
Total word count: 15,000
Signed:
Date:
This dissertation is copyright ©2019 Sami Alabed.
All trademarks used in this dissertation are hereby acknowledged.
Acknowledgements
I would like to express gratitude to my supervisor Dr. Eiko Yoneki for valuable and constructive suggestions during the planning and development of this research work. I would also like to especially thank Michael Schaarschmidt for the constant mentoring, intellectual discussions, and encouragements throughout the various ups and downs of this project. Additionally, I would like to thank Raad Aldakhil and Mihai Bujanca for their proof-reading of this report and comments.
Abstract
This study investigates the use of reinforcement learning to guide a general purpose cache manager decisions. Cache managers directly impact the overall performance of computer systems. They govern decisions about which objects should be cached, the duration they should be cached for, and decides on which objects to evict from the cache if it is full. These three decisions impact both the cache hit rate and size of the storage that is needed to achieve that cache hit rate. An optimal cache manager will avoid unnecessary operations, maximise the cache hit rate which results in fewer round trips to a slower backend storage system, and minimise the size of storage needed to achieve a high hit-rate.
Current approaches assume characteristics of underlying data and use rule-based mechanisms that are tailored for the general case. Caches are exposed to a changing workload regularly, especially the caches at a lower level of the stack. For example, a cache in front of a general purpose database that is used by several different services observes a varying level of traffic patterns. Rule-based methods are static and do not adapt to changes in workload, resulting in the cache operating in a sub-optimal state. Using reinforcement learning, the system learns ideal caching policies tailored to individual systems and the traffic pattern it observes without any prior assumption about the data.
This project investigates using reinforcement learning in cache management by designing three separate agents for each of the cache manager tasks. Furthermore, the project investigates two advanced reinforcement learning architectures for multi-decision problems: a single multi-task agent and a multi-agent. We also introduce a framework to simplify the modelling of computer systems problems as a reinforcement learning task. The framework abstracts delayed experiences observations and reward assignment in computer systems while providing a flexible way to scale to multiple agents.
Simulation results based on an established database benchmark system show that reinforcement learning agents can achieve a higher cache hit rate over heuristic driven algorithms while minimising the needed space. They are also able to adapt to a changing workload and dynamically adjust their caching strategy accordingly. The proposed cache manager model is generic and applicable to other types of caches, such as file system caches. This project is the first, to our knowledge, to model cache manager decisions as a multi-task control problem.
introduction background cache-manager evaluation summary