LRU and CLOCK

Deep dive

How it works

In: key lookups and inserts · Out: hit or miss; the evicted entry on a full insert · State: hash map plus recency order (LRU: doubly linked list; CLOCK: ring with a reference bit per slot and a hand) · Cost: O(1) per operation; an LRU hit relinks a node, a CLOCK hit sets one bit.

LRU

1. get(k): look up node; unlink and push to the front; return value.
2. put(k, v): if present, update + move to front; else if full, evict the tail; insert at the front.

CLOCK (second chance)

1. Slots in a ring; each has a referenced bit.
2. get(k): set the bit.
3. On miss with a full cache: look at the slot under the hand. Bit set → clear it and advance. Bit clear → evict, put the new entry there, advance.
4. GCLOCK / usage counts: a small counter instead of a bit (increment on hit up to a cap, decrement on sweep) approximates frequency too.

LRU:   head ⇄ [k7] ⇄ [k2] ⇄ [k9] ⇄ [k4] ⇄ tail      hit k9 → move to head
CLOCK:      [k1:1] [k2:0] [k3:1] [k4:1]             miss: hand clears k1,
               ▲hand                                 evicts k2

Code

use std::collections::HashMap;
use std::hash::Hash;

const NIL: usize = usize::MAX;
struct Node<K, V> { key: K, val: V, prev: usize, next: usize }

/// LRU with an index-linked list in a Vec: no unsafe, no per-node allocation.
pub struct Lru<K, V> { map: HashMap<K, usize>, nodes: Vec<Node<K, V>>, head: usize, tail: usize, cap: usize }

impl<K: Hash + Eq + Clone, V> Lru<K, V> {
    pub fn new(cap: usize) -> Self {
        assert!(cap > 0);
        Lru { map: HashMap::with_capacity(cap), nodes: Vec::with_capacity(cap), head: NIL, tail: NIL, cap }
    }
    fn unlink(&mut self, i: usize) {
        let (p, n) = (self.nodes[i].prev, self.nodes[i].next);
        if p != NIL { self.nodes[p].next = n } else { self.head = n }
        if n != NIL { self.nodes[n].prev = p } else { self.tail = p }
    }
    fn push_front(&mut self, i: usize) {
        self.nodes[i].prev = NIL;
        self.nodes[i].next = self.head;
        if self.head != NIL { self.nodes[self.head].prev = i } else { self.tail = i }
        self.head = i;
    }
    pub fn get(&mut self, k: &K) -> Option<&V> {
        let i = *self.map.get(k)?;
        if i != self.head { self.unlink(i); self.push_front(i); }
        Some(&self.nodes[i].val)
    }
    /// Returns the evicted entry, if any.
    pub fn put(&mut self, k: K, v: V) -> Option<(K, V)> {
        if let Some(&i) = self.map.get(&k) {
            self.nodes[i].val = v;
            if i != self.head { self.unlink(i); self.push_front(i); }
            return None;
        }
        let fresh = Node { key: k.clone(), val: v, prev: NIL, next: NIL };
        if self.nodes.len() < self.cap {
            self.nodes.push(fresh);
            let i = self.nodes.len() - 1;
            self.map.insert(k, i);
            self.push_front(i);
            return None;
        }
        let i = self.tail;                                   // reuse the victim's slot
        self.unlink(i);
        let old = std::mem::replace(&mut self.nodes[i], fresh);
        self.map.remove(&old.key);
        self.map.insert(k, i);
        self.push_front(i);
        Some((old.key, old.val))
    }
}

/// CLOCK: hits only set a bit; the hand does the work on misses.
pub struct Clock<K, V> { map: HashMap<K, usize>, slots: Vec<(K, V, bool)>, hand: usize, cap: usize }

impl<K: Hash + Eq + Clone, V> Clock<K, V> {
    pub fn new(cap: usize) -> Self {
        assert!(cap > 0);
        Clock { map: HashMap::with_capacity(cap), slots: Vec::with_capacity(cap), hand: 0, cap }
    }
    pub fn get(&mut self, k: &K) -> Option<&V> {
        let i = *self.map.get(k)?;
        self.slots[i].2 = true;          // in a concurrent cache: AtomicBool::store(Relaxed)
        Some(&self.slots[i].1)
    }
    pub fn put(&mut self, k: K, v: V) -> Option<(K, V)> {
        if let Some(&i) = self.map.get(&k) { self.slots[i].1 = v; self.slots[i].2 = true; return None; }
        if self.slots.len() < self.cap {
            self.map.insert(k.clone(), self.slots.len());
            self.slots.push((k, v, false));
            return None;
        }
        loop {                           // at most one full lap clears all bits
            let i = self.hand;
            self.hand = (self.hand + 1) % self.cap;
            if self.slots[i].2 { self.slots[i].2 = false; continue; }
            let (ok, ov, _) = std::mem::replace(&mut self.slots[i], (k.clone(), v, false));
            self.map.remove(&ok);
            self.map.insert(k, i);
            return Some((ok, ov));
        }
    }
}

