A Multi-Factor Adaptive Multi-Level Cooperative Replacement Policy in Block Storage Systems

As a vital method for computer system design, multilevel cache technology is still a research hotspot in the field of storage. Recently, researchers have designed many multilevel cache replacement algorithms by analyzing the historical trajectories of data blocks between different cache levels but suffer from high overhead and poor adaptability. In addition, these methods still try to determine the most suitable victim to be replaced, given a new block to be loaded into the cache but do not consider how to cooperate between different cache levels. To overcome these challenges, we propose a multi-factor adaptive multi-level cooperative cache replacement policy in block storage systems that leverages the hierarchical characteristics of multilevel cache and multi-factor orthogonality by the probability distribution. This adaptation is mainly reflected in two aspects: each cache level automatically adapts different cache policies based on I/O access patterns, and different cache levels cooperate by adjusting the dynamic frequency threshold. In this work, we choose as our target for optimization the replacement policy of the cloud block cache, because rich storage stacks in cloud environments can be well used as multi-level cache scenarios. We have evaluated our proposed framework by using block-based I/O traces collected from Alibaba Cloud, one of the largest cloud providers in the world, and several open-source traces. Experimental results show that our method improves the hit ratios by 28.9% and reduces the response time by 9.6% to the state-of-the-art cache replacement policies for multi-level cache across different workloads and cache sizes.