CDN Caching: LRU vs LFU Under Real Zipf Traffic

Why a CDN exists at all

Light in fibre travels at roughly two-thirds of c, which puts a hard floor under latency: New York to Sydney and back is about 160 milliseconds no matter how good your server is. A Content Delivery Network solves this not by making the origin server faster but by making the origin unnecessary for most requests — it places edge caches in hundreds of physical locations close to users, and routes each request to a nearby one via DNS or anycast. If the content is already sitting in that edge cache, the origin server is never even contacted.

Hit rate is the entire economic argument

The cache hit rate — the fraction of requests an edge node can answer from its own storage — is the single number that determines whether a CDN is worth running. A miss means the edge node has to fetch from the origin (or a parent cache), pay the full round-trip latency, and then decide whether to store the result for next time. Every cache has finite capacity, so when it is full and a new object arrives, something existing has to be evicted — and which object gets evicted is the whole game.

LRU: recency as the only signal

Least Recently Used eviction keeps objects ordered by the time they were last accessed and evicts whichever one has gone longest untouched. Implemented as a doubly linked list plus a hash map, both lookup and the promote-to-front operation on a hit are O(1):

on request(key):
  if key in cache:
    move node[key] to front of list        // O(1) — recency updated
    return node[key].value                 // HIT
  else:
    if cache is full: evict node at back    // the coldest item, O(1)
    fetch from origin, insert node[key] at front   // MISS

LRU is cheap, simple, and adapts instantly to shifting popularity — yesterday's viral video falls out naturally as today's takes over. Its weakness is that it treats a single access exactly like a hundred: a large object requested once (a crawler sweeping through a catalog, someone scrubbing through a video) can flush truly popular content out of the cache purely because it happened to be touched most recently — a failure mode usually called cache pollution or scan resistance failure.

LFU: frequency as the signal instead

Least Frequently Used eviction keeps a hit counter per object and evicts whichever has the lowest count, typically implemented with a hash map plus a min-heap or a bucket list keyed by frequency for O(1) or O(log n) operations. It resists the one-off-scan problem that hurts LRU — a truly popular object accumulates a count that a single scan cannot match.

But LFU has the opposite failure mode: cache staleness. An object that was enormously popular last week but is now irrelevant can sit on a high counter and refuse to be evicted, permanently occupying space that newly popular content needs. Production systems almost always add decay — periodically halving all counters, or weighting by recency as well as frequency (the LRU-K and ARC families, and Redis's own approximated-LFU with logarithmic counters and time-based decay, are all attempts to blend the two signals rather than pick one).

Why Zipf, not uniform, traffic changes everything

Real request traffic to a CDN is not evenly spread across content — it follows a Zipf distribution: if you rank objects by popularity, the request frequency of the k-th ranked object is proportional to 1/k^s for some skew parameter s (s = 1 is the classical Zipf law; measured web and video traffic typically sits around s = 0.6-0.9):

frequency(rank k)  ∝  1 / k^s

s = 1.0, top 1% of objects  →  carries roughly 60-70% of all requests
s = 1.0, top 10% of objects →  carries roughly 90%+ of all requests

This is the entire reason caching works at internet scale: because a small head of extremely popular content accounts for the overwhelming majority of requests, a cache holding even 1-5% of the total object catalog can achieve a hit rate well above 80% — provided the eviction policy actually keeps that head resident. Under Zipf-distributed traffic, LFU tends to outperform LRU on raw hit rate precisely because it directly tracks the quantity (frequency) that Zipf traffic is skewed by; LRU can still do well because popular objects also tend to be requested recently, but it is more exposed to pollution from cold scans through the long tail.

TTL and cache invalidation: the other half of the problem

Hit rate alone is not the whole story — a cached object also has a Time To Live after which it is considered stale and must be revalidated with the origin (via a conditional request using an ETag or Last-Modified header) even if it was never evicted. Set TTL too long and users see outdated content after the origin changes; set it too short and hit rate collapses because objects expire before they are reused. Phil Karlton's famous line — “there are only two hard things in computer science: cache invalidation and naming things” — is aimed squarely at this trade-off, and production CDNs spend enormous engineering effort on fast purge APIs and stale-while-revalidate strategies precisely because getting TTL wrong in either direction is expensive.

Multi-tier caching: edge, regional, origin shield

A single layer of edge caches all missing simultaneously and hammering the origin at once (the thundering herd problem, common right after a cache-wide purge or a sudden traffic spike) is why large CDNs insert a middle tier — regional or shield caches — between hundreds of edge nodes and the origin. A miss at an edge node checks the shield cache first; only a miss at the shield actually reaches the origin. This turns what would be hundreds of simultaneous origin requests into, at most, one per unique object per region, and it is the same hierarchical idea as an L1/L2/L3 CPU cache, just at internet scale and with network latency standing in for memory latency.

Frequently asked questions

Try it live

Everything above runs in your browser — open CDN & Cache Hit Rate and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.