Complexity and constants

• LRU: O(1) get/put; a hit touches the node, its two neighbours and the head: up to 4 cache lines written. Under a global mutex, throughput tops out around a few million ops/s regardless of cores.
• CLOCK: hit = 1 store to an already-loaded line; eviction amortized O(1), worst case one lap over all entries when every bit is set.
• Memory: LRU above ≈ key + value + 16 B links + map entry (~ 1.1-1.5× key+value+8 B with SwissTable); CLOCK saves the links (1 bit or byte per slot).
• Miss ratio: CLOCK is typically within a few percent of LRU on the same trace.

Efficiency

• Cost: An LRU hit writes up to 4 cache lines (node, two neighbours, head) under a lock; with a global mutex throughput stays at a few million ops/s whatever the core count (order of). A CLOCK hit is one store to a line already loaded. LRU adds 16 B of links per item, CLOCK 1 bit or byte. The bound is lock and cache-line contention, not compute.
• Levers:
  • Reference bit instead of a list move — 4 line writes → 1 store, no lock — read-heavy page caches.
  • Shard by key hash — N independent locks — in-process caches.
  • Buffer hits per thread and replay under a try-lock (Caffeine) — hits leave the critical path — highly concurrent caches.
  • Sampled LRU (Redis, 5 samples by default) — no list at all — very large key counts.
• Naive → standard → state of the art:
  • One global-mutex LRU list · a few million ops/s total.
  • Sharded LRU, or hit buffers with batched replay · scales with shards, hits still write shared lists.
  • CLOCK with usage counts (PostgreSQL), or scan-resistant W-TinyLFU / S3-FIFO · lock-free hits, miss ratio within a few percent of LRU or better.

Implementation notes

• Concurrent LRU options: shard by key hash (N independent LRUs, like Guava's segmented cache), buffer hits in per-thread queues and replay under a try-lock (Caffeine), or bump at most once per interval (memcached: 60 s).
• Sampled LRU (Redis allkeys-lru): store a last-access timestamp per key, sample 5 random keys (maxmemory-samples), evict the oldest; no list at all.
• Segmented LRU (SLRU): probation + protected segments; a second hit promotes. Cheap scan resistance; used by memcached (hot/warm/cold) and as the main space of W-TinyLFU.
• CLOCK with usage counts: PostgreSQL increments to BM_MAX_USAGE_COUNT = 5; the sweep decrements and evicts at 0, so frequently used pages survive several laps.
• Use index-based lists (as above) or an intrusive list in a slab to avoid one heap allocation per node.

Pitfalls

• Sequential scans or a large batch job flushing the whole cache; detect scans or use a scan-resistant policy.
• A global LRU lock on a 32-core box: throughput collapses under hits, not misses.
• CLOCK with every bit set: one miss walks the entire ring (latency spike); GCLOCK caps limit how long this takes.
• Evicting by count when items vary in size: charge by bytes (weight) and evict until under budget.

Variants and alternatives

In production

Linux page cache (active/inactive lists, MGLRU), PostgreSQL shared buffers (CLOCK sweep with usage counts), memcached (segmented LRU), Redis (sampled approximate LRU/LFU), InnoDB buffer pool (LRU with a midpoint insertion "old" sublist).

Implementations

Sources

• Fernando J. Corbató, A Paging Experiment with the Multics System, MIT Project MAC report, 1968.
• Song Jiang, Feng Chen, Xiaodong Zhang, CLOCK-Pro: An Effective Improvement of the CLOCK Replacement, USENIX ATC 2005. paper
• Nimrod Megiddo, Dharmendra S. Modha, ARC: A Self-Tuning, Low Overhead Replacement Cache, FAST 2003. paper
• Elizabeth J. O'Neil, Patrick E. O'Neil, Gerhard Weikum, The LRU-K Page Replacement Algorithm for Database Disk Buffering, SIGMOD 1993. paper
• Theodore Johnson, Dennis Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, VLDB 1994. paper