Accurate Probabilistic Miss Ratio Curve Approximation for Adaptive Cache Allocation in Block Storage Systems
Rongshang Li1, Yingtian Tang2, Qiquan Shi3,a, Hui Mao3,b, Lei Chen3,c, Jikun Jin4,d, Peng Lu4,e and Zhuo Cheng4,f
1The University of Sydney, NSW, Australia
roli5128@uni.sydney.edu.au
2University of Electronic Science and Technology of China, Chengdu, China
yingtiantd@outlook.com
3Huawei Noah's Ark Lab, Hongkong, China
ashiqiquan@huawei.com
bmao.hui1@huawei.com
clc.leichen@huawei.com
4Huawei Storage Product Line, Chengdu, China
djinjikun@huawei.com
elupeng25@huawei.com
fchengzhuo@huawei.com
ABSTRACT
Cache plays an important role in storage systems. With better allocation of cache space to each storage device, total I/O latency can be reduced remarkably. To achieve this goal, we propose an Accurate Probabilistic miss ratio curve approximation for Adaptive Cache allocation (APAC) system. APAC can obtain near-optimal performance for allocating cache space with low overhead. Specifically, with a linear-time probabilistic approximation of reuse distance of all blocks inside each device, APAC can accurately estimate the miss ratio curve (MRC). Furthermore, APAC utilizes the MRCs to obtain the near-optimal configuration of cache allocation by dynamic programming. Experimental results show that APAC achieves higher accuracy in MRC approximation compared to the state-of-the-art methods, leading to higher hit ratio and lower latency of the block storage systems.
Keywords: Reuse Distance Estimation, Miss Ratio Curve, Cache Allocation.
