LeaFTL: A Learning-Based Flash Translation Layer for Solid-State Drives

An SSD's address-mapping table is the biggest tenant of its scarce in-device DRAM, and every prior compression was a hand-written heuristic for one rigid access pattern; LeaFTL LEARNS the logical-to-physical mapping as piecewise linear segments — 8 bytes covering ~20 entries each, irregularity absorbed by a tunable error bound — and makes approximation safe inside firmware because flash's out-of-band metadata verifies every prediction at the cost of at most one extra access, yielding 2.9× smaller tables and 1.4× faster storage, validated on a real open-channel SSD.

The argument in one glance

Problem

The map of the SSD is crowding out the SSD's own memory

Flash forbids in-place updates: writes go to fresh pages, so a logical address's physical home moves constantly, and the flash translation layer must maintain a logical-to-physical mapping for every page. Modern SSDs use page-level mapping — 8 bytes per 4 KB page — because it gives the fastest lookups and cheapest garbage collection. But that makes the mapping table the largest data structure in the controller's DRAM, and while flash capacity keeps climbing, controller DRAM cannot follow (cost and power budgets). Whatever DRAM the map consumes, data caching loses.
What people did

Cache it on demand, or compress the obvious patterns

DFTL keeps only recently-used mapping entries in DRAM, fetching the rest from flash on miss — trading table size for extra flash reads on the critical path. SFTL compresses by exploiting spatial locality: strictly sequential runs of pages collapse into compact entries.
Why it fell short

Human heuristics recognize one pattern each

SFTL's compression fires only on STRICTLY sequential mappings — one heuristic, one rigid pattern. Real workloads mix contiguous runs, regular strides, and near-linear-but-jittery regions that no hand-written rule captures, so most of the table stays uncompressed, DRAM stays tight, cache hit rates stay low, and misses keep adding flash accesses. The heuristic toolbox had no way to adapt to whatever pattern the workload actually exhibits at runtime.
This paper's idea

Learn the map — and let the flash itself catch the errors

LeaFTL fits piecewise linear regression over logical-to-physical mappings as writes flow through the controller's existing data buffer: each learned segment (start, length, slope, intercept) takes 8 bytes and covers 20.3 mappings on average — and with a tunable error bound γ, even irregular patterns compress, falling back to point segments (never worse than page mapping) for pure randomness. Mispredictions are made SAFE by flash's out-of-band metadata: each page's OOB stores the reverse mappings of its 2γ+1 neighbors, so a wrong guess costs exactly one extra flash access. A log-structured segment table with conflict resolution and compaction absorbs constant remapping. Results: 2.9× smaller tables than SFTL (up to 37.7× vs DFTL), 1.4× average storage speedup — confirmed on a real 1 TB open-channel SSD.

Why this problem is worth solving

The

flash translation layer — the firmware inside every SSD that hides flash’s physics from the host: it maps logical page addresses (LPAs) to physical page addresses (PPAs), runs garbage collection (flash erases only whole blocks, so stale pages must be reclaimed), and wear-levels (each block endures a limited number of erases). It runs on embedded ARM-class cores with a small pool of in-device DRAM

is one of computing’s great hidden systems: every phone, laptop, and datacenter drive runs one, and its address-mapping table sits on a textbook space-versus-speed knife edge. Because flash’s out-of-place writes relocate data continuously, the map is huge, hot, and ever-changing — and it competes for controller DRAM against the data cache that actually absorbs I/O latency. Every byte the map gives back converts directly into cache hit rate.

What makes this paper more than an SSD tweak is the idea it transplants:

the insight (Kraska et al., 2018) that an index is just a model of the mapping from keys to positions — so a fitted model, often piecewise linear, can replace a tree or table at a fraction of the space, IF mispredictions can be bounded and corrected cheaply. Celebrated in databases; previously confined to hosts with abundant resources

. Firmware seems like the worst place for approximate data structures — a wrong physical address means reading the wrong page — and the paper’s central discovery is that SSDs are, in fact, the best place: flash pages already carry

out-of-band bytes — 64–256 spare bytes physically attached to every flash page, written together with the data, conventionally holding ECC and a reverse mapping (the page’s own LPA). LeaFTL repurposes them to store the reverse mappings of neighboring pages too, turning every page into a self-verifying, self-correcting index leaf

that makes verification free and correction one bounded access. A learned structure is only as deployable as its failure handling, and here the hardware supplies it.

What people did before, and where it broke

