What does Cache Hit Ratios and the Che Approximation conclude, in numbers, about “Non-Stationary Requests: Popularity Drift, Frozen Lists and Cold Starts”?
Answer: Chapter 5 shows that under popularity drift the stationary approximation can only overestimate, that fast turnover can cut the hit ratio from 0.4483 to 0.3488, that frozen lists age quickly, and that refill after a flush runs on the characteristic time.
Scope of the numbers: Under Zipf requests the hit ratio of a least-recently-used (LRU) cache grows slowly with capacity: with illustrative parameters, a hundred-and-twenty-eight-fold increase in capacity raises the hit ratio only 6.80 times. Chapter 4 derives the optimal capacity from slope and cost, 4187 slots or 0.2094 of the catalogue under illustrative parameters, with a flat cost curve around the optimum.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.3488, 0.4483
| LRU under turnover, C = 2000, stationary Che = 0.4483 | |||
| turnover f | E = 50000 | E = 10000 | E = 2000 |
| 0.0 | 0.4496 | 0.4496 | 0.4496 |
| 0.1 | 0.4487 | 0.4457 | 0.4312 |
| 0.3 | 0.4474 | 0.4383 | 0.3965 |
| 0.6 | 0.4454 | 0.4281 | 0.3488 |
Show the full program
# Chapter 5. p51: when popularity drifts, the stationary Che value lies.
# Model: request ranks follow Zipf (a = 0.8, N = 20000), but the key
# behind each rank is not fixed: every E requests each rank, with
# probability f, is handed to a brand-new key (a chart nobody asked for
# before). LRU (C = 2000) is replayed on 300000 requests with 50000
# warm-up; the same rank sequence is reused for every (E, f) cell, and
# each cell's turnover draws come from its own seeded generator. E and
# f are illustrative, not measurements of any real service.
import math
import random
from collections import OrderedDict
N, A, L, WARM, C = 20000, 0.8, 300000, 50000, 2000
def zipf(n, a):
w = [1.0 / (i ** a) for i in range(1, n + 1)]
s = math.fsum(w)
return [x / s for x in w]
def occupancy(p, t):
return math.fsum(-math.expm1(-x * t) for x in p)
def che_t(p, c, tol=1e-9):
lo, hi = 0.0, 1.0
while occupancy(p, hi) < c:
hi = 2.0 * hi
while hi - lo > tol * hi:
mid = 0.5 * (lo + hi)
if occupancy(p, mid) < c:
lo = mid
else:
hi = mid
return 0.5 * (lo + hi)
def che_hit(p, t):
return math.fsum(x * -math.expm1(-x * t) for x in p)
def churn_lru(ranks, c, warm, e, f, seed):
r = random.Random(seed)
key = list(range(N))
fresh = N
cache = OrderedDict()
hits = 0
for t, k in enumerate(ranks):
if t and t % e == 0 and f > 0:
for i in range(N):
if r.random() < f:
key[i] = fresh
fresh += 1
x = key[k]
if x in cache:
cache.move_to_end(x)
if t >= warm:
hits += 1
else:
cache[x] = None
if len(cache) > c:
cache.popitem(last=False)
return hits / (len(ranks) - warm)
if __name__ == "__main__":
p = zipf(N, A)
rng = random.Random(20261113)
ranks = rng.choices(range(N), weights=p, k=L)
che = che_hit(p, che_t(p, C))
print("LRU under turnover, C = {}, stationary Che = {:.4f}"
.format(C, che))
print(" turnover f E = 50000 E = 10000 E = 2000")
seed = 20261200
for f in (0.0, 0.1, 0.3, 0.6):
row = []
for e in (50000, 10000, 2000):
seed += 1
row.append(churn_lru(ranks, C, WARM, e, f, seed))
print(" {:.1f} {:.4f} {:.4f} {:.4f}".format(
f, row[0], row[1], row[2]))Single source and citation
Fan, Y. (2026). Cache Hit Ratios and the Che Approximation: Optimal Capacity for Caching Computed Charts (Version 1.0.0), Chapter 5: Non-Stationary Requests: Popularity Drift, Frozen Lists and Cold Starts. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-327 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026327,
author = {Fan, Yafu},
title = {Cache Hit Ratios and the Che Approximation: Optimal Capacity for Caching Computed Charts},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · The Doubling Illusion: Hit-Ratio Curves under Zipf Requests
- Chapter 2 · The Characteristic Time: Solving the Che Approximation by Bisection, and How Accurate It Is
- Chapter 3 · Belady's Bound: Optimal Replacement, the Static Bound and the Capacity Price of LRU
- Chapter 4 · Marginal Returns: the Slope of the Capacity Curve and the Cost-Optimal Boundary
- Chapter 6 · Partitions and Tiers: the Same Slots, Arranged Differently
- Chapter 7 · Eastern and Western Classics: the Nine-Year Reserve of the Royal Regulations and Belady's Optimal Replacement
- Chapter 8 · Closing the Loop: Read-Only Capacity Planning for a Toll Booth's Chart-Result Cache