Beyond LRU & LFU: Modern Cache Design Strategies for High-Performance Systems

Caching isn’t just an optimization anymore — it’s a foundational requirement for modern distributed systems. In the previous article, we explored LRU and LFU, two of the most widely deployed eviction algorithms in browsers, databases, and in-memory stores.

But real production workloads are rarely simple. A single eviction strategy almost never fits every access pattern. That’s why large-scale systems like Redis, ZFS, PostgreSQL, and CDNs use hybrid, multi-layer, or probabilistic caching strategies.

In this post, we’ll level up from classical interview questions into real-world cache engineering.

Beyond LRU & LFU: Modern Cache Design Strategies

🚀 Why We Need More Than LRU/LFU

While LRU and LFU perform well in controlled conditions, real-world systems face:

• scan pollution (a single large sequential request evicting useful data)
• bimodal popularity (some items stay hot for days, others for seconds)
• adversarial or skewed traffic
• multi-tier memory hierarchies
• distributed eviction pressure

No single policy can handle all of these efficiently.

So engineers started combining ideas — recency + frequency + adaptive feedback.

Let’s explore.

🧠 1. ARC (Adaptive Replacement Cache)

Used in: ZFS, IBM storage systems Strength: Self-tuning balance between recency & frequency Goal: Avoids LRU’s scan problems and LFU’s slow adaptivity

ARC maintains four lists:

T1 = recent entries (seen once)
T2 = frequent entries (seen multiple times)
B1 = ghost entries evicted from T1
B2 = ghost entries evicted from T2

Ghost lists don’t store values — they track “misses” to adapt the recency/frequency ratio.

⭐ Why ARC is powerful

• Quickly adapts between LRU-like or LFU-like behavior
• Ghost lists act as feedback loops
• Prevents scan pollution
• Fully O(1)

When ARC is a great fit:

• File system caching
• Database buffer pools
• Workloads with unpredictable or shifting patterns

✔️ ARC — Simplified TypeScript Example

This is not the full production algorithm — but a clean, conceptual implementation for learning:

class ARC<K, V> {
    private capacity: number;

    private T1: K[] = []; // recent
    private T2: K[] = []; // frequent
    private B1: K[] = []; // ghost recent
    private B2: K[] = []; // ghost frequent

    private store: Map<K, V> = new Map();
    private p: number = 0; // adaptive balance

    constructor(capacity: number) {
        this.capacity = capacity;
    }

    get(key: K): V | undefined {
        if (this.store.has(key)) {
            if (this.T1.includes(key)) {
                this.T1 = this.T1.filter(k => k !== key);
                this.T2.unshift(key);
            }
            return this.store.get(key);
        }
        return undefined;
    }

    put(key: K, value: V) {
        if (this.store.has(key)) {
            this.store.set(key, value);
            this.get(key);
            return;
        }

        if (this.T1.length + this.B1.length === this.capacity) {
            if (this.T1.length < this.capacity) {
                this.B1.pop();
                this.replace(key);
            } else {
                this.T1.pop();
            }
        } else {
            const total = this.T1.length + this.T2.length +
                          this.B1.length + this.B2.length;

            if (total >= this.capacity) {
                if (total === this.capacity * 2) this.B2.pop();
                this.replace(key);
            }
        }

        this.store.set(key, value);
        this.T1.unshift(key);
    }

    private replace(key: K) {
        if (this.T1.length > 0 && (this.B2.includes(key) && this.T1.length === this.p)) {
            const removed = this.T1.pop()!;
            this.B1.unshift(removed);
            this.store.delete(removed);
        } else {
            const removed = this.T2.pop()!;
            this.B2.unshift(removed);
            this.store.delete(removed);
        }
    }
}

🔥 2. CAR (Clock with Adaptive Replacement)

CAR is ARC’s cheaper sibling.

Used in: Kernel memory managers Benefit: ARC’s intelligence + CLOCK’s efficiency

CLOCK avoids pointer-heavy linked lists and improves CPU cache friendliness.

CAR tracks:

• Recent pages
• Frequent pages
• Two clock hands
• Ghost lists for adaptivity

Think of it as:

ARC, but with lower overhead.

🧮 3. Probabilistic Frequency Tracking (Count–Min Sketch)

Very large caches — such as CDNs, streaming services, and search engines — need to track frequency across millions or billions of keys.

Traditional LFU becomes:

• too slow
• too memory-heavy
• too granular

So systems like YouTube, Cloudflare, and Twitter use approximate LFU via Count–Min Sketch.

What it does:

• Tracks frequency with sublinear memory
• Allows fast increments on every request
• Gives estimates, not exact counts

Real-world example:

Cloudflare built a variant called W-TinyLFU, which massively improved their CDN caching performance.

✔️ Count–Min Sketch Example (TypeScript)

class CountMinSketch {
    private width: number;
    private depth: number;
    private table: number[][];

    constructor(width = 2000, depth = 5) {
        this.width = width;
        this.depth = depth;
        this.table = Array.from({ length: depth }, () =>
            Array(width).fill(0)
        );
    }

    private hash(value: string, i: number): number {
        return Math.abs((value + i).split('')
            .reduce((a, c) => a + c.charCodeAt(0), 0)) % this.width;
    }

