# Clean-first replacement: count reads and the final drain

Hesela, 31 October 2026. Five constructed comparisons, a window sweep and a write-coverage comparison.
No storage device was benchmarked. This is not a replication of a paper.

## Method

Three initially empty equal-size slots; successful serial operations only.
Every read or partial-page write miss fetches one page. Full-page overwrite
misses allocate without fetching old data. Hits update recency.
The first five examples compare LRU (window 0) with fixed-window CFLRU
(window 3); the sensitivity example replays all windows from 0 to 3.
FLUSH writes all dirty resident pages and preserves recency. Every run then
writes the remaining dirty pages in a final drain.

| Trace | LRU reads | CFLRU reads | LRU eviction writes | CFLRU eviction writes | LRU total writes | CFLRU total writes |
| --- | ---: | ---: | ---: | ---: | ---: | ---: |
| W0 R1 R2 R3 | 4 | 4 | 1 | 0 | 1 | 1 |
| W0 R1 R2 R3 W0 | 5 | 4 | 1 | 0 | 2 | 1 |
| W0 W1 R2 R3 R2 R3 | 4 | 6 | 1 | 0 | 2 | 2 |
| W0 R1 R2 FLUSH R3 W0 | 5 | 5 | 0 | 0 | 2 | 2 |
| W0 W1 R2 R3 R2 R3 W0 | 5 | 6 | 2 | 0 | 3 | 2 |

W means partial-page write, R means read; numbers are arbitrary logical page
IDs. Reads equal misses for these partial-write traces, not for full overwrites. Total writes include
dirty evictions, explicit flushes and the final drain.

The first trace only defers a write. The second coalesces updates.
The third adds two reads without saving a write. The fourth shows a flush
removing that coalescing opportunity. In the fifth, CFLRU saves one write
but needs one extra read.

## Cost boundary

For the fifth trace only, a score reads*r + totalWrites*w gives
CFLRU minus LRU = r - w. For positive costs, CFLRU wins if w > r,
ties if w = r and loses if w < r. At r=1, illustrative w=0.5, 1, 2
give LRU/CFLRU scores 6.5/7, 8/8, 11/10.

This arithmetic is not elapsed time, energy, NAND programming or endurance.
It omits CPU work, dirty-flag search (nine probes here), queueing and overlap.
Unlike an eviction-only score it includes cold reads and the final drain.
Actual read/write costs need not be constant or identical across policies.

## A larger window can cause more writes

For the constructed trace `W0 W1 R2 W3 R0 R1 W2 W3`, keep capacity
fixed at three slots and vary only the clean-first window:

| Window (slots) | Backing reads | Eviction writes | Final-drain writes | Total writes | Dirty-flag probes |
| ---: | ---: | ---: | ---: | ---: | ---: |
| 0 (LRU) | 8 | 3 | 2 | 5 | 0 |
| 1 | 8 | 3 | 2 | 5 | 5 |
| 2 | 6 | 1 | 3 | 4 | 6 |
| 3 | 6 | 2 | 3 | 5 | 9 |

There are no explicit flushes in this trace. At `W3`, window 2 writes
dirty page 0 because neither of its two oldest candidates is clean.
Window 3 instead drops clean page 2. That avoids a write now but changes
later residency: at `W2`, the wider window evicts dirty page 3, so the
final `W3` must fetch and dirty it again. Window 2 still holds page 3
and combines that last update.

Both runs end with the same three dirty pages, in order 1, 2, 3.
The difference survives the final drain: window 3 adds one backing write,
with no read-count advantage over window 2. For any positive constant
write cost, its read-plus-write score is worse on this trace. Write count
is not monotone in window size here: it is 5, 5, 4, 5 for windows 0-3.

This is an exact counterexample to a universal monotonic-write assumption
under this model, not a claim that window 2 is generally optimal, a
frequency estimate, a shortest-trace proof or an SSD benchmark. Capacity
does not change, so this is not a cache-capacity anomaly. The original
five LRU/full-window examples remain unchanged; the additive
`windowSensitivity` field retains every run and event.


## A cache miss is not always a backing read

The earlier examples use partial-page writes, which fetch the old page on
a miss in this model. A full-page overwrite supplies the complete replacement
and allocates a dirty cache page without reading its old contents. Both update
recency, and both must write dirty victims before reuse. This is write allocation,
not write-around, and skipping the old-data read does not make the write durable.

Keep the fifth trace's page references and write positions, but replace W
(partial write) with O (successful full-page overwrite):
`O0 O1 R2 R3 R2 R3 O0`. Capacity and the two policies stay unchanged.

| Write coverage | LRU misses | CFLRU misses | LRU backing reads | CFLRU backing reads | LRU total writes | CFLRU total writes |
| --- | ---: | ---: | ---: | ---: | ---: | ---: |
| Partial (W) | 5 | 6 | 5 | 6 | 3 | 2 |
| Full (O) | 5 | 6 | 2 | 4 | 3 | 2 |

The hit decisions, victims and final dirty pages are identical between
coverage variants for each policy. Only the old-data read requirement changes.
LRU avoids three reads, including the final overwrite miss; CFLRU avoids
only two because that final overwrite was already a hit.

Using backingReads*r + totalWrites*w, CFLRU minus LRU is now 2*r - w,
rather than r - w. At r=1 and w=1.5, partial writes favor CFLRU
(9 versus 9.5), but full overwrites favor LRU (6.5 versus 7).
These exact scores describe this selected trace, not a workload average.
The new `backingReads` field counts reads separately from `misses`;
all earlier counters, hit/victim decisions and traces are preserved.

