LIRS — Low Inter-reference Recency Set — Cache Eviction

Overview

What this concept solves

LIRS — Low Inter-reference Recency Set — was proposed by Song Jiang and Xiaodong Zhang in 2002 as a stronger answer to LRU's scan problem. Instead of measuring how recently a key was touched, it measures the gap between consecutive touches. Keys with small gaps are 'hot' (LIR); keys with large gaps are 'cold' (HIR). Only hot keys are protected from eviction.

It is widely considered the highest-hit-rate non-ML eviction policy in the literature. MySQL adopted a LIRS-inspired layout for some of its buffer pools, and Apache Cassandra and Apache Impala use LIRS or close variants. It's more complex than 2Q but consistently wins on workloads with weak locality.

Mechanics

How it works

The key insight: inter-reference recency (IRR)

When you access a key, look back to its previous access. The number of distinct other keys accessed in between is its IRR. Small IRR means 'used often within a short window' — hot. Large IRR means 'long gaps between uses' — cold.

LIR — keys with low IRR. The genuine working set. Always cached.
HIR — keys with high IRR. Two flavors: resident HIR (cached, but on the chopping block) and non-resident HIR (only the key is remembered, like a ghost).

Two data structures hold this state:

Stack S — an LRU-ordered list containing all LIR keys plus some HIR keys (resident and non-resident). Used to determine when an HIR key should be promoted to LIR.
Queue Q — a FIFO of just the resident HIR keys. Used to pick the next eviction victim cheaply.

The algorithm on access:

Hit on a LIR key — move to the top of S. (Standard LRU touch.)
Hit on a resident HIR key in S — promote to LIR (you've now seen it within a short window). Move the bottom LIR key to HIR to make room.
Hit on a non-resident HIR key in S — same as above: it just earned LIR status. Evict the head of Q to load it.
Miss on a key not in S — load as resident HIR, push onto Q. Evict the head of Q if Q is full.

LIR keys get unbounded protection — by design

Once a key is in LIR, only another key with even smaller IRR can dislodge it. That's why LIRS is so robust against scans: a one-shot scan key has near-infinite IRR (it never gets accessed again), so it stays HIR and falls off Q quickly.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › LIRS — Low Inter-reference Recency Set

About this simulation

Two structures: the S stack (left) holds recent access history with each key tagged LIR (always cached, blue), HIR-r (cached but probationary, amber), or ghost (key remembered, data evicted, dashed). The Q list (right) holds only the resident HIR — the next victim on a miss. LIR slots: 3, HIR-resident slot: 1.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Fill the LIR tier

Click A, B, C. Each enters S tagged LIR (blue) — that's the protected working set, three slots strong. Now click D — it enters as HIR-resident (amber) and shows up in Q. The chopping block.

try 02

Promote with a short re-access

After step 1, click D again. The status line says 'promote to LIR' — D's inter-reference gap was small, so it earns LIR status. The previously-bottom LIR is demoted to HIR-resident in its place.

try 03

Scan without polluting LIR

Click Reset, then A, B, C (LIR set established). Now scan: D, E, F. They each enter as HIR-r, churn through Q, and never reach LIR — their IRRs are too large. A, B, C are untouched. That's LIRS's scan resistance.

In practice

When to use it — and what you give up

When to reach for it

Weak-locality workloads — DB buffer pools mixing OLTP with analytics, large-key-space caches where LRU consistently underperforms.
You've outgrown 2Q — LIRS gives the next jump in hit rate at the cost of more complex state.
Long-running caches where the IRR signal has time to stabilize.

Real-world example

MySQL adopted a LIRS-inspired layout for InnoDB's adaptive hash index; Apache Cassandra uses LIRS for its row cache. Academic surveys consistently rank LIRS at or near the top of non-ML eviction policies on standard benchmark traces.

Pros

Excellent hit rate, especially on workloads where LRU does badly (scans, mixed locality).
Strong scan resistance — scan keys never accumulate the low IRR needed to enter LIR.
Self-tuning in spirit — LIR/HIR membership is determined by the workload, not by a tunable parameter.

Cons

Considerably more complex than LRU or 2Q. Real implementations are tricky to get right.
Higher memory overhead — the stack S can grow to hold non-resident HIR keys, which costs metadata.
Eviction logic involves pruning the bottom of S; subtle bugs around 'stack pruning' have plagued real implementations.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

lirs.ts

// Sketch only — full LIRS needs careful stack pruning.
// LIR keys + some HIR keys live in stack S (LRU order).
// Resident HIR keys also live in queue Q (FIFO).
type Status = "LIR" | "RESIDENT_HIR" | "NON_RESIDENT_HIR";

class LIRS<K, V> {
  private values = new Map<K, V>();          // only resident
  private status = new Map<K, Status>();
  private s: K[] = [];                        // LRU-ordered stack (head = MRU)
  private q: K[] = [];                        // FIFO of resident HIRs
  constructor(private lirCap: number, private hirCap: number) {}

  get(key: K): V | undefined {
    if (!this.values.has(key)) return undefined;
    const st = this.status.get(key);
    if (st === "LIR") {
      this.bumpInStack(key);
    } else if (st === "RESIDENT_HIR") {
      if (this.s.includes(key)) {
        // Promote: HIR -> LIR; demote bottom LIR -> HIR
        this.promoteToLIR(key);
      } else {
        this.bumpInStack(key);
      }
    }
    return this.values.get(key);
  }

  set(key: K, value: V): void {
    // ... see paper for full insert + stack pruning rules
    this.values.set(key, value);
  }

  private bumpInStack(_: K) { /* move key to top of s */ }
  private promoteToLIR(_: K) { /* LIR/HIR boundary management */ }
}

References & further reading

3 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

What does 'inter-reference recency' (IRR) measure for a given key?

question 02 / 03

Why is LIRS especially robust against scan workloads?

question 03 / 03

What is the role of the queue Q in LIRS?

0/3 answered