Solid State Drive Primer # 11 - Controller Functions - Garbage Collection
This article follows the Wear Leveling post and covers SSD controller’s Garbage Collection algorithms. Garbage Collection is the process to reclaim previously written blocks of data so they can be rewritten with new data.
The reason there is a need for Garbage Collection is NAND’s requirement to be erased prior to being written. A block is the smallest erasure unit of NAND flash and it is typically made up of 32 to 64 Pages.
A page of data can be written as long as it is already erased, but it is very inefficient to erase 32 or 64 pages in a block just to reclaim a single Page. There are many challenges related to Garbage Collection algorithms and the efficiency, reliability and performance can be affected by its design.
New SSD with all Erased NAND Blocks:
The diagram above shows two blocks of a fresh SSD which contain 32 Pages capable of storing 4KB of data each. This is a typical configuration of NAND and we will use it for the remainder of this article.
As you can see all of the Pages are erased from the factory and ready to be written. We will cover the other states of Valid Data and Dirty/Stale Data as we move forward.
First Page Writes to Fresh SSD:
On the first write to a fresh NAND block, things are easy. All pages are erased and it is just a matter of writing sequentially to these erased Pages.
Shown above is how a typical Garbage Collection algorithm would perform the initial task of writing 10 new pages of data on an already erased block.
Updating Page Data:
We take it a step further in the above diagram by updating the 10 pages we originally wrote to the NAND. Since we would have to erase the entire block to erase the pages we want to update, we instead copy and write the updated data in the next available erased pages and mark the previous pages as dirty or stale.
At this point, the 10 pages are stored with valid data and we have 10 pages marked as dirty which cannot be written until the entire NAND Block is erased.
Filling the NAND Block:
This latest diagram above shows an additional 12 pages of data written to the NAND block. These new items 11 - 22 were placed in the final 12 erased pages at the end of NAND Block #1.
At this point, the entire NAND Block has been used. There are no longer erased pages to store data since there is only stored data or dirty data which needs to be erased to reclaim these pages.
What happens next - Garbage Collection?
Now the moment you’ve all been waiting for. What happens when all of the pages of the NAND block are either occupied with good data or previously written data which is no longer valid?
This is where Garbage Collection comes into play. To reclaim the NAND pages to an erased state, first any valid data in that block needs to be copied and written to the erased pages in a new NAND block. As you can see from the latest diagram, 22 valid pages of data were copied from the full Block #1 and written to the fully erased Block #2.
Once the valid data has been successfully written to the new block, then the entire Block #1 is erased. This is a one step process and it deletes any valid or dirty/stale data. Now Block #1 can be written to as if it were a fresh block.
The design of the Garbage Collection algorithm has a lot to do with other factors such as Write Amplification, so it is an important part of an overall SSD design.
The next article will continue with additional issues and methods SSDs use to address them.
If you would like to discuss this further please contact us.
