LRU, LFU, and TinyLFU

The worst production debugging session I ever had started with a single alert: "Cache hit rate dropped from 95% to 40%." Our Redis cluster was thrashing—evicting keys as fast as we could insert them. The root cause? A misconfigured analytics job was scanning millions of keys that would never be accessed again. LRU eviction, in its infinite wisdom, decided that since those scanned keys were "recently used," they were worth keeping. Our hot data got evicted.

Cache eviction seems simple—when the cache is full, remove something. But the choice of what to remove has a massive impact on hit rate, latency, and infrastructure cost. This tutorial explores the evolution of eviction algorithms from simple LRU to the sophisticated TinyLFU used in Caffeine, the most performant Java cache today.

The Caching Problem

A cache is a fast, finite storage layer that sits in front of a slow, infinite storage layer. When the cache is full and a new item arrives, something must be evicted. The goal is to evict the item least likely to be accessed in the future.

This is inherently a prediction problem. We don't know the future, so we approximate it using past access patterns:

The Optimal Algorithm: Belady's Algorithm

In 1966, Laszlo Belady proved that the optimal eviction strategy is to evict the item that will be used farthest in the future. This is called Belady's MIN algorithm. It's impossible to implement in practice because it requires knowledge of future accesses, but it serves as a theoretical upper bound for hit rate.

Every practical eviction algorithm is an approximation of Belady's algorithm, using past behavior as a proxy for future behavior.

LRU: Least Recently Used

LRU is the most widely used eviction algorithm. It's simple, performs well for many workloads, and has an efficient O(1) implementation.

How LRU Works

The classic implementation uses a doubly-linked list with a hash map:

Operations:

The hash map provides O(1) lookup by key. The linked list maintains access order: most recently accessed at the head, least recently accessed at the tail.

Why LRU Works (and When It Doesn't)

LRU works well when access patterns have temporal locality—items accessed recently are likely to be accessed again soon. This is true for most real-world workloads:

• User sessions: a user who just logged in will make more requests
• API responses: a recently fetched resource is likely to be fetched again
• Database query results: recent queries are often repeated

The scanning problem:

When a workload sequentially accesses many unique keys (a "scan"), LRU performs terribly. Each new key becomes the "most recently used," pushing out truly hot data. After the scan completes, the cache is filled with cold data.

LRU-K: Resisting Scans

LRU-K improves on LRU by tracking the K most recent access times for each item, not just the single most recent. An item is only considered "recently used" after being accessed K times.

The problem with LRU-K: it requires maintaining a priority queue, and tracking historical access times adds memory overhead per entry. In practice, LRU-2 is often "good enough" for most scanning-resistant workloads.

LRU-2 insight: Items accessed once (scans) stay in the first queue and get evicted quickly. Items accessed twice (potentially popular) move to the LRU queue where they compete fairly.

LFU: Least Frequently Used

LFU evicts the item with the lowest access frequency. The intuition: if you access an item once and never again, its frequency stays at 1 and it gets evicted first when the cache fills.

How LFU Works

Each cache entry maintains a frequency counter. When the cache is full, the entry with the lowest counter is evicted. If multiple entries have the same frequency, LRU among them (or FIFO).

LFU Weaknesses

Temporal burst unfriendliness:

Consider a news article that goes viral. In the first minute, it gets 10,000 accesses. But the topic is so niche that it never gets accessed again. Meanwhile, a database index that's accessed once every 5 minutes has accumulated a low but steady count over hours. LFU keeps the database index (higher total count) and evicts the breaking news (lower total count but high recent burst).

Frequency inertia (the "old hot" problem):

An item that was extremely popular yesterday (millions of accesses) has such a high frequency count that it takes hours or days for new popular items to overtake it. The cache is slow to adapt to workload changes.

Imagine a Black Friday sale page that had 1M hits on Friday. By Saturday, users are looking at regular product pages. The sale page's frequency counter is so high that it stays in cache for days, evicting Saturday's actually-hot items.

Memory Overhead for Counters

Using smaller counters limits the maximum frequency you can track, but also wastes space on items with low counts (most of them). The Pareto principle applies: 80% of items have very low frequencies.

Window-TinyLFU (Caffeine)

Caffeine is a high-performance Java caching library that uses the Window-TinyLFU eviction policy. It's the default cache implementation in Spring Boot and achieves hit rates within 1-2% of the theoretical optimal (Belady's MIN) for most workloads.

Caffeine's real innovation is not the eviction algorithm alone—it's how it combines three distinct mechanisms:

1. Admission policy: Should this new item be admitted to the cache at all?
2. Eviction policy: Which item should be removed when the cache is full?
3. Frequency estimation: How do we track access frequency with minimal memory?

The Three-Segment Architecture

The three segments work together:

How Admission Works

When a new item arrives and the cache is full, Caffeine doesn't automatically admit it. Instead, it asks TinyLFU:

1. TinyLFU estimates the frequency of the new item
2. TinyLFU estimates the frequency of the victim (the item about to be evicted)
3. If the new item's frequency is higher, admit it (evict the victim)
4. If not, reject the new item (keep the cache unchanged)

This admission policy is the key insight. Most caches blindly accept new items and evict old ones. Caffeine rejects new items that are unlikely to be accessed again, preventing cache pollution.

TinyLFU Frequency Estimation

