1
Turn a hit rate into backend load and latency
(1 − h)λ and the ρ it leaves the backend at, the mean latency by expectation, and the reason the p99 is the miss latency whenever the miss rate is at least one per cent.
Course · System Design
Caching and Hit Rates
A cache is a number — the miss rate — and every decision about it is arithmetic on that number: what it does to the backend, what it does to the average and to the tail, how big the cache must be given how skewed the requests are, how stale it is allowed to be, and what happens in the second after a hot key expires.
backend load = (1 − h)λ 90% → 99% is a 10× cut, not 9% better
E[latency] = h·t_hit + (1 − h)·t_miss
h(C) = H(C,s) / H(N,s) Zipf: the top keys carry the traffic
stampede size = λ·d one, with coalescing
global miss = (1 − h₁)(1 − h₂ | miss)
What this course is about
- Subject
- System Design
- Lessons
- 10
- Format
- Interactive
Overview
What you will be able to do
By the end you can convert a hit rate into backend load and into latency, size a cache from the skew of its workload, judge a policy on a trace, and price the two failure modes a cache has: staleness and the stampede.
2
Size a cache from the skew
The top-k share under a Zipf popularity as a ratio of harmonic numbers, the C that reaches a target hit rate, and the diminishing returns that make the next nine expensive.
3
Judge a replacement policy on a trace
Hits for FIFO, LRU, LFU and farthest-in-future at two cache sizes, with the optimum as the bound and Belady’s anomaly as the reason a bigger cache is not a guarantee.
4
Price staleness and the stampede
The stale fraction for a TTL against an update interval, the miss rate a short TTL buys, the λ·d requests that pass through at expiry, and what coalescing reduces them to.
Lessons
10 lessons
What the miss rate does first, then what decides it (skew, size, policy), then the two ways a cache goes wrong, and last the two places a cache is something else: a second level, and a CDN.
Hit Rate and Backend LoadTurn a hit rate into the requests per second the backend still receives, and into the utilisation that leaves it at.Not marked
Average Latency under a CacheCompute the mean latency as a weighted average of two outcomes, and the p99 as a rank that is one of them.Not marked
Popularity Is Skewed: ZipfCompute the share of requests the top k keys carry, as an exact ratio of harmonic sums.Not marked
Cache Size and Hit RateFind the smallest cache that reaches a target hit rate, and price the next nine.Not marked
Replacement Policies on a TraceCount hits for FIFO, LRU, LFU and farthest-in-future at two cache sizes, and find a trace where a bigger cache is worse.Not marked
TTL and StalenessCompute the fraction of reads that see a stale value for a chosen TTL, and the miss rate that shortening it costs.Not marked
Cache StampedesCompute how many requests reach the backend in the window after a hot key expires, with and without coalescing.Not marked
Write PoliciesCount backend writes and bytes at risk for write-through and write-back on a write trace.Not marked
Multi-level CachesCompute the global hit rate and mean latency of two cache levels, given that the second level's rate is conditional.Not marked
CDN Egress and Origin LoadCompute origin gigabytes per day and the monthly egress bill from a byte hit rate, and the gap between that and the request hit rate.Not marked
Recommended background
Capacity Estimation and Queues and Utilisation. Discrete Mathematics “Expected Value”, “Conditional Probability” and “Independence”. Algebra “Piecewise Functions” and “Sigma Notation”.
Practice suggestions
State the miss rate, not the hit rate, whenever you are talking about the backend. Ninety per cent and ninety-nine per cent sound adjacent; ten per cent and one per cent do not, and the backend sees the second pair.
Run the policy lab at two cache sizes before reading the anomaly lesson. Seeing FIFO lose hits when the cache grows is more convincing than the sentence that says it does.
Treat the TTL formula as a sensitivity, not a prediction. It assumes periodic updates and a uniform refresh phase, and the timeline in the lab exists so that you can see the assumption rather than take it.
What it does not cover
Cache coherence protocols; this course’s caches are independent copies with a TTL, not a coherent memory system.
CPU caches beyond the latency table of “Latency Numbers on a Log Scale”.
Eviction implementations — the data structures that make LRU cheap are Algorithms’ business, not this course’s.