Rong Gu, Simian Li, Haipeng Dai, Hancheng Wang, and Yili Luo, State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China; Bin Fan, Alluxio Inc; Ran Ben Basat, University College London; Ke Wang, Meta Inc; Zhenyu Song, Princeton University; Shouwei Chen and Beinan Wang, Alluxio Inc; Yihua Huang and Guihai Chen, State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China
Big data applications extensively use cache techniques to accelerate data access. A key challenge for improving cache utilization is provisioning a suitable cache size to fit the dynamic working set size (WSS) and understanding the related item repetition ratio (IRR) of the trace. We propose Cuki, an approximate data structure for efficiently estimating online WSS and IRR for variable-size item access with proven accuracy guarantee. Our solution is cache-friendly, thread-safe, and light-weighted in design. Based on that, we design an adaptive online cache capacity tuning mechanism. Moreover, Cuki can also be adapted to accurately estimate the cache miss ratio curve (MRC) online. We built Cuki as a lightweight plugin of the widely-used distributed file caching system Alluxio. Evaluation results show that Cuki has higher accuracy than four state-of-the-art algorithms by over an order of magnitude and with better stability in performance. The end-to-end data access experiments show that the adaptive cache tuning framework using Cuki reduces the table querying latency by 79% and improves the file reading throughput by 29% on average. Compared with the cutting-edge MRC approach, Cuki uses less memory and improves accuracy by around 73% on average. Cuki is deployed on one of the world’s largest social platforms to run the Presto query workloads.
USENIX ATC '23 Open Access Sponsored by
King Abdullah University of Science and Technology (KAUST)
Open Access Media
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.
This content is available to:
author = {Rong Gu and Simian Li and Haipeng Dai and Hancheng Wang and Yili Luo and Bin Fan and Ran Ben Basat and Ke Wang and Zhenyu Song and Shouwei Chen and Beinan Wang and Yihua Huang and Guihai Chen},
title = {Adaptive Online Cache Capacity Optimization via Lightweight Working Set Size Estimation at Scale},
booktitle = {2023 USENIX Annual Technical Conference (USENIX ATC 23)},
year = {2023},
isbn = {978-1-939133-35-9},
address = {Boston, MA},
pages = {467--484},
url = {https://www.usenix.org/conference/atc23/presentation/gu},
publisher = {USENIX Association},
month = jul
}