Background of SSD Wear Leveling Algorithm

The wear leveling algorithm is based on the basic characteristics of flash :

1. Do not support local update (outplace-update that is data in original location cannot be overwrite or change directly, this data will need to be relocated to a new available page while the original location labeled as an invalid page and being erased before this original location can be written again);

2. Take the basic unit of page for write and block for erase. To erase block, the valid data of selected page will need to be relocated. When large number of block are chosen for erase, the data relocation of pages in the block for subsequent reuse will determine the erase counts of the different related blocks;

3. Each block has a limited number of times for erase where frequently erased block will soon become a "bad block". Therefore, the balance on times of erase for each block can allow a longer life of the flash memory.

FTL usually view page as three different types: valid page, invalid page and free page, if there is a matching physical page to a logical address, the corresponding page data is valid or known as a valid page. Conversely, it will be an invalid page and become a free page after garbage collection operation where the invalid page being erased. From this point, data can be written to the free page.

For example, when logical address A (assume corresponding physical address 1) data needs to be revised, it is not possible to modify address A data directly but to read this data to cache for modification and write the modified data to new physical address 6 with mapping to logical address A. TRIM will then mark physical address 1 to be invalid. When free pages get lesser, garbage collection will be activated to erase invalid pages for free pages. At this point, questions arising as :

As the basic unit for erase is block, the valid pages in block to be erased need to be relocated first before the block erase. So should block erase be done on block with least valid pages or significantly more valid pages but less erase counts? Should erase counts of the valid block with cold data be considered? Or is there other condition to select some block for erase? Since garbage collection is directly linked to block erase count, the approach for a balance block erase instead of regular erase of hot data blocks or rare erase of other blocks contributed the background for wear leveling algorithm.

Topics covered in this article