Find the plateau and the knee

Simulate a modelNeeds Python with NumPy

Problem

Real request streams are mixtures: a hot set read again and again, scans that read many keys once per cycle, and keys read only once. Each stream has its own miss-ratio curve, and the cache's curve is their combination. So the curve is not a smooth slope: it has knees, where a whole stream suddenly fits, and plateaus, where adding memory changes nothing because the next stream is still far too big to fit.

See that adding cache memory can do nothing, then a lot.

Build a trace as a mixture of three streams: a hot set of 1,000 keys (70% of requests), a cyclic scan over 50,000 keys (20%), and one-time keys that never repeat (10%).
Simulate LRU at sizes 500, 1,000, 2,000, 5,000, 20,000, 50,000, 60,000. Plot hit rate against size.
Repeat with FIFO and random eviction and compare with the LRU curve.

The script runs 1 million requests and adds sizes 80,000 and 100,000, so the curve reaches the point where the scan fits.

The question. At which cache sizes does the hit rate jump, where is it flat, and does the eviction policy change the shape?

Predict

Under LRU, where does the hit rate's second jump come?

At 50,000 entries, when the scan's keys fitLater, between 60,000 and 80,000There is no second jump

Run it

1Install uv once. It fetches Python and the lab's packages for you.
Terminal
```
curl -LsSf https://astral.sh/uv/install.sh | sh
```

2Get the script. It is the whole lab: read it, then download it.

find-the-plateau-and-the-knee.py82 linesDownload

View the code

find-the-plateau-and-the-knee.py

# /// script
# requires-python = ">=3.10"
# dependencies = ["numpy"]
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""Find the plateau and the knee.

