W-TinyLFU

Deep dive

How it works

In: key accesses (hit or miss) and inserts · Out: hit or miss; an admit-or-drop decision per candidate · State: window LRU (1 %), probation (20 %) and protected (80 %) segments, a 4-bit Count-Min sketch of about 8 B per entry · Cost: O(1) per access: 4 sketch counters plus list operations.

1. Every access increments the key's counters in the frequency sketch (hit or miss).
2. A new key enters the window LRU.
3. When the window overflows, its LRU victim becomes a candidate for the main space.
4. If the main space is full, its probation segment's LRU entry is the victim. Admit the candidate (evict the victim) iff freq(candidate) > freq(victim); otherwise drop the candidate.
5. A hit in probation promotes the entry to protected; protected overflow demotes its LRU entry back to probation (SLRU).
6. After 10 × capacity sketch increments, halve every counter (aging); the window of history is therefore about 10 × capacity accesses.

         new key                      candidate  ┌── freq(cand) > freq(victim)? ──┐
access ─► [ window LRU 1% ] ─ overflow ─►        │ yes: admit, evict victim       │
                                                 │ no:  drop candidate            │
          [ probation 20% ] ⇄ [ protected 80% ]  └────────────────────────────────┘
               ▲ victim = probation LRU          counts: 4-bit Count-Min sketch, halved every 10·C

Code

The sketch and admission decision (the part that makes it TinyLFU); the three LRU segments are ordinary LRU lists.

/// 4-bit Count-Min sketch: 16 counters per u64, 4 rows, periodic halving (Caffeine-style).
pub struct FrequencySketch {
    table: Vec<u64>,
    mask: usize,
    additions: u32,
    sample_size: u32,
}

const SEEDS: [u64; 4] = [0x97cb3127e8b2c9d1, 0xc3a5c85c97cb3127, 0xb492b66fbe98f273, 0x9ae16a3b2f90404f];

#[inline]
fn mix(mut z: u64) -> u64 {
    z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
    z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
    z ^ (z >> 31)
}

impl FrequencySketch {
    pub fn new(capacity: usize) -> Self {
        let words = capacity.max(16).next_power_of_two(); // ~16 counters per cached entry
        FrequencySketch { table: vec![0; words], mask: words - 1, additions: 0,
                          sample_size: (10 * capacity.max(1)).min(u32::MAX as usize) as u32 }
    }

    #[inline]
    fn slot(&self, key_hash: u64, row: usize) -> (usize, u32) {
        let h = mix(key_hash ^ SEEDS[row]);
        ((h as usize) & self.mask, ((h >> 60) as u32) * 4) // word index, bit offset of 4-bit counter
    }

    pub fn frequency(&self, key_hash: u64) -> u8 {
        (0..4).map(|r| { let (w, s) = self.slot(key_hash, r); ((self.table[w] >> s) & 0xF) as u8 })
              .min().unwrap()
    }

    pub fn increment(&mut self, key_hash: u64) {
        let mut added = false;
        for r in 0..4 {
            let (w, s) = self.slot(key_hash, r);
            if (self.table[w] >> s) & 0xF < 15 { self.table[w] += 1 << s; added = true; }
        }
        if added {
            self.additions += 1;
            if self.additions >= self.sample_size { self.reset(); }
        }
    }

    /// Aging: halve every counter in place (shift, then clear bits that crossed nibbles).
    fn reset(&mut self) {
        for w in self.table.iter_mut() { *w = (*w >> 1) & 0x7777_7777_7777_7777; }
        self.additions /= 2;
    }
}

/// TinyLFU admission. `rand` is a cheap per-thread random number.
pub fn admit(sketch: &FrequencySketch, candidate: u64, victim: u64, rand: u32) -> bool {
    let (c, v) = (sketch.frequency(candidate), sketch.frequency(victim));
    if c > v { return true; }
    // Caffeine: a warm candidate occasionally wins anyway, so an attacker can't pin
    // the victim by inflating its count with colliding keys (hash flooding).
    c >= 6 && rand & 127 == 0
}