Page-level mapping (the incumbent). One 8-byte entry per page: fastest lookup, minimal GC overhead, enormous table — a 2 TB SSD needs ~4 GB of map. Block-level and hybrid mappings shrink the table but perform dramatically worse (lookup indirection, brutal GC), which is why modern SSDs don’t use them.
DFTL (demand caching). Keep hot entries in DRAM, page the rest from flash. Misses put flash reads on the critical path — the cost scales with how badly the working set overflows DRAM.
SFTL (heuristic compression). Detects strictly sequential LPA→PPA runs and stores them compactly. Works exactly as far as the heuristic’s pattern: regular strides, interleaved streams, and approximately-linear regions — abundant in real traces — get no compression, and nothing adapts at runtime.
Semantic FTLs (e.g., GraphSSD). Import application knowledge into the controller — effective but application-specific, complicating generic SSDs. LeaFTL’s premise is the opposite: no host semantics, just patterns learnable from the address stream itself.

How LeaFTL works

LeaFTL inside the SSD controller

Learn on the write buffer, for free new

SSD controllers already buffer writes to issue large flash chunks in parallel. When the buffer flushes, LeaFTL sorts the buffered pages by LPA (an allocation tweak that also makes patterns more learnable), takes the resulting LPA→PPA pairs, and runs greedy piecewise linear regression — negligible work for the controller's ARM cores, on data already in hand.
↓ →
Segments: 8 bytes for ~20 mappings new

Each learned segment (S, L, K, I) says: for LPAs in [S, S+L], PPA = ⌈K·LPA + I⌉. Encoding: 1 byte each for S and L (S is an offset within a 256-LPA group), 2 bytes slope, 4 bytes intercept. Accurate segments capture contiguous and regularly-strided runs exactly; with error bound γ > 0, APPROXIMATE segments capture jittery near-linear patterns too. Average coverage: 20.3 mappings per segment; worst case degenerates to single-point segments (L=0, K=0, I=PPA) — never larger than page-level mapping.
↓ →
Misprediction safety via OOB neighbors new

An approximate segment returns a PPA within ±γ of the truth. LeaFTL reads the predicted page and checks the reverse mapping in its OOB; on a mismatch, the OOB's stored reverse mappings for the 2γ+1 neighboring PPAs pinpoint the correct page — exactly ONE extra flash access, versus log(γ) probing without the trick. OOB's 128–256 spare bytes hold 32–64 reverse entries; γ is configurable (0 by default, up to 16 evaluated).
↓ →
A log-structured segment table + CRB new

Out-of-place writes constantly supersede old mappings, so segments land in the topmost level of a per-group log-structured table (levels sorted, lookups top-down via binary search). Overlapping APPROXIMATE segments are disambiguated by a Conflict Resolution Buffer — a nearly-sorted, deduplicated list of each approximate segment's exact member LPAs (one byte each; 13.9 bytes average per group). Background compaction merges levels, reconstructing member LPAs via bitmaps and pruning superseded entries.
↓ →
Coexistence with GC and wear leveling

Garbage collection and wear leveling migrate pages, invalidating learned mappings for moved blocks; LeaFTL simply relearns segments for the migrated pages and inserts them as new topmost-level entries — the same path as ordinary writes. Lifetime impact is measured as minimal.
↓ →
Implementations

Built in the validated WiscSim SSD simulator (2 TB configuration, LRU read-write cache) AND as 4,016 lines of C on a real 1 TB open-channel SSD (16 channels, 16 KB pages) whose host-side FTL SDK exposes raw read/write/erase. Open source.

From UIUC and Western Digital Research (ASPLOS 2023). Compared against DFTL (demand-cached page mapping) and SFTL (spatial-locality compression) — block/hybrid mappings excluded as uncompetitive — on MSR Cambridge and FIU traces, plus FileBench and MySQL/BenchBase workloads on the real device.

The idea

An address map is a function; fit it. Plotted as points (LPA, PPA), a mapping table is just a scatter — and because controllers batch writes and allocate physical pages in order, that scatter is full of near-linear structure: contiguous runs (slope 1), regular strides (slope 1/k), and jittery almost-lines. Piecewise linear regression is the minimal model family that captures all of these in constant space per piece, degrades gracefully to point segments under pure randomness (costing no more than the incumbent), and fits in microseconds on an embedded core. Where SFTL hard-coded one recognizable pattern, regression discovers whatever pattern the workload exhibits — the measured result being that 98–99% of learned segments stay small enough for the compact encoding while averaging 20.3 entries each, a ~20× density win over one entry per page.

