KBP: Mining Block Access Pattern for I/O Prediction with K-Truss
Jia Ma, Xianqi Zheng, Yubo Liu, Zhiguang Chen · 2021
Block prefetching is a technology widely used to improve the I/O efficiency of storage systems. Block access pattern prediction is a key part of the prefetching algorithm. However, existing block access pattern prediction methods cannot achieve the goals of low overhead, real-time, and self- adaptability at the same time. In this paper, we propose a real-time prediction method, called KBP (K-Truss-based Block access pattern Prediction). KBP uses SA (Sequential Access) Filter to identify and filter sequential access patterns to distinguish different patterns. Then, KBP uses K-Truss dense subgraph algorithm to detect compound access patterns, so as to use the time and space advantages of the K-Truss algorithm to reduce the overhead of access pattern recognition and make it possible for KBP to run in real time. Furthermore, KBP uses online reinforcement learning to achieve the goal of self- adaptability. We evaluate KBP in real-world workloads and the results show that KBP can improve the hit rate of 11.2% compared to the state-of-the-art prefetching algorithms on average.