Cache Eviction Policies Compared: LRU, LFU, ARC, and W-TinyLFU

Last Black Friday we watched our Chicago edge cluster's hit ratio fall from 96% to 71% in about forty minutes, even though the SSD cache wasn't full and origins were healthy. The culprit wasn't capacity or traffic volume — it was a single product video that went viral and started churning millions of one-hit image variants through our LRU cache. I've seen this pattern repeat for a decade: teams throw more memory at the problem when they should be rethinking their eviction policy. How you decide what to throw away matters more than how much you can store.

Why Eviction Policy Beats Raw Cache Size

When I started working on CDN caching back in 2014, the standard advice was simple: if your hit ratio is low, add RAM. We did exactly that on a video delivery fleet and doubled our per-node cache from 128GB to 256GB, and our byte hit ratio barely moved — maybe 1.5%. The working set for that property was huge and highly skewed, with a long tail of cold objects that would never be requested again. Without a smarter Cache Coherence Protocols at the CDN Edge: Keeping Distributed Caches in Sync strategy in place, we were just keeping garbage around longer instead of keeping the right objects.

Every cache eviction decision is a bet about the future. You're predicting which objects won't be needed again soon, based only on past history. That bet shows up directly in your origin offload and your p95 time-to-first-byte. A poor eviction policy doesn't just cost you a few extra origin fetches; it creates latency spikes, increases transit bills, and during peak events it can cascade into origin overload. I've learned to look at eviction policy as a performance control plane, not just a memory management detail. The HTTP Working Group Specifications define how freshness and validation work, but they don't tell you what to evict when you're under pressure — that's entirely your policy's job.

At its core, LRU — Least Recently Used — is beautifully simple, which is why nearly every cache supports it. You maintain an ordered list where each hit moves an object to the head, and you evict from the tail. It assumes recency predicts future popularity, which is often true for web traffic. Implementation-wise, it's an O(1) hash map plus a doubly linked list. If you've ever hand-rolled one for an edge worker or a custom nginx module, you've written something like this:

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: str):
        if key not in self.cache:
            return -1
        # Move to head on hit - marks as recently used
        self.cache.move_to_end(key, last=False)
        return self.cache[key]

    def put(self, key: str, value: bytes):
        if key in self.cache:
            self.cache.move_to_end(key, last=False)
        self.cache[key] = value
        self.cache.move_to_end(key, last=False)
        if len(self.cache) > self.capacity:
            # Evict least recently used (tail)
            self.cache.popitem(last=True)

LRU vs LFU: When Recency and Frequency Fight Each Other

I learned LFU's weakness the hard way on a news site during the 2018 World Cup. We'd switched that tier to LFU — Least Frequently Used — to protect hot objects, and it worked great for the first week. Then a semi-final match ended, and the cache was still full of highlight clips from three days prior that had racked up huge hit counts. They weren't popular anymore, but their frequency counters were so high that fresh, actually-hot content kept getting evicted. We call it cache pollution, and LFU is notorious for it when popularity shifts. The eviction policy had perfectly memorized the past and completely missed the present.

Here's the trade-off in practice. LRU is scan-resistant in the wrong direction: it gets polluted by one-hit wonders and sequential scans. If a crawler walks your entire catalog once, LRU will dutifully move every one of those cold objects to the head and push your genuinely hot assets out. I've seen a single bot scanning 2M old image derivatives evict 30% of a hot working set in minutes. LFU solves that — cold scans never build up enough frequency to survive — but it can't forget. Once an object earns a high count, it sticks around forever, even if nobody wants it now. Your web.dev Articles guidance on cache headers won't save you here; this is about what happens after an object is already stored.

For CDN workloads specifically, you don't get a clean Zipf distribution. You get a mix: a tiny hot set that lives for hours, a churny mid-tier that lives for minutes, and a massive tail that is requested exactly once. Neither pure recency nor pure frequency handles all three well. LFU also needs per-object counters, which adds memory overhead you can't ignore at 100M+ objects. And Both policies struggle with size-aware decisions — evicting a 4KB thumbnail to make room for a 4MB video chunk isn't always the right call for byte hit ratio. That's why we started looking at adaptive approaches, and why for many teams a smarter warming layer matters too, as described in Machine Learning for Cache Warming: Predictive Prefetching That Actually Works.

