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.
🚀 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 T2Ghost 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.
Get Kavindu Kokila (Kavi Castelo)’s stories in your inbox
Join Medium for free to get updates from this writer.
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 hotA 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
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:
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.
