che-approximation · research · also Characteristic-time approximation, TTL approximation for LRU

Che approximation

The Che approximation estimates LRU hit probabilities by replacing random, object-dependent eviction times with a common deterministic characteristic time.

Related Observatory article: Read on hesela.com

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

  1. Fricker, Robert and Roberts. A versatile and accurate approximation for LRU cache performance. arXiv:1202.3974v1 (2012), sections 2-4. (accessed 2026-11-19)
  2. Martina, Garetto and Leonardi. A unified approach to the performance analysis of caching systems. arXiv:1307.6702v6 (2016), sections II-IV.A. (accessed 2026-11-19)
  3. Jiang, Nain and Towsley. On the Convergence of the TTL Approximation for an LRU Cache. arXiv:1707.06204v4 (2018), sections 2-4. (accessed 2026-11-19)
  4. Hesela. Constructed common-time, exact-LRU and periodic-TTL controls, with explicit units and assumptions. (accessed 2026-11-19)
  5. Hesela. Dependency-free arithmetic and exact small-catalogue stationary LRU enumeration. (accessed 2026-11-19)

Further reading

  1. Hesela. Analytic, rate-scaling, monotonicity and invalid-input tests. (accessed 2026-11-19)
  2. Hesela. Storage cache models and workload assumptions. (accessed 2026-11-19)
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.

JSON: /data/terms/che-approximation.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Che approximation. Hesela. 2026-11-21. https://hesela.dev/terms/che-approximation/