Caching for Dollars, Not Hits: An Exact Offline Reference for Cloud-Egress Caching and the Crossover That Decides When It Pays
arXiv:2606.20539v1 [cs.DB] 18 Jun 2026
Madhulatha Mandarapu∗
Sandeep Kunkunuru†
VaidhyaMegha Private Limited, India https://samyama.ai/ June 2026
Abstract When a cache miss fetches from cloud object storage, the bill is per GET request and per byte of egress, not latency. Classic caching minimizes the miss rate, the wrong objective: a rarely but expensively fetched object can cost thousands of times more dollars than a frequently but cheaply fetched one. Generalized-caching theory bounds the miss-cost objective, but no reported benchmark measures how far deployed heuristics sit from the dollar-optimal offline policy on real cloud prices. We supply that reference. For uniform-size page caches with heterogeneous miss costs the offline dollar-optimum is exact in polynomial time via an integral interval linear program – validated against brute force; variable sizes are NP-hard, so we extend the flow-based offline bound from the hit-ratio objective to dollars (cost-FOO), tight to about four percent. Against this reference we find: (i) a heterogeneity-regret law – LRU’s dollar-regret rises with miss-cost dispersion (Spearman 0.87) while cost-aware GreedyDual cuts it to roughly a tenth; (ii) a contention frontier – GreedyDual’s residual regret collapses to near zero exactly when the budget fits the expensive working set, and is the open slice otherwise; and (iii) a closed-form crossover s⋆ = GET_fee/egress_rate (about 4 KB on S3, 330 B on GCS) that predicts which deployments need dollar-aware caching at all. On a real Twitter trace the price vector alone moves the workload across s⋆ , shifting the regime as predicted. The artifact is a reproducible billing-faithful benchmark; heuristics and bounds it builds on are prior work, credited.
1
Introduction
A compute node caches objects locally; a miss fetches from cloud object storage (S3, GCS, Azure Blob), which bills per GET request and per byte of egress / cross-zone transfer, not in latency. The miss cost of object i is therefore ci =
f |{z}
GET fee
+ si e (+ latency penalty),
(1)
|{z}
egress
with size si and per-byte egress rate e. This cost is heterogeneous: a large or cross-region object costs orders of magnitude more than a small same-region one, and the flat GET fee matters independently ∗ †
[email protected] [email protected]
1
of bytes. Minimizing the miss rate – the classic objective behind LRU and Belady’s rule [Belady, 1966] – is then the wrong objective. A one-slot cache with a 1 KB object accessed 100 times and a 1 GB object accessed 10 times illustrates it: hit-rate caching keeps the small hot object and saves ∼ $5 × 10−5 ; keeping the large cold object saves ∼ $0.90, over four orders of magnitude more dollars for fewer hits. Minimizing total billed dollars under a capacity budget is generalized (size- and cost-weighted) caching. Its online competitive theory is settled up to constants: O(log k) randomized and k deterministic [Bansal et al., 2012], with the GreedyDual-Size family the practical workhorse [Cao and Irani, 1997] and learning-augmented variants for predicted reuse [Lykouris and Vassilvitskii, 2021, Antoniadis et al., 2020]. What is missing is empirical: no reported benchmark measures how far deployed heuristics sit from the dollar-optimal offline policy on real cloud price structures. That gap is a measurement gap, and we close it. Contributions. 1. An exact dollar-optimal reference. For uniform-size page caches with heterogeneous costs, the offline dollar-optimum is an integral interval LP, hence exact in polynomial time (§2); validated to the cent against brute force. Variable sizes are NP-hard [Folwarczný and Sgall, 2015], so we extend the flow-based offline bound (FOO) [Berger et al., 2018] from hit-ratio to dollars (cost-FOO), tight to ≈ 4%. 2. A heterogeneity-regret law and a contention frontier (§4): cost-blindness (LRU) costs more as miss-cost dispersion H grows; cost-awareness converts that into a contention problem whose residual regret collapses exactly when the budget fits the expensive working set (B = Nexp ). 3. The crossover s⋆ = f /e (§3): a closed-form, price-vector rule for when dollar-aware caching pays, validated on a real production trace. We add no new caching algorithm and beat no competitive ratio; the contribution is the exact reference and the characterization it enables. Code, data scripts, and the full pre-registration are public.1
2
Model and the exact dollar-optimum
A cache of capacity B serves a request stream over objects with sizes si and miss costs ci (1); total cost is the sum of ci over every fetch. We score policies in dollars. Interval-packing optimum. For each request t whose object recurs at next(t), a binary xt decides whether the object is retained across the gap, yielding a hit (saving co(t) ) and occupying a slot at every interior step. The dollar-optimum maximizes savings subject to, at each step τ , so(τ ) +
X
so(t) xt ≤ B.
(2)
t: t<τ <next(t)
Each variable covers a contiguous range of constraints, so for uniform sizes the constraint matrix has the consecutive-ones property and is totally unimodular: the LP relaxation is integral and (2) solves the offline dollar-optimum exactly in polynomial time. We verify this is centexact against an exhaustive brute force on 250 random instances. For variable sizes, the size 1
https://github.com/samyama-ai/cloud-egress-cache
2
weights break unimodularity; the LP relaxation is a fractional-caching lower bound on the NPhard optimum [Folwarczný and Sgall, 2015] – the dollar analogue of FOO [Berger et al., 2018], which bounds the hit-ratio optimum. A feasible policy upper-brackets it; we call the pair costFOO. This exact-or-tightly-bounded reference is what lets us measure regret, R(π) = (Cost(π) − Cost(OPT))/Cost(OPT), against a true optimum rather than against another heuristic. Policies. We score LRU, LFU, GreedyDual-Size with cost (GDS) and its frequency variant (GDSF) [Cao and Irani, 1997], Belady (hit-rate oracle) [Belady, 1966], and a cost-aware Belady heuristic – all in dollars.
3
The GET-fee / egress crossover
Equation (1) has a scale at which the flat fee and the egress term are equal: s⋆ = f /e.
(3)
Below s⋆ a miss is dominated by the GET fee, so costs are near-homogeneous and hit-rate caching is near-optimal; above s⋆ egress dominates, costs are heterogeneous, and cost-aware caching matters. This is a property of the price vector, not the workload: with list prices (June 2026) s⋆ ≈ 4.4 KB on S3 internet egress, ≈ 330 B on GCS, ≈ 460 B on Azure, and ≈ 20 KB on S3 cross-region transfer. It predicts which deployments need dollar-aware caching at all.
4
Experiments
All hypotheses and thresholds were pre-registered before the runs; one pre-registered regime form failed and was reframed (below), disclosed in the public pre-registration. Synthetic workloads use Zipf popularity assigned independently of size, so cheap-hot versus expensive-cold tension exists. Heterogeneity-regret law (Fig. 1). Let H be the access-weighted coefficient of variation of the miss-cost vector. LRU’s dollar-regret rises with H (Spearman 0.87); cost-aware GDSF’s median regret is 0.13× LRU’s where H ≥ 0.5. Cost-blindness is expensive, and cost-awareness buys most of it back. Contention frontier (Fig. 2). The pre-registered “three regimes in H” form failed: even at H = 0, LRU carries an intrinsic recency regret (∼0.65 vs Belady), so raw LRU regret conflates recency and egress components. The honest structure is two knobs. Heterogeneity drives LRU’s cost-blindness, which GDSF removes; the residual is governed by expensive-object contention. With Nexp expensive objects, GDSF’s regret is 0.23–0.69 while B < Nexp and collapses to 0.0002 exactly at B = Nexp : once the expensive working set fits, greedy cost-ranking is optimal; when it does not, greedy provably leaves money on the table – the open slice. Cost-awareness converts a heterogeneity problem into a contention problem. cost-FOO bracket. On variable-size synthetic traces the cost-FOO bracket (U − L)/L is a median 0.04, so variable-size regret numbers are meaningful rather than artifacts of a loose bound.
3
price vector S3 cross-region S3 internet Azure internet GCS internet
s⋆ (bytes)
H
LRU regret
GDSF/LRU
20000 4444 460 333
0.017 0.075 0.498 0.608
0.152 0.153 0.160 0.162
0.82 0.81 0.69 0.65
Table 1: Same real Twitter trace, four real price vectors. As the crossover s⋆ falls, more objects become egress-dominated, H rises, and cost-aware caching helps more.
Figure 2: Contention frontier: GDSF residual regret collapses at B = Nexp .
Figure 1: Heterogeneity-regret law: dollar-regret versus miss-cost heterogeneity H (exact OPT).
Real trace across price vectors (Table 1, Fig. 3). We replay a real Twitter twemcache production trace [Yang et al., 2020] (cluster 52; a 20,000-request window, real per-object sizes), computing the exact dollar-optimum, under four real price vectors. Under S3 the small memcache objects (mean 243 B) sit below s⋆ ≈ 4.4 KB, so misses are GET-fee-dominated: H = 0.075 and GDSF ≈ LRU – egress-aware caching buys almost nothing on small-object cache traffic, a useful negative. The same trace under GCS or Azure pricing (a 10× cheaper GET fee pushes s⋆ to ∼330–460 B) crosses the threshold: H rises to 0.5–0.6 and the GDSF/LRU regret ratio falls from 0.82 to 0.65. The regime is set by the price vector, exactly as s⋆ predicts.
4
Figure 3: Real Twitter trace: the price vector, through s⋆ , sets the regime; color is H.
5
Related work
Cost-aware caching by miss-cost-over-size weighting is GreedyDual-Size [Cao and Irani, 1997], the practical workhorse we measure. The online competitive theory for generalized (size- and cost-) caching is O(log k) randomized [Bansal et al., 2012]; ski-rental / rent-or-buy [Karlin et al., 1994] governs the per-request-fee batching sub-problem; learning-augmented caching adds predicted reuse [Lykouris and Vassilvitskii, 2021, Antoniadis et al., 2020]. The offline side is where our reference lives: general caching with variable sizes is NP-hard [Folwarczný and Sgall, 2015], and FOO/PFOO [Berger et al., 2018] compute tight flow-based bounds on the hit-ratio optimum – we extend the construction to the billing objective. Cloud engines cache object-store results aggressively [Dageville et al., 2016], but evaluations are workload-specific with no dollar-optimality reference. Our real arm uses the Twitter production cache traces [Yang et al., 2020]; the classic hit-rate oracle is Belady’s rule [Belady, 1966].
6
Limitations and honest scope
This is a reproducible benchmark and characterization, not a new caching algorithm. The preregistered three-regime-in-H form failed and was reframed into the two-knob decomposition above; we report the failure rather than relabel it. The dense interval-LP optimum does not scale to long traces (millions of nonzeros at tens of thousands of requests), so the real arm uses a windowed slice and a min-cost-flow FOO solver is the scalability path. The real arm is one trace family (in-memory cache), which lands in the low-H regime under S3 – large-object / CDN traces that exceed s⋆ are the natural next workload. List prices are date-stamped and re-tiering shifts s⋆ ; adversarial re-pricing is left to future work. Every number is regenerated by one command over public code.
References Antonios Antoniadis, Christian Coester, Marek Eliáš, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In International Conference on Machine Learning (ICML), 2020.
5
Nikhil Bansal, Niv Buchbinder, and Joseph (Seffi) Naor. Randomized competitive algorithms for generalized caching. SIAM Journal on Computing, 41(2):391–414, 2012. L. A. Belady. A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal, 5(2): 78–101, 1966. Daniel S. Berger, Nathan Beckmann, and Mor Harchol-Balter. Practical bounds on optimal caching with variable object sizes. Proceedings of the ACM on Measurement and Analysis of Computing Systems (POMACS / SIGMETRICS), 2(2):32:1–32:38, 2018. Pei Cao and Sandy Irani. Cost-aware WWW proxy caching algorithms. In USENIX Symposium on Internet Technologies and Systems (USITS), 1997. Benoit Dageville, Thierry Cruanes, Marcin Zukowski, et al. The snowflake elastic data warehouse. In ACM SIGMOD International Conference on Management of Data, 2016. Lukáš Folwarczný and Jiří Sgall. General caching is hard: Even with small pages. In International Symposium on Algorithms and Computation (ISAAC), 2015. Anna R. Karlin, Mark S. Manasse, Lyle A. McGeoch, and Susan Owicki. Competitive randomized algorithms for nonuniform problems. In Algorithmica, 1994. Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM, 68(4):24:1–24:25, 2021. Juncheng Yang, Yao Yue, and K. V. Rashmi. A large-scale analysis of hundreds of in-memory cache clusters at twitter. In USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2020.
6