Mapping Granularity in a Flash Translation Layer

The controller on a solid-state drive is a computer with firmware, a small processor, a few hundred megabytes to a few gigabytes of DRAM, and a large array of NAND dies. Its central data structure is a table translating the logical block addresses the host writes into the physical pages where those contents currently live. The granularity at which that table is maintained determines how much DRAM the drive needs, how much copying garbage collection performs, and how long a power-loss recovery takes. The table exists because of the mismatch between page-sized writes and block-sized erases described in erase blocks and program granularity. There is no single correct granularity, only three well-understood points on the curve.

What the table must answer

The host issues a read or write for a range of logical blocks. The controller must find the physical page or pages holding the current contents. On a write, it must additionally choose a free page, program it, and update the table so that later reads find the new page and the old one becomes invalid.

Every mapping scheme is an answer to one question: does the table have an entry per logical block, or per group of logical blocks. A page-level table has an entry for each logical 4 KiB page. A block-level table has an entry for each logical block of, say, 512 pages, and the physical page for logical page i within the group is derived by offset arithmetic from the group’s base.

Block-level mapping and its write cost

Block-level mapping is the cheapest table. For a drive with 1 MiB erase blocks and 4 KiB logical pages, one entry covers 256 logical pages, so the table has one entry per 1 MiB of logical capacity. A 32-bit entry per megabyte is 4 KiB of table per gigabyte of capacity, which is negligible: a terabyte-class drive needs a few megabytes.

The cost appears on the write path. If logical page 17 of group g is overwritten, the new contents must be programmed at offset 17 of a physical block, and the physical block currently mapped to g already has offset 17 programmed. The controller must read the other 255 pages of that block, write them to a fresh block together with the new page 17, and update the single mapping entry. One 4 KiB host write produces up to 1 MiB of program traffic. This is a write amplification of 256, and on any workload that rewrites data in place it consumes endurance at that rate.

The mitigation is a log block: a block-level mapping for stable data, plus a small pool of log blocks that absorb overwrites. A write to logical page 17 of group g goes into a log block associated with g, at the next free page. The log block is written sequentially and records which logical offset each of its pages holds, so a read must consult both the log block’s page map and the main block’s fixed offset. When the log block fills or the number of log blocks exceeds its pool, the log is merged into a new main block: valid pages from both are copied, invalid ones dropped. This hybrid design trades a bounded amount of copying per merge for a table that stays small, and it is the scheme the original FTL specification described.

Merge policy drives the behaviour. Switching merges when the log block’s pages cover a different offset range than the main block, partial merges when they overlap partially, and full merges otherwise. A merge triggered too eagerly copies pages that would have been overwritten anyway; too lazily and the log pool exhausts, forcing a full merge of a block whose main data is mostly stale. The decision is the same one that garbage collection makes at the page level, just with coarser units.

Page-level mapping and the DRAM bill

Page-level mapping removes the merge entirely. Each logical page has its own entry, a write programs a free page anywhere and updates one entry, and no data is ever copied on the write path. Garbage collection still copies valid pages out of a block being reclaimed, but only at the rate invalid pages accumulate, and the victim choice is free to pick the block with the fewest valid pages.

The price is the table’s size. A 4-byte entry per 4 KiB logical page is one entry per page, so a terabyte of logical capacity has 2^28 pages and needs 1 GiB of table. At 8 bytes per entry, for a physical page number plus flags, it is 2 GiB. That is DRAM the drive must carry and refresh, and DRAM is a significant fraction of a drive’s bill of materials. The arithmetic is unavoidable: page-level mapping costs roughly 0.1 to 0.2 percent of logical capacity in DRAM, block-level mapping costs a small fraction of that.

