Day 41: Cache Replacement Algorithms – Beyond LRU

Hands-On Distributed Systems Engineering in Java ~10 min read 60 min hands-on

Alright, team. Settle in. Today, we're diving deep into a topic that separates the good engineers from the truly exceptional ones: cache replacement algorithms. You've likely heard of LRU (Least Recently Used), it's the workhorse, the default choice for many. But in the hyperscale world, where every millisecond and every cache miss can translate into millions of dollars or a cascading system meltdown, "good enough" isn't enough. We need to go beyond.

The Unseen Cost of a Cache Miss

Before we even talk algorithms, let's hammer this home: a cache miss is not just a missed opportunity; it's a liability. In a system handling 100 million requests per second, even a 1% increase in cache miss ratio means an additional 1 million requests hitting your backend services or database every second. That's a massive, sudden load spike that can:

  1. Increase Latency: More work, more network hops, slower response times for end-users.

  2. Overload Backend Services: Databases, microservices, and external APIs aren't designed for sustained, high-volume direct access; they rely on caching to buffer the load.

  3. Drive Up Costs: More backend processing means more CPU, memory, and network egress, directly impacting your cloud bill.

  4. Trigger Cascading Failures: An overloaded backend can become unresponsive, leading to timeouts, retries, and a domino effect across your entire system.

This is why the choice of how your cache decides what to keep and what to throw away is a critical system design decision, not just an implementation detail.

Why LRU Falls Short at Hyperscale

LRU is simple: evict the item that hasn't been accessed for the longest time. It works great for many general-purpose workloads where recency of access is a good predictor of future access. Think about a user's recent browsing history – the items they just looked at are most likely to be viewed again soon.

However, LRU struggles with:

  • Scan Resistance: If your cache is scanned (e.g., a daily report generation touches every item once), LRU will evict all your frequently accessed items, replacing them with items that will likely never be accessed again.

  • Highly Skewed Access Patterns: Imagine a few "hot" items accessed millions of times, and many "cold" items accessed a few times, interspersed. LRU might evict a moderately popular item just because a temporary "burst" of less popular items pushed it out.

  • Periodic Accesses: An item accessed every hour might be evicted by LRU if enough unique items are accessed in between its hourly access windows.

Beyond Recency: Introducing LFU (Least Frequently Used)

This is where algorithms like LFU (Least Frequently Used) shine. Instead of only tracking when an item was last accessed, LFU tracks how many times an item has been accessed. When the cache needs to make space, it evicts the item with the lowest access count.

Core Concept: LFU is excellent for workloads where some items are consistently more popular than others, regardless of their recent access time. It's "scan resistant" because a single scan won't drastically increase the frequency count of an item enough to make it appear "hot."

Architecture Fit: A custom LFU cache can sit as a local in-memory cache within a Java microservice, reducing direct calls to a distributed cache or a database. For distributed caches (like Redis or Memcached), you'd typically use their native eviction policies, but understanding LFU helps you reason about why you might choose a specific distributed cache's policy or even implement a client-side LFU layer for critical path data.

Control Flow & Data Flow:

Keep going with the full lesson

The rest of this lesson — plus its implementation guide, runnable scripts and source code — is included with the course or an All Access plan. Create a free account to start the free lessons in every course.

Already a member? Sign in