LIMES: Mining Spatial-Temporal Associations for Cloud Block Storage Cache Prefetching

Data prefetching is a crucial technique for enhancing performance in cloud block storage (CBS). Through a comprehensive analysis of numerous real-world traces, we identify two key limitations in existing prefetchers. First, individual requests in CBS often access multiple consecutive data blocks, leading to significant time overhead when current prefetchers attempt to exploit the temporal block associations. Second, single-mode prefetchers, whether temporal or spatial, fail to deliver satisfactory performance under complex and dynamic workloads. To address these challenges with low cost, we propose an offset-based and ideal length temporal prefetcher (OIL) based on the request offset analysis. OIL reduces time overhead and prefetching table redundancy by leveraging coarse-grained offset associations rather than block-grained associations. Subsequently, we introduce an offset-based and adaptive length temporal prefetcher (OAL), which optimizes storage efficiency by replacing history access tables with a self-adaptive global prefetching length adjusted through performance feedback. OAL mitigates the high storage overhead introduced by OIL and achieves a balance between performance and storage efficiency. Furthermore, we design a lightweight multi-expert spatial-temporal prefetching framework (LIMES) that integrates temporal and spatial prefetching experts to fit varying workloads by switching optimal approaches in real time. In comparison with state-of-the-art prefetchers, the implementation of LIMES with OIL and OAL demonstrates performance enhancements, yielding improvements in average cache hit rates by 9.88% and 4.46%, while reducing average access latency by 21.32% and 10.01%, respectively.