Most controllers resolve this with a two-level table and a cache. The table lives in flash, organized so that a group of entries covering a contiguous logical region occupies one flash page; a small DRAM cache holds the entries for logical regions currently being accessed, and a miss reads the group from flash into the cache, evicting another. The DFTL paper describes exactly this structure and its consequence: a mapping miss on the read path adds a flash read before the data read, so a random read workload over a working set larger than the cache pays two reads per host read. Sequential access, whose entries share a group, pays one.

/* Two-level page map: a cached group of entries covers LPN_GROUP logical pages.
 * load_group() reads a group from flash on a cache miss; it is elided. */
#define LPN_GROUP 512

struct map_group {
    uint64_t lpn_base;                  /* first logical page covered */
    uint32_t ppn[LPN_GROUP];            /* physical page numbers, 0 = unmapped */
    uint64_t flash_addr;                /* where this group is stored in flash */
    bool dirty;
};

static uint32_t translate(struct map_group *g, uint64_t lpn)
{
    if (lpn < g->lpn_base || lpn >= g->lpn_base + LPN_GROUP)
        g = load_group(lpn / LPN_GROUP); /* flash read on cache miss */
    return g->ppn[lpn - g->lpn_base];
}

The cache-miss path is the reason page-level mapping is not universally adopted. A drive optimized for sequential throughput and mixed read/write can afford the copying of a hybrid scheme and avoid the second read; a drive optimized for random reads over a large working set wants the page map and must then pay for the DRAM or accept the miss.

Rebuilding the table after power loss

The mapping table is too large to write to flash on every update, and the drive’s DRAM loses its contents when power fails. The table must therefore be reconstructible from data already on media. The mechanism is the per-page metadata in the spare area: each programmed page records the logical address it was written for and a monotonically increasing sequence number assigned when it was programmed.

Recovery scans the blocks and, for each valid page, compares its sequence number against the entry currently in the reconstructed table. A page with a higher sequence number for the same logical address wins, and the loser is marked invalid. Because the sequence number orders writes across the whole device, the scan does not need to know the order in which blocks were written; it needs only that the counter did not wrap within the set of pages being compared. A 32-bit counter at one increment per page program wraps after 2^32 programs, which a busy drive can reach, so implementations use a wider counter or checkpoint it.

Scanning every page of a large drive at startup would take minutes. Controllers avoid it with periodic checkpoints: a snapshot of the table written to a dedicated flash region, plus a bounded region of the log written since. Recovery loads the checkpoint and replays the tail, so the scan is proportional to the uncheckpointed window rather than the drive’s capacity. The checkpoint itself must be atomic, which means it is written to a fresh block and its validity is established by a checksum and a sequence number, so that a power failure during the checkpoint leaves the previous one intact. That is the same problem the write cache ordering rules solve one interface down, applied to a structure that is far larger than a single command.

Which granularity a drive actually uses

Production controllers rarely implement a textbook pure scheme. The common shape is page-level mapping for data, block-level or hybrid mapping for the metadata region, and a log-structured write policy for the table itself. Some drives map large-aligned sequential writes at block granularity and random writes at page granularity, on the theory that a sequential stream will be rewritten as a unit anyway.

The observable consequence for the host is that write amplification depends on the access pattern, not only on the volume of data written. A stream of sequential writes that fills whole erase blocks leaves almost no invalid pages behind and costs near 1.0 amplification. The same volume of writes scattered over a small set of logical addresses leaves nearly every page it touches invalid and forces collection at a rate proportional to the scatter. This is why a device’s endurance rating is quoted against a workload definition, such as the JEDEC JESD219 enterprise and client workloads, rather than as an absolute number of bytes.

Two limits bound what any of these schemes can do. The controller cannot see which logical blocks the filesystem has freed, so pages belonging to deleted files stay valid in the mapping table and are copied by garbage collection until the host says otherwise; that is the subject of discard and TRIM. And the controller cannot rearrange writes across a cache flush boundary, so the host’s ordering discipline constrains how freely the drive can batch programs; that is the subject of flush and FUA. The mapping layer is capable but it operates inside a contract it did not write.