// LFU with aging to avoid pollution - simplified TinyLFU-style
struct LFUEntry {
    bytes value;
    int freq;
    long lastAccess;
}

int estimateFreq(String key) {
    // Count-Min Sketch with periodic halving (aging)
    // avoids unbounded growth of old hot keys
    return sketch.estimate(key);
}

bool shouldAdmit(String newKey, String victimKey) {
    int newFreq = estimateFreq(newKey);
    int victimFreq = estimateFreq(victimKey);
    // Don't admit if victim has higher frequency
    // This is the admission filter that stops scans
    return newFreq > victimFreq;
}

// Periodically decay all counters: every N requests, halve counts
void ageCounters() {
    if (requestCount % SAMPLE_SIZE == 0) {
        sketch.halveAllCounters();
    }
}

ARC and W-TinyLFU: Policies That Actually Adapt to Traffic

ARC — Adaptive Replacement Cache — was the first policy that made me feel like the cache was thinking. IBM designed it to balance recency and frequency without tuning knobs. It maintains two real lists (T1 for recent, T2 for frequent) and two ghost lists (B1, B2) that remember what you've evicted. If you evict something from T1 and immediately miss on it, ARC knows it should have kept more recent items and grows T1. If the miss comes from B2, it grows T2 instead. It adapts its own target size on every miss. I deployed ARC on a mid-tier shield cache in 2019 and watched it automatically shift from LRU-like behavior during flash crowds to LFU-like behavior overnight when traffic stabilized — no config change needed.

W-TinyLFU is what most of us are moving to now, and for good reason. It was built for high-throughput caches like Caffeine and has become the default in several CDN stacks I've worked with. The design is clever: a small Window LRU (about 1% of capacity) handles burst admission, a larger Main segment is split into Protected and Probation via SLRU, and a TinyLFU admission filter — a compact Count-Min Sketch with aging — decides whether a new item deserves to enter Main at all. That filter is where it crushes one-hit wonders. A scan of cold objects never passes admission because their sketched frequency is 1, while your hot objects sit safely in Protected. The memory tricks behind that sketch are closely related to Probabilistic Caching with Bloom Filters: Memory-Efficient Cache Lookups, where we trade perfect accuracy for huge memory savings. In our edge tests, the sketch added less than 2% overhead but cut origin fetches from scans by over 60%.

We benchmarked all four policies on the same production trace — 14 days of image and API traffic from a North America edge PoP, ~850M requests, cache size fixed at 50GB per node. The differences weren't subtle. LRU is still fine if your working set is small and stable, but if you have churn or scans, you're leaving hit ratio on the table. ARC was strong but cost us more CPU on ghost list management. W-TinyLFU gave us the best hit ratio with the lowest overhead, which is why we standardized on it for edge SSD tiers last year.

Beyond Theory: Implementing W-TinyLFU Without Shooting Yourself in the Foot

Look, you probably shouldn’t hand-roll a full W-TinyLFU from scratch unless you really have to. If you’re running a JVM-based edge service or origin-side cache, just use Caffeine — it’s got the most battle-tested W-TinyLFU implementation out there and it’ll beat your custom LRU by 8-12% hit ratio on typical CDN workloads without you writing a line of sketch code. But if you’re working at the CDN edge itself — think Varnish VCL, Nginx with custom modules, or a Rust/Go sidecar — you don’t have that luxury. You’re building the admission and eviction logic yourself.

