Timevolt

Posted on Aug 17

Designing a URL Shortener: The Cache Strikes Back

#systemdesign #architecture #backend #programming

The Quest Begins (The "Why")

I remember the first time I tried to build a URL shortener for a side‑project. I slapped together a simple hash table, threw it behind an Express route, and called it a day. It worked… until my friend shared the link on a Reddit thread and the traffic spiked from a handful of requests per second to a few thousand. Suddenly the single‑node hash map started to choke, latency climbed, and the whole thing felt like trying to drink from a firehose with a straw.

That moment was my “aha!” — scaling a URL shortener isn’t just about generating a tiny string; it’s about making sure that lookup stays lightning‑fast and cheap under unpredictable load. I needed a system that could absorb bursts, survive node failures, and still give me sub‑millisecond redirects most of the time.

The Revelation (The Insight)

After a few sleepless nights debugging Redis timeouts and watching CPU spikes on my EC2 instances, the insight hit me like a plot twist in a good thriller: the majority of lookups are for a small, hot set of URLs. Think about it — viral memes, breaking news links, or a popular product page get clicked thousands of times while the long tail sits idle.

If we can serve those hot entries from an ultra‑fast, in‑process cache and fall back to a persistent store only when we miss, we get the best of both worlds:

In‑process LRU cache (e.g., a tiny lru_map in Go or a functools.lru_cache in Python) gives us nanosecond‑scale hits with zero network hop.
Redis (or any distributed key‑value store) holds the full mapping, survives restarts, and provides the source of truth for cold keys and for spreading the load across multiple API nodes.

The trade‑off is simple: we add a tiny amount of complexity (two layers, a miss‑handling path) but we slash the 99th‑percentile latency from tens of milliseconds to under a millisecond for the majority of traffic.

Here’s how the pieces fit together (ASCII art, because every engineer loves a good diagram):

+-------------------+       +-------------------+       +-------------------+
|   API Node A      |       |   API Node B      |       |   API Node C      |
|  (in‑process LRU) |       |  (in‑process LRU) |       |  (in‑process LRU) |
+--------+----------+       +--------+----------+       +--------+----------+
         |                         |                         |
         |  HIT? (LRU)             |  HIT? (LRU)             |  HIT? (LRU)
         | Yes --------------------+------------------------+ Yes
         |                         |                         |
         | No                      | No                      | No
         v                         v                         v
+-------------------+       +-------------------+       +-------------------+
|      Redis        |<----->|      Redis        |<----->|      Redis        |
| (persistent map)  |       | (persistent map)  |       | (persistent map)  |
+-------------------+       +-------------------+       +-------------------+

When a request arrives:

Check the local LRU. If present → redirect immediately (cache hit).
If miss, ask Redis. If present → populate the local LRU (write‑through) and redirect.
If still missing → generate a new short code, store it in Redis, and optionally seed the LRU.

The beauty is that the LRU size can be tuned to fit comfortably in each node’s memory (say 10 k–100 k entries). Even a modest 50 k entry cache covers the top 0.1 % of URLs, which often accounts for >80 % of traffic in real‑world shortener workloads.

Wielding the Power (Code & Examples)

The Naïve Struggle

First attempt – a single global map backed by a Redis GET on every request:

# naive.py
import redis
r = redis.Redis(host='redis', port=6379, db=0)

def resolve(short_code):
    # Every hit goes to Redis – O(network) latency
    long_url = r.get(short_code)
    if not long_url:
        raise KeyError("unknown code")
    return long_url.decode()

When traffic spiked, the Redis instance became the bottleneck. Each request incurred a round‑trip (≈0.5 ms on a good LAN) plus serialization overhead. Under 5k rps, latency crept to 12 ms and error rates rose as the connection pool exhausted.

The Victorious Design

Now the two‑layer version:

# shortener.py
import redis
from cachetools import LRUCache

# Shared Redis client (connection‑pooled)
redis_client = redis.Redis(host='redis', port=6379, db=0)

# Local LRU cache – size tuned per node
LOCAL_CACHE = LRUCache(maxsize=50_000)

def resolve(short_code):
    # 1️⃣ Try the blazing‑fast in‑process cache
    long_url = LOCAL_CACHE.get(short_code)
    if long_url is not None:
        return long_url   # cache hit – pure memory access

    # 2️⃣ Miss: ask Redis (still fast, but only for the miss stream)
    long_url_bytes = redis_client.get(short_code)
    if not long_url_bytes:
        raise KeyError("unknown code")

    long_url = long_url_bytes.decode()
    # 3️⃣ Write‑through: populate the local LRU for future requests
    LOCAL_CACHE[short_code] = long_url
    return long_url

Why this beats the naive approach

Hit latency drops from ~0.5 ms (Redis RTT) to ~0.05 ms (L1 cache hit).
Redis load is reduced to the miss rate. If 80 % of requests hit the LRU, Redis only sees 20 % of the traffic – a 5× reduction in QPS, leaving headroom for bursts or background jobs (e.g., analytics aggregation).
Fault tolerance: If a node dies, its local cache is lost, but Redis still holds the authoritative map. New nodes warm up lazily as they serve misses.

Common traps to avoid

Trap	What happens	Fix
Cache stampede on a miss for a hot key	Many threads simultaneously query Redis, thundering the backend	Use a lock or `redis.setnx`‑style “miss‑marker” so only one thread populates the LRU, others wait for the result
Stale entries after a URL is updated or deleted	LRU serves an old redirect	Implement a write‑through delete: when you `DEL` the key in Redis, also `LOCAL_CACHE.pop(short_code, None)`. Or adopt a short TTL (e.g., 5 min) and let the cache expire naturally.
Over‑sizing the LRU	Exhausts node memory, triggers swapping → worse performance	Monitor memory usage; start with a modest size (e.g., 50 k) and scale up only if hit‑rate stalls.

Why This New Power Matters

With this two‑layer cache in place, your URL shortener can now:

Handle viral spikes without melting your Redis instance.
Keep redirect latency consistently low, improving user experience and SEO (search engines love fast redirects).
Scale horizontally simply by adding more API nodes – each node brings its own LRU, so total cache capacity grows with the fleet.
Operate cheaply – a modest Redis instance (or even a managed elasticache) can sustain the miss traffic, while the bulk of work is served from free, local memory.

In short, you’ve turned a simple key‑value store into a resilient, high‑performance service that feels instantaneous to the end‑user, even when the internet decides to test its limits.

Your Turn

Grab a language you love, spin up a tiny LRUCache (or implement your own with a doubly‑linked list and hash map), wire it to a Redis backend, and watch the miss rate drop as you feed it synthetic traffic.

Challenge: instrument the hit/miss ratios, plot them over time, and see how changing the LRU size reshapes the curve. Share your results — let’s see who can push the hit‑rate above 95 % with the smallest memory footprint!

Happy caching, and may your redirects always be swift! 🚀

DEV Community