Building a URL shortener (TinyURL)

Base62 encoding

Turn a numeric ID into a short string over [0-9a-zA-Z]:

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
def encode(n):                      # int -> short code
    if n == 0: return ALPHABET[0]
    s = []
    while n:
        n, r = divmod(n, 62)
        s.append(ALPHABET[r])
    return "".join(reversed(s))     # e.g. 1,000,000 -> "4c92"

A monotonically increasing ID gives short, unique, collision-free codes. The only problem is generating that ID without a single hot counter.

Distributed ID ranges (defeating the counter bottleneck)

A central counter would serialize every create. Instead, each app server leases a block of IDs and hands them out locally; it only touches the central store once per block:

class IdGenerator:
    def __init__(self): self.next = self.end = 0
    def get_id(self):
        if self.next >= self.end:                 # block exhausted → lease another
            self.next, self.end = lease_block(size=1000)   # atomic incr-by on a counter row
        i = self.next; self.next += 1
        return i

lease_block does an atomic UPDATE counter SET val = val + 1000 RETURNING val — one round trip per thousand creates, so the counter is no longer hot. (A key-generation service pre-filling random codes is the alternative; same goal, no ordering leak.)

The create path

def shorten(long_url, alias=None):
    code = alias or encode(idgen.get_id())
    if alias and store.exists(alias):
        raise AliasTaken()
    store.put(code, {"long_url": long_url, "created_at": now()})   # sharded by code
    return f"https://lyte.ly/{code}"

The redirect path (cache-first)

The 100k/sec read load must hit cache, not the DB:

def redirect(code):
    long_url = cache.get(code)                    # Redis, hot mappings
    if long_url is None:
        rec = store.get(code)                     # miss → sharded KV
        if not rec or expired(rec): return 404
        long_url = rec["long_url"]
        cache.set(code, long_url, ttl="24h")      # populate
    emit_click_event(code)                         # async, non-blocking
    return Redirect(long_url, code=302)

Mappings are immutable, so caching is easy (no invalidation problem) — TTL is just for memory management. A CDN/edge can cache the redirect response too.

Sharding the store

Partition by code (consistent hashing). Since lookups are always by code, every read/write hits exactly one shard — no scatter-gather. Replicate each shard for availability. Tens of TB over years spreads cleanly across shards.

Click analytics without slowing redirects

Never write analytics inline on the hot path. Emit an event to a queue; aggregate asynchronously:

def emit_click_event(code):
    queue.publish("clicks", {"code": code, "ts": now(), "ref": header("Referer")})
# stream/batch workers → counters in a time-series store (Chapter 4 analytics)

Failure handling & edge cases

• Cache down → reads fall through to the sharded store (degraded latency); the store is replicated, so it absorbs it.
• Duplicate long URLs → counter approach makes a new code each time (fine); to dedup, keep a hash(long_url) → code index and return the existing code.
• Custom alias collision → uniqueness check before insert.
• Expiry → lazy check on read + a background purge job.
• Abuse (shortening malicious URLs) → rate-limit creates per user; scan/blocklist.

The takeaway

Concrete signals: base62 over a range-leased distributed ID (no hot counter), an immutable cache-first redirect path sized for 100k/sec, shard by code so every op is single-shard, and async click events. It’s a compact showcase of ID generation, caching, and sharding — the reason it’s the classic opener.