The trickiest part isn’t the LRU segments, it’s sizing them right. In Caffeine’s default, 1% of your cache goes to the Window LRU (to catch burst/recency) and 99% to the Main space, which is itself split into Protected and Probation LRU. For CDN object caching where you’ve got 50-500GB per node and a long tail of large objects, I’ve found bumping that Window to 3-5% helps absorb scan pollution from crawlers without polluting your Protected segment. Your TinyLFU sketch doesn’t need to be huge either — a Count-Min Sketch with 4-bit counters and a periodic decay (halve all counters every ~1M requests or every 10x your cache size in misses) gives you ~98% accuracy for under 200KB per 1M entries. Add a Bloom filter door-keeper in front and you’ll filter out ~90% of one-hit wonders before they even touch the sketch.

Don’t forget that eviction doesn’t live in isolation. How you shard keys across POPs changes what your eviction policy even sees. If you’re using naive modulo hashing, a single node failure reshuffles 30-40% of your keys and nukes your carefully tuned frequency data. That’s why you want to pair your eviction strategy with Consistent Hashing for CDN Cache Distribution: A Practical Implementation Guide — you’ll keep data locality and let TinyLFU’s frequency estimates actually converge instead of resetting every deploy.

// Simplified W-TinyLFU admission - Go-style pseudocode
func ShouldAdmit(key string, sketch *CountMinSketch, victimFreq int) bool {
    // Estimate frequency with 4-bit counters + periodic decay
    estFreq := sketch.Estimate(key)
    if estFreq == 0 {
        // Bloom filter doorkeeper: first seen? Don't admit to Main
        if !doorkeeper.MightContain(key) {
            doorkeeper.Add(key)
            return false // stay in Window LRU only
        }
    }
    // Admit only if more frequent than LRU victim in Probation
    // This is the TinyLFU gate that gives you 15-20% fewer eviction misses vs plain LRU
    return estFreq > victimFreq
}

// Decay every N requests to handle workload shifts
if requestCount % 1000000 == 0 {
    sketch.Decay(0.5) // halve all counters
}

Advanced Patterns and Production Troubleshooting

Even with a perfect policy on paper, production traffic will humble you. The classic failure mode I see is a sudden hit ratio cliff — you’re cruising at 92% hit ratio, then a partner does a full-site prefetch and your hit ratio drops to 71% in 10 minutes and never recovers. That’s scan pollution overwhelming your Window segment. If you’re still on pure LRU, you’re toast. With ARC or W-TinyLFU, watch your ghost list hit rate. If ARC’s B1/B2 ghost hits spike above 15-20%, your cache is too small for the working set shift. With W-TinyLFU, if your admission rate drops below 5% for more than an hour while origin 5xx spikes, your sketch is stale — force a decay or cut your window size. We alert if p99 origin fetch latency jumps more than 40ms correlated with a hit ratio drop, that’s usually eviction, not origin.

Another gotcha: don’t conflate eviction with invalidation. Eviction is capacity management; invalidation is correctness. I’ve audited setups where teams cranked up TTLs to 24h to “improve hit ratio” and then relied on LRU to purge old content. That’s backwards and it’ll serve stale pricing data for hours. Use explicit Cache Tag Design Patterns: Organizing Content for Granular Invalidation and Surrogate Keys for Targeted Cache Purging: Beyond URL-Based Invalidation for correctness, and let your eviction policy handle only the capacity pressure. Your eviction logic should never be your purge strategy. On Fastly or Akamai, we tag product pages with `product-123`, `category-shoes`, `price-tier` and purge by surrogate key in <150ms globally instead of waiting for LFU to *eventually* evict it.

Finally, instrument like you mean it. Don’t just graph hit ratio. Break it down: hit ratio by object size bucket (small <10KB vs large >1MB), by cache tier (Window vs Main Protected), and admission rate. If your large objects (>500KB) have a hit ratio 25 points lower than small objects, you’ve got a size-aware eviction problem — consider SLRU or size-weighted TinyLFU. And always test with a shadow cache: mirror 1% of production traffic to a second instance running the new policy and compare hit ratios for a week before you flip the fleet. It’s saved us from three bad rollouts that looked great in wrk benchmarks but tanked on real Zipf 0.85 traffic.

Frequently Asked Questions