Linear Elastic Caching via Ski Rental
Abstract
In this work we study the Linear Elastic Caching problem, where
the goal is to minimize the total cost of a cache inclusive of not
just its misses, but also its memory footprint integrated over time.
We demonstrate a theoretical connection to the classic ski rental
problem and propose a practical algorithm that combines online
caching algorithms with ski rental policies. We also introduce a
lightweight machine learning-based algorithm for ski rental that
is optimized for production workloads and is easy to integrate
within existing database systems. Evaluations on both production
workloads in Google Spanner and publicly available traces show
that the proposed elastic caching approach can significantly reduce
the total cache cost compared to traditional fixed-size cache policies.
the goal is to minimize the total cost of a cache inclusive of not
just its misses, but also its memory footprint integrated over time.
We demonstrate a theoretical connection to the classic ski rental
problem and propose a practical algorithm that combines online
caching algorithms with ski rental policies. We also introduce a
lightweight machine learning-based algorithm for ski rental that
is optimized for production workloads and is easy to integrate
within existing database systems. Evaluations on both production
workloads in Google Spanner and publicly available traces show
that the proposed elastic caching approach can significantly reduce
the total cache cost compared to traditional fixed-size cache policies.
