Multigrain: Adaptive multilevel hot data identifier with a stack distance-based prefilter
Hyerim Lee, Dongchul Park · Future Generation Computer Systems · 2025
Many computer system applications, such as data caching and Not AND (NAND) flash memory-based storage systems, employ a hot data identification scheme. However, regardless of the workload characteristics, most existing studies have adopted only a fine-grained (i.e., block-level) hot data decision policy, causing high computational overhead and error rates. Different workloads mandate different treatments to achieve effective hot data identification. Based on our comprehensive workload studies, this paper proposes Multigrain, an adaptive multilevel hot data identification scheme that dynamically selects a coarse-grained (i.e., subrequest-level) policy or coarser-grained (i.e., request-level) policy based on the workload. The proposed Multigrain employs multiple effective bloom filters to capture frequency and recency information. Moreover, it adopts a simple and smart prefilter mechanism leveraging workload stack distance information. To our knowledge, the proposed scheme is the first multilevel coarse-grained hot data identification scheme that judiciously selects an optimal hot data decision granularity to achieve effective and accurate identification. Our extensive experiments with many realistic workloads demonstrate that our adaptive multilevel scheme significantly reduces the execution time (by an average of up to 6.9 × ) and error rate (by an average of up to 2.27 × ) using the effective coarse-grained policies and a prefiltering mechanism. • The first multilevel coarse-grained hot data identification scheme. • Strong correlation between the starting LBA and subsequent LBAs of each request. • Stack distance-based prefiltering mechanism to drop unnecessary I/O requests. • Automatic granularity decision based on the workload analysis. • Up to 6.9x faster execution time and 2.27x lower error rate.