# Segmented LRU: make the capacity rule explicit

This is a constructed, sequential worked example, not a device benchmark or a
native execution of Caffeine. All entries have equal size; every miss is admitted.
There is no TTL, concurrency, ghost history, dirty-data cost or frequency filter.

## Cold start

Total ceiling: three entries. Protected limit: two entries. Requests: A B C A.
Arrays below run from least to most recently used.

| Rule | After A B C: probation | Protected | Final A | Hits / requests |
| --- | --- | --- | --- | --- |
| Shared ceiling | A B C | empty | promotes A | 1 / 4 |
| Reserved segments | C | empty | misses | 0 / 4 |

The reserved variant leaves unused protected slots unavailable to new arrivals.
This is a statement about these specified machines, not a claim that every SLRU
implementation reserves empty slots.

For A A B B C C, both have protected B C and probation A: the sixth request
demotes A without evicting it. A subsequent D miss evicts A from probation.
An entry being protected therefore does not make it pinned.

## Run

Requires Node.js with its built-in test runner; no packages or downloads.

```sh
node --test model.test.mjs
node --input-type=module -e 'import {replay} from "./model.mjs"; console.log(JSON.stringify(replay(["A","B","C","A"],3,2),null,2))'
```

[Model](model.mjs) and [tests](model.test.mjs) are the complete example.
Tests include hand-traced decisions, invalid inputs and 19,680 replay configurations
covering all ternary sequences through length seven, two rules and three capacities.
Exhaustive invariant checks do not prove equivalence with an external implementation.

## Source boundaries

The [2015 TinyLFU preprint, sections 2.1 and 4](https://arxiv.org/pdf/1512.00727v2)
supplies the segment transitions and describes fixed-size segments.
The [pinned simulator's onHit, onMiss and evict methods](https://github.com/ben-manes/caffeine/blob/5227a98b51e02b4d4fbfc2b0e33c362a138f51b1/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/linked/SegmentedLruPolicy.java)
supply the shared-capacity comparison, under positive protected capacity and
always-admit behavior. They were inspected, not compiled here.
The model code is an independently written educational representation.
The [original full 2Q description](https://www.vldb.org/conf/1994/P439.PDF)
is used for the glossary comparison, rather than the differing 2Q summary in
the later preprint.

Generated on 2026-11-18. No published hit-rate, throughput, or latency result is
reproduced or extrapolated. Return to the [definition](https://hesela.dev/terms/segmented-lru/).
