Garbage Collection

The first cost of any log-structured approach such as this one is that garbage is created, and therefore garbage collection (i.e., dead-block reclamation) must be performed. Let’s use our continued example from the last lesson to make sense of this. Recall that logical blocks 100, 101, 2000, and 2001 have been written to the device.

Now, let’s assume that blocks 100 and 101 are written to again, with contents c1 and c2. The writes are written to the next free pages (in this case, physical pages 4 and 5), and the mapping table is updated accordingly. Note that the device must have first erased block 1 to make such programming possible: