Part 4 of 7 · 6 min read
Garbage collection
Think of a car park where cars leave at random. Soon every floor has a few cars scattered among empty spaces, and no floor is empty. To reuse a floor, a worker must move its remaining cars to another floor first. The analogy stops in one place: moving a car costs fuel, and moving a flash page costs one program and wear.
In plain words: Stale pages cannot be reused until their block is erased, and a block with valid pages must have those pages copied elsewhere first. This is garbage collection. The copies are extra writes that the host did not ask for. The ratio of the data written to flash to the data the host wrote is the write amplification (WA). A block that is 75% valid, with 48 of 64 pages valid, frees only 16 pages for the price of 48 copies. The host gets 16 pages of room, and the drive wrote 64 pages in total, so the write amplification is 64 / 16 = 4.
A worked example (made up to show the idea). If a victim block has a share u of valid pages, then each erase frees 64(1 - u) pages and costs 64u copies. The write amplification is 64 / (64(1 - u)) = 1 / (1 - u). With u = 0.5 the value is 2. With u = 0.75 it is 4. With u = 0.9 it is 10. The time to collect the 75% case is 48 copies at (50 + 500) microseconds, which is 26.4 ms, plus the 3 ms erase, so 29.4 ms. During this time the drive may be slow to answer.
The key lines. The simulator below has 64 blocks of 64 pages. It fills the logical space once and then overwrites random pages 200,000 times. When fewer than two erased blocks remain, it collects the block with the fewest valid pages. The command line gives the spare share: the percentage of flash that the host cannot address.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define PPB 64 /* pages per block */
#define NB 64 /* blocks */
static int map[PPB * NB]; /* logical page -> physical page, -1 if none */
static int owner[PPB * NB]; /* physical page -> logical page, -1 if stale or free */
static int valid[NB]; /* valid pages in each block */
static int is_free[NB]; /* 1 if the block is erased */
static int open_b = 0, open_off = 0, nfree = NB - 1;
static long flash_writes = 0, erases = 0;
static void put(int lp) { /* write one logical page to the open block */
if (open_off == PPB) { /* open block full: take an erased one */
for (int b = 0; b < NB; b++) if (is_free[b]) { open_b = b; break; }
is_free[open_b] = 0; nfree--; open_off = 0;
}
int pp = open_b * PPB + open_off++;
if (map[lp] >= 0) { owner[map[lp]] = -1; valid[map[lp] / PPB]--; }
map[lp] = pp; owner[pp] = lp; valid[open_b]++; flash_writes++;
}
static void collect(void) { /* garbage collection: free the block with fewest valid pages */
int v = -1;
for (int b = 0; b < NB; b++)
if (!is_free[b] && b != open_b && (v < 0 || valid[b] < valid[v])) v = b;
for (int p = 0; p < PPB; p++) {
int lp = owner[v * PPB + p];
if (lp >= 0) put(lp); /* copy a valid page: this is extra flash writing */
}
is_free[v] = 1; valid[v] = 0; nfree++; erases++;
}
int main(int argc, char **argv) {
int spare = argc > 1 ? atoi(argv[1]) : 25; /* percent of flash kept spare */
int nlog = PPB * NB * (100 - spare) / 100;
memset(map, -1, sizeof map); memset(owner, -1, sizeof owner);
for (int b = 1; b < NB; b++) is_free[b] = 1;
for (int i = 0; i < nlog; i++) put(i); /* fill the logical space once */
flash_writes = 0; erases = 0; srand(1);
for (long i = 0; i < 200000; i++) {
while (nfree < 2) collect();
put(rand() % nlog); /* the host overwrites a random page */
}
printf("spare %2d%%: host 200000, flash %ld, erases %ld, write amplification %.2f\n",
spare, flash_writes, erases, flash_writes / 200000.0);
return 0;
}
Output on the test machine:
spare 10%: host 200000, flash 1324506, erases 20691, write amplification 6.62
spare 20%: host 200000, flash 594093, erases 9272, write amplification 2.97
spare 25%: host 200000, flash 471793, erases 7358, write amplification 2.36
spare 40%: host 200000, flash 303622, erases 4721, write amplification 1.52
spare 50%: host 200000, flash 254388, erases 3945, write amplification 1.27
At 25% spare the 7,358 erases freed 471,793 - 200,000 = 271,793 copied pages in all, so the average victim held 271,793 / 7,358 = 36.9 valid pages. That is u = 0.577 and 1 / (1 - u) = 2.36, which matches. More spare space means emptier victims and lower write amplification.
Write amplification
Write amplification is the ratio of the amount of data a flash drive writes to its chips to the amount of data the host asked it to write. It is at least 1. It rises when garbage collection must copy many valid pages before it can erase a block.
Example: 200,000 host writes that cause 471,793 page programs give a write amplification of 2.36.
Check yourself: 1. A victim block has 32 valid pages out of 64. What is the write amplification of collecting it? 2. Why does more spare space lower write amplification? 3. Why might a user see a pause during garbage collection?