Some of the most well-known terms that come up when discussing flash memory are, without a doubt, the most poorly named in the NAND flash ecosystem. The other unusual thing about these terms is how much their importance—when it comes to describing the properties or operations of a flash system—has changed over time. Those terms that were once the most important are now among the least important.
Garbage Collection (GC) is a well-known term because much of the behavior and performance of any system using NAND flash is a function of how the GC is performed. Yet it’s the most poorly named in flash technology, because collecting the garbage is exactly what it does not do. GC is the process of collecting everything that is not garbage from a block of flash and finding somewhere new to write it before the system can erase the block. Really, GC should be called recycling (it shares much in common with the recycling that most of us are familiar with).
There are different kinds of recycling that have differing levels of efficiency. Just as recycling varies from single to multiple streams, so too does GC. General GC is where all data is put together in a block, and hot/cold GC is where data with different rates of change are put into different blocks. Today, GC is one of the most important aspects of an all flash memory array. And like real garbage collection, if your NAND garbage collection does not happen fast enough or frequently enough to handle what you have put out for collection, you will not be happy.
Wear leveling used to be the most important aspect of flash systems. To understand how wear leveling went from being possibly the most important term in flash to one of the least, we have to go back to the earliest days of NAND flash. Just like hard disk drives, a block of flash might go bad, which means flash has always needed a way to map a spare block in place of a bad one, using what is called a Flash Translation Layer (FTL). At first, bad block mapping was essentially the only function of the FTL, which would be called a “block mapping FTL.”
The problem with block mapping FTLs is that, if you want to write a page to a new block (so that you can change the contents of the address mapped to by that page), you have to copy the rest of the pages in the block along with it.
Flash chips once had very few spare blocks; to make life easy for the computer, companies used to always want their capacity to be a nice round “power of two” in size. Imagine you have just one spare flash chip beyond those you need—when the user writes to a given address, there is only one choice for which empty block to write it into (and move the rest of its block, or garbage-collect it), along with the page the user wrote; then the block that contained the old copy can be erased. But if the user writes to the same address again and again, the only free block is the one that was just garbage, so the system will just ping pong between those two blocks until one of them wears down.
The job of the wear-leveling algorithm was to track the number of times a block had been written, and occasionally swap two blocks on its own. Eventually, flash acquired more spare blocks, so companies stopped caring if it was more work for the computer to handle non-power of two sizes—this meant that companies could have as many spares as they wanted.
Most importantly, the FTLs started to track pages instead of just blocks. Now when one page moves, the garbage collector—which once had no choice in what it moved—didn’t have to move the rest of the block. Suddenly almost all the responsibility for preventing wear-out, which used to belong to the wear leveler, is now given to the garbage collector. Since the garbage collector essentially handles the wear leveler’s job for all the active data, all that is left for the wear leveler today is to occasionally check for blocks that have not changed in a long time, and move their pages to a block that has been used more frequently.
Don’t judge a book by its cover or title. A lesson that is true in technology nomenclature as well. While both garbage collection and wear leveling imply a certain function and purpose, the true meaning is either quite the opposite, or has shifted due to changes in the technology.
Jon Bennett is a Violin Memory co-founder and CTO, as well as the inventor of the Violin Switched Memory (VXM) technology.