On the Cost of Near-Perfect Wear Leveling in Flash-Based SSDs

Wear leveling (WL) techniques in flash-based SSDs aim at distributing the erase cycles as uniformly as possible across the memory blocks within the SSD to extend its life span. The downside of any WL technique is that it causes additional internal write operations, thereby increasing the so-called write amplification (WA) factor, which equals the ratio between the total number of writes performed and the number of writes requested by the host system. In this article, we address the question whether near-perfect WL is possible at low costs in terms of the WA factor. We answer this question affirmatively by presenting a simple randomized algorithm that combines WL with garbage collection. This algorithm guarantees that the wear is nearly perfectly balanced at all times while causing a low increase in the WA. This is demonstrated mathematically using a mean field model in case of uniform random writes and using trace-driven simulation experiments for general workloads.