Facebook engineers have invented a new way to cache billions of small objects in flash that saves DRAM and reduces the flash wear-out rate, and called it Kangaroo.

The company encountered a problem when caching small (<100 bytes) objects in flash as the two existing methods either wore out the flash with too many writes, or needed too much DRAM to index the objects in the flash cache. 

One existing method is the set-associative cache, and this stores cache data in 4KB flash pages. Adding any object to the cache incurs a minimum 4KB write. Facebook has many small objects that are less than 100 bytes in size, such as edges in its social graph. Sticking a 100-byte edge object in a set-associative flash cache means about 40 times too many bytes are written. 

The problem with the second method, log-structured caching, is that an entry in a DRAM cache is needed for every object in the flash cache. If Facebook puts millions of small objects in a flash cache then there is a commensurately sized index in DRAM.

Facebook software engineers Sathya Gunasekar and Jimmy Lu write: “Flash caches require either too much DRAM, which loses the efficiency benefits of flash, or too many writes, which wears out the flash device too quickly. In either case, flash caching fails to live up to its potential as an efficient, large cache for tiny objects.”

The Kangaroo flash cache alternative has a hierarchical design with two parts: KLog, a small log-structured flash cache; and KSet, a large set-associative flash cache. 

The engineers write: “Kangaroo can amortize writes to KSet over multiple objects, decreasing the overall number of bytes written to flash. KLog accomplishes this goal with a small capacity (~5 per cent of flash), so Kangaroo needs only a small amount of DRAM to index KLog’s entire capacity.“

Kangaroo uses KLog to find multiple objects mapping to the same set in KSet. Whenever an object is evicted from KLog, Kangaroo proactively evicts other objects from KLog to minimize write amplification in KSet. 

Kangaroo can reduce cache misses by 29 per cent as well as help extend the working life of SSDs.

The details of how Kangaroo works are described in a downloadable Facebook research paper — “Kangaroo: Caching Billions of Tiny Objects on Flash“ — written by a team of Facebook engineers including Gunasekar and Lu.

Kangaroo is implemented within CacheLib, Facebook’s open source caching engine, and developers can use Kangaroo through CacheLib’s API to build their own customised cache services.