Reuse distance and an LRU miss curve

For a repeated reference to key x, count the distinct other keys accessed since the previous x. That is the reuse distance under the convention used here. A first reference has no previous occurrence and is cold. In a fully associative C-entry LRU cache that admits all misses, stores equal-size entries, and has no expiration or external invalidation, x hits exactly when this distance is less than C. Equality means enough distinct competitors have displaced it.

Consider A, B, B, C, A. Between the two A references are three requests but only two distinct keys, B and C. A three-entry LRU cache can retain A through those competitors, while a two-entry one cannot. Write the actual recency list after each operation if the boundary feels confusing. Hit accesses update recency too; ignoring them changes the policy being simulated and can produce an incorrect trace even when the resident key set initially looks plausible.

Count cold references separately and group repeated references by reuse distance. For each candidate capacity, add cold references and repeated references whose distance is at least that capacity. Dividing by all references gives the miss ratio for this trace under the specified LRU model. It is a historical calculation, not a guarantee that the future workload has the same distribution. Warm-start state and trace truncation can change which references are classified as cold.

Byte-bounded caches require object-size-aware reasoning, and TTL or invalidation can remove an entry even when its stack distance is small. Admission rejection also breaks the admit-all premise. Distributed caches add placement and independent per-node budgets; a global trace curve cannot automatically predict each shard's pressure. Treat the simple curve as a baseline hypothesis and explain every extra mechanism before comparing it with a measured application hit ratio.

A deterministic cyclic workload makes the capacity boundary easy to verify. If the cycle has P distinct keys and no other requests intervene, each repeated reference has distance P−1. A capacity of at least P retains the cycle after cold fills; smaller capacity misses continually under admit-all LRU. This is not a claim that real traffic is cyclic. It is a useful diagnostic example for learning why a one-entry capacity difference can change reuse sharply.

Reset the cache lab and set both C=4, s=4. Its (i×s) mod 16 stream has period four; predict four misses and twelve hits among its initial sixteen requests, then Step to add one hit. For a separate run Reset and re-set C=3, s=4; predict sixteen misses. The trace starts empty and caps at 4096 requests. These are abstract equal-size entries with no TTL or admission filter, so this activity directly tests the stated LRU distance condition rather than a Redis implementation.