# Why a second read need not earn a place in the main cache

The fixed trace A B C D A E A uses four equal-size slots, Kin=1 and
Kout=2. The fifth request finds A resident in both variants; request six
then distinguishes their eviction decisions.

| Variant | Resident hits | Backing reads | Sixth-request victim | Seventh-request action |
| --- | ---: | ---: | --- | --- |
| Full 2Q | 1 | 6 | A | Reload A from history |
| Simplified 2Q | 2 | 5 | B | Refresh resident A |

These seven-request totals are a constructed example, not a representative
workload, performance ranking, SSD measurement or reproduction of published
experiments. The seventh request is a history hit only in the full variant,
but still counts as a data miss. All snapshots are retained in example.json.

## Reproduce

Download [source](./decision-example.mjs), [tests](./decision-example.test.mjs) and [evidence](./example.json)
into one directory, then run:

```sh
node decision-example.mjs
node --test decision-example.test.mjs
```

No package installation or network fetch is required. The JSON command writes
to stdout; the tests compare it with the retained bytes. Node's built-in test
runner is required.

## Scope

The model is read-only, starts empty and uses equal-size page IDs. Arrays are
ordered oldest first. Reclaim precedes removal of a returning history ID,
matching the pseudocode operation order; histories are disjoint from residents.
It models neither dirty-write costs, pinning, concurrency nor I/O latency.
The small test set checks explicit decisions and bounds, not all possible traces.
Array lookup work is not a constant-time implementation of the paper.

## Reading the history budget

Kout counts identifiers, not seconds or resident payload slots. Only input-list
eviction appends to the history in this model. The added regression checks
distinguish that event from resident requests and main-list eviction; the
original seven-request evidence is unchanged. A larger history needs more
metadata even when resident capacity stays fixed.

## Larger history can increase reads

Keeping more ghost identifiers does not guarantee fewer misses. Starting empty,
the read trace **A B C D A E B C A** uses three resident slots and Kin=1:

| Kout (ghost identifiers) | Resident hits | Backing reads | Final A |
| ---: | ---: | ---: | --- |
| 1 | 1 | 8 | Resident hit |
| 2 | 0 | 9 | Data miss |

Only Kout changes. Both cases have the same resident data capacity, but the
larger history has a larger metadata allowance. Ghost hits still require reads.

After request six, both cases retain D and E in A1in and A in Am. With Kout=1,
history contains only C; with Kout=2, it contains B then C. The divergence follows:

| Request | Kout=1 | Kout=2 |
| --- | --- | --- |
| 7: B | History expired; admit to A1in, evict D | History hit; admit to Am, evict D |
| 8: C | History expired; admit to A1in, evict E | History hit; A1in equals Kin, so evict A from Am |
| 9: A | Resident in Am; no read | Absent from every queue; read again |

The additional promotion changes the next victim. A history entry can therefore
affect future misses, not merely rescue the identity of an already missed page.
This finite example disproves a monotonic guarantee under this model; it does
not estimate how often the effect occurs or identify an optimal history size.
It neither varies resident capacity nor demonstrates a hardware slowdown.

Download [counterexample data](./history-budget.json) and
[transition tests](./history-budget.test.mjs) alongside the three original
files. Every one of the eighteen queue snapshots has a hand-traced expectation:

```sh
node decision-example.mjs --history-budget
node --test decision-example.test.mjs history-budget.test.mjs
```

The default command and original seven-request JSON are unchanged. Unrecognized
options return an error instead of silently selecting the default example.
This is an additional constructed example, not a replay of either paper's traces.

## Primary references

- Johnson and Shasha, VLDB 1994, section 2, printed pages 441-442:
  https://www.vldb.org/conf/1994/P439.PDF
- Waldspurger et al., USENIX ATC 2017, sections 2 and 4.2:
  https://www.usenix.org/system/files/conference/atc17/atc17-waldspurger.pdf

Source PDFs are linked, not redistributed. Accessed 2026-10-31.