TinyLFU uses a Count-Min Sketch, a probabilistic data structure that estimates event frequencies with bounded error using minimal memory.

Count-Min Sketch
================
Structure: d rows of w counters each
Hash functions: h1, h2, ..., hd (one per row)

Increment(key):
  for each row i:
    counter[i][hi(key)] += 1

Estimate(key):
  return min over all rows of counter[i][hi(key)]

The sketch has 4 rows of 4096 4-bit counters. Each counter saturates at 15 (4 bits), which limits the influence of ancient hot items. Four hash functions map each key to one counter per row, and the estimate is the minimum across all rows (this minimizes overcounts from hash collisions).

The Reset Mechanism

TinyLFU doesn't let counters grow forever. It uses an adaptive reset:

1. After N accesses (the "window"), the sketch is halved: all counters are divided by 2
2. This exponentially decays the influence of past access patterns
3. The window size adapts based on workload: shorter windows for bursty workloads, longer for stable ones

This solves LFU's "frequency inertia" problem. Old hot items have their frequency halved every window, allowing the cache to adapt to changes in popularity.

The Victim Duel

When probation is full and a new item arrives from the window, Caffeine stages a "duel" between the new item and the probation victim:

The duel ensures that every entry in the cache has "earned" its place by having a frequency at least as high as the item it displaced.

Comparison: LRU vs LFU vs ARC vs TinyLFU

ARC: Adaptive Replacement Cache

ARC deserves mention as a precursor to TinyLFU. It maintains two lists: recent items (recency) and frequent items (frequency). It dynamically adjusts the balance between the two based on access patterns using a "ghost" entry feedback mechanism.

Ghost entries don't store values—just keys. A hit on a ghost entry signals that the adaptive balance is wrong. ARC adjusts its target sizes based on these signals.

ARC achieves excellent hit rates but at the cost of ghost entry memory and implementation complexity.

Real-World Implementations

Redis LFU Mode

Redis 4.0 introduced LFU as an optional eviction policy. It uses a Morris counter (logarithmic counter) instead of a linear one, which uses only a few bits to track frequencies spanning orders of magnitude.

Redis LFU Counter:
- 16 bits total (in the existing 24-bit LRU field)
- 8-bit logarithmic counter (max frequency ~200)
- 8-bit log decrement (aging factor / 2)

The counter increases logarithmically:
  p = 1 / (counter * logarithm_factor + 1)
  if rand(0,1) < p: counter += 1

At high counters, increment probability decreases exponentially.

This means a frequently accessed item's counter grows quickly at first, then slows. Old items decay based on the log decrement field, enabling workload adaptation.

S3-FIFO: Simple Yet Effective

In 2023, researchers from Carnegie Mellon and Google published S3-FIFO (Scan-Resistant Segmented FIFO), a remarkably simple eviction algorithm that achieves hit rates comparable to TinyLFU with far less complexity.

S3-FIFO uses three FIFO queues instead of LRU lists:

The key insight: S3-FIFO achieves scan resistance by separating new, unproven items into a small FIFO queue. Items that survive this queue (by being re-accessed) are promoted. Items that never get re-accessed are quickly evicted.

S3-FIFO admission flow:

1. New item K inserted into Small FIFO queue
2. If K is accessed while in Small queue:
   - Move K to Main FIFO queue
   - Mark K as "accessed" (one bit)
3. If K is evicted from Small queue without re-access:
   - Insert K's key into Ghost queue
   - Ghost tracks keys of items evicted from Small
4. When cache is full and new item arrives:
   - If item is found in Ghost: admit it (was popular)
   - If not in Ghost: reject it (likely a scan)
5. Items in Main queue get a second chance on first eviction attempt
   (re-insert at head of Main queue if accessed bit is set)

Compared to Window-TinyLFU, S3-FIFO uses no frequency sketch, no probabilistic counters, and no hashing. Just three FIFO queues and one "accessed" bit per entry. Despite this simplicity, it achieves hit rates within 1-3% of Caffeine on standard benchmarks.

Choosing the Right Eviction Policy

Practical Tuning Guidelines

Key Takeaways

• LRU is simple and effective for recency-biased workloads but suffers from scanning pollution where one-time large scans evict hot data
• LRU-2 and LRU-K improve scan resistance by requiring multiple accesses before considering an item "recent"
• LFU tracks access frequency but suffers from frequency inertia—old hot items resist eviction long after they've cooled
• Cumulative frequency accumulates linearly with cache size, making exact LFU expensive for large caches
• TinyLFU uses a Count-Min Sketch for approximate frequency estimation with minimal memory (99%+ accuracy at ~64KB for millions of items)
• Window-TinyLFU's admission policy (rejecting low-frequency new items) is the key innovation—it prevents cache pollution at the entry point
• Caffeine's three-segment architecture (Window, Probation, Protected) handles both bursts and stable popularity
• The adaptive reset mechanism halves all counters periodically, solving LFU's frequency inertia problem
• For most workloads, TinyLFU achieves hit rates within 1-2% of theoretical optimal (Belady's algorithm)
• Measure your working set size before tuning eviction—the right policy can't fix a cache that's too small

In the next tutorial, we will explore distributed ID generation with Twitter's Snowflake algorithm and understand how time-ordered unique IDs are generated across thousands of nodes without coordination.