Course contentsShow
← System Design
Lesson 1525 of 1,91937. Real-World System: URL ShortenerFree lesson

Cache Eviction Policy for URL Shortener

Use LRU eviction to keep the most frequently accessed URLs in memory and let cold URLs expire naturally.

Cache Eviction Policy for URL Shortener

What you'll learn: How to choose and implement the right cache eviction policy to maximize hit rates for a URL shortener's access patterns.


Why Cache Eviction Matters

A URL shortener serves millions of redirect requests daily, but can't cache every URL in memory. When the cache fills up, you must decide which URLs to evict. The wrong policy wastes precious cache space on URLs no one visits, degrading performance.

The Access Pattern Reality

URL shorteners exhibit a power-law distribution: a small percentage of URLs (viral links, popular campaigns) receive the vast majority of traffic, while most URLs get accessed rarely or never. This makes certain URLs "hot" and others "cold."

LRU: The Natural Fit

Least Recently Used (LRU) eviction is ideal here:

  • Keeps hot URLs cached: Frequently accessed links naturally get touched recently, staying in cache
  • Evicts cold URLs automatically: Links that haven't been accessed in a while get pushed out organically
  • No manual expiration needed: The algorithm self-adjusts based on actual access patterns
  • Simple to implement: Most cache libraries (Redis, Memcached) support LRU natively

Think of LRU like a library reading room with limited seats. The books people keep reading stay on the table; books nobody touches get returned to the stacks. The popular ones naturally maintain their spot.

Alternative Considerations

While LRU works well, you might combine it with:

  • TTL (time-to-live) for expired short URLs
  • Size-aware eviction if URL metadata varies significantly
  • LFU (Least Frequently Used) if you track access counts

Key Takeaway: LRU eviction naturally aligns with URL shortener traffic patterns, keeping viral and frequently-accessed links in memory while cold links expire organically, maximizing cache hit rates without manual tuning.