Skip to main content

I 7 A Log Structured FTL

This page is a generated reference surface for selective reading. It exists to keep the learner apps guide-first while still preserving source access.

Learning objectives​

  • Explain the main ideas and vocabulary in I 7 A Log Structured FTL.
  • Work through the source examples for I 7 A Log Structured FTL without depending on raw chunk order.
  • Use I 7 A Log Structured FTL as selective reference when learner modules point back to Ostep.

Prerequisites​

  • None curated yet.

Module targets​

  • module-04-file-systems-io

AI companion modes​

  • Explain simply
  • Socratic tutor
  • Quiz me
  • Challenge my understanding
  • Diagnose my confusion
  • Generate extra practice
  • Revision mode
  • Connect forward / backward

Source-of-truth note​

This unit is anchored to Ostep and the source chapter "I 7 A Log Structured FTL". Use external resources only to clarify, extend, or modernize details without replacing the chapter's conceptual spine.

External enrichment​

No chapter-specific enrichment resources are curated yet. Add them in the unit manifest when a source clearly improves learning.

Source provenance​

  • Primary source: Ostep
  • Source chapter: I 7 A Log Structured FTL
  • Raw source file: 270-i-7-a-log-structured-ftl.md

Merged source​

I 7 A Log Structured FTL​

I.7 A Log-Structured FTL

For these reasons, most FTLs today arelog structured, an idea useful in both storage devices (as we'll see now) and file systems above them (as we'll see in the chapter onlog-structured file systems). Upon a write to logical blockN, the device appends the write to the next free spot in the currently-being-written-to block; we call this style of writinglogging. To allow for subsequent reads of blockN, the device keeps amapping 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.

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 contentsa1
  • Write(101) with contentsa2
  • Write(2000) with contentsb1
  • Write(2001) with contentsb2 Theselogical 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, whichphysical pageof 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 markedINVALID(i):

Block: 0 1 2

Page: 00 01 02 03 04 05 06 07 08 09 10 11

Content:

State: i i i i i i i i i i i i

When the first write is received by the SSD (to logical block 100), the

FTL decides to write it to physical block 0, which contains four physical pages: 0, 1, 2, and 3. Because the block is not erased, we cannot write to it yet; the device must first issue an erase command to block 0. Doing so leads to the following state:

Block: 0 1 2

Page: 00 01 02 03 04 05 06 07 08 09 10 11

Content:

State: E E E E i i i i i i i i

Block 0 is now ready to be programmed. Most SSDs will write pages in order (i.e., low to high), reducing reliability problems related toprogram disturbance. The SSD then directs the write of logical block 100 into physical page 0:

Block: 0 1 2

Page: 00 01 02 03 04 05 06 07 08 09 10 11

Content: a1

State: V E E E i i i i i i i i

But what if the client wants toreadlogical block 100? How can it find where it is? The SSD must transform a read issued to logical block 100 into a read of physical page 0. To accommodate such functionality, when the FTL writes logical block 100 to physical page 0, it records this fact in anin-memory mapping table. We will track the state of this mapping table in the diagrams as well:

Table: 100 0 Memory

Block: 0 1 2

Page: 00 01 02 03 04 05 06 07 08 09 10 11 Flash

Content: a1 Chip

State: V E E E i i i i i i i i

Now you can see what happens when the client writes to the SSD.

The SSD finds a location for the write, usually just picking the next free page; it then programs that page with the block's contents, and records the logical-to-physical mapping in its mapping table. Subsequent reads simply use the table totranslatethe logical block address presented by the client into the physical page number required to read the data.

Let's now examine the rest of the writes in our example write stream:

101, 2000, and 2001. After writing these blocks, the state of the device is:

Table: 100 0 101 1 2000 2 2001 3 Memory

Block: 0 1 2

Page: 00 01 02 03 04 05 06 07 08 09 10 11 Flash

Content: a1 a2 b1 b2 Chip

State: V V V V i i i i i i i i

The log-based approach by its nature improves performance (erases only being required once in a while, and the costly read-modify-write of the direct-mapped approach avoided altogether), and greatly enhances reliability. The FTL can now spread writes across all pages, performing what is called wear levelingand increasing the lifetime of the device;

we'll discuss wear leveling further below.