Exercises — Wear leveling and flash controllers

WHAT: We name the piece of firmware that decouples what the OS asks for from where the bits live. Answer: The Flash Translation Layer (FTL), running inside the flash controller. It keeps a map from logical block addresses (LBAs) → physical page addresses (PPAs). WHY it matters: Because that map can be rewritten on every single write, the physical home of "logical 100" is free to move to a fresh, less-worn page each time. That freedom is the entire foundation of wear leveling. See SSD Architecture for where the FTL sits.

Answer: False. WHY: Flash can program bits $1\to 0$ individually, but the only way to reset a bit $0\to 1$ is to erase the whole block it lives in (all bits go back to 1 together). You cannot flip a single bit up. This is the erase-before-write rule, and the reason writes go out-of-place to fresh pages instead of overwriting.

(a) → Dynamic wear leveling. (b) → Static wear leveling. WHY the distinction exists: Dynamic alone ignores cold data, so blocks holding a never-changing movie stay pristine while the working blocks wear out fast. Static pays extra writes now to move that cold movie onto a tired block, letting the fresh block join the rotation. More in Garbage Collection.

Step 1 — Identify $u$. "40% valid" means $u=0.40$. Why: $u$ is defined as exactly the valid fraction, so we read it straight off. Step 2 — Apply the formula. $\text{WAF}=\frac{1}{1-u}=\frac{1}{1-0.40}=\frac{1}{0.60}=1.67$ WHAT IT MEANS: Every 1 GB the host writes causes about 1.67 GB to actually be written to flash — the extra 0.67 GB is GC (garbage collection) copying valid pages out of the way before erasing.

Step 1 — Rearrange the formula. Start from $\text{WAF}=\frac{1}{1-u}$. Why rearrange: we are given the output and want the input, so we invert. $1-u=\frac{1}{\text{WAF}}⟹u=1-\frac{1}{\text{WAF}}$ Step 2 — Substitute. $u=1-\frac{1}{2.5}=1-0.40=0.60$ WHAT IT MEANS: On average, victim blocks were 60% full of live data that had to be copied. To lower WAF you'd want GC to wait until blocks are emptier — that is what Over-provisioning and TRIM enables.

Step 1 — What WAF means directionally. WAF = physical ÷ host, so physical = host × WAF. Why multiply: WAF is defined as the ratio of physical-to-host, so to go from host to physical we multiply. Step 2 — Compute. $\text{physical}=20\text{GB}\times 1.67=33.3\text{GB}$ WHAT IT MEANS: The 13.3 GB of extra writing is pure GC overhead — invisible to the host, but it burns real endurance.

Step 1 — WAF of each. Why: lifetime depends on how much physical writing each design forces. ${\text{WAF}}_A=\frac{1}{1-0.80}=5.0,{\text{WAF}}_B=\frac{1}{1-0.50}=2.0$ Step 2 — Total endurance (bytes writable). Why: each of 512 GB of cells can be programmed 1000 times. $512\text{GB}\times 1000=512,000\text{GB of physical writes.}$ Step 3 — Daily physical writes. Why: WAF converts host demand into real flash traffic. $A:30\times 5.0=150\text{GB/day},B:30\times 2.0=60\text{GB/day}.$ Step 4 — Lifetime = endurance ÷ daily. $A:\frac{512,000}{150}\approx 3413\text{days}\approx 9.35\text{yr}$ $B:\frac{512,000}{60}\approx 8533\text{days}\approx 23.38\text{yr}$ Step 5 — Ratio. $\frac{{\text{WAF}}_A}{{\text{WAF}}_B}=\frac{5.0}{2.0}=2.5$, and indeed $\frac{23.38}{9.35}=2.5$. WHAT IT MEANS: Halving the valid fraction $u$ from 0.80 to 0.50 makes the drive last 2.5× longer. Because lifetime $\propto 1/\text{WAF}$, driving $u$ down is the single biggest lever — that's why controllers hoard free space.

WHAT the figure shows: WAF plotted against $u$. The magenta curve is flat and gentle for small $u$, then rockets upward as $u\to 1$ (the violet vertical asymptote). WHY it curves, not a straight line: $u$ sits in the denominator. As $u$ approaches 1, the denominator $1-u$ approaches zero, and dividing by a near-zero number blows up. Doubling how full a block is doesn't double the pain — near the top it can multiply it tenfold. Concrete reading: at $u=0.5$, $\text{WAF}=2$; at $u=0.9$, $\text{WAF}=10$; at $u=0.99$, $\text{WAF}=100$. The last sliver of "fullness" costs the most. WHAT IT MEANS: A nearly-full SSD (high $u$ because there are almost no stale-only blocks to reclaim) writes catastrophically more and dies fast. This is the mathematical face of "keep your SSD under ~80% full."

Step 1 — Turn spare fraction into $u$. Why: our WAF formula speaks in $u$, so we translate the design parameter $s$ into it using the linear model $u=1-s$. $s=0.07\Rightarrow u=0.93,s=0.28\Rightarrow u=\mathrm{0.72.}$ Step 2 — WAF of each. Why: WAF is what determines endurance, and it depends only on $u$. ${\text{WAF}}_{\text{consumer}}=\frac{1}{1-0.93}=\frac{1}{0.07}\approx 14.29$ ${\text{WAF}}_{\text{enterprise}}=\frac{1}{1-0.72}=\frac{1}{0.28}\approx 3.57$ Step 3 — Lifetime multiplier. Why: lifetime $\propto 1/\text{WAF}$, so the ratio of WAFs (larger over smaller) is exactly how many times longer the low-WAF design lives. $\frac{{\text{WAF}}_{\text{consumer}}}{{\text{WAF}}_{\text{enterprise}}}=\frac{14.29}{3.57}=4.0\times \text{ longer.}$ WHAT IT MEANS: Giving up ~21 percentage points more of raw capacity to spare pool buys a 4× longer life. This is exactly why enterprise SSDs advertise less usable space but far higher endurance — the "missing" capacity is working invisibly as headroom. Compare SLC MLC TLC QLC, where fewer bits-per-cell is the other endurance lever.

