Cache Hit Ratios and the Che Approximation: Optimal Capacity for Caching Computed Charts: chapter answers
Owners of pay-per-computation services commonly believe that doubling a cache doubles its hit ratio. This book overturns that instinct. 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. The Che approximation, using nothing but request probabilities and capacity, computes the LRU hit ratio in advance, with a largest gap of 0.0013 from request-by-request simulation. After checking the sources the book corrects the project bluep…
DOI pending · monograph page goes live after publication · 5DL-B-327 · 中文版
- Chapter 1 · The Doubling Illusion: Hit-Ratio Curves under Zipf Requests
At the four capacities the simulated hit ratios are 0.1380, 0.2624, 0.4496 and 0.7374; the Che approximation gives 0.1373, 0.2613, 0.4483 and 0.7367. The gaps are -0.0007, -0.0010, -0.0013 and -0.0007, and the largest a… - Chapter 2 · The Characteristic Time: Solving the Che Approximation by Bisection, and How Accurate It Is
At all three capacities the Che value falls inside the interval. At two hundred and fifty slots the simulated mean is 0.1930, the interval runs from 0.1921 to 0.1940, and the approximation gives 0.1931. At one thousand… - Chapter 3 · Belady's Bound: Optimal Replacement, the Static Bound and the Capacity Price of LRU
Chapter 3 takes Belady's optimal replacement as a lower bound on misses and the static top C as an upper bound on hits, and finds that LRU needs 4.48 times the slots for not knowing popularity. - Chapter 4 · Marginal Returns: the Slope of the Capacity Curve and the Cost-Optimal Boundary
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. - Chapter 5 · Non-Stationary Requests: Popularity Drift, Frozen Lists and Cold Starts
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 flus… - Chapter 6 · Partitions and Tiers: the Same Slots, Arranged Differently
Then the Che column. The front-level hit ratios, 0.1931, 0.2613, 0.3450 and 0.4027, match a single cache of the same size exactly; this level is fine. The trouble lies at the back. The approximation for both levels toge… - Chapter 7 · Eastern and Western Classics: the Nine-Year Reserve of the Royal Regulations and Belady's Optimal Replacement
Chapter 7 examines "a state without a reserve of nine years is said to be short" from the Royal Regulations of the Book of Rites alongside Belady's optimal replacement of 1966, uses a granary model to show that spoilage… - Chapter 8 · Closing the Loop: Read-Only Capacity Planning for a Toll Booth's Chart-Result Cache
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…
Illustrative model calculation, not a live quote