The Cache Shelf
A small cache in front of a slow origin. Change the eviction policy, the shelf size and the request pattern, and watch the hit rate move.
A small cache in front of a slow origin. Change the eviction policy, the shelf size and the request pattern, and watch the hit rate move.
Experiment 01 · Caching
An empty shelf of 3 bays in front of a slow origin.
A is missing: fetched from the origin into empty bay 1.
B is missing: fetched from the origin into empty bay 2.
A is on the shelf in bay 1: a hit, served without touching the origin.
C is missing: fetched from the origin into empty bay 3.
A is on the shelf in bay 1: a hit, served without touching the origin.
B is on the shelf in bay 2: a hit, served without touching the origin.
D is missing: fetched from the origin into bay 3, evicting C, the least recently used key.
B is on the shelf in bay 2: a hit, served without touching the origin.
A is on the shelf in bay 1: a hit, served without touching the origin.
B is on the shelf in bay 2: a hit, served without touching the origin.
E is missing: fetched from the origin into bay 3, evicting D, the least recently used key.
A is on the shelf in bay 1: a hit, served without touching the origin.
B is on the shelf in bay 2: a hit, served without touching the origin.
C is missing: fetched from the origin into bay 3, evicting E, the least recently used key.
A is on the shelf in bay 1: a hit, served without touching the origin.
B is on the shelf in bay 2: a hit, served without touching the origin.
| Policy | 2 bays | 3 bays | 4 bays | 5 bays |
|---|---|---|---|---|
| Least recently used | 25% | 63% | 63% | 69% |
| Oldest first | 13% | 38% | 50% | 69% |
Dots under each bay show the eviction order; the single dot goes next.
The tall cabinet is the origin: correct, but slow and expensive to reach. The shelf in front of it holds a few keys. A request that finds its key on the shelf is a hit and never touches the origin. A miss goes to the origin, and the key it brings back needs a bay, so something already on the shelf has to leave.
Which key leaves is the eviction policy. Least recently used evicts the key that has gone longest without being asked for. Oldest first evicts the key that has been on the shelf longest, however popular it is.
Every key is the same size, nothing expires and the request order is fixed. Real caches weigh entries by size, expire them by time, and see traffic that shifts through the day. The trade-off, keeping what will be asked for next, is the same.