Optimizing cloud economics with linear elastic caching
Linear elastic caching treats cache memory as a variable cost rather than a fixed allocation. It dynamically adjusts how long pages remain in memory by balancing ongoing memory expense against the cost of fetching evicted data again, using the ski rental problem as its theoretical foundation. Experiments in Spanner and public cache traces show meaningful cost reductions with only modest increases in misses. ## Fixed-Size Cache Limitations - Traditional caches allocate a fixed amount of RAM and use policies such as LRU when space runs out. - Undersizing the cache causes excessive disk or storage access and poor performance. - Oversizing it wastes money during periods of low demand; some serverless providers charge up to $3 per day for 1 GiB of memory. - Fixed sizing therefore creates a “Goldilocks” problem as workloads fluctuate. ## Ski Rental Model for Cache Eviction - Each cached page presents two choices: - **Rent:** Keep it in RAM and continuously pay for its memory footprint. - **Buy the miss:** Evict it and risk a latency and I/O penalty if it is requested again. - A ski rental algorithm assigns each page a time-to-live (TTL). - If the page is not accessed before its TTL expires, it is evicted. - If the cache becomes physically full, a conventional policy such as LRU handles capacity pressure. - The researchers prove that eviction policy and rental duration can be optimized separately, simplifying implementation. - Unlike worst-case break-even or randomized ski rental strategies, lightweight machine learning can exploit predictable workload patterns. ## Lightweight TTL Prediction - In Spanner, each page receives a TTL based on: - Page size - Cost of a cache miss - Type of database operation - Observed access behavior - A shallow decision tree was chosen because Spanner processes billions of requests per second. - The model can be translated into a few lines of interpretable C++ code. - Its cost-aware decisions allow extra misses mainly for data that is inexpensive to retrieve. ## Spanner Production Results - Compared with a standard fixed-size cache: - Memory usage fell by **15.5%**. - Cache misses increased by only **5.5%**. - Total cost of ownership fell by approximately **5%**. - The additional misses increased actual I/O costs by only **0.5%**, because they were concentrated on cheap-to-fetch data. - The policy was deployed on production Spanner servers and evaluated over several months. ## Public Trace Evaluation - The approach was tested on public industry cache traces using GDSF as the fixed-size baseline. - GDSF generalizes LRU to account for pages with different sizes. - Researchers evaluated four elastic-cache variants using: - Break-even or randomized ski rental policies - Learned or non-learned TTL selection - Because public traces lacked application-level features, learning used the first half of each trace to calculate the best TTL for individual pages. - Caches were warmed with one day of requests before performance measurement began. ## Overall Results - Elastic caching consistently produced lower total cost across diverse workloads. - Its advantage increased as memory became more expensive relative to cache misses. - At comparable cache sizes, elastic policies also achieved substantially lower miss rates than fixed-size approaches. Linear elastic caching is most useful when memory costs vary significantly or workloads are bursty and predictable. Dynamically assigning page TTLs offers a practical way to reduce memory spending while limiting performance impact, especially when the system can estimate the cost of each miss.
Read original(opens in new tab)