Skip to main content

Hyperbolic Caching: Flexible Caching for Web Applications

Author(s): Blankstein, Aaron; Sen, Siddhartha; Freedman, Michael J

To refer to this page use:
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-toend throughput by ~5-10%.
Publication Date: 2017
Citation: Blankstein, Aaron, Siddhartha Sen, and Michael J. Freedman. "Hyperbolic Caching: Flexible Caching for Web Applications." In USENIX Annual Technical Conference (2017): pp. 499-511.
Pages: 499 - 511
Type of Material: Conference Article
Journal/Proceeding Title: USENIX Annual Technical Conference
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.