Hint-K: An Efficient Multi-level Cache Using K-Step Hints

I/O performance has been critical for large scale distributed systems. Many approaches, including hint-based multi-level cache, have been proposed to smooth the gap between different levels. These solutions demote or promote cache blocks based on the latest history information, which is insufficient for applications where frequent demote and promote operations occur. In this paper we propose a novel multi-level buffer cache using K-step hints (Hint-K) to improve the I/O performance of distributed systems. The basic idea is to promote a block from the lower level cache to the higher level or demote a block vice versa based on the block’s previous K-step promote or demote operations, which are referred to as K-step hints. If we make an analogy between Hint-K and LRU-K, LRU-K keeps track of the times of last K references for blocks within a single cache level, while our Hint-K keeps track of the information of the last K movements (either demote or promote) of blocks among different cache levels. We develop our Hint-K algorithm and design a mathematical model that can efficiently describe the activeness of any blocks in any cache level. Simulation results show that Hint-K achieves better performance compared to current popular multi-level cache schemes such as PROMOTE, DEMOTE, and MQ under different representative I/O workloads.