Buy compression with an error bound, then make errors cost exactly one access. The γ knob is the paper’s central trade: raising it lets one segment swallow messier point sets (fewer segments, smaller table), at the price of predictions that may be off by up to γ pages. What makes the trade safe — and this is the transplant insight — is that flash already writes metadata physically alongside every page. Storing the reverse mappings of the 2γ+1 neighbors in each page’s OOB turns the error bound into a guarantee: the true page is provably within the neighborhood the predicted page’s OOB describes, so verification is free (the OOB arrives with the read) and correction is one bounded follow-up read. Approximation without verification is a bug factory; approximation with hardware-supplied verification is a compression scheme.

Log-structure the learning, because flash never sits still. A learned index over a static array is easy; an FTL’s mapping churns with every write, GC pass, and wear-leveling swap. LeaFTL’s answer is the LSM playbook applied to segments: new learning always lands on top, lookups scan levels newest-first, compaction merges and prunes below, and the CRB resolves the one genuinely tricky ambiguity — approximate segments with overlapping LPA ranges whose exact membership can’t be inferred from four parameters. The engineering keeps every auxiliary structure tiny (one-byte LPAs within 256-LPA groups, ~14-byte CRBs, bitmap-based merges) so the savings the segments earn aren’t spent on the bookkeeping that manages them.

A write burst and a read, through LeaFTL

From buffered writes to a verified lookup

LPA/PPA = logical/physical page address. Segment = (S, L, K, I): PPA = ⌈K·LPA + I⌉ for LPA ∈ [S, S+L]. γ = error bound of approximate segments (default 0). CRB = conflict resolution buffer listing approximate segments' exact member LPAs. Numbers from the paper's simulator and real-SSD evaluations.

Step 1 of 7

Writes accumulate; allocation sets up the lesson

