Garbage Collection
This lesson discusses how garbage collection takes place in the flash-based SSDs.
We'll cover the following...
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:
The problem we have now should be obvious: physical pages 0 and 1, although marked VALID, have garbage in them, i.e., the old versions of blocks 100 and 101. Because of the log-structured nature of the device, overwrites create garbage blocks, which the device must reclaim to provide free space for new writes to take place.