# S3-FIFO: Two Decisions, Not a Cache Benchmark

Published: 2026-11-05. Original Hesela example and explanation: CC0-1.0.
Third-party sources retain their own rights.

## Which Counter Test Applies?

The small queue promotes an entry after at least two hits since insertion.
The main queue reinserts a candidate after at least one hit and decreases its
counter. A ghost match routes a fetched object to main; it does not supply data.

These are different decisions. Section 4.1 of the SOSP paper explicitly clears
access bits on movement from small to main. Its printed Algorithm 1 does not
show that reset in the promotion branch. Our isolated decision follows the prose.

The paper caps policy counters at three. The pinned author simulator instead
increments a 64-bit field on hits and clips it when reinserting a main candidate.
The policy's two bits are not a measured total-memory budget.

## A Bound on One Eviction

Let N be the number of main-queue entries, ordered oldest to newest, and let
each initial counter be an integer from zero through three. Assume one eviction
with no concurrent hits, insertions, expiration or resizing.

Every reinsertion subtracts one from the sum of counters. A final inspection
removes a zero-counter entry. Thus:

    inspections <= sum(initial counters) + 1 <= 3N + 1

For two entries starting at three, the candidate IDs are:

| Inspection | Candidate | Counter Before | Action |
| --- | --- | --- | --- |
| 1 | 0 | 3 | Reinsert with 2 |
| 2 | 1 | 3 | Reinsert with 2 |
| 3 | 0 | 2 | Reinsert with 1 |
| 4 | 1 | 2 | Reinsert with 1 |
| 5 | 0 | 1 | Reinsert with 0 |
| 6 | 1 | 1 | Reinsert with 0 |
| 7 | 0 | 0 | Evict |

The bound is attained when every counter starts at three. Concurrent accesses
can replenish credits, so this initial-credit argument no longer establishes
that bound. Candidate inspections are neither milliseconds nor NAND operations.

## Reproduce and Inspect

Download these three files into the same directory:

- [Transition implementation](https://hesela.dev/research/s3fifo-transitions.mjs)
- [Tests with a separate queue oracle](https://hesela.dev/research/s3fifo-transitions.test.mjs)
- [Constructed results and assumptions](https://hesela.dev/research/s3fifo-transitions.json)

With Node.js:

    node --test s3fifo-transitions.test.mjs

The tests exhaust all 5,460 counter vectors of lengths one through six and
check maximum-credit cases up to 4,096 entries. This is deterministic model
verification, not sampling: no confidence interval is appropriate.
The code is not a complete S3-FIFO simulator and does not reproduce the paper's
trace miss ratios, concurrent throughput or flash-admission experiments.

## Sources and Context

- Yang et al., [FIFO Queues are All You Need for Cache Eviction](https://jasony.me/publication/sosp23-s3fifo.pdf), SOSP 2023, DOI 10.1145/3600006.3613147, section 4.1 and Algorithm 1, printed pages 134-135.
- [Pinned author artifact](https://github.com/Thesys-lab/sosp23-s3fifo/tree/6bc49d9630572721b41cd08adfa982775f3cb1de), S3FIFO.c and cacheObj.h. Source inspection; this example does not execute the author simulator.
- [FIFO record and evaluation limitations](https://hesela.dev/terms/fifo-replacement/).
- [Hesela's cache analysis](https://hesela.com/analyses/sieve-cache-eviction-traces/).

Paper and artifact revisited 2026-11-05. The constructed numerical results retain
their original 2026-10-31 example date.