PATTERN Cited by 1 source

Linear elastic cache sizing

Pattern

Replace a fixed-size cache with eviction policy by a variable-size cache with per-item TTL derived from the ski-rental breakeven point. Each item's TTL is set so that cumulative memory rental cost equals expected miss cost — the theoretically optimal stopping point for the rent-vs-buy decision.

When to use

• Cache memory is a significant portion of total cost (common in large-scale databases)
• Items have heterogeneous miss costs (some are cheap to re-fetch, others expensive)
• The workload is too dynamic for static cache sizing to be optimal
• You need provable worst-case guarantees (2-competitive ratio from ski-rental theory)

Mechanism

1. For each page/item on access, compute breakeven TTL = miss_cost / (size × memory_cost_per_unit_time)
2. Optionally refine with an ML model that considers additional features (operation type, historical access frequency)
3. Cache the item with the computed TTL; let it expire naturally
4. Cache size fluctuates dynamically based on workload cost structure

Why "linear"

The "linear" qualifier refers to the cost model: memory cost is assumed to be linear in (size × time held). This linearity makes the ski-rental mapping exact — each item's caching decision is independent and can be solved in isolation.

Production evidence

Spanner deployment: −15.5% memory, −~5% TCO, +0.5% I/O cost. Four variants tested (breakeven/randomized × with/without ML). (Source: sources/2026-06-25-google-optimizing-cloud-economics-with-linear-elastic-caching)

Seen in

• sources/2026-06-25-google-optimizing-cloud-economics-with-linear-elastic-caching — production deployment in Spanner with breakeven and randomized ski-rental variants