fn main() {
    let mut s = FrequencySketch::new(1000);
    for _ in 0..5 { s.increment(42); }
    s.increment(7);
    assert!(admit(&s, 42, 7, 1) && !admit(&s, 7, 42, 1));
    println!("f(42)={} f(7)={}", s.frequency(42), s.frequency(7));
}

Complexity and constants

• Per access: 4 counter updates. Caffeine places a key's 4 counters within one 64-byte block so an access costs about one cache miss.
• Sketch memory: one u64 (16 counters) per cache entry ≈ 8 B/entry, e.g. 8 MB for a 1M-entry cache. A doorkeeper Bloom filter can cut it further.
• Counter cap 15 is enough: admission compares relative popularity within a 10 × capacity sample, and halving keeps counts small.
• Hit ratio: on the traces in the TinyLFU paper and Caffeine's simulator, W-TinyLFU matches or beats ARC and LIRS and is often close to Bélády's optimum.

Efficiency

• Cost: Each access updates 4 counters; Caffeine places a key's 4 counters in one 64-byte block, so an access costs about one cache miss. The sketch is about 8 B per entry (8 MB for 1M entries). The bound is cache misses on the sketch and the lock on the LRU lists, which read buffers keep off the hit path.
• Levers:
  • Lossy striped read buffer, batched replay under a try-lock — hits take no lock (Caffeine) — many threads.
  • 4 counters in one 64-byte block — about 1 cache miss per access — large caches.
  • 4-bit counters with halving — about 8 B per entry — memory-tight caches.
  • Doorkeeper Bloom filter — first occurrences never reach the sketch (TinyLFU paper) — heavy one-hit-wonder traffic.
  • Hill-climbing window size — adapts between recency and frequency (Einziger et al. 2018) — shifting workloads.
• Naive → standard → state of the art:
  • Plain LRU · no admission, scan- and one-hit-wonder-sensitive.
  • TinyLFU admission in front of LRU (or ARC / LIRS) · better hit ratio, weak on bursty traces.
  • W-TinyLFU with adaptive window (Caffeine, moka) · near-optimal hit ratio on the traces in the papers, about 1 miss per access.

Implementation notes

• Hash keys once (64-bit, well mixed) and derive the 4 indices from it; reuse the hash for the map.
• Make reads cheap: record hits in a lossy striped ring buffer and apply sketch + LRU updates in batches under a try-lock (Caffeine's read buffer); writes go through a bounded write buffer.
• Window size: 1 % is a good default; recency-heavy workloads want a larger window (Caffeine's hill climber moves it in steps and keeps the best).
• Doorkeeper: a Bloom filter absorbs first occurrences; only repeat keys reach the sketch; frequency = sketch + doorkeeper bit. Clear it on reset.
• Weighted entries: charge by size and admit only if the candidate's frequency beats the combined victims it would displace.

Pitfalls

• Hash flooding: an attacker raising a victim's estimated frequency via collisions keeps everything else out; hence the random admission above.
• Forgetting to count misses in the sketch: frequency of non-resident keys is the whole point.
• No aging: the cache freezes on yesterday's popular keys.
• Sketch too small (counters saturate at 15 everywhere): admission becomes a coin flip; size it from the max entry count.

Variants and alternatives

In production

Caffeine (Java; the default cache behind Spring's Caffeine cache and many JVM services, used in Apache Cassandra), moka (Rust), Ristretto (Go, Dgraph), Cloudflare Pingora's TinyUFO (TinyLFU admission + S3-FIFO-style queues).

Implementations

Sources

• Gil Einziger, Roy Friedman, Ben Manes, TinyLFU: A Highly Efficient Cache Admission Policy, ACM Transactions on Storage 2017. paper · arXiv
• Gil Einziger, Ohad Eytan, Roy Friedman, Ben Manes, Adaptive Software Cache Management, Middleware 2018. paper
• Graham Cormode, S. Muthukrishnan, An Improved Data Stream Summary: The Count-Min Sketch and its Applications, J. Algorithms 2005. paper
• Ben Manes, Caffeine, Java caching library and its simulator. code · efficiency