Ouroboros Wear-leveling: A Two-level Hierarchical Wear-leveling Model for NVRAM

Abstract

Emerging non-volatile memory (NVM) technologies have a limit on the number of writes that can be made to any cell, similar to the erasure limits in NAND Flash. This motivates the need for wear-leveling techniques to distribute the writes evenly among the cells. Unlike NAND Flash, cells in NVM can be rewritten without the need for erasing the entire containing block, avoiding the issues of space reclamation and garbage collection, motivating alternate approaches to the problem.

In this thesis, we propose a hierarchical wear-leveling model called Ouroboros Wear-leveling. Ouroboros uses a two-level strategy whereby frequent low-cost intra-region wear-leveling at small granularity is combined with inter-region wear-leveling at a larger time interval and granularity. Ouroboros constructs the optimal lexicographically smooth block permutation based on the current wear and access distributions. The past access patterns are used to predict the accesses till the next inter-region wear leveling. Two optimizations, adaptive pruning and randomization, are applied to the cycle decomposition of the permutation in order to reduce the number of block movements and avoid destructive repetitive patterns that accelerate wear out. We also propose a way to optimize wear-leveling parameter settings with target smoothness level under limited timing and space overhead constraints for different memory architectures and trace characteristics.

Several experiments are performed on both synthetically-generated memory traces with special characteristics and two block-level storage traces generated by Microsoft and FIU. The results show that Ouroboros Wear-leveling can distribute writes smoothly across the whole NVM with around 0.2% space overhead and around 0.52% timing overhead for a 512GB memory with 500MB/s write rate.