‘Garbage Collection in SSDs’ is a contributed article that was submitted by LSI and authored by Kent Smith, Senior Director of Product Marketing, Flash Components Division, LSI Corporation. It’s importance cannot be understated for anyone venturing into today’s world of SSDs.
Garbage collection (GC) is a fundamental process with all solid state drives (SSDs), but it can be implemented in different ways that can impact the overall SSD performance and endurance. In this article, we’ll look at how GC works, how it can be implemented, and how it relates to the TRIM command and over provisioning.
Unlike hard disk drives (HDDs), NAND flash memory cannot overwrite existing data they must first erase old data before writing new data to the same location. With SSDs, GC is the name for the process of relocating existing data to new locations and allowing the surrounding invalid data to be erased. Flash memory is divided into blocks, which is further divided in pages. Data can be written directly into an empty page, but only whole blocks can be erased. Therefore, to reclaim the space taken up by invalid data, all the valid data from one block must be first copied and written into the empty pages of a new block. Only then can the invalid data in the original block be erased, making it ready for new valid data to be written.
The process is illustrated in Figure 1. Column one shows pages A-D are written to block X. Sometime later that data is changed, so pages A-D are written and the original pages A-D are marked invalid (shown in column two). At the same time, additional data is written to pages E-H. Column two shows these changes and now block X is full, but is holding space for now invalid data (A-D) which cannot be reclaimed until the whole block is erased.
To achieve this objective, the valid data in block X must be moved to a new block so that the original block can be erased to start over. Column three shows the data from pages A-D as well as E-H being written to a new block (Y), so the space from block X can be reclaimed by erasing it. The writes from this step are not from the host system and are the source for increased write amplification in an SSD, meaning the flash in the SSD is being written more than what came from the host originally. Since flash memory has a limited number of erase and write cycles this operation should be minimized when possible, but it is still a necessary part of an SSD’s operation.
Figure 1: The garbage collection process. Source: Wikipedia
Note that wear leveling typically occurs during GC, as data is written to a variety of new blocks in order to spread wear around over the breadth of the SSD. Since there are a limited number of writes the flash can sustain over its lifetime, if data was always written to the same block, its life of write cycles would be exhausted prematurely compared to all other blocks. This continued early block retirement would eventually reduce the available capacity of the drive and prevent it from performing at its full capability. Ideally, all of the blocks of the SSD need to be worn at the same rate throughout the life of the drive.
OS AWARENESS VS DRIVE AWARENESS
In an HDD system, the Operating System (OS) can simply request that new data be written to the same location where the older, now invalid data, is stored, and the HDD will directly overwrite the old data. In an SSD, however, the page must first be erased before it can be written to locations previously holding data the SSD cannot directly overwrite existing data as stated earlier.
The OS understands the files, their structure, and the logical locations where they are stored, but does not understand the physical storage structure of the storage device. In any storage system, the storage device doesn’t know the file structure it simply knows that there are bytes of data written in specific sectors. The storage system, whether SSD or HDD, returns the data from physical locations when the OS asks for data in the corresponding logical locations.
When the OS deletes the file, it simply marks the space used for that data as free in its logical data table. With HDDs, the OS does not need to tell the storage device anything about the deletion because it would simply write something new into that same physical location in the future. In the case of an SSD, it only becomes aware that the data is deleted (or invalid) when the OS tries to write to that location again. At that time the SSD marks the old data as invalid and it writes the new data to a new physical location. It may also perform GC at that same time, but that varies between SSD architectures and other conditions at that moment.