A Log-Structured FTL

Logging

Most FTLs today are log structured, an idea useful in both storage devices (as we’ll see now) and file systems above them (as we saw in the chapter on log-structured file systems). Upon a write to logical block $N$, the device appends the write to the next free spot in the currently-being-written-to block; we call this style of writing logging. To allow for subsequent reads of a block $N$, the device keeps a mapping table (in its memory, and persistent, in some form, on the device). This table stores the physical address of each logical block in the system.

Example

Let’s go through an example to make sure we understand how the basic log-based approach works. To the client, the device looks like a typical disk, in which it can read and write 512-byte sectors (or groups of sectors). For simplicity, assume that the client is reading or writing 4-KB sized chunks. Let us further assume that the SSD contains some large number of 16-KB sized blocks, each divided into four 4-KB pages. These parameters are unrealistic (flash blocks usually consist of more pages) but will serve our didactic purposes quite well.

Assume the client issues the following sequence of operations:

• Write(100) with contents a1
• Write(101) with contents a2
• Write(2000) with contents b1
• Write(2001) with contents b2

These logical block addresses (e.g., 100) are used by the client of the SSD (e.g., a file system) to remember where information is located.

Internally, the device must transform these block writes into the erase and program operations supported by the raw hardware, and somehow record, for each logical block address, which physical page of the SSD stores its data. Assume that all blocks of the SSD are currently not valid, and must be erased before any page can be programmed. Here we show the initial state of our SSD, with all pages marked INVALID(i):