The controller's data buffer fills with write requests. On flush, LeaFTL orders the buffered pages by LPA before assigning physical pages — a free re-ordering that makes the resulting LPA→PPA relation as close to linear as the workload allows — then issues the parallel flash writes, storing each page's reverse mappings (its own LPA and its 2γ+1 neighbors') into the OOB.

learning input = the flush batch: no extra data collection
allocation tweak converts learnability into policy

Why it works

Controllers batch writes and allocate physical pages in order → the LPA→PPA scatter is largely piecewise-linear → regression compresses ~20 mappings into 8 bytes where heuristics saw only “not strictly sequential,” and pure randomness degrades to point segments no worse than the incumbent.
The error bound γ converts messiness into compression → more point sets fit per segment as tolerance grows → the table shrinks further (another 1.3× by γ=16) while correctness never depends on the fit being good.
Flash pages carry OOB bytes written with the data → storing 2γ+1 neighbors’ reverse mappings makes every prediction self-verifying and self-correcting within one extra access → the classic learned-index deployment blocker (misprediction handling) is solved by hardware the SSD already has.
Mapping churn is the FTL’s steady state → a log-structured segment table with CRB and compaction absorbs continuous relearning, and GC/wear-leveling reuse the ordinary insert path → learning survives contact with flash’s lifecycle.
DRAM freed from the map becomes data cache → the compression compounds into hit-rate and latency wins → memory savings (2.9×) translate to end-to-end speedups (1.4×) rather than staying a bookkeeping statistic.

What it costs

Approximation machinery. CRBs, per-group levels, and compaction are new moving parts in firmware; the CRB averages ~14 bytes per group but is another structure to maintain correctly under churn.
Misprediction reads, bounded but real. With γ > 0, some lookups pay one extra flash access; the default configuration (γ=0) forgoes the extra compression to keep every segment exact.
OOB is shared real estate. The reverse-mapping trick spends 4(2γ+1) of the 64–256 OOB bytes that also serve ECC and existing metadata — fine at evaluated γ, a constraint on how far the knob turns.
Workload dependence. Compression tracks how linear the allocation-ordered address stream is; adversarially random workloads collapse to point segments and parity with page mapping (the safety floor, but no win).
Evaluation scale. The headline numbers come from a simulator (validated, plus a real open-channel prototype at 1 TB with host-side FTL); enterprise-controller integration — with its vendor-specific buffers, ECC pipelines, and multi-core firmware — remains engineering ahead.

The evaluation

Two platforms: a validated simulator (WiscSim, 2 TB SSD, 1 GB controller DRAM) replaying MSR Cambridge and FIU block traces, and a real 1 TB open-channel SSD running FileBench and MySQL/BenchBase database workloads (10–30 GB databases, 37–230 GB of read traffic) on ext4. Baselines are the strongest page-level schemes: DFTL and SFTL. Sensitivity covers γ from 0 to 16, DRAM 256 MB–1 GB, and page sizes 4–16 KB; overhead and lifetime studies close the loop.

Page-level FTL address mapping: three generations

Property	DFTL (demand-cached page mapping)	SFTL (heuristic compression)
Mapping representation
Mapping table size	Baseline (full table 8 B/page)	Smaller on sequential workloads
Correctness under approximation	Always exact	Always exact
Adaptation & churn handling	LRU caching adapts to hot sets, not to structure	Static heuristic
Performance	Baseline; misses add critical-path flash reads	Slightly above DFTL

Simulator: WiscSim, 2 TB SSD, 4 KB pages, 1 GB DRAM, MSR Cambridge + FIU traces. Real prototype: 1 TB open-channel SSD (16 channels, 16 KB pages), host-side FTL in 4,016 lines of C, FileBench (OLTP, CompFlow) and BenchBase-on-MySQL (TPCC, AuctionMark, SEATS) on ext4, 256 MB mapping DRAM. Block/hybrid mappings excluded as uncompetitive with page-level schemes. γ=0 default; sensitivity to γ∈[0,16], DRAM size, and page size reported.Underlined values explain themselves when clicked.

Background

Learned structures find their natural habitat

LeaFTL is this site’s first storage-layer paper and its purest instance of the learned-systems thread: TLP replaced hand-engineered cost-model features with a learned representation, Lucid replaced black-box scheduling models with interpretable learned ones, and here Kraska-style learned indexes replace the hand-heuristic compressions of FTL design. The transplant lesson is about failure handling: learned indexes stalled in many systems because mispredictions need a verification-and-correction story, and LeaFTL’s is supplied by the hardware itself — flash’s OOB bytes make every page a self-identifying index leaf, so the error bound becomes a one-extra-read guarantee. The general pattern worth carrying: approximate structures deploy best where the substrate offers cheap ground truth — and the memory-economics argument (map bytes compete with cache bytes inside a fixed DRAM budget) rhymes with the site’s datacenter papers, from Memory-Harvesting VMs’ stranded-DRAM economics to IKS’s dual-use expander.

If you remember only three things

1. The SSD mapping table is a hidden memory crisis: page-level mapping costs 8 bytes per page in controller DRAM that cannot scale with flash capacity, competes directly against the data cache, and prior compressions were single-pattern human heuristics (SFTL's strict sequentiality) blind to the strided and near-linear structure real workloads exhibit.
2. LeaFTL learns the map as piecewise linear segments — 8 bytes covering ~20 mappings, fitted for free on write-buffer flushes with allocation ordered for learnability — and makes approximation firmware-safe through flash's own OOB metadata: storing 2γ+1 neighbors' reverse mappings turns the regression error bound into a guarantee of at most one extra flash access per misprediction, while a log-structured segment table with conflict-resolution buffers and compaction absorbs the churn of out-of-place writes, GC, and wear leveling.
3. The compression compounds into performance — 2.9× smaller tables than SFTL (up to 37.7× vs DFTL) free DRAM for data caching, yielding 1.4–1.6× average storage speedups in simulation and 1.4× on a real 1 TB open-channel SSD with database workloads, tails unharmed — establishing that learned indexes belong precisely where verification is hardware-cheap, with graceful degradation to page-mapping parity as the randomness floor.

Check yourself

Check your understanding

1. Learned indexes had a deployment blocker everywhere: mispredictions need detection and correction, and both usually cost more than the index saves. Predict why an SSD is the one place this problem nearly solves itself.
2. Each LeaFTL segment stores just (S, L, K, I) in 8 bytes yet replaces ~20 page-mapping entries (160 bytes) on average. What creates all that linear structure in a mapping between logical and physical addresses?
3. Why does LeaFTL need a log-structured, multi-level segment table with a Conflict Resolution Buffer, when classic learned-index papers just fit their model once?
4. The γ knob trades table size against misprediction rate. Why does the paper nonetheless DEFAULT to γ=0, and what does that reveal about the design's priorities?

Sources

arXiv preprint 2301.00072 — full text used for this explainer
ACM DL: LeaFTL: A Learning-Based Flash Translation Layer for Solid-State Drives — ASPLOS 2023
LeaFTL on GitHub