Reuse distance and the miss-ratio curve

Why does one histogram of reuse distances give the miss ratio for every cache size, and how do you sample it?

Reuse distance is the primitive, not time

The wrong measure is "time since the last access". The right one is reuse distance (also called stack distance): the number of distinct items accessed since the previous access to this same item.

Why distinct items and not elapsed time? A cache is displaced by distinct new items, not by clock ticks. Imagine a key accessed 10,000 times in a tight loop over 50 distinct keys. Its reuse distance is at most 49, however long the loop ran. Reuse time overestimates the capacity you need, because it counts repeats that never pushed anything out.

With an LRU cache (LRU = Least Recently Used: when full, evict the entry unused for the longest time) of size 3, all three repeats hit. With size 2, none of them hits. This is the rule behind the next result.

Mattson's result

This is the operationally important theorem of this whole mechanism:

Therefore the miss-ratio curve (MRC), the miss ratio as a function of cache size C, is

DefinitionThe miss-ratio curve →

MRC (C) = P (reuse distance \geq C)

$C$: cache size in entries

One histogram of reuse distances gives the miss ratio for every cache size at once. You do not deploy four cache sizes and compare. You need one trace and one histogram.

Notice the shape: going from 100 to 1,000 entries (ten times more cache) removes 40 points of misses, but going from 1,000 to 10,000 removes only 10 more.

The boundary condition: stack algorithms

The "one histogram gives everything" claim is usually overstated. It holds exactly for stack algorithms: policies that satisfy the inclusion property, meaning the contents of a size-C cache are always a subset of the contents of a size-(C+1) cache. LRU, LFU (Least Frequently Used) and Belady's OPT are stack algorithms.

FIFO (first in, first out), CLOCK (a cheap approximation of LRU), random eviction, and anything with an admission filter (TinyLFU, W-TinyLFU) are not stack algorithms. For those, the MRC must be simulated, not derived. Variable item sizes also break the theorem, and that matters because half of what a data system caches is variable-sized.

So the theorem gives you a free MRC for the LRU family and a reference curve for everything else. That is still valuable: a policy that does worse than the LRU-family MRC at the same size is simply misconfigured.

How to measure it cheaply: SHARDS

Why did nobody measure this before? The naive exact algorithm for stack distance costs O(M·N) for M requests over N distinct items. With an order-statistic tree over the LRU order (a balanced tree that can answer "how many items sit above this one") it is O(M log N). With an algorithm called SHARDS, it is effectively free:

Hash each key.
Admit a key to the sampler only if its hash falls below a threshold T (for a sampling rate of 1%, keep a key if hash mod 100 < 1).
Scale each observed distance by 1/rate (a distance of 12 at a 1% rate stands for about 1,200).

This produces MRCs within about one percent of exact, from a fixed few megabytes of state, regardless of trace length, and it runs online.

import hashlib

RATE = 0.01
def sampled(key: str) -> bool:
    h = int(hashlib.md5(key.encode()).hexdigest(), 16) % 1_000_000
    return h < RATE * 1_000_000

lru = []                         # most recent at the end; only sampled keys
hist = {}                        # scaled distance -> count
for key in request_log:
    if not sampled(key):
        continue                 # spatial sampling: skip the KEY, not the time
    if key in lru:
        d = len(lru) - 1 - lru.index(key)      # distinct sampled keys since last use
        hist[round(d / RATE)] = hist.get(round(d / RATE), 0) + 1
        lru.remove(key)
    lru.append(key)

(This uses a plain list for clarity. It is O(n) per access; real tools use a tree.)

The subtlety that matters, and a common error. The sampling must be spatial (on the key), not temporal (on the request). You cannot estimate an MRC from a five-minute window of requests. Reuse distance counts intervening distinct items. If you drop 90% of the requests you erase exactly the quantity you want to measure, and every distance is biased downward. Key-hash sampling preserves it: for an admitted key you see all of its accesses and all accesses to the other admitted keys, so you get a faithful, scaled-down copy of the trace. This is a case of randomization replacing exhaustive bookkeeping and also of using a sound approximation when the exact computation is too expensive.

In one sentence: distinct-item distance, not elapsed time; one histogram gives the whole curve; sample the keyspace, never the timeline.