    add(value: string) {
        for (let i = 0; i < this.depth; i++) {
            const index = this.hash(value, i);
            this.table[i][index]++;
        }
    }

    estimate(value: string): number {
        let min = Infinity;
        for (let i = 0; i < this.depth; i++) {
            const index = this.hash(value, i);
            min = Math.min(min, this.table[i][index]);
        }
        return min;
    }
}

This is the foundation of TinyLFU.

🏎️ 4. Multi-Tier Caching (L1/L2/L3)

Modern architectures often use 2–3 layers of caches:

Example:

• L1 (in-process): microseconds
• L2 (Redis or Memcached): sub-millisecond
• L3 (database): milliseconds

Each tier can use a different policy.

Common pairings:

• L1 = LRU (fast, small)
• L2 = LFU or TinyLFU (larger, needs frequency analysis)

This design keeps hot data in the fastest layer while preventing churn in lower layers.

🔄 5. Cache Admission Policies

Eviction gets a lot of attention, but admission is equally important.

A naive cache inserts everything that’s requested — even items that will be used exactly once.

This causes:

• scan pollution
• buffer churn
• eviction of valuable data

Modern caches use selective admission.

Examples:

• TinyLFU decides whether an item is worthy before inserting it.
• Sampling LRU inserts only if its frequency surpasses a threshold.

🎯 TinyLFU — Modern Admission Control

One of the biggest mistakes of traditional caches:

They admit everything.

TinyLFU fixes this by rejecting items that won’t be reused.

How TinyLFU works

• Every access increments CMS
• Before inserting a new item:
• compare its estimated frequency to the victim’s frequency
• insert only if it’s more valuable

✔️ TinyLFU — Pseudocode Implementation

class TinyLFU {
    private sketch = new CountMinSketch(2048, 4);

    record(key: string) {
        this.sketch.add(key);
    }

    shouldAdmit(candidateKey: string, victimKey: string): boolean {
        const freqCandidate = this.sketch.estimate(candidateKey);
        const freqVictim = this.sketch.estimate(victimKey);
        return freqCandidate > freqVictim;
    }
}

This tiny snippet is the heart of Google’s Caffeine cache — one of the fastest Java caches ever built.

🧱 Segmented LRU (SLRU)

Used in: Twitter, Redis, Caffeine Strength: Combines recency + protection from churn

SLRU separates the cache into two segments:

[Probation]  - items recently inserted
[Protected]  - items proven to be hot

A new item enters probation; if re-accessed, it moves to protected.

✔️ Segmented LRU Example

class SegmentedLRU<T> {
    private probation: T[] = [];
    private protected: T[] = [];
    private capacity: number;

    constructor(capacity: number) {
        this.capacity = capacity;
    }

    access(key: T) {
        if (this.protected.includes(key)) {
            this.protected = this.protected.filter(k => k !== key);
            this.protected.unshift(key);
            return;
        }

        if (this.probation.includes(key)) {
            this.probation = this.probation.filter(k => k !== key);
            this.protected.unshift(key);
            return;
        }

        this.probation.unshift(key);

        if (this.probation.length + this.protected.length > this.capacity) {
            if (this.probation.length > 0) this.probation.pop();
            else this.protected.pop();
        }
    }
}

SLRU is simple but extremely effective.

In fact, the combination of:

TinyLFU (admission) + LRU (eviction) is state-of-the-art and used by systems like Caffeine, the Java caching library that powers Google products.

📦 6. Write Policies: Write-Through vs Write-Back vs Write-Around

A cache isn’t only about reads — writes matter too.

Write-Through

Write to cache and backing store simultaneously. ✔️ Strong consistency ❌ Slower writes

Write-Back

Write only to cache; flush later. ✔️ Faster ❌ Risk of data loss if not persisted

Write-Around

Skip the cache on writes, write directly to storage. ✔️ Avoids polluting cache with write-heavy items ❌ Read-after-write may miss

Systems choose these based on workload.

🧰 7. Real-World Example: Caffeine (Google) Cache

Caffeine is one of the highest-performance production caches ever built.

It uses:

• W-TinyLFU for admission
• Segmented LRU for eviction
• Count–Min Sketch for frequency
• Ring buffers for write counters
• Non-blocking reads with Java intrinsics

This is the modern gold standard for JVM-based systems.

⚙️ Putting It All Together: How To Choose a Cache Policy

[embed]How to Choose the Right Cache Strategy

There is no “one best algorithm.” There is only the best fit for your workload.

🏗️ How Big Companies Engineer Caches

YouTube

• Uses Count–Min Sketch based LFU for video metadata.

Cloudflare

• Uses W-TinyLFU + Count–Min Sketch for global CDN edge caching.

Amazon DynamoDB Accelerator (DAX)

• Uses multi-layer caching with locality-aware eviction.

Google Search

• Uses multi-level segmented LRU variants optimized at CPU-cache granularity.

More Examples:

[embed]Real-World Industry Uses

When the scale gets massive, precision goes down and approximation becomes the secret weapon.

🎯 Closing Thoughts

LRU and LFU are powerful building blocks, but modern systems go far beyond them. If you want to design real-world caching systems, you need to think in terms of:

• admission
• eviction
• frequency tracking
• multi-level hierarchies
• adaptivity
• workload feedback loops

That’s what turns an “interview solution” into production engineering.

Find me on: 📎 GitHub | LinkedIn