FLOWS: Balanced MRC Profiling for Heterogeneous Object-Size Cache

While Miss Ratio Curve (MRC) profiling methods based on spatial sampling are effective in modeling cache behaviors, previous MRC studies lack in-depth analysis of profiling errors and primarily target homogeneous object-size scenarios. This has caused imbalanced errors of existing MRC approaches when employed in heterogeneous object-size caches. For instance, in CDN traces, the error of the Byte Miss Ratio Curve (BMRC) could be two orders of magnitude larger than that of the Object Miss Ratio Curve (OMRC).

In this paper, we reveal an important insight from our experimental analysis, namely, the source of profiling inaccuracy is twofold, the "imbalanced requests" and the heterogeneous object-size distribution. To this end, we propose 𝐹 𝐿𝑂𝑊 𝑆, a Filtered LOw-variance Weighted Sampling approach, to address the root causes of the problem by combining a Cache Filter, designed to balance sampled requests, with a Weighted Sampling technique, designed to reduce bytelevel estimation error. 𝐹 𝐿𝑂𝑊 𝑆 constructs a more accurate MRC for traces with heterogeneous content popularity and object sizes. Evaluation on real-world traces demonstrates that 𝐹 𝐿𝑂𝑊 𝑆 reduces the error of the BMRC and OMRC profiling by 16× and 3×, respectively, compared with stateof-the-art approaches. Additionally, 𝐹 𝐿𝑂𝑊 𝑆 enables cache systems to effectively balance the Byte Hit Ratio (BHR) and Object Hit Ratio (OHR), achieving an improvement of up to 26.5% in overall hit rate compared to other methods.