Hot data identification for flash-based storage systems using multiple bloom filters

Dongchul Park, David H Du

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

23 Scopus citations

Abstract

Hot data identification can be applied to a variety of fields. Particularly in flash memory, it has a critical impact on its performance (due to a garbage collection) as well as its life span (due to a wear leveling). Although the hot data identification is an issue of paramount importance in flash memory, little investigation has been made. Moreover, all existing schemes focus almost exclusively on a frequency viewpoint. However, recency also must be considered equally with the frequency for effective hot data identification. In this paper, we propose a novel hot data identification scheme adopting multiple bloom filters to efficiently capture finer-grained recency as well as frequency. In addition to this scheme, we propose a Window-based Direct Address Counting (WDAC) algorithm to approximate an ideal hot data identification as our baseline. Unlike the existing baseline algorithm that cannot appropriately capture recency information due to its exponential batch decay, our WDAC algorithm, using a sliding window concept, can capture very fine-grained recency information. Our experimental evaluation with diverse realistic workloads including real SSD traces demonstrates that our multiple bloom filter-based scheme outperforms the state-of-theart scheme. In particular, ours not only consumes 50% less memory and requires less computational overhead up to 58%, but also improves its performance up to 65%.

Original languageEnglish (US)
Title of host publication2011 IEEE 7th International Workshop on Storage Network Architecture and Parallel I/Os, SNAPI 2011
PublisherIEEE Computer Society
ISBN (Print)9781457704284
StatePublished - 2011
Event2011 IEEE 7th International Workshop on Storage Network Architecture and Parallel I/Os, SNAPI 2011 - Denver, CO, United States
Duration: May 25 2011May 25 2011

Publication series

Name2011 IEEE 7th International Workshop on Storage Network Architecture and Parallel I/Os, SNAPI 2011

Other

Other2011 IEEE 7th International Workshop on Storage Network Architecture and Parallel I/Os, SNAPI 2011
CountryUnited States
CityDenver, CO
Period5/25/115/25/11

Keywords

  • Bloom filter
  • Flash memory
  • Hot and cold data
  • Hot data idenficiation
  • SSD
  • WDAC

Fingerprint Dive into the research topics of 'Hot data identification for flash-based storage systems using multiple bloom filters'. Together they form a unique fingerprint.

Cite this