What does Cache Hit Ratios and the Che Approximation conclude, in numbers, about “Closing the Loop: Read-Only Capacity Planning for a Toll Booth's Chart-Result Cache”?

Answer: Chapter 8 gives a read-only planning workflow for a toll booth's chart-result cache, the distilled Cache Hit Ratio Estimator and a pre-registered test, and flags for drift any capacity whose characteristic time reaches 9.58 days. Marked boxes separate published evidence, runnable Python calculations (22 programs), classical sources and the author's hypotheses.

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: 9.58

Chart cache sheet: N50000, a = 0.9, R = 30000/day
C hit misses/day CPU-s/day memory MB T_C days
12500.4174 17477 3495 14.6 0.06
25000.5000 15001 3000 29.3 0.14
50000.5928 12215 2443 58.6 0.33
100000.6983 9052 1810 117.2 0.81
200000.8189 5433 1087 234.4 2.25
400000.9557 1330 266 468.8 9.58
gain per doubling:
12502500: +0.0825 hit, 2475 fewer misses/day
25005000: +0.0929 hit, 2786 fewer misses/day
500010000: +0.1054 hit, 3163 fewer misses/day
1000020000: +0.1207 hit, 3620 fewer misses/day
2000040000: +0.1367 hit, 4102 fewer misses/day
Show the full program
# Chapter 8. p81: a read-only capacity sheet for a chart-result cache.
# Model: the Che approximation turns four planning inputs into a table:
# distinct chart keys N, Zipf exponent a, requests per day R and the
# compute time per recomputed chart. Entry size converts slots into
# memory. Every input is illustrative (N = 50000, a = 0.9, R = 30000,
# 0.2 CPU-seconds per miss, 12 KB per entry); the sheet is advice to be
# read, not a setting written anywhere.
import math

N, A, R, CPU, KB = 50000, 0.9, 30000, 0.2, 12


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)


if __name__ == "__main__":
    p = zipf(N, A)
    print("Chart cache sheet: N = {}, a = {}, R = {}/day".format(N, A, R))
    print("      C   hit     misses/day   CPU-s/day   memory MB   T_C days")
    rows = []
    for c in (1250, 2500, 5000, 10000, 20000, 40000):
        t = che_t(p, c)
        h = che_hit(p, t)
        rows.append((c, h))
        print("  {:5d}  {:.4f}    {:7.0f}      {:7.0f}     {:7.1f}    {:6.2f}"
              .format(c, h, R * (1 - h), R * (1 - h) * CPU,
                      c * KB / 1024, t / R))
    print("  gain per doubling:")
    for (c0, h0), (c1, h1) in zip(rows, rows[1:]):
        print("    {:5d} -> {:5d}: +{:.4f} hit, {:5.0f} fewer misses/day"
              .format(c0, c1, h1 - h0, R * (h1 - h0)))

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 8: Closing the Loop: Read-Only Capacity Planning for a Toll Booth's Chart-Result Cache. 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