A trace mixing three streams (a hot set, a cyclic scan, one-time keys), run
through LRU, FIFO and random eviction at a range of cache sizes.
"""
import argparse, json, random
from collections import OrderedDict, deque
import numpy as np

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--requests", type=int, default=1_000_000, help="Requests in the trace.")
p.add_argument("--hot", type=int, default=1_000, help="Keys in the hot set.")
p.add_argument("--scan", type=int, default=50_000, help="Keys in the cyclic scan.")
p.add_argument("--mix", type=lambda s: [float(v) for v in s.split(",")], default=[0.7, 0.2, 0.1],
               help="Shares of hot, scan and one-time requests, comma-separated.")
p.add_argument("--sizes", type=lambda s: [int(v) for v in s.split(",")],
               default=[500, 1_000, 2_000, 5_000, 20_000, 50_000, 60_000, 80_000, 100_000], help="Cache sizes, comma-separated.")
p.add_argument("--seed", type=int, default=0, help="Random seed.")
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()
rng = np.random.default_rng(args.seed)
random.seed(args.seed)

# The trace: hot keys 0..hot-1, scan keys cycle in order, one-time keys never repeat
stream = rng.choice(3, size=args.requests, p=args.mix)
trace, scan_pos, fresh = [], 0, 0
hot_draws = rng.integers(0, args.hot, args.requests)
for i, s in enumerate(stream.tolist()):
    if s == 0: trace.append(("h", int(hot_draws[i])))
    elif s == 1: trace.append(("s", scan_pos)); scan_pos = (scan_pos + 1) % args.scan
    else: trace.append(("o", fresh)); fresh += 1


def lru(c):
    cache, hits = OrderedDict(), 0
    for k in trace:
        if k in cache: hits += 1; cache.move_to_end(k)
        else:
            cache[k] = True
            if len(cache) > c: cache.popitem(last=False)
    return hits / len(trace)

def fifo(c):
    cache, order, hits = set(), deque(), 0
    for k in trace:
        if k in cache: hits += 1
        else:
            cache.add(k); order.append(k)
            if len(cache) > c: cache.discard(order.popleft())
    return hits / len(trace)

def rand(c):
    cache, slots, hits = {}, [], 0                      # key -> slot index, so a random victim is O(1)
    for k in trace:
        if k in cache: hits += 1
        elif len(slots) < c:
            cache[k] = len(slots); slots.append(k)
        else:
            i = random.randrange(c); del cache[slots[i]]; slots[i] = k; cache[k] = i
    return hits / len(trace)


rows = []
print(f"{'size':>8} {'LRU':>7} {'FIFO':>7} {'random':>7}")
for c in args.sizes:
    r = {"size": c, "LRU": lru(c), "FIFO": fifo(c), "random": rand(c)}
    rows.append(r)
    print(f"{c:>8,} {r['LRU']:7.1%} {r['FIFO']:7.1%} {r['random']:7.1%}")
ceiling = 1 - args.mix[2]
print(f"ceiling from one-time keys: {ceiling:.0%}")

long_rows = [{"size": r["size"], "policy": pol, "hit_pct": r[pol] * 100} for r in rows for pol in ("LRU", "FIFO", "random")]
if args.json:
    with open(args.json, "w") as f:
        json.dump({"tables": {"hits": long_rows, "summary": [{"ceiling_pct": ceiling * 100}]}}, f)

3Run it in the folder you saved it to, with the defaults first. Then change a knob from the table below and run it again.
Terminal
```
uv run find-the-plateau-and-the-knee.py
uv run find-the-plateau-and-the-knee.py --help     # every knob
```

Knobs
Knob · default	What it changes
--requests1,000,000	Requests in the trace.
--hot1000	Keys in the hot set.
--scan50,000	Keys in the cyclic scan.
--mix0.7, 0.2, 0.1	Shares of hot, scan and one-time requests, comma-separated.
--sizes500, 1000, 2000, 5000, 20,000, 50,000, 60,000, 80,000, 100,000	Cache sizes, comma-separated.
--seed0	Random seed.

Our run

Hit rate by cache size, three eviction policiesApple M2 · 8 cores · 8 GB

LRUFIFOrandom

Data table

Hit rate by cache size, three eviction policies
Cache size (entries)	series	Hit rate
500	LRU	23%
500	FIFO	21.5%
500	random	21.6%
1K	LRU	42.2%
1K	FIFO	36.7%
1K	random	36.7%
2K	LRU	64.2%
2K	FIFO	52.1%
2K	random	52.2%
5K	LRU	69.8%
5K	FIFO	63.3%
5K	random	63.3%
20K	LRU	69.8%
20K	FIFO	68.3%
20K	random	68.7%
50K	LRU	69.8%
50K	FIFO	69.2%
50K	random	74.3%
60K	LRU	69.8%
60K	FIFO	69.3%
60K	random	76.3%
80K	LRU	84.9%
80K	FIFO	79.6%
80K	random	80%
100K	LRU	84.9%
100K	FIFO	79.6%
100K	random	82.5%

macOS 26.6.2 · Python 3.13.3 · numpy 2.5.4 · run 2026-10-20

Output · uv run find-the-plateau-and-the-knee.py

    size     LRU    FIFO  random
     500   23.0%   21.5%   21.6%
   1,000   42.2%   36.7%   36.7%
   2,000   64.2%   52.1%   52.2%
   5,000   69.8%   63.3%   63.3%
  20,000   69.8%   68.3%   68.7%
  50,000   69.8%   69.2%   74.3%
  60,000   69.8%   69.3%   76.3%
  80,000   84.9%   79.6%   80.0%
 100,000   84.9%   79.6%   82.5%
ceiling from one-time keys: 90%

What we found

LRU shows the knee and the plateau as expected: the hit rate climbs to 64.2% by 2,000 entries and then stays at 69.8% all the way to 50,000. The second jump does not come at 50,000, where the scan's keys would fit on their own. Between two visits to the same scan key, the hot set and about 25,000 one-time keys pass through the cache too, so LRU needs room for all of them: the jump arrives between 60,000 (69.8%) and 80,000 (84.9%), and the curve then levels off below the 90% ceiling.

FIFO and random eviction reach the knee more slowly, because they sometimes evict hot keys. Random eviction has no clean plateau: it keeps a random part of the scan, so it climbs slowly through the range where LRU is flat, and at 50,000 entries it is ahead of LRU (74.3%).

Read it

Inside a plateau, doubling the memory buys nothing; just past a knee, a little memory buys a lot. That is why cache sizing has to start from the curve and not from a rule of thumb, and why "the hit rate did not improve when we added memory" is not proof that more memory will not help.

LRU is the worst possible policy for a cyclic scan just larger than the cache: it evicts each scan key just before it is needed again, so the scan never hits. The one-time keys show the other lesson. They can never hit, yet they occupy LRU slots on their way through, which moves the knee of every other stream. Keeping such keys out of the cache in the first place is admission, the subject of the scan-resistance lab.