# Leveraging Static and Dynamic Wear Leveling to Prolong the Lifespan of Solid-State Drives
## 2 Background and Related Work
### Wear Leveling Policies  
Policies designed to achieve wear leveling are broadly classified into dynamic wear leveling and static wear leveling. Dynamic wear leveling policies aim to achieve wear leveling by selecting victim blocks during garbage collection. For instance, the CB (Cost Benefit) policy [15] calculates a cost-benefit metric for each block, considering factors such as the number of valid pages in the block and the elapsed time since the block was last written to (referred to as its age). The block with the lowest cost-benefit metric is then designated as the victim block. If all pages in a block are invalidated, the block is selected as the victim block regardless of its age. Otherwise, a block with a high proportion of valid pages can be selected as the victim block if its age is high, indicating that it has been unused for a long time. Consequently, a more uniform distribution of erase counts across blocks is achieved compared to the greedy policy. The WOGC (Write Order Based Garbage Collection) policy [16] also employs a formula that considers factors such as the number of valid pages in each block, the cumulative erase count of blocks, and the chronological order in which blocks were used after being erased to select victim blocks. Similar to CB, if a block has no valid pages, it is chosen as the victim block regardless of its erase count or the write order. However, if valid pages are present, a block with a substantial number of valid pages may still be chosen as the victim block if it exhibits a low erase count and was written earlier, indicating it has been unused for a long time. Consequently, the distribution of erase counts across blocks tends to be more uniform compared to the greedy policy. Dynamic wear leveling policies such as CB and WOGC effectively reduce the standard deviation of block erase counts by maintaining a more uniform distribution of erase counts across all blocks. However, blocks with a high number of valid pages are more likely to be selected as victim blocks, resulting in fewer clean pages being reclaimed compared to the greedy policy. This could potentially lead to more frequent garbage collections. Thus, despite achieving a lower standard deviation in block erase count distribution, the extension of SSD lifespan may be constrained by frequent garbage collections. Furthermore, the longer duration of individual garbage collection operation due to a higher number of valid pages to copy may also result in performance degradation. Additionally, since values such as the cost-benefit of all blocks must be calculated to find the minimum or maximum value when selecting a victim block for garbage collection, the worst-case time complexity for performing garbage collection is \(O(N)\) (where \(N\) is the number of blocks). On the other hand, static wear leveling policies do not intervene in the selection of victim blocks of garbage collection. In other words, they employ a greedy policy, selecting the block with the fewest valid pages as the victim block, and tolerate some level of imbalance in erase count distribution among blocks. However, if a specific block undergoes excessive erasures compared to other blocks, surpassing a predefined threshold, cold data stored in other blocks is relocated to the worn-out block [18; 19; 20]. If the identification of cold data is accurate, the probability of selecting the block as the victim block decreases, as it is likely to have a higher proportion of valid pages in the future compared to other blocks. Consequently, the rate of increase in the erase count of the block is mitigated, thereby reducing the likelihood of it transitioning into a bad block. The BET (Block Erase Table) policy [18] and the Rejuvenator [19] policies perform migration when the erase count of a victim block exceeds a fixed threshold. However, this approach can lead to excessive migration even when the erase count of blocks is relatively low compared to the tolerable maximum erase count, resulting in significant migration overhead [20].