Multi-Queue Algorithm

We have designed a new replacement algorithm, called Multi-Queue (MQ), that satisfies the three properties above. This algorithm maintains blocks with different access frequencies for different periods of time in the second level buffer cache.

The MQ algorithm uses multiple LRU queues: $Q_0$, $\dots$, $Q_{m-1}$, where $m$ is a parameter. Blocks in $Q_j$ have a longer lifetime in the cache than those in $Q_i$ ($i < j$). MQ also uses a history buffer $Q_{out}$, similarly to the 2Q algorithm [23], to remember access frequencies of recently evicted blocks for some period of time. $Q_{out}$ only keeps block identifiers and their access frequencies. It is a FIFO queue of limited size.

On a cache hit to block $b$, $b$ is first removed from the current LRU queue and then put at the tail of queue $Q_k$ according to $b$'s current access frequency. In other words, $k$ is a function of the access frequency, $QueueNum(f)$. For example, for a given frequency $f$, $QueueNum(f)$ can be defined as $log_2 f$. So the 8th access to a block that is already in the second level buffer cache will promote this block from $Q_2$ to $Q_3$ according to this $QueueNum(f)$ function.

On a cache miss to block $b$, MQ evicts the head of the lowest non-empty queue from the second level buffer cache in order to make room for $b$, i.e. MQ starts with the head of queue $Q_0$ when choosing victims for replacement. If $Q_0$ is empty, then MQ evicts the head block of $Q_1$, and so on. If block $c$ is the victim, its identifier and current access frequency are inserted into the tail of the history buffer $Q_{out}$. If $Q_{out}$ is full, the oldest identifier in $Q_{out}$ will be deleted. If the requested block $b$ is in $Q_{out}$, then it is loaded and its frequency $f$ is set to be the remembered value plus 1, and then $b$'s entry is removed from $Q_{out}$. If $b$ is not in $Q_{out}$, it is loaded into the cache and its frequency is set to 1. Finally, block $b$ is inserted into an LRU queue according to the value of $QueueNum(f)$.

MQ demotes blocks from higher to lower level queues in order to eventually evict blocks that have been accessed frequently in the past, but have not been accessed for a long time. MQ does this by associating a value called $expireTime$ with each block in the server buffer cache. ``Time'' here refers to logical time, measured by number of accesses. When a block stays in a queue for longer than a permitted period of time without any access, it is demoted to the next lower queue. This is easy to implement with LRU queues. When a block enters a queue, the block's $expireTime$ is set to be $currentTime + lifeTime$, where $lifeTime$, a tunable parameter, is the time that each block can be kept in a queue without any access. At each access, the $expireTime$ of each queue's head block is checked against the $currentTime$. If the former is less than the latter, it is moved to the tail of the next lower level queue and the block's $expireTime$ is reset. Figure 5 gives a pseudo-code outline for the MQ algorithm.

Figure 5: MQ algorithm

When $m$ equals 1, the MQ algorithm is the LRU algorithm. When $m$ equals 2, the MQ algorithm and the 2Q algorithm [23] both use two queues and a history buffer. However, MQ uses two LRU queues, while 2Q uses one FIFO and one LRU queue. MQ demotes blocks from $Q_1$ to $Q_0$ when their life time in $Q_1$ expires, while 2Q does not make this kind of adjustment. When a block in $Q_1$ (or $A_m$) is evicted in the 2Q algorithm, it is not put into the history buffer whereas it is with MQ.

Like the 2Q algorithm, MQ has a time complexity of $O(1)$ because all queues are implemented using LRU lists and $m$ is usually very small (less than 10). At each access, at most $m-1$ head blocks are examined for possible demotion. MQ is faster in execution and also much simpler to implement than algorithms like FBR, LFRU or LRU-K, which have a time complexity close to $O(log_2 n)$ (where $n$ is the number of entries in the cache) and usually require a heap data structure for implementation.

MQ satisfies the three properties that a good second level buffer cache replacement algorithm should have. It satisfies the minimal lifetime property because warm blocks are kept in high level LRU queues for at least $expireTime$ time, which is usually greater than the $minDist$ value of a given workload. It satisfies the frequency-based priority property because blocks that are accessed more frequently are put into higher level LRU queues and are, therefore, less likely to be evicted. It also satisfies the temporal frequency property because MQ demotes blocks from higher to lower level queues when its lifetime in its current queue expires. A block that has not been accessed for a long time will be gradually demoted to queue $Q_0$ and eventually evicted from the second level buffer cache.