In cloud object storage, a cache miss incurs costs based on each GET request and bytes of egress, not latency. Classic caching aims to minimize the miss rate, which is a flawed objective: a rarely accessed but expensive object can cost thousands of times more than a frequently accessed but cheaper one.
We introduce a generalized caching theory to bound the miss-cost objective, but no benchmarks exist to measure how far deployed heuristics deviate from the dollar-optimal offline policy under real cloud pricing. We provide that reference.
For uniform-size page caches with heterogeneous miss costs, the offline dollar-optimum can be computed exactly in polynomial time using 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), accurate to about four percent.
We find: (i) a heterogeneity-regret law—LRU's dollar-regret increases with miss-cost dispersion (Spearman 0.87) while cost-aware GreedyDual reduces 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; (iii) a closed-form crossover s* = GET_fee/egress_rate (about 4 KB on S3, 330 B on GCS) that predicts which deployments require dollar-aware caching.
On a real Twitter trace, the price vector alone shifts the workload across s*, altering the regime as anticipated. The artifact is a reproducible, billing-faithful benchmark; heuristics and bounds it builds on are prior work, credited.
Blogger's Review: This article presents an innovative approach that integrates cost optimization into caching design in cloud computing, highlighting the importance of considering economic factors in cloud environments. This research not only supports the theory but also provides valuable guidance for practical deployments, especially on how to choose appropriate caching strategies under budget constraints.