Eviction and admission
Design a cache key, freshness policy and miss path while calculating load and mean-latency effects.
THE IDEA
Eviction and admission
A cache is finite. Eviction picks what leaves when it is full; admission picks what may enter. With capacity 2 and the requests A B A B A B X Y Z A B, an LRU cache lets the one-off keys X, Y and Z push out the hot A and B and hits only 4 times; an admission rule that refuses newcomers less popular than the victim hits 6 times. Other access patterns favour other policies, and size matters: a big response that is rarely reused costs more space than it saves.
| policy | hits of 11 | hit rate |
|---|---|---|
| LRU (evict least recently used) | 4 | 0.364 |
| frequency admission (new key must be more popular than the victim) | 6 | 0.545 |
A cache has finite capacity: eviction chooses what leaves, admission chooses what may enter. One-off keys (X, Y, Z) wash out useful entries under LRU. Admission helps here, but other access patterns favour other policies, and a large response that is rarely reused is often not worth caching.
Predict first. Is a rarely reused large response always worth caching?
Chapter context
A cache serves a previously obtained representation instead of repeating work. Its correctness depends on which requests can share a value and how long that value may remain useful. Fast retrieval of the wrong representation is still an error.
TRY IT YOURSELF
Part 1. Do it hands-on
Count hits for two policies by hand, then write both and a value-per-byte rule.
| policy | hits of 11 | hit rate |
|---|---|---|
| LRU (evict least recently used) | 4 | 0.364 |
| frequency admission (new key must be more popular than the victim) | 6 | 0.545 |
A cache has finite capacity: eviction chooses what leaves, admission chooses what may enter. One-off keys (X, Y, Z) wash out useful entries under LRU. Admission helps here, but other access patterns favour other policies, and a large response that is rarely reused is often not worth caching.
- To do: Capacity 2. Requests: A B A B A B X Y Z A B (11 requests). An LRU cache hits how many times? (After the one-off X, Y, Z push A and B out, both miss again.)
- To do: An admission rule lets a new key replace a cached one only if the new key has been requested MORE often. X, Y, Z (seen once each) are refused, A and B stay. Hits?
- To do: LRU hit rate on the 11 requests (3 decimals)?
- To do: Is a rarely reused large response always worth caching? Type yes or no
Part 2. Do it in code
- lru_hits(trace, capacity): number of hits for an LRU cache holding `capacity` keys (a hit refreshes recency; a miss inserts and evicts the least recently used key when full).
- admission_hits(trace, capacity): a frequency-aware cache. Keep a request count for EVERY key seen (including the current request). A hit refreshes recency. On a miss: insert if there is room; otherwise find the victim (the cached key with the lowest count; ties: least recently used) and replace it only if the new key's count is strictly higher; otherwise do not cache the new key.
- hit_rate(hits, total): hits / total (0 for none).
- value_density(expected_reuses, fetch_ms, size_bytes): expected_reuses × fetch_ms / size_bytes (what caching it is worth per byte).
- should_admit(expected_reuses, fetch_ms, size_bytes, min_density): True if the value density is at least min_density.
Stuck, or something not working? You can come back to it any time.
CHECK YOUR UNDERSTANDING
Is a rarely reused large response always worth caching?
Chapter reference: math, worked example & code
This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.
Math and notation
If h is hit probability, t-hit hit-path time and t-miss complete miss-path time:
The miss time here already includes lookup overhead. Means do not establish tail latency, and background refresh can add origin traffic.
Worked example
At 90% hits, 2-ms hit paths and 50-ms complete miss paths, mean latency is 0.9×2+0.1×50=6.8 ms. For 1000 requests/s, nominal origin demand is 100 requests/s. During a complete cache outage, it could become 1000 requests/s rather than remaining at the normal miss rate.
Reference code
The following example uses the Python standard library and does not call a remote service.
from math import isclose
hit=.9
assert isclose(hit*2+(1-hit)*50,6.8)
assert isclose((1-hit)*1000,100)
assert 1000/100 == 10
Python examples are provided for study and local execution; this page does not execute Python.
Common mistakes
A hit ratio is not a correctness guarantee. Mean latency does not reveal p95. Shared caching requires a safe identity and privacy policy; TTL does not replace authorization.