Wear leveling and flash controllers

WHY does flash need special handling at all?

Three physical facts drive everything in this topic:

Erase-before-write. You cannot overwrite a flash bit from 0→1 in place. You must first erase a whole block (set all bits to 1), then program bits to 0.
Asymmetric granularity. You read/write in pages (e.g. 4 KB) but erase in blocks (e.g. 256 KB = 64 pages). Erase is coarse; write is fine.
Wear is finite and local. Each erase damages the cells slightly. Cells that are erased more often die sooner.

The key trick: an indirection layer (the FTL)

WHAT it buys us: Since the OS's address 100 is decoupled from any physical location, the controller is free to write each new version of "logical 100" to a fresh, less-worn physical page.

HOW a write works (out-of-place writing):

OS says "write logical page 100."
Controller picks a free, low-wear physical page and writes there.
Controller updates the map: LBA 100 → new PPA.
The old physical page is marked stale (invalid), to be reclaimed later.

Two flavours of wear leveling

Garbage collection & write amplification

Because GC copies valid data, one logical write can trigger several physical writes.

Deriving a WAF estimate from first principles

WHY: We want to predict how much extra writing GC forces, because it eats endurance.

Consider GC on a victim block of $N$ pages. Suppose a fraction $u$ of its pages are still valid (the rest are stale). To reclaim this block we must:

copy $uN$ valid pages to a fresh block, then
erase the block, giving us $N$ free pages, of which $uN$ are already consumed by the copies.

So each GC cycle nets us $N(1-u)$ genuinely free pages while performing $uN$ internal copy-writes.

Host writes that consume $N(1-u)$ free pages = $N(1-u)$ . Total physical writes = host writes + copies = $N(1-u) + uN = N$ ... but the extra work is the copies:

\text{WAF} = \frac{\text{host writes} + \text{copies}}{\text{host writes}} = \frac{N(1-u) + uN}{N(1-u)} = \frac{1}{1-u}

Why this step? (the algebra) We added the mandatory copies ( $uN$ ) to the useful host writes ( $N(1-u)$ ), then divided by the useful part. The valid data "rides along for free" but still burns endurance — hence amplification.

Figure — Wear leveling and flash controllers

Worked examples

Worked example Example 2 — Lifetime estimate

Drive: 256 GB, TLC rated 1000 P/E cycles, WAF = 3.33, host writes 50 GB/day. Estimate lifetime.

Step 1 — Total flash endurance (bytes writable): $256\ \text{GB} \times 1000 = 256{,}000\ \text{GB}$ of physical writes possible. Why? Each of 256 GB worth of cells can be programmed 1000 times.

Step 2 — Convert host writes to physical writes: $50\ \text{GB/day} \times 3.33 = 166.5\ \text{GB/day physically}$ . Why? WAF converts what the host asked for into what actually hits the flash.

Step 3 — Divide: $\dfrac{256{,}000}{166.5} \approx 1538\ \text{days} \approx 4.2\ \text{years}$ . Why? Total endurance ÷ daily consumption = number of days.

Common mistakes (steel-manned)

Recall

Recall Active recall — cover the answers

What physical fact forces "erase-before-write"? ⇒ Flash bits can go 1→0 by programming, but 0→1 only by erasing a whole block.
What is the FTL and why does it exist? ⇒ A map from logical to physical addresses; it decouples them so writes can move freely for wear leveling and out-of-place writes.
Formula for WAF from GC and each symbol? ⇒ $1/(1-u)$ ; $u$ = valid-page fraction in GC victims.
Difference between dynamic and static wear leveling? ⇒ Dynamic spreads only active writes; static also relocates cold data.
Why does over-provisioning reduce WAF? ⇒ More free space ⇒ GC picks emptier blocks ⇒ smaller $u$ ⇒ lower amplification.

Recall Feynman: explain to a 12-year-old

Imagine a notebook where you can only write in pencil, and each page can only be erased about 1000 times before it tears. If you always erased and rewrote page 1, it would rip apart while the rest of the book is brand new. A smart helper (the controller) instead writes each new note on a fresh page and keeps a tiny index at the front saying "your grocery list is really on page 57 now." When pages fill up with crossed-out junk, the helper copies the good notes to a clean page and erases the messy one. It even moves your old drawings you never change onto worn pages so the fresh ones can be reused. That way the whole notebook wears out slowly and evenly, instead of one page dying first.