There is a concrete source boundary behind the distinction: Linux v6.12
`__iomap_write_begin` skips old-data preparation for a fully covered folio
outside the unshare path. This is a scoped implementation example, not a
claim that every full application write avoids every lower-layer read.
[Source: Linux v6.12, fs/iomap/buffered-io.c](https://github.com/torvalds/linux/blob/v6.12/fs/iomap/buffered-io.c).

Our model does not implement Linux, folios, holes, unwritten extents,
unaligned sub-block writes, copy-on-write unsharing, metadata, RAID or
short/failed copies. Partial writes to an existing uncached page are modeled
as needing its prior contents; a real sparse/new allocation can instead
require zeroing. The full overwrite completes successfully by assumption.
No hardware speedup, crash atomicity or durability result follows.


## Policy probes are not implementation work

A clean-victim search examines at most the configured window on a full-cache
miss; a hit needs no such search. This counter does not include finding the
requested page, maintaining recency, building output, runtime allocation or GC.
Hesela's earlier array implementation could scan every resident on a hit and
shift elements on promotion, even when cleanSearchProbes was zero.

The replay now uses an insertion-ordered Map, promotes with delete/reinsert,
and leaves an already newest page in place. It still scans the original
window: neither the policy nor any retained trace, victim or counter changes.
Explicit flush visits dirty residents via a separate index; the final output
still enumerates all residents. Per-event output is retained, so total memory
is not bounded by cache capacity alone.

This is different from the two-queue improvement in DaMoN09 section 3.1,
which removes clean-page search while preserving the original CFLRU hit/write
behavior described there. CFDC then adds dirty clustering in section 3.2.
A faster implementation and a different victim policy are separate changes.
[Primary paper, sections 3.1-3.2](https://event.cwi.nl/damon2009/DaMoN09-FlashReplacementPolicy.pdf).

Map access is required to be sublinear on average, not guaranteed constant-time
in the worst case by ECMAScript. Iterator, allocation and dirty-window costs
remain runtime-dependent; the change does not promise every replay is faster.
[ECMAScript Map requirements](https://tc39.es/ecma262/multipage/keyed-collections.html#sec-map-objects).

## Reproduce without the Hesela repository

Download these five files into an empty directory:
- [model.mjs](https://hesela.dev/research/clean-first-accounting/model.mjs)
- [model.test.mjs](https://hesela.dev/research/clean-first-accounting/model.test.mjs)
- [examples.json](https://hesela.dev/research/clean-first-accounting/examples.json)
- [README.md](https://hesela.dev/research/clean-first-accounting/README.md)
- [SHA256SUMS](https://hesela.dev/research/clean-first-accounting/SHA256SUMS)

With Node.js 22 or later, no npm packages are required:

```sh
sha256sum -c SHA256SUMS
node --test model.test.mjs
node model.mjs > regenerated.json
cmp examples.json regenerated.json
```

The input traces, event-level hit/victim decisions, explicit flush counts,
dirty residents before the drain and all counters are in examples.json.
No randomness is used. The independent timestamp/sort oracle checks 531,441
length-five cases over four page IDs and flush across capacities 1-3 and
windows 0-capacity, plus the longer tradeoff and window-sensitivity traces.
Four page IDs ensure that the three-slot cache actually evicts pages. Another
257,049 comparisons cover all length-four traces mixing reads, partial writes,
full overwrites and flushes over four IDs and the same nine configurations.
The paired coverage example is also checked independently. These 788,490
finite oracle comparisons are not a formal proof. The portable suite has 17 tests. Longer mixed traces also check 14 capacity/window settings,
large page IDs, recency promotion and flush boundaries.

## Evidence and limits

CFLRU's window rule is from Park et al., CASES 2006, section 3:
https://www.cecs.uci.edu/~papers/esweek06/cases/p234.pdf

For why fewer writes need not mean higher throughput, see Ou, Harder and Jin,
DaMoN 2009, section 4.3:
https://event.cwi.nl/damon2009/DaMoN09-FlashReplacementPolicy.pdf

All traces, cost boundaries, the window sweep and coverage pair are Hesela's constructed examples,
not data taken from either paper. There is no CFDC implementation, FTL,
garbage collection, background writeback, prefetch, admission, crash recovery,
concurrency or failed operation. A full clean-first window illustrates a
boundary; it is not a recommended production configuration.

## Flush implementation and cost

Explicit flush now uses a separate set of dirty resident objects. A clean-to-dirty
transition adds one membership; a dirty eviction removes it; a successful flush
clears those pages and the set. Repeated writes to an already dirty page do not
add another membership. Eviction removes membership without changing the saved
victim's dirty flag, so earlier event records remain accurate. The resident LRU
order, window search, counters, final-drain convention and example JSON do not
change.

With R resident pages and D dirty residents immediately before flush, the explicit
flush loop visits D pages rather than R: O(D) loop work, including zero visits
when D=0. This needs additional membership metadata for up to R objects and
bookkeeping on dirty transitions and evictions. The final output still enumerates
all R residents; recording every event still costs space proportional to trace
length. This is not a memory-free optimization or a constant-time whole replay.

The regression fills 1024 slots, dirties two pages, then issues 512 flushes.
Resident-map enumeration falls from 525312 visits to 1024 for the final snapshot;
the dirty-set loop visits two objects. Both versions record exactly two explicit
backing writes. An independent timestamp/sort oracle checks the entire output.

This is an implementation change to the same fixed-window model, not a CFDC
implementation, asynchronous writeback or a storage-device benchmark. A flush
still means synchronous successful cleaning of every dirty resident, not measured
fsync latency or proof of power-loss durability.