PaperCache: In-Memory Caching with Dynamic Eviction Policies

What is it about?

Caches play a critical role in improving the performance of modern computer systems. They temporarily store copies of data that are likely to be needed again soon on media that is faster but more costly, and hence smaller, than the media from which the data was originally obtained. For example, modern processors have caches that use fast but expensive static memory (SRAM) to temporarily store data originally obtained from main memory (DRAM). Our work focuses on in-memory caches that use DRAM to temporarily store copies of data that are stored on storage servers consisting of hard disk drives (HDDs) or solid-state drives (SSDs). DRAM has significantly lower access latencies than storage servers, but is considerably more expensive per byte. As a result, in-memory caches are configured to have a size in the Gigabyte-range, while the size of HDDs or SSDs is often in the Terabyte-range. In-memory caches are ubiquitous in modern distributed systems because they significantly improve the average latency of accessing data and make the system more scalable by decreasing the load on storage servers. For example, consider an in-memory cache serving an e-commerce site; caching information of popular products (e.g., description, price, images, reviews) would speed up average page loading times when customers browse products. Because in-memory caches are limited in size, they must employ an eviction policy that determines which data objects to remove from the cache when the cache is full and a new data object is to be inserted. The most popular eviction policy supported by most in-memory caches is Least Recently Used (LRU) which evicts the least recently accessed data object in the cache. The choice of eviction policy plays a large role in the cache's performance; while the LRU eviction policy excels when the access patterns have high temporal locality (where recently accessed data will likely be accessed again in the near future), other policies, such as Least Frequently Used (LFU), perform better when the access patterns follow Zipfian distributions (where the majority of accesses are to a small amount of data). It can be challenging to select an eviction policy for a cache as access patterns change over time. For example, diurnal access patterns typically see Zipfian-distributed traffic during the day when real users are using the service, while scanning patterns (where all the data is accessed just once) caused by analytics programs are prevalent at night. Unfortunately, in-memory caches today are not able to switch eviction policies at runtime and thus adapt to changing workload patterns. This paper describes PaperCache, a new in-memory cache design which is able to switch between any eviction policy at runtime, as well as periodically and automatically choosing the best eviction policy for the current access pattern. The PaperCache prototype we describe implements eight different eviction policies and is able to switch between any of them at runtime.

Featured Image

Photo by Adam Kring on Unsplash

Photo by Adam Kring on Unsplash

Why is it important?

The choice of eviction policy can greatly affect the performance of a cache, typically measured as the cache's miss ratio (i.e., the ratio of accesses to data that does not exist in the cache to the total number of accesses). Ideally, a cache should have as low a miss ratio as possible. Consider the figure below which shows the miss ratios over time of caches employing the LRU and LFU eviction policies for a real-world cache access trace (Cloudphysics w42). It is quickly apparent that there is no "one size fits all" eviction policy for a cache; the ideal eviction policy changes over time and a cache must adapt to these changes in real-time. We expect PaperCache to benefit both industry and research. For industry, PaperCache has better latency and miss ratio performance than other popular in memory caches. With regard to research, PaperCache allows eviction policy researchers to design more workload-targeted eviction policies as they no longer need to keep the general use case in mind. A good example of this is the Most Recently Used (MRU) eviction policy which has terrible general-case performance, but excels under strict scanning patterns. PaperCache allows researchers to be more creative with how they design eviction policies. Our work follows a common trend of designing self-managing systems which automatically optimize their performance at runtime. Whereas in the past, system administrators were expected to configure and maintain their own services, recently, automated "elastic" services which adapt to changing workloads have gained popularity.