An efficient buffer replacement algorithm for NAND flash storage devices

NAND flash storage devices are now revolutionizing storage stacks. As their capacities are rapidly increasing, they are now being adopted virtually in all classes of computing devices, including mobile devices, desktop computers, and cloud servers. However, there are two remaining problems: first, as flash density increases, the lifetime of the storage medium decreases rapidly. Second, random writes significantly decrease performance and lifetime since they generate more hidden writes inside NAND flash storage devices. In this paper, we propose a novel buffer replacement algorithm called TS-CLOCK, to address those two problems. TS-CLOCK exploits temporal locality to keep the cache hit ratio high and also exploits spatial locality to maintain evicted writes flash-friendly. The key idea of our flash-friendly eviction is that, when evicting a dirty page, TS-CLOCK first selects a flash block with the largest number of dirty pages that are least likely to be accessed and then sequentially evicts pages in the block. Since it generates pseudo sequential writes for a flash block, it significantly increases performance and lifetime at once by reducing the number of hidden writes. We have implemented TS-CLOCK and compared it with seven replacement algorithms, including traditional and flash-aware ones, for several real workloads. Our experimental results show that TS-CLOCK outperforms the state-of-the-art replacement algorithm, Sp. Clock, by 30% on the NAND flash storage devices and extends the lifetime by 53%.