hesela.devMulti-Queue cache replacement
Multi-Queue cache replacement combines frequency-ranked LRU queues, access-driven demotion and a bounded history of evicted blocks.
MQ addresses a lower-level buffer cache whose requests have been filtered by upper caches. Its original evaluation used four historical traces with 8 KiB blocks; this is a different request population from the application stream. [2]
Resident blocks occupy LRU queues ranked by access frequency. Replacement selects the head of the lowest nonempty queue. Evicted identifiers and counts enter FIFO history Qout; a history hit still fetches data and uses the remembered count plus one. [1]
Aging uses logical time measured in cache accesses, not elapsed seconds. An expired head above Q0 moves down one level and receives a new deadline. This is queue-priority aging, not a wall-clock data-validity TTL. Figure 5 changes position and deadline without decreasing the stored reference count; a later hit increments that count and recomputes placement. [1]
The reported experiments used eight resident queues and history capacity four times the resident block count. These are configuration choices, not the definition of MQ. [3] Linux blk-mq instead dispatches block I/O requests; it is not this cache policy. [5]
Each access checks at most m-1 queue heads for demotion, where m is the resident queue count. The paper calls this constant-time with a fixed, small queue count; allowing m to grow changes that work bound. [1]
With one queue, MQ reduces to LRU. With two queues, it is not 2Q: MQ uses two LRU queues and age-based demotion, while 2Q uses FIFO admission and does not put main-queue evictions into its history. Queue count alone therefore does not identify a replacement policy. [1]
Relations
Limitations
- The historical storage-server results do not establish modern SSD mapping-cache performance or a universal advantage over LRU. [4]
- The simulations adapt lifeTime from access-history statistics; the paper delegates the adjustment method to the author's thesis, so fixed-lifeTime demonstrations alone do not reproduce that evaluation. [3]
- MQ+Hints (2005) requires client tags: SYNCH marks imminent eviction, REPLACE preparation for eviction, and RECOV recovery-driven cleaning. SYNCH describes eviction timing, not durability. At a full cache, READ hits are served without queue updates and RECOV leaves replacement state unchanged; cold-start handling differs. These hints do not cancel storage writes. [6]
Citations
- Zhou, Philbin and Li. Multi-Queue Replacement Algorithm for Second Level Buffer Caches. USENIX ATC 2001, section 4 and Figure 5.
- Zhou, Philbin and Li. Multi-Queue Replacement Algorithm. USENIX ATC 2001, section 2.2: traces and cache boundaries.
- Zhou, Philbin and Li. Multi-Queue Replacement Algorithm. USENIX ATC 2001, section 5.1: simulation configuration.
- Zhou, Philbin and Li. Multi-Queue Replacement Algorithm. USENIX ATC 2001, section 6.1: storage-server architecture.
- Linux 6.16 documentation. Multi-Queue Block IO Queueing Mechanism: software staging and hardware dispatch.
- Li, Aboulnaga, Salem, Sachedina and Gao. Second-Tier Cache Management Using Write Hints. FAST 2005, sections 3, 4.1, 4.3 and 5.1.
Sources & caveats
- Source review of the original 2001 paper by Yuanyuan Zhou, James F. Philbin and Kai Li; no trace replay or hardware measurement.
- The storage-server implementation used Oracle 8i with TPC-C, a 128 MB upper cache and write-through storage caching.
- The 2005 hint-aware variant was evaluated by simulation of instrumented DB2 8.2/TPC-C traces, measuring second-tier read hit ratios after cache fill, with history space charged against the memory budget.