Offline and Online Algorithms for Cache Allocation with Monte Carlo Tree Search and a Learned Model

Cloud block storage systems rely heavily on the cache server to guarantee system performance. Cache servers serve multi-tenants simultaneously, and the workload of each tenant changes at any time, together with its changed demand for the cache capacity. How to dynamically re-allocate the cache space for each tenant to achieve overall high performance is a crucial problem. The mainstream cache space allocations are usually based on miss ratio curve (MRC) construction. Although it can achieve on-demand allocation, it is not designed for optimal performance: it only considers the performance in a single period, but this does not mean that all periods can achieve optimization. In this paper, we propose a search framework for allocation schemes based on a policy tree, where a path from the root to a tree node corresponds to an allocation scheme from the initial period to that period. We aim to explore the tree nodes in the policy tree to find the optimal allocation scheme. To achieve this, we design an offline cache space allocation method using Monte Carlo Tree Search (Opt-CA) to approach the optimal algorithm, which provides better performance than the MRC method. Guided by Opt-CA, we implement an online Learned Monte Carlo Tree Search based cache allocation scheme (LMCTS-CA) which uses a learning-based model to estimate the hit ratio of each allocation scheme. The experiments with MSR traces show that LMCTS-CA enhances the hit ratio of the cache by 4.55% and reduces the total number of misses by 16.60% compared to the MRC method.