Priority-based Dynamic Replacement Cache

Soumyaroop Dutta
Arushi Grove

ABSTRACT

We introduce Priority-based Dynamic Replacement Cache (PDRC), a
low-overhead, scan-resistant cache management system that dynamically
adapts its cache replacement policy to acclimate changing
workloads. By adding priority-based replacement policy to the standard
Least Recently Used (LRU) policy, caches can elegantly handle varying
use cases and minimize the cache miss rate. PDRC performs cache
eviction based on the priority of objects stored in the cache, as well
as, on its last access time. The cache maintains a history of evicted
entries, to dynamically learn the access pattern, and update its
caching policy accordingly. The priorities of these data objects are
constantly promoted or demoted based on the time of last access,
frequency of accesses and eviction history.  PDRC demonstrates evident
improvement in the cache hit rate as compared to that of the popularly
used LRU-based cache replacement systems, by generating a 35.7% higher
hit rate, on average, on increasing cache sizes, and 70.57% higher hit
rate, on average, on increasing number of requests. PDRC also displays
a 24% lower latency than LRU schemes, on average, when using
user-defined caching hints. This paper aims to provide a detailed
description our algorithm and an evaluation of its performance against
LRU caching, while also measuring any potential overheads. Being an
experimental project, PDRC has been evaluated on a small-scale
infrastructure, and yet, it displays surprisingly good results on
various workloads that we generated for its testing.