Rejuvenator: A static wear leveling algorithm for NAND flash memory with minimized overhead

Abstract

NAND flash memory is fast replacing traditional magnetic storage media due to its better performance and low power requirements. However the endurance of flash memory is still a critical issue in using it for large scale enterprise applications. Rethinking the basic design of NAND flash memory is essential to realize its maximum potential in large scale storage. NAND flash memory is organized as blocks and blocks in turn have pages. A block can be erased reliably only for a limited number of times and frequent block erase operations to a few blocks reduce the lifetime of the flash memory. Wear leveling helps to prevent the early wear out of blocks in the flash memory. In order to achieve efficient wear leveling, data is moved around throughout the flash memory. The existing wear leveling algorithms do not scale for large scale NAND flash based SSDs. In this paper we propose a static wear leveling algorithm, named as Rejuvenator, for large scale NAND flash memory. Rejuvenator is adaptive to the changes in workloads and minimizes the cost of expensive data migrations. Our evaluation of Rejuvenator is based on detailed simulations with large scale enterprise workloads and synthetic micro benchmarks.