Kangaroo: A flash cache optimized for tiny objects (2021)

Summary

What the research is: Kangaroo is a new flash cache that enables more efficient caching of tiny objects (objects that are ~100 bytes or less) and overcomes the challenges presented by existing flash cache designs. Since Kangaroo is implemented within CacheLib, Facebook’s open source caching engine, developers can use Kangaroo through CacheLib’s API to build their own customized cache services. We partnered with Carnegie Mellon University (CMU) on this research. The resulting paper won the Best Paper award at the 2021 Symposium on Operating Systems Principles (SOSP) conference. CacheLib’s API allows developers to build and customize concurrent caches. Optimized for tiny objects, Kangaroo minimizes dynamic random-access memory (DRAM) usage and the number of writes — and introduces a new cache eviction policy that reduces cache misses with minimal DRAM overhead, further reducing load on back-end storage systems. Kangaroo’s CacheLib implementation also allowed our researchers to quickly evaluate the impact of Kangaroo’s design on real world production workloads. We evaluated Kangaroo using traces from production social graph caching workloads at Facebook and Twitter. Our experiments show Kangaroo reduces misses by 29 percent under realistic system constraints (DRAM and write rate constraints) compared with prior, state-of-the-art flash cache designs. These results are corroborated with a test deployment of Kangaroo in a shadow production setup. Miss ratio for all three systems over a seven-day Facebook trace. Kangaroo reduces cache misses by 29 percent versus set-associative (SA) caches and by 56 percent versus log-structured (LS) caches. How it works: Current flash caches fall into two main categories: set-associative caches and log-structured caches. Set-associative caches write many more bytes than necessary because they have to write a 4 KB flash page — the minimum write granularity — for every object. With tiny objects that are roughly 100 bytes or less in size, th...