A flash cache that stops punishing small objects
Flash caches have a dirty secret: they are terrible at caching tiny objects. Objects around 100 bytes or less force existing flash cache designs into a trade-off between excessive DRAM usage or excessive flash writes. Kangaroo, a new flash cache design developed by Meta (then Facebook) and Carnegie Mellon University, aims to close that gap. The work took the Best Paper award at SOSP 2021 and is implemented inside CacheLib, Meta's open-source caching engine, meaning developers can use it through CacheLib's standard API.
Kangaroo is optimized specifically for small objects and targets the two dominant flash cache architectures, both of which struggle with them. Set-associative caches must write a full 4 KB flash page for every object, regardless of object size. For a 100-byte object, that is roughly 40x write amplification. Log-structured caches avoid that problem but need an in-DRAM index entry for every object on flash, which quickly becomes untenable at billions of objects.
Kangaroo's solution is to combine both designs into a hybrid with two tiers: KLog, a small log-structured cache, and KSet, a large set-associative cache. This decomposition lets Kangaroo keep DRAM overhead low while amortizing flash writes.
The key innovation is in how objects move between tiers. KLog is small — about 5 percent of total flash capacity — so its entire index fits in a modest amount of DRAM. When objects are evicted from KLog, Kangaroo is careful about where they go. Instead of writing each object to KSet individually, it searches KLog for multiple objects that map to the same KSet set. Writing to a flash set costs a full 4 KB regardless of how many objects are inserted, so batching two objects into one set write cuts the per-object write cost in half. This mechanism lets Kangaroo amortize KSet writes across multiple objects and keep total flash writes low.
Kangaroo also takes advantage of its position as a cache rather than a key-value store. A threshold admission policy evicts objects outright when fewer than n objects are queued for insertion into KSet from KLog, rather than paying the write cost for a sparse set. This guarantees that KSet write overhead stays far below that of a conventional set-associative cache. Additional optimizations in the full paper further trim DRAM usage and reduce miss rates.
Why tiny objects need a different cache
Caches exist to cut load on databases and other backend services. Flash is the practical medium for caches that are too large for DRAM, but the architectural mismatch with small objects has left that capacity largely untapped. Prior designs either consumed enough DRAM to erase flash's cost advantage or wore out flash devices with write amplification. The practical consequence is smaller effective caches and heavier backend load.
That matters because tiny objects are not a corner case. Social graph edges at Facebook — the links connecting friends, posts, and images — average under 100 bytes, and many IoT and social media workloads look similar. Efficiently caching those objects on flash means faster access at scale and less pressure on storage systems. Kangaroo's low DRAM and write overheads directly attack the miss ratio that forces traffic back to those backends.
The design was validated with production trace replays from Facebook and Twitter social graph workloads. Under realistic DRAM and write-rate constraints, Kangaroo reduced cache misses by 29 percent compared with prior state-of-the-art flash caches. A shadow deployment at Facebook corroborated the simulation results. The full paper, Kangaroo: Caching billions of tiny objects on flash, is available from the SOSP 2021 proceedings.
