Google Research 与 Google Cloud 提出线性弹性缓存，将缓存管理转为线性成本优化问题，动态调整大小以最小化总拥有成本。为每条数据引入“滑雪租赁”决策框架，在租用内存（持续付费）与购买缺失（缓存未命中惩罚）间选择，并用轻量级机器学习实时优化内存占用与缺失率权衡。无服务器云场景下（每 GiB 内存每天 $3），该技术可在不牺牲性能的同时显著降本。论文发表于 CIDR。
原文 · 未翻译
Explore our many areas of focus
Explore all research areas
Applied AI & sciences
Earth AI Health AI Science AI Sustainability & crisis resilience
Foundational ML & algorithms
Algorithms & theory Information retrieval Machine intelligence Machine perception Natural language processing
People, systems & quantum AI
Human-computer interaction and visualization Networking Quantum AI Responsible AI Anti abuse Software engineering Software systems
Learn More
Publications Projects Building a collaborative ecosystem
Datasets Access high-quality datasets to accelerate your research. Tools & services Explore our latest AI models and products.
Open source Discover open-source code and collaborate with the community. Shaping the future together
See all programs
Faculty programs Participating in the academic research community through meaningful engagement with university faculty. Student programs Supporting the next generation of researchers through a wide range of programming.
Locations Find your place in our global offices and research labs. Translating discovery into real-world impact
People Our researchers drive advancements in computer science through both fundamental and applied research.
Teams Collaborative groups tackling the world's most challenging AI problems.
Research Explore our many areas of focus
Explore all research areas
Applied AI & sciences
Foundational ML & algorithms
People, systems & quantum AI
Learn More
Publications Projects
Resources Building a collaborative ecosystem
Datasets Access high-quality datasets to accelerate your research. Tools & services Explore our latest AI models and products. Open source Discover open-source code and collaborate with the community.
Conferences & events
Careers Shaping the future together
See all programs
Faculty programs Participating in the academic research community through meaningful engagement with university faculty. Student programs Supporting the next generation of researchers through a wide range of programming. Locations Find your place in our global offices and research labs.
Google Research 与 Google Cloud 提出线性弹性缓存，将缓存管理转为线性成本优化问题，动态调整大小以最小化总拥有成本。为每条数据引入“滑雪租赁”决策框架，在租用内存（持续付费）与购买缺失（缓存未命中惩罚）间选择，并用轻量级机器学习实时优化内存占用与缺失率权衡。无服务器云场景下（每 GiB 内存每天 $3），该技术可在不牺牲性能的同时显著降本。论文发表于 CIDR。
原文 · 保持原样，未翻译
Explore our many areas of focus
Explore all research areas
Applied AI & sciences
Earth AI Health AI Science AI Sustainability & crisis resilience
Foundational ML & algorithms
Algorithms & theory Information retrieval Machine intelligence Machine perception Natural language processing
People, systems & quantum AI
Human-computer interaction and visualization Networking Quantum AI Responsible AI Anti abuse Software engineering Software systems
Learn More
Publications Projects Building a collaborative ecosystem
Datasets Access high-quality datasets to accelerate your research. Tools & services Explore our latest AI models and products.
Open source Discover open-source code and collaborate with the community. Shaping the future together
See all programs
Faculty programs Participating in the academic research community through meaningful engagement with university faculty. Student programs Supporting the next generation of researchers through a wide range of programming.
Locations Find your place in our global offices and research labs. Translating discovery into real-world impact
People Our researchers drive advancements in computer science through both fundamental and applied research.
Blog
About Translating discovery into real-world impact
People Our researchers drive advancements in computer science through both fundamental and applied research. Teams Collaborative groups tackling the world's most challenging AI problems.
Google Research
Google AI Learn about all our AIGoogle DeepMind Explore the frontier of AIGoogle Labs Try our AI experiments
Research
Resources
Conferences & events
Careers
Blog
About
Search
Home 2. Blog Optimizing cloud economics with linear elastic caching
June 25, 2026
Todd Lipcon, Distinguished Engineer, Google Cloud, and Manish Purohit, Research Scientist, Google Research
Linear elastic caching minimizes total cache cost by framing page eviction as a ski rental problem, using lightweight machine learning to optimize the trade-off between memory footprint and cache misses. Quick links Paper [](https://twitter.com/intent/tweet?text=https%3A//research.google/blog/optimizing-cloud-economics-with-linear-elastic-caching/ "Share on Twitter") [](https://www.facebook.com/sharer/sharer.php?u=https%3A//research.google/blog/optimizing-cloud-economics-with-linear-elastic-caching/ "Share on Facebook") [](https://www.linkedin.com/shareArticle?url=https%3A//research.google/blog/optimizing-cloud-economics-with-linear-elastic-caching/&mini=true "Share on LinkedIn") [](mailto:name@example.com?subject=Check%20out%20this%20site&body=Check%20out%20https%3A//research.google/blog/optimizing-cloud-economics-with-linear-elastic-caching/ "Send via Email") Copy link ×
Modern high-performance database systems and cloud services rely on in-memory caching to keep frequently accessed data in RAM to bypass slow disk operations and deliver the lightning-fast response times users expect. But this performance comes with a cost (literally): high-speed memory is expensive, and some serverless cloud providers charge up to $3 per day for just 1 GiB of memory.
Historically, cache management has been treated as a fixed-resource problem. With regular, fixed-sized caching, engineers allocate a specific amount of memory for the cache and the system uses eviction policies like least recently used (LRU) replacement to decide which data to keep when that space runs out. This leads to a classic “Goldilocks” problem: size the cache too small and performance plummets; size it too large for peak demand, and you waste thousands of dollars on idle memory.
In a paper published at the Conference on Innovative Data Systems Research (CIDR), we introduced linear elastic caching, a new approach designed to minimize the total cost of ownership (TCO) of cache management by dynamically adjusting cache size in response to real-time workloads. Instead of treating memory as a fixed, pre-allocated resource, we treat it as an utility whose cost is linear in both the size of the cached data and the duration for which it is held in the cache. By treating memory footprint as a variable cost that integrates over time, we showed that we can significantly reduce expenses without compromising system performance. The "ski rental" approach to memory
To solve the challenge of dynamic cache sizing, let’s use the classic ski rental problem. Imagine you’re on a ski trip of unknown length. Each day, you face a choice: rent skis for a small daily fee or buy them for a larger upfront cost and ski for free thereafter. If you knew exactly how many days you would ski, the choice would be easy. But without that knowledge, you need an algorithm to minimize your total spend.
Similarly, in a linear elastic cache, every piece of data faces a comparable dilemma. When a piece of data is accessed, the system must decide between two alternatives:
_"Rent" the space:_ Keep the data in RAM and pay a continuous cost for the memory it occupies. 2. _"Buy" the miss:_ Evict the data to save memory costs, but risk a "buy" cost (the latency and I/O penalty) if the data is needed again soon.
At the same time, the system cannot optimize for each piece of data independently since the cache has a maximum allocated size (think of a large group of people at a ski resort, where the resort only has a limited number of skis to offer). Our core theoretical contribution proves that we can optimize these two factors — the eviction policy and the "rental" duration — separately. This separation lends itself nicely into a clean practical implementation. We can use a ski rental algorithm to determine the time-to-live (TTL) of a page (analogous to the rental duration). If a page isn’t accessed again before its TTL expires, it is automatically evicted. But if the cache ever becomes physically full, a traditional eviction policy like least recently used) (LRU) steps in to manage the space.
Traditional online algorithm design focuses on providing worst-case performance guarantees. For the ski rental problem, the classic “break-even” algorithm is to rent until the accumulated cost equals the purchase price, and then buying the skis. While this approach (and its randomized counterpart) provide solid worst-case guarantees, production workloads are mostly predictable. Data access in systems like Spanner — our globally distributed database — often follows discernible patterns that can be exploited to make better renting decisions. Testing linear elastic caching
To ensure our theory holds up in the real world, we conducted extensive experiments using two primary sources:
_Production workloads:_ We integrated the system into Spanner. 2. _Public traces:_ We tested against a variety of publicly available cache traces from industry benchmarks to ensure the results weren't specific to Google’s infrastructure. Production workloads
We developed a practical algorithm that assigns a time-to-live (TTL) to the cached page on each page request based on the page’s access patterns and costs. Because Spanner handles billions of requests per second, this TTL prediction model has to be incredibly lightweight. We opted for a shallow decision tree that can be translated into a few lines of C++ code. The resulting code is also easily interpretable and provides valuable insights on the workload characteristics. This model considers features such as the size of the data, the cost of a cache miss (when data isn’t in the cache and the system needs to retrieve it from some other, slower system like a disk), and the type of database operation being performed to predict the optimal TTL for each page.
We integrated the elastic caching policy into Spanner's production servers over several months. Compared to a standard fixed-size cache, the results were substantial: _Memory usage:_ Reduced by 15.5%. _Cache misses:_ Increased by only 5.5%. _Total cost of ownership (TCO):_ Reduced by approximately 5%.
Crucially, because the algorithm is "cost-aware," the small increase in cache misses was concentrated on data that is cheap to fetch from storage, meaning the impact on actual I/O costs was a negligible 0.5%. Public traces
We also evaluated our elastic caching approach using several publicly available cache traces. We used an optimized implementation of the greedy dual size frequency (GDSF) eviction algorithm — a generalization of the well-known LRU policy that allows for pages of different sizes — as a fixed cache size baseline policy.
We considered four variants of elastic caching depending on which ski rental algorithm we used and whether or not we used a machine learned model. Since the available public traces don't have application-level features available for training, we didn’t implement decision trees for prediction. Instead, we developed a simple learning strategy that splits each trace in half and uses the first half for training. For each individual page in the training trace, we computed the best TTL for the page that minimizes the cost over the training trace.
Since the behavior of the cache changes depending on what's initially in the cache, a common practice, known as “warming up”, is to use some prefix of the cache trace to populate the cache but not actually measure performance on it. We warmed up all caches with one day’s worth of requests from the second half of the trace and used the rest for testing and measurements. During the test trace, if we encountered a page that was seen during training, we set the TTL to be the best precomputed TTL for that page. Otherwise, we set the TTL using either the breakeven or randomized policies. Results
We found that the elastic approach consistently outperformed fixed-size caches across diverse workloads. As the cost of memory increases relative to the cost of a cache miss, the savings provided by elastic caching become even more pronounced.
As the following figures demonstrate, elastic caching policies incur significantly lower total cost by dynamically adapting the cache size to the workload. We also observe that the elastic policies incur a much lower cache miss rate when compared to a fixed size policy at a comparable size.
_A plot of total cost (memory + cache misses) incurred by different caching policies against varying cache capacities. As cache capacity increases, the baseline GDSF policy incurs a high cost due to increasing memory costs, while the elastic caching policy adapts the utilized cache size to the working set of the problem and maintains a lower total cost._
_A plot of the cache miss rate for different average cache sizes. The chart demonstrates that (variants of) the elastic caching policies consistently maintain a significantly lower cache miss rate compare…
Teams Collaborative groups tackling the world's most challenging AI problems.
Research Explore our many areas of focus
Explore all research areas
Applied AI & sciences
Foundational ML & algorithms
People, systems & quantum AI
Learn More
Publications Projects
Resources Building a collaborative ecosystem
Datasets Access high-quality datasets to accelerate your research. Tools & services Explore our latest AI models and products. Open source Discover open-source code and collaborate with the community.
Conferences & events
Careers Shaping the future together
See all programs
Faculty programs Participating in the academic research community through meaningful engagement with university faculty. Student programs Supporting the next generation of researchers through a wide range of programming. Locations Find your place in our global offices and research labs.
Blog
About Translating discovery into real-world impact
People Our researchers drive advancements in computer science through both fundamental and applied research. Teams Collaborative groups tackling the world's most challenging AI problems.
Google Research
Google AI Learn about all our AIGoogle DeepMind Explore the frontier of AIGoogle Labs Try our AI experiments
Research
Resources
Conferences & events
Careers
Blog
About
Search
Home 2. Blog Optimizing cloud economics with linear elastic caching
June 25, 2026
Todd Lipcon, Distinguished Engineer, Google Cloud, and Manish Purohit, Research Scientist, Google Research
Linear elastic caching minimizes total cache cost by framing page eviction as a ski rental problem, using lightweight machine learning to optimize the trade-off between memory footprint and cache misses. Quick links Paper [](https://twitter.com/intent/tweet?text=https%3A//research.google/blog/optimizing-cloud-economics-with-linear-elastic-caching/ "Share on Twitter") [](https://www.facebook.com/sharer/sharer.php?u=https%3A//research.google/blog/optimizing-cloud-economics-with-linear-elastic-caching/ "Share on Facebook") [](https://www.linkedin.com/shareArticle?url=https%3A//research.google/blog/optimizing-cloud-economics-with-linear-elastic-caching/&mini=true "Share on LinkedIn") [](mailto:name@example.com?subject=Check%20out%20this%20site&body=Check%20out%20https%3A//research.google/blog/optimizing-cloud-economics-with-linear-elastic-caching/ "Send via Email") Copy link ×
Modern high-performance database systems and cloud services rely on in-memory caching to keep frequently accessed data in RAM to bypass slow disk operations and deliver the lightning-fast response times users expect. But this performance comes with a cost (literally): high-speed memory is expensive, and some serverless cloud providers charge up to $3 per day for just 1 GiB of memory.
Historically, cache management has been treated as a fixed-resource problem. With regular, fixed-sized caching, engineers allocate a specific amount of memory for the cache and the system uses eviction policies like least recently used (LRU) replacement to decide which data to keep when that space runs out. This leads to a classic “Goldilocks” problem: size the cache too small and performance plummets; size it too large for peak demand, and you waste thousands of dollars on idle memory.
In a paper published at the Conference on Innovative Data Systems Research (CIDR), we introduced linear elastic caching, a new approach designed to minimize the total cost of ownership (TCO) of cache management by dynamically adjusting cache size in response to real-time workloads. Instead of treating memory as a fixed, pre-allocated resource, we treat it as an utility whose cost is linear in both the size of the cached data and the duration for which it is held in the cache. By treating memory footprint as a variable cost that integrates over time, we showed that we can significantly reduce expenses without compromising system performance. The "ski rental" approach to memory
To solve the challenge of dynamic cache sizing, let’s use the classic ski rental problem. Imagine you’re on a ski trip of unknown length. Each day, you face a choice: rent skis for a small daily fee or buy them for a larger upfront cost and ski for free thereafter. If you knew exactly how many days you would ski, the choice would be easy. But without that knowledge, you need an algorithm to minimize your total spend.
Similarly, in a linear elastic cache, every piece of data faces a comparable dilemma. When a piece of data is accessed, the system must decide between two alternatives:
_"Rent" the space:_ Keep the data in RAM and pay a continuous cost for the memory it occupies. 2. _"Buy" the miss:_ Evict the data to save memory costs, but risk a "buy" cost (the latency and I/O penalty) if the data is needed again soon.
At the same time, the system cannot optimize for each piece of data independently since the cache has a maximum allocated size (think of a large group of people at a ski resort, where the resort only has a limited number of skis to offer). Our core theoretical contribution proves that we can optimize these two factors — the eviction policy and the "rental" duration — separately. This separation lends itself nicely into a clean practical implementation. We can use a ski rental algorithm to determine the time-to-live (TTL) of a page (analogous to the rental duration). If a page isn’t accessed again before its TTL expires, it is automatically evicted. But if the cache ever becomes physically full, a traditional eviction policy like least recently used) (LRU) steps in to manage the space.
Traditional online algorithm design focuses on providing worst-case performance guarantees. For the ski rental problem, the classic “break-even” algorithm is to rent until the accumulated cost equals the purchase price, and then buying the skis. While this approach (and its randomized counterpart) provide solid worst-case guarantees, production workloads are mostly predictable. Data access in systems like Spanner — our globally distributed database — often follows discernible patterns that can be exploited to make better renting decisions. Testing linear elastic caching
To ensure our theory holds up in the real world, we conducted extensive experiments using two primary sources:
_Production workloads:_ We integrated the system into Spanner. 2. _Public traces:_ We tested against a variety of publicly available cache traces from industry benchmarks to ensure the results weren't specific to Google’s infrastructure. Production workloads
We developed a practical algorithm that assigns a time-to-live (TTL) to the cached page on each page request based on the page’s access patterns and costs. Because Spanner handles billions of requests per second, this TTL prediction model has to be incredibly lightweight. We opted for a shallow decision tree that can be translated into a few lines of C++ code. The resulting code is also easily interpretable and provides valuable insights on the workload characteristics. This model considers features such as the size of the data, the cost of a cache miss (when data isn’t in the cache and the system needs to retrieve it from some other, slower system like a disk), and the type of database operation being performed to predict the optimal TTL for each page.
We integrated the elastic caching policy into Spanner's production servers over several months. Compared to a standard fixed-size cache, the results were substantial: _Memory usage:_ Reduced by 15.5%. _Cache misses:_ Increased by only 5.5%. _Total cost of ownership (TCO):_ Reduced by approximately 5%.
Crucially, because the algorithm is "cost-aware," the small increase in cache misses was concentrated on data that is cheap to fetch from storage, meaning the impact on actual I/O costs was a negligible 0.5%. Public traces
We also evaluated our elastic caching approach using several publicly available cache traces. We used an optimized implementation of the greedy dual size frequency (GDSF) eviction algorithm — a generalization of the well-known LRU policy that allows for pages of different sizes — as a fixed cache size baseline policy.
We considered four variants of elastic caching depending on which ski rental algorithm we used and whether or not we used a machine learned model. Since the available public traces don't have application-level features available for training, we didn’t implement decision trees for prediction. Instead, we developed a simple learning strategy that splits each trace in half and uses the first half for training. For each individual page in the training trace, we computed the best TTL for the page that minimizes the cost over the training trace.
Since the behavior of the cache changes depending on what's initially in the cache, a common practice, known as “warming up”, is to use some prefix of the cache trace to populate the cache but not actually measure performance on it. We warmed up all caches with one day’s worth of requests from the second half of the trace and used the rest for testing and measurements. During the test trace, if we encountered a page that was seen during training, we set the TTL to be the best precomputed TTL for that page. Otherwise, we set the TTL using either the breakeven or randomized policies. Results
We found that the elastic approach consistently outperformed fixed-size caches across diverse workloads. As the cost of memory increases relative to the cost of a cache miss, the savings provided by elastic caching become even more pronounced.
As the following figures demonstrate, elastic caching policies incur significantly lower total cost by dynamically adapting the cache size to the workload. We also observe that the elastic policies incur a much lower cache miss rate when compared to a fixed size policy at a comparable size.
_A plot of total cost (memory + cache misses) incurred by different caching policies against varying cache capacities. As cache capacity increases, the baseline GDSF policy incurs a high cost due to increasing memory costs, while the elastic caching policy adapts the utilized cache size to the working set of the problem and maintains a lower total cost._
_A plot of the cache miss rate for different average cache sizes. The chart demonstrates that (variants of) the elastic caching policies consistently maintain a significantly lower cache miss rate compare…