Hot Data Identification for Flash Memory Using Multiple Bloom Filters

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 garbage collection) as well as its lifespan (due to wear leveling). Although this is an issue of paramount importance in flash memory, it is the least investigated one. Moreover, all existing schemes focus only or mainly on a frequency viewpoint. However, recency factor also must be considered as much importantly as the frequency for 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 (named 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 proposed scheme outperforms the state-of-the-art hot data identification scheme. In particular, our scheme not only consumes less memory (50% less) and requires less computational overhead up to 58%, but also improves its performance up to 65%.