Che approximation
The Che approximation estimates LRU hit probabilities by replacing random, object-dependent eviction times with a common deterministic characteristic time.
For independent Poisson requests with rates lambda_i and an equal-size, fully associative LRU cache of C objects, choose T so that sum_i (1 - exp(-lambda_i T)) = C. Then h_i = 1 - exp(-lambda_i T); request hit ratio is sum_i lambda_i h_i / sum_i lambda_i, not the unweighted mean. T is in seconds when rates are per second. This common-time form discards object-specific cutoffs. [1]
With two objects requested at rates 2 and 1 per second and one slot, Che predicts 53.93% hits; exact stationary LRU gives 55.56%. A one-slot hit requires consecutive requests to match, so its exact probability is (2/3)^2 + (1/3)^2 = 5/9. These are constructed model probabilities. [4]
For reset-on-request TTL with inter-request CDF F_i, occupancy is lambda_i times the integral of 1 - F_i(t) from 0 to T. Hit probability is F_i(T), away from expiry ties. Poisson arrivals make them coincide; general renewal arrivals need not. [2]
An object requested once per second with stationary random phase and a half-second TTL is resident half the time, but every request misses. This TTL example does not describe LRU. [4]
The linked code compares the common-time equation with exact stationary recency-order enumeration for small catalogues. A small numerical root residual does not bound the model's difference from LRU. [5]
Relations
- related
- Independent reference model, Least recently used replacement, Miss-ratio curve, Average eviction time (AET), Tsetlin library
Limitations
- Convergence requires growing caches and catalogues, independent stationary request processes and further regularity/popularity assumptions; it is not an exactness guarantee for a fixed small cache. [3]
- Variable-size byte-capacity equations additionally ignore object-boundary effects; correlated or changing requests and cache hierarchies require separate modelling. [1, 2]
Citations
- Fricker, Robert and Roberts. A versatile and accurate approximation for LRU cache performance. arXiv:1202.3974v1 (2012), sections 2-4.
- Martina, Garetto and Leonardi. A unified approach to the performance analysis of caching systems. arXiv:1307.6702v6 (2016), sections II-IV.A.
- Jiang, Nain and Towsley. On the Convergence of the TTL Approximation for an LRU Cache. arXiv:1707.06204v4 (2018), sections 2-4.
- Hesela. Constructed common-time, exact-LRU and periodic-TTL controls, with explicit units and assumptions.
- Hesela. Dependency-free arithmetic and exact small-catalogue stationary LRU enumeration.
Further reading
- Hesela. Analytic, rate-scaling, monotonicity and invalid-input tests.
- Hesela. Storage cache models and workload assumptions.
Sources & caveats
- Selected full-text methods and limitations read in three primary papers; no original workload or hardware benchmark reproduced.
- The name refers to Che, Tung and Wang (2002); the common-time equations here are verified from the explicitly versioned 2012 treatment, not a claimed reading of the original 2002 paper.
- Exact recency-order enumeration is Hesela's independent small-state arithmetic control, not the cited papers' experimental implementation.