How RRIParoo Works

RRIParoo

RRIParoo is usage-based eviction without a DRAM index. Usage-based eviction policies can significantly improve miss ratio, effectively doubling the cache size (or more) without actually adding any resources. Unfortunately, implementing these policies on set-associative flash caches is hard, as such policies involve per-object metadata that must be updated whenever an object is accessed.

Most flash caches use FIFO eviction, which keeps no per-object state. Unfortunately, FIFO significantly increases miss ratio because popular objects continually cycle out of the cache.

Kangaroo introduces RRIParoo, a new technique to efficiently support usage-based eviction policies in flash caches. Specifically, RRIParoo implements RRIPRRIP, a state-of-the-art eviction policy originally proposed for processor caches, while using only ≈1 bit of DRAM per object and without any additional flash writes.