Erasing Belady's limitations: In search of flash cache offline optimality

Yue Cheng, Fred Douglis, Philip Shilane, Michael Trachtman, Grant Wallace, Peter Desnoyers, Kai Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution

29 Scopus citations


NAND-based solid-state (flash) drives are known for providing better performance than magnetic disk drives, but they have limits on endurance, the number of times data can be erased and overwritten. Furthermore, the unit of erasure can be many times larger than the basic unit of I/O; this leads to complexity with respect to consolidating live data and erasing obsolete data. When flash drives are used as a cache for a larger, disk-based storage system, the choice of a cache replacement algorithm can make a significant difference in both performance and endurance. While there are many cache replacement algorithms, their effectiveness is hard to judge due to the lack of a baseline against which to compare them: Belady's MIN, the usual offline best-case algorithm, considers read hit ratio but not endurance. We explore offline algorithms for flash caching in terms of both hit ratio and flash lifespan. We design and implement a multi-stage heuristic by synthesizing several techniques that manage data at the granularity of a flash erasure unit (which we call a container) to approximate the offline optimal algorithm. We find that simple techniques contribute most of the available erasure savings. Our evaluation shows that the container-optimized offline heuristic is able to provide the same optimal read hit ratio as MIN with 67% fewer flash erasures. More fundamentally, our investigation provides a useful approximate baseline for evaluating any online algorithm, highlighting the importance of comparing new policies for caching compound blocks in flash.

Original languageEnglish (US)
Title of host publicationProceedings of the 2016 USENIX Annual Technical Conference, USENIX ATC 2016
PublisherUSENIX Association
Number of pages14
ISBN (Electronic)9781931971300
StatePublished - Jan 1 2016
Event2016 USENIX Annual Technical Conference, USENIX ATC 2016 - Denver, United States
Duration: Jun 22 2016Jun 24 2016

Publication series

NameProceedings of the 2016 USENIX Annual Technical Conference, USENIX ATC 2016


Conference2016 USENIX Annual Technical Conference, USENIX ATC 2016
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • General Computer Science


Dive into the research topics of 'Erasing Belady's limitations: In search of flash cache offline optimality'. Together they form a unique fingerprint.

Cite this