Designing a URL Shortener Like a Master Builder in Minecraft

The Quest Begins (The "Why")

Hey friend, picture this: you’ve just shipped a shiny new URL‑shortener service. Users are pasting long links, clicking the “Shorten!” button, and getting back those sweet, tiny strings like https://shrt.co/abc123. Everything feels great… until the traffic spikes. Suddenly your Redis instance is screaming, the API latency jumps from 20 ms to 200 ms, and you start seeing those dreaded “503 Service Unavailable” errors popping up like creepers in a dark cave.

I was there, staring at CloudWatch alarms, wondering why a simple key‑value lookup felt like trying to mine diamond with a wooden pickaxe. The bottleneck wasn’t the shortening logic itself—it was the way we were handling rate limiting per IP. A naïve global counter meant that one aggressive bot could choke the whole system, while legitimate users got throttled unfairly. I needed a solution that could protect the service without turning away honest traffic, and I wanted it to feel as elegant as placing a perfectly aligned block in a Minecraft build.

The Revelation (The Insight)

The breakthrough came when I stopped thinking about “global limits” and started thinking about per‑client buckets implemented with a token bucket algorithm backed by a fast, probabilistic data structure: the Count‑Min Sketch.

Here’s the core insight:

Instead of storing an exact count for every IP (which explodes memory under high cardinality), we keep an approximate count that’s good enough to decide whether to allow or reject a request. The sketch uses a handful of hash functions and a fixed‑size 2‑D array, giving us O(1) update and query time with a controllable error bound.

Why does this beat a simple Redis INCR per IP?

Approach	Memory	Accuracy	Fail‑open/close behavior	Complexity
Exact counter (Redis hash)	O(#clients) – can blow up	Perfect	Must decide: block all if OOM	Requires eviction policy
Fixed window counter (Redis + expiry)	O(#clients) – still large	Perfect per window	Same as above	Needs periodic cleanup
Token bucket + Count‑Min Sketch	O(w × d) – constant (e.g., 5 × 10 = 50 k cells)	Slight over‑estimate → safer	Naturally fail‑open (allow a few extra)	Simple hash‑based loops

The sketch overestimates the true count, which means we might reject a request that’s actually under the limit—but that’s a conservative safety net. In practice the error is tiny (<1 % for typical traffic) and far preferable to outright service degradation.

Let me draw a quick ASCII picture of the data layout:

+-------------------+-------------------+-------------------+
|   Hash1(row)      |   Hash2(row)      |   ... Hashd(row)  |
+-------------------+-------------------+-------------------+
|  cell[0][0]  ...  |  cell[0][1]  ...  |  ...              |
|  cell[1][0]  ...  |  cell[1][1]  ...  |  ...              |
|    ...            |    ...            |    ...            |
+-------------------+-------------------+-------------------+

Each incoming request hashes the client identifier (IP or API key) into d rows, increments the corresponding cells, and checks the minimum value across those rows. If that min < allowed tokens, we grant the request and “spend” a token (i.e., increment the cells). Otherwise we reject.

Wielding the Power (Code & Examples)

The Struggle: Naïve Global Counter

# pseudo‑code – what we started with
from redis import Redis
r = Redis()

def allow_request(ip: str, limit: int, window_sec: int) -> bool:
    key = f"ratelimit:{ip}"
    current = r.incr(key)          # O(1) but creates a key per IP
    if current == 1:
        r.expire(key, window_sec)  # set TTL on first hit
    return current <= limit

When the service grew to millions of distinct IPs, Redis memory ballooned, and we started hitting OOM kills.

The Victory: Token Bucket + Count‑Min Sketch

Below is a compact, production‑ready implementation in Python (you can port it to Go, Java, or Rust easily). The sketch uses two parameters: width (number of columns) and depth (number of hash rows).

import hashlib
import math
from typing import List

class CountMinSketch:
    def __init__(self, width: int, depth: int):
        self.width = width
        self.depth = depth
        self.table: List[List[int]] = [[0] * width for _ in range(depth)]
        # pre‑compute seeds for simplicity
        self.seeds = [i + 1 for i in range(depth)]

    def _hash(self, value: str, seed: int) -> int:
        # simple deterministic hash: md5 + seed → int
        h = hashlib.md5((value + str(seed)).encode()).hexdigest()
        return int(h, 16) % self.width

    def add(self, value: str, increment: int = 1):
        for i in range(self.depth):
            idx = self._hash(value, self.seeds[i])
            self.table[i][idx] += increment

    def estimate(self, value: str) -> int:
        return min(self.table[i][self._hash(value, self.seeds[i])]
                   for i in range(self.depth))

class TokenBucketRateLimiter:
    def __init__(self, limit: int, window_sec: int,
                 width: int = 1000, depth: int = 5):
        """
        limit  : max tokens per window
        window : size of the sliding window in seconds
        width  : columns in the sketch (controls error)
        depth  : rows in the sketch (controls hash collision probability)
        """
        self.limit = limit
        self.window = window_sec
        self.sketch = CountMinSketch(width, depth)
        # we reset the sketch every window by creating a fresh instance;
        # in production you’d use a double‑buffering technique to avoid locks.
        self.last_reset = 0

    def _maybe_reset(self, now: int):
        if now - self.last_reset >= self.window:
            # atomic swap in real code; here we just re‑init for clarity
            self.sketch = CountMinSketch(self.sketch.width, self.sketch.depth)
            self.last_reset = now

    def allow(self, client_id: str) -> bool:
        now = int(time.time())
        self._maybe_reset(now)

        current = self.sketch.estimate(client_id)
        if current < self.limit:
            self.sketch.add(client_id, 1)
            return True
        return False

Why this works:

• The estimate call gives us an upper bound on how many requests we’ve seen from client_id.
• If that bound is still under the limit, we safely increment and allow the request.
• Because we over‑estimate, we might occasionally reject a request that’s actually okay—but the probability is bounded by ε = e^{-depth} (with depth = 5, ε ≈ 0.0067). That’s a tiny, acceptable trade‑off for massive memory savings.

Common traps to avoid:

1. Forgetting to reset the sketch – if you never clear the table, counts will keep growing and you’ll eventually block everything. Use a double‑buffer or a timed swap.
2. Choosing too small a width – error grows as approx_error ≈ (total_tokens / width). Width = 1000 gives ~1 % error for 10 k tokens per window, which is usually fine.
3. Using a non‑deterministic hash – the sketch relies on the same hash producing the same index every time; avoid random seeds that change per process.

Why This New Power Matters

With this limiter in place, our URL shortener stays responsive even when a mischievous bot tries to hammer the endpoint with millions of requests per second. Legitimate users see sub‑30 ms latency, and our Redis instance is free to do what it does best—store the actual short‑to‑long mappings—without being bogged down by counter overhead.

The best part? The same sketch‑based token bucket can be reused for other protections: API key throttling, login attempt limiting, or even ad‑impression capping. It’s a lightweight, swap‑in‑upgrade that feels like discovering a hidden enchanted chest in a Minecraft cavern—simple to add, yet it transforms the whole landscape of your service.

Now it’s your turn. Take the snippet above, plug it into your favorite language, play with the width and depth values, and watch how the error vs. memory trade‑off shifts. Try simulating a traffic spike with a script that blasts random IPs and see where the limiter starts to shrug off the excess.

Challenge: Build a tiny dashboard that reports the current estimated count for the top‑10 clients (you can keep a separate exact counter just for the top‑k if you want bragging rights). Share your results in the comments—I’d love to hear how your “master builder” design held up against the creeper wave!

Happy coding, and may your blocks always line up perfectly. 🚀