Connections

NAND vs NOR Flash — the physical cells being worn out
SLC MLC TLC QLC — cell density sets the P/E cycle budget
Log-Structured File Systems — same out-of-place idea one layer up
Garbage Collection — the reclamation engine behind WAF
Over-provisioning and TRIM — how the host helps lower $u$
Bad Block Management and ECC — the controller's other survival jobs
SSD Architecture — where the FTL and controller physically live

Why can't flash overwrite a page in place?

Bits can be programmed 1→0, but going 0→1 requires erasing an entire block first (erase-before-write).

What is the granularity mismatch in flash?

You read/write in pages (~4 KB) but must erase in whole blocks (~64+ pages).

What does the Flash Translation Layer (FTL) do?

Maps logical block addresses to physical page addresses, decoupling them so data can be relocated freely.

What is out-of-place writing?

Each write goes to a new free page and the map is updated; the old page is marked stale.

Define the write amplification factor.

WAF = (data physically written to flash) / (data requested by host).

Derive WAF for garbage collection with valid fraction u.

Copies = uN, useful host writes = N(1−u); WAF = (N(1−u)+uN)/(N(1−u)) = 1/(1−u).

What happens to WAF as GC victim blocks approach fully valid (u→1)?

WAF → ∞ (GC copies huge amounts of valid data).

Dynamic vs static wear leveling?

Dynamic spreads writes across active/free blocks only; static also relocates cold data off low-wear blocks.

Why does over-provisioning extend SSD life?

More free space lets GC pick emptier victim blocks (lower u), reducing WAF and endurance consumption.

What is a P/E cycle and why does it matter?

A program/erase of a block; each erase degrades cells, and blocks have a finite P/E budget (~10^3–10^5).

Why is dynamic-only leveling insufficient?

Cold data stays parked on fresh blocks, starving them from rotation so active blocks wear faster.

Lifetime formula intuition given endurance E, WAF, host rate H?

Lifetime ≈ E / (H × WAF); higher WAF shortens life proportionally.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, flash memory ka ek badा problem hai: har block sirf ek fixed number of times erase ho sakta hai (P/E cycles, roughly 1000–100000). Agar hum baar-baar same physical location pe likhein — jaise ek log file ya FAT table — to wahi block jaldi mar jayega aur baaki chip brand-new padi rahegi. Isiliye wear leveling ka concept aata hai: writes ko poore chip pe evenly spread karo taaki sab blocks ek saath, dheere-dheere ghisein.

Yeh kaam karta hai flash controller ke andar ka FTL (Flash Translation Layer). OS sochta hai wo ek simple disk se baat kar raha hai (logical addresses), par FTL secretly ek map rakhta hai jo logical address ko kisi bhi physical page pe point karwa sakta hai. Jab bhi naya write aata hai, controller kisi fresh, kam-ghise page pe likhta hai aur map update kar deta hai — purani copy "stale" ban jaati hai. Isko out-of-place writing kehte hain. Yahi wajah hai ki flash internally ek log jaisा behave karta hai.

Ab stale pages jama hote rehte hain, to unhe clean karna padta hai — yeh hai garbage collection: ek block uthao, uske valid pages copy karo doosri jagah, phir block erase karo. Par copying se extra writes hote hain! Isko measure karte hain Write Amplification Factor, WAF = 1/(1−u), jahan u = victim block mein valid pages ka fraction. Agar block zyada valid data rakhta hai (u bada), to WAF badhta hai aur drive ki life ghisti hai. Isiliye over-provisioning (extra free space) rakhte hain — controller emptier blocks choose kar pata hai, u kam rehta hai, WAF gir jaata hai.

Ek aur baat: sirf dynamic wear leveling (jo sirf active writes ko spread karta hai) kaafi nahi. Kyunki agar aapke paas ek movie hai jo aap kabhi touch nahi karte, wo fresh block pe permanently baith jaayegi. Static wear leveling us cold data ko bhi occasionally move karta hai taaki wo fresh block bhi rotation mein aa sake. Yaad rakho — thoda extra kaam abhi, taaki drive saal-saal chale.

WHY does flash need special handling at all?

The key trick: an indirection layer (the FTL)

Two flavours of wear leveling

Garbage collection & write amplification

Deriving a WAF estimate from first principles

Worked examples

Common mistakes (steel-manned)

Recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Memory Technologies

Connections