Hyperbolic caching: Flexible caching for web applications

Aaron Blankstein, Siddhartha Sen, Michael J. Freedman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

Abstract

Today's web applications rely heavily on caching to reduce latency and backend load, using services like Redis or Memcached that employ inflexible caching algorithms. But the needs of each application vary, and significant performance gains can be achieved with a tailored strategy, e.g., incorporating cost of fetching, expiration time, and so forth. Existing strategies are fundamentally limited, however, because they rely on data structures to maintain a total ordering of the cached items. Inspired by Redis's use of random sampling for eviction (in lieu of a data structure) and recent theoretical justification for this approach, we design a new caching algorithm for web applications called hyperbolic caching. Unlike prior schemes, hyperbolic caching decays item priorities at variable rates and continuously reorders many items at once. By combining random sampling with lazy evaluation of the hyperbolic priority function, we gain complete flexibility in customizing the function. For example, we describe extensions that incorporate item cost, expiration time, and windowing. We also introduce the notion of a cost class in order to measure the costs and manipulate the priorities of all items belonging to a related group. We design a hyperbolic caching variant for several production systems from leading cloud providers. We implement our scheme in Redis and the Django web framework. Using real and simulated traces, we show that hyperbolic caching reduces miss rates by ~10-20% over competitive baselines tailored to the application, and improves end-to-end throughput by ~5-10%.

Original languageEnglish (US)
Title of host publicationProceedings of the 2017 USENIX Annual Technical Conference, USENIX ATC 2017
PublisherUSENIX Association
Pages499-511
Number of pages13
ISBN (Electronic)9781931971386
StatePublished - 2019
Event2017 USENIX Annual Technical Conference, USENIX ATC 2017 - Santa Clara, United States
Duration: Jul 12 2017Jul 14 2017

Publication series

NameProceedings of the 2017 USENIX Annual Technical Conference, USENIX ATC 2017

Conference

Conference2017 USENIX Annual Technical Conference, USENIX ATC 2017
CountryUnited States
CitySanta Clara
Period7/12/177/14/17

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Hyperbolic caching: Flexible caching for web applications'. Together they form a unique fingerprint.

  • Cite this

    Blankstein, A., Sen, S., & Freedman, M. J. (2019). Hyperbolic caching: Flexible caching for web applications. In Proceedings of the 2017 USENIX Annual Technical Conference, USENIX ATC 2017 (pp. 499-511). (Proceedings of the 2017 USENIX Annual Technical Conference, USENIX ATC 2017). USENIX Association.