The Dual-pool algorithm is a classic wear leveling algorithm designed to extend the life of flash memory. It achieves two solutions: the first is to store cold data to prevent the block from being worn, because the frequently updated thermal data will increase wear; the second is not to deal with the processed blocks until the wear balance is in effect.
The uneven wear of the flash block is due to the spatial locality of the workload. The pages are divided into three categories: free page, which means that pages can be written, live page for valid pages, and dead page for invalid pages. Because the cold data can be stored more stably on the valid page in the block, and the hot data is updated quickly, the constant update will make the valid page in the original page become an invalid page, which will leave a lot of dead pages in the block. When doing garbage collection, it tends to reclaim these blocks with more dead pages, so always free pages are recovered from those blocks that store more hot data. Writing hot data is more frequent than writing cold data, so this hot data is stored in a specific block. But such a phenomenon will gradually make the worn blocks unbalanced.
Young block & Old block: The former is a young block with a small number of erasures, the latter is an old block with a lot of erasures, and the core of the dual pool algorithm implements the following operations:
Cold-data migration: putting cold data from young blocks Migrate to old blocks
Hot-cold regulation: After the cold data migration occurs, the blocks involved should be prevented from erasing the old blocks, and the young blocks should be erased.
Logically, the flash blocks are divided into two groups: a hot pool dedicated to storing hot data blocks and a cold pool dedicated to storing cold data blocks. Set the queue in the hot pool
The Dirty Swap (DS) operation implements the above-mentioned Cold-data migration and Hot-cold regulation. Each time a write operation is completed, a check is made to determine whether the hot data block of the hot pool and the cold data in the cold pool. The erase period difference of the block is greater than the threshold. The process is as follows:
If the above conditions are met, perform the following steps:
Adaptive Pool Resizing: This part deals with the dynamic changes of spatial locality and extends the basic concepts above. If the access mode has not changed, the above execution results will have a good effect. But in the actual workload, it is difficult to achieve. Access to hot and cold data is not static, and using DS alone is not acceptable. Considering that a block has just migrated from the cold pool to the hot pool and no longer stores cold data, assuming that the hot data in the block happens to be cold, the block is in the hot pool as the block is no longer erased and worn. It becomes "silent" because storing cold data makes its erase cycle relatively small, and the block is no longer erased by wear. So, for improvement, a new operation is defined in the hot pool:
Considering that there is a block in the DS that migrates to the cold pool, this block has a large erase period, and the effective erase period is zero. The DS places the cold data in the block to stop it from being erased and erased. On the one hand, if the cold data is maintained, the effective erase period value of this block will remain at a low value. On the other hand, if this block no longer stores cold data, the effective erase cycle will grow very quickly. These two cases can be clearly distinguished by the introduction of an effective erase period test.
Therefore, when a write operation is completed, the DS operation is performed first, then the CPR is executed, and finally the HPR is executed.
For very large-scale flash storage systems, this proposed algorithm provides a very powerful solution to the wear leveling problem.