hesela.devClean-First LRU (CFLRU)
Clean-First LRU (CFLRU) is a buffer replacement policy that prefers clean victims within a bounded least-recently-used window.
On a full-cache miss, search from the LRU end for the oldest clean page inside the window; otherwise evict the LRU page. A larger window considers more clean candidates but can displace reusable pages. [1]
The paper's trace simulations weighted writes eight times reads. Its Linux 2.4.28 evaluation used emulated flash and disabled read-ahead in the CFLRU variants. Weighted replacement cost is not measured SSD throughput, and the static simulation reported the best tested window. [1]
Accounting example, not a device measurement: with three initially empty slots, writes to page A and reads of B, C, D leave one backing-page write under either LRU or a full clean-first window after a final drain. CFLRU merely postpones it. Rewriting A before that drain lets CFLRU combine the updates into one write while LRU needs two. These results assume write allocation, no intervening flush and successful serial operations. The method, code, tests and exact traces are downloadable. [2]
Another constructed trace saves one backing write but adds one read. Under a constant per-operation cost model, its ranking reverses with the write/read cost ratio; this is not an SSD timing prediction. [4]
A constructed window sweep increases drained writes from 4 to 5 at the same 6 reads when the window grows from two to three slots. Both runs finish with the same dirty residents. Local clean-victim preference does not guarantee fewer total writes over a trace. [4]
Replacing partial writes with full-page overwrites in one paired trace preserves hits and victims but shifts the model's cost crossover from w=r to w=2r. Misses need not equal backing reads: this variant assumes complete coverage without fetching old data. [2]
Relations
- related
- Clean-First Dirty-Clustered (CFDC), Least recently used replacement, Write-back cache, Storage cache flush, Write amplification
Limitations
- A dirty-flag probe count excludes page lookup, recency maintenance and allocation; it does not measure total CPU work or make implementations with the same victim decisions equally fast. [3]
- The replay's dirty-page index avoids scanning clean residents during flush, but adds membership metadata and bookkeeping on dirty-state transitions and evictions. [3]
- Keeping dirty pages cached is not durable commit. Ext4's default journal covers metadata rather than file contents; a journaling filesystem is not a blanket guarantee for retained dirty user data. [6]
Citations
- Seon-yeong Park, Dawoon Jung, Jeong-uk Kang, Jin-soo Kim and Joonwon Lee. CFLRU: A Replacement Algorithm for Flash Memory. CASES 2006, sections 3-6.
- Hesela. Clean-first accounting: method, assumptions and reproduction instructions.
- Hesela. Dependency-free fixed-window CFLRU accounting model.
- Hesela. CFLRU/LRU traces, window sweep and write-coverage comparison, with backing-read and final-drain accounting.
- Linux kernel documentation. Ext4 journal: metadata, file-data modes and committed recovery scope.
Further reading
Sources & caveats
- Historical research policy, not a claim about current Linux reclaim or any shipping SSD.
- The accounting example is an original deterministic model at /research/clean-first-accounting/model.mjs with downloadable tests and inputs; it is not a paper replication or a NAND-write measurement.