Garbage Collection

Data is written to the flash memory in units called pages. However, the memory can only be erased in larger units called blocks. If the data in some of the pages of the block are no longer needed (also called stale pages), only the pages with good data in that block are read and re-written into another previously erased empty block. Then the free pages left by not moving the stale data are available for new data. This is a process called garbage collection.

Garbage collection is a method the SSD uses to create “free blocks.”  “Free blocks” are simply empty blocks or blocks marked with all invalid data, which are therefore available for the SSD to use.  In this example, we have 4 blocks available.  Computers count starting with 0, so we have Blocks 0, 1, 2, and 3.  We’re going to assume that we must always maintain at least one free block and that the TRIM command is not supported (TRIM is discussed here).

Let’s say we write File A, which in this case is 3 pages in size.  We write to the first available free page, which is in BLK 0. 

Next, we write file B, which is 5 pages in size.  We write to the next available page, which is the last one in BLK 0, and continue to BLK1 for the next available pages.

Now, we want to modify File A.  The new file is 4 pages in size.  You cannot overwrite a file on an SSD.  Instead, we write the newly modified file A to the next available free pages, which are in BLK 2, and mark the existing File A as invalid in BLK 0.

Finally, we want to write File C, which is 3 pages in size.  The problem is that if we write File C now, we will have no free blocks available (one of our assumptions is that we must ALWAYS have at least one free block).  So, before we can write File C, we must clear a free block.  BLK0 is almost ready for an erase, except it contains one valid piece of data from File B.  When Garbage Collection runs, it takes this valid page of data and copies it to the next available free page in BLK 3.  Now, BLK0 can be erased, creating a free block and freeing us to write File C to the remaining pages in BLK 3.