Step 1 — Build the effective WAF from its definition (don't accept it by fiat). Why derive it: we want to see why compression and GC multiply, not just be told. Follow one host request of size $H$ through the two stages:

• Stage 1 — compression. Before anything reaches the flash, the controller squashes $H$ down to $cH$. Only $cH$ of real data ever needs to be stored.
• Stage 2 — GC amplification. Every unit actually stored still triggers the usual copy-along overhead, so storing $cH$ of data costs ${\text{WAF}}_{\text{GC}}\times (cH)$ physical bytes.

By definition ${\text{WAF}}_{\text{eff}}$ = physical bytes ÷ host bytes requested: ${\text{WAF}}_{\text{eff}}=\frac{{\text{WAF}}_{\text{GC}}(cH)}{H}=c\times {\text{WAF}}_{\text{GC}}.$ The $H$ cancels, and the two factors multiply because they act in series — compression shrinks the input, GC amplifies whatever survives. Step 2 — Substitute. ${\text{WAF}}_{\text{eff}}=c\times {\text{WAF}}_{\text{GC}}=0.5\times 2.0=1.0$ WHAT IT MEANS: Compression exactly cancelled the GC amplification here. If $c$ were 0.4, we'd get ${\text{WAF}}_{\text{eff}}=0.8<1$ — the drive physically writes less than the host requested, which the pure GC formula (always $\ge 1$) can never explain on its own. GC amplification and compression are separate, opposing mechanisms.

Step 1 — Total endurance budget. Why: everything hangs on how many physical bytes the chip can absorb over its life. $1000\text{GB}\times 400=400,000\text{GB of physical writes.}$ Step 2 — Physical write budget per day for a 5-year life. Why: spread the total over the required lifetime in days. $5\text{yr}\times 365=1825\text{days},\frac{400,000}{1825}\approx 219.2\text{GB/day physical allowed.}$ Step 3 — Maximum tolerable WAF. Why: WAF = physical ÷ host, so the ceiling on physical writes sets the ceiling on WAF. ${\text{WAF}}_{\max }=\frac{219.2\text{GB/day}}{40\text{GB/day}}\approx 5.48$ Step 4 — Required $u$. Why: we are given the WAF ceiling and want the validity that produces it, so we invert the formula (as in L2.2) with $u=1-\frac{1}{\text{WAF}}$. $u=1-\frac{1}{5.48}=1-0.1825\approx 0.8175$ Step 5 — Over-provisioning. Why: the linear model $u=1-s$ ties validity to spare, so solving for $s$ tells us how much capacity to reserve. $s=1-u\approx 0.1825,\text{i.e. reserve }\text{ 18\% spare.}$ Step 6 — Is static wear leveling mandatory? Yes. Why: QLC's tiny 400-cycle budget leaves no margin to let cold-data blocks sit fresh while the working set wears out. Under dynamic-only leveling, a large cold region (say a media library) would keep hogging its own low-wear blocks and never join the write rotation; the handful of active blocks would then absorb all the writes and blow past 400 cycles long before 5 years. Static wear leveling fixes this by periodically relocating that cold data onto the more-worn blocks, which frees the fresh blocks to share the write load so every block ages together. The extra relocation writes it costs are small and already sit comfortably inside the ~5.48 WAF headroom we budgeted. Without static leveling the drive would die in a fraction of the target life even though most cells were barely touched. See Garbage Collection and Over-provisioning and TRIM. WHAT IT MEANS: The whole design closes: keep WAF $\lesssim 5.48$ by holding victim-block validity near $u\approx 0.82$, achieved with ~18% over-provisioning, and run static leveling so wear stays even. Miss any one and the 5-year target fails.

Baseline: at $u=0.82$, $\text{WAF}=1/(1-0.82)=1/0.18\approx 5.556$. Option (a) — lower $u$ to 0.75: ${\text{WAF}}_a=\frac{1}{1-0.75}=\frac{1}{0.25}=4.0$ Option (b) — compression on baseline: ${\text{WAF}}_b=c\times \frac{1}{1-0.82}=0.85\times 5.556\approx 4.72$ Compare: lower is better. ${\text{WAF}}_a=4.0<{\text{WAF}}_b=4.72$, so option (a), more over-provisioning, wins — it stretches life by $5.556/4.0=1.39\times$ versus $5.556/4.72=1.18\times$ for compression. WHAT IT MEANS: Because $u$ lives in the denominator, attacking it directly beats a mere 15% compression here. But note the caveat: compression's benefit depends entirely on how squishy the data is — incompressible data (video, encrypted) gives $c\approx 1$ and no help, whereas over-provisioning always works. That robustness is why it's the primary knob.

WAF formula ::: $\text{WAF}=\frac{1}{1-u}$, with $u$ = valid fraction of GC victim blocks. Invert to find u from a measured WAF ::: $u=1-\frac{1}{\text{WAF}}$. Lifetime formula ::: $\frac{\text{raw capacity}\times \text{P/E cycles}}{\text{host GB/day}\times \text{WAF}}$ = days of life. Why WAF explodes near a full drive ::: $u\to 1$ makes the denominator $1-u\to 0$, so WAF $\to \infty$. Why static wear leveling is mandatory on low-endurance flash ::: it recirculates cold data so every block ages evenly; without it active blocks die while cold ones stay fresh.