Research notes / Cache replacement
Hyperbolic caching: priorities can cross without hits
Published / Exact constructed example
An eviction ranking can become obsolete even when neither object receives another access. The comparison below changes its answer at time 12, without changing either access count.
On this page6 sections
Residence age, not last-access age
Blankstein, Sen and Freedman's hyperbolic policy scores a resident object using its access count divided by time since insertion. It evaluates randomly sampled candidates at eviction time. A hit increments the count without resetting the insertion time. [1, Figure 1]
Consider equal-size, equal-cost objects A and B. A entered at time 0 and has four accesses; B entered at time 9 and has one. A possible history is A at times 0, 1, 2 and 3, then B at 9. Both stay resident and receive no further accesses in this example. These are arbitrary elapsed-time units, not a measured production trace.
The two priorities are 4 / t and 1 / (t - 9), for t > 9. Lower priority means the less valuable candidate under this particular score.
The lower-priority object changes
| Time | A: count 4 | B: count 1 | Lower priority |
|---|---|---|---|
| 10 | 2/5 | 1 | A |
| 12 | 1/3 | 1/3 | Tie |
| 20 | 1/5 | 1/11 | B |
At time 10, A is the lower-priority candidate. At time 20, B is. A queue ordered only by scores calculated at time 10 would still put A first. Reusing that ordering without maintaining it produces the wrong comparison at time 20. This does not rule out an exact time-aware data structure; it rules out treating old keys as current keys.
To find the crossing, multiply by the positive denominators: 4(t - 9) = t, hence t = 12. More generally, counts a and b with insertion times x and y cross at (ay - bx) / (a - b) when a differs from b and the result is later than both insertions. Equal counts need separate handling; there may be no future crossing or a persistent tie.
The table is a comparison at three observation times, not three successive evictions. Removing A at time 10 would violate the assumption that both remain resident until time 20.
A sampled minimum is not the global minimum
The pinned author simulator's ordinary sampling path permits repeated draws. It also offers retained-candidate variants, which this calculation does not model. [2, Sampling.sample]
Fix 100 residents and mark the ten with lowest priority. Eight independent, uniform draws with replacement miss all ten with probability (90/100)^8. The complement is 56.953279%. This answers whether the sample contains any of those ten, not whether it contains the unique worst candidate. For the latter event, substitute one qualifying object for ten.
Eight distinct uniformly sampled residents instead give 1 - choose(90,8) / choose(100,8), exactly 219338127/375935140. Sampling without replacement and eight independent draws are different experiments. Neither probability predicts application hit rate.
What this establishes
This is an exact teaching calculation, not a cache benchmark. It establishes a crossing and two conditional sampling probabilities. It does not rank eviction policies or reproduce the paper's Redis and Django experiments. Costs, expiration, concurrent accesses and history after eviction are outside the constructed case.
The reference rejects zero residence age; deployed software needs an explicit timestamp-resolution and zero-age policy. It reports both objects at a tie instead of inventing a tie-break. Changing time units scales both scores equally and leaves the ordering unchanged.
For a different aging mechanism, compare LRFU. For measured versus constructed evidence, see our SIEVE trace analysis. The corpus definition provides the stable entity and source links.
Reproduce the arithmetic
Download the reference calculation, tests, exact JSON results and method notes. Python's standard library suffices; no workload data or random seed is needed.
python3 -B model.py
python3 -B -m unittest discover -s . -p test_model.pyTests compare scores against integer cross-products, enumerate small sampling spaces independently and cover invalid inputs, zero draws, empty qualifying sets, complete samples, ties and time-unit changes.