Innovative Caching Method Honored With Best Paper at SOSP

Friday, November 19, 2021 - by Aaron Aupperlee

Computer science Ph.D. student Sara McAllister led a research team that developed a better way to use flash memory to cache tiny objects. Their system reduced the number of times an item wasn't found in the cache by 29%.

Caching tiny objects can be a big deal to social media companies, IoT devices and other services scattered across the internet. Items like a tweet, the connections of a social network or identifying information about a smart doorbell may all be small in size — about 100 to 200 bytes — but delivering them quickly is largely important.

Sara McAllister, a Ph.D. student in computer science at Carnegie Mellon University, led a research team that developed a better way to use flash to cache tiny objects. Kangaroo collects as many tiny objects as possible before caching them to flash memory, reducing the number of writes to a disk and the space needed to index the contents. The system reduced the number of times an item wasn't found in the cache, called misses, by 29%.

"Kangaroo's design hasn't been tried in caching before," McAllister said. "Just like kangaroos rechew their food before digesting, we're rechewing objects every time they are rewritten to the cache."

Their paper, "Kangaroo: Caching Billions of Tiny Objects on Flash" received the Best Paper award at the 2021 Symposium on Operating Systems Principles (SOSP) conference. Kangaroo was tested using Facebook and Twitter workloads and performed better than existing options. Kangaroo is available on GitHub and was implemented in Facebook's CacheLib.

"Having effective caches mean your internet service will load and provide information much more quickly," McAllister said. "And it will make it cheaper, decreasing the cost of infrastructure."

For more information, Contact:
Aaron Aupperlee | 412-268-9068 | aaupperlee@cmu.edu