Who Is More Adaptive? ACME: Adaptive Caching Using Multiple Experts

Abstract

The trend in cache design research is towards finding the single optimum replacement policy that performs better than any other proposed policy by using all the useful criteria at once. However, due to the variety of workloads and system topologies it is daunting, if not impossible, to summarize all this information into one magical value using any static formula. We propose a workload and topology adaptive cache management algorithm to address this problem. Based on proven machine learning techniques, this algorithm uses a weighted voting mechanism guided by a pool of cache replacement policies. Objects that collect the highest total vote from all policies stay in the cache. The policies that predict the workload well are rewarded by an increase in their weight and the policies that lead to wrong decisions are punished by a decrease in their weight. Weight adjustments of the replacement policies, or caching experts, are managed by extremely powerful but computationally simple machine learning algorithms. The scheme is different from hybrid criteria schemes and partitioned cache management policies because it is adaptive, and because it favors objects that are rated highly by many policies rather than simply favoring objects with high weight by a single, possibly complex policy.