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.