Design a URL Shortener: Base62 Counters, the KGS & 91 Terabytes

Intuition: why the “easy” question is a trap

“Design a URL shortener” is the most underestimated prompt in system-design interviews. It sounds like a weekend project — until the interviewer starts pulling threads, and the candidate discovers the project has four distributed-systems problems hiding inside it. This guide pulls each thread in the order the interview will.

First, uniqueness: how do you mint short codes that never collide, across dozens of app servers, at a hundred million new links a day? The naive answers — random strings, hash the URL — both have a collision story, and the interviewer will make you tell it. Second, scale of the read path: shortening is a write; following a link is a read, and reads outnumber writes roughly ten to one. The write path is a feature; the read path is the product — it must be fast, cached, and nearly free per click. Third, the counter bottleneck: the cleanest key scheme (a global counter, base62-encoded) puts one counter on the critical path of every write in the fleet. Scaling the counter without breaking uniqueness is the heart of the interview. Fourth, abuse: a shortener is a trust-laundering machine — a phishing link hiding behind your domain. Any design that skips malware scanning and creation limits is incomplete.

How the pieces fit — and the bottleneck at the heart of it

Base62: turning a counter into a short code

The core trick is embarrassingly simple. Keep a counter — 1, 2, 3, … — and write each value not in decimal but in base62: the digits 0–9, the lowercase a–z, and the uppercase A–Z, 62 symbols in all. Counter value 61 becomes Z; 62 becomes 10; 3,844 becomes 100. A 7-character code spans 62⁷ = 3,521,614,224,896 — over 3.5 trillion unique tickets. You will never run out.

Why base62 instead of random strings? Three reasons, and you should state all three. Deterministic: the counter never repeats, so collisions are structurally impossible — no database check needed to mint a code. Compact: base62 packs ~5.95 bits per character versus ~4.7 for hex, so codes stay short. Ordered: codes grow monotonically, which makes range-based sharding and debugging trivial. The price is that the counter itself becomes the thing you must scale — which is exactly what the Key Generation Service is for.

The hash alternative — and the collision tax

The other classic design skips the counter entirely: hash the long URL (MD5, SHA-256), take the first few bytes, base62-encode them. No counter, no coordination, every app server can mint codes independently. It is genuinely elegant — and it has a collision story you must tell before the interviewer asks.

Two different URLs can hash to the same prefix. The fix is a lookup on every mint: hash the URL, check whether the code already exists in the database, and on a clash re-hash with a salt — hash(url + salt) — until the code is free. At 100M links a day the birthday bound says collisions are rare but not imaginary, and every mint now costs a database read. So the real comparison: hashing buys you coordination-free minting and pays for it with a collision-handling path on every write; the counter buys you collision-free minting and pays for it with a counter you must scale. The counter wins — simpler, collision-free — and the rest of this guide is about making the counter cheap.

The write path: dedup first, then mint

Before minting anything, check whether you have seen this URL before. Hash the long URL (SHA-256) and look it up in a dedup table. Duplicates are extremely common — the same viral article gets shortened by thousands of people — and a hit means you return the existing code without touching the counter or writing a row. Bitly does exactly this: shortening the same link twice gives you the same short URL.

On a miss, the flow is: take the next counter value, base62-encode it, write the mapping code → long URL plus metadata (created-at, owner), and record the dedup entry. Custom aliases fit here as a branch: if the user asked for sho.rt/my-talk, check availability first, reserve dictionary words and previously deleted codes, then store it like any other row — but never let user-chosen codes come from the counter’s namespace, or a future counter value will collide with someone’s vanity link.

The read path: 301s and the 10-to-1 ratio

Reads outnumber writes roughly ten to one, so the read path gets the engineering budget. The flow: look up the code, answer with an HTTP redirect, let the browser do the rest. The redirect flavor matters. 301 Moved Permanently tells the browser the mapping will never change — browsers cache it, so repeat visits never reach your servers at all. 302 Found forces the browser to re-request every time, which costs you a request per click but lets you count every click — the reason analytics-heavy shorteners historically preferred 302.

Then cache the hot keys. A viral link can take millions of hits an hour; without a cache, every one of those hits is a database lookup. A Redis or Memcached layer in front of the mapping store absorbs the skew: the top fraction of a percent of links serves the overwhelming majority of reads, and the database only sees the long tail. A cache miss falls through to the database, fills the cache, and the next million hits cost nothing. Target a p99 redirect latency in the low tens of milliseconds — the read path is the product, and every millisecond shows up in someone else’s page load.

The KGS: fixing the single-counter bottleneck

Here is the trap the interview is really about. One global counter, incremented on every write, is a bottleneck and a single point of failure: every app server in the fleet must coordinate on one number, forty times a second, forever. The fix is the Key Generation Service — a tiny dedicated service whose only job is handing out numbers in bulk.

The KGS keeps its own counter, but instead of dispensing one value per request, it dispenses range blocks: app server A gets keys 1,000,000–1,999,999, server B gets 2,000,000–2,999,999. Each server mints from its private block with zero coordination — no lock, no RPC, no contention per request. When a server exhausts its block, it asks the KGS for another. The KGS itself is simple enough to make highly available (its own counter, replicated, with blocks pre-allocated ahead of time), because it only sees one request per million writes instead of one per write. The codes are no longer globally sequential — server A’s codes interleave with server B’s — which is fine, because nobody promised ordering. Throughput scales with the fleet; uniqueness is preserved by construction.

Storage: sharding with consistent hashing

The mapping table is simple — code → long URL plus created-at, owner, and optional expiry — but at ~91 terabytes over five years (the numbers section does the math) it does not live on one machine. Shard by hashing the short code: shard = hash(code) mod N. Use consistent hashing so that adding or removing a node re-maps only roughly 1/N of the keys instead of reshuffling the whole dataset — a resharding event that moves everything is an outage wearing a migration costume. Replicate each shard for the read path: reads are the product, so read replicas and the cache layer carry the fleet while the primary handles the comparatively rare writes.

Abuse: the interviewer always asks

A URL shortener is a trust-laundering machine: a phishing page hiding behind your reputable domain. Any design that skips abuse controls is incomplete, and interviewers probe this specifically. Three defenses, in order of importance. Rate-limit creation per IP and per account — a script minting ten thousand links a minute is not a power user. Scan every target against malware and phishing blocklists (the Google Safe Browsing API is the canonical feed) before the link goes live, and re-scan periodically — a clean page today can be compromised tomorrow. Friction on suspicion: CAPTCHA on creation for anonymous users, link expiry, and a kill-switch that disables a code without deleting the row (so you keep the forensic trail). Say it plainly: the shortener is only as trustworthy as the links it hides.

Extras: aliases, expiry, analytics

Once the core works, the interview rewards a crisp tour of the options. Custom aliases — sho.rt/my-talk — checked for availability against the counter’s namespace and a reserve list, stored like any other row. Expiry — a TTL per link, enforced on read (return 410 Gone after expiry) and reclaimed by a background sweeper; note that expired codes should not be recycled into the counter stream, or old printed links resurrect as someone else’s page. Click analytics — timestamp, referrer, rough geo, device class — which is precisely why some systems choose 302 over 301: every click must touch the server to be counted. Name the tradeoff explicitly: 301 buys you free caching, 302 buys you complete data, and the business decides which is worth more.

Who runs this at scale — and what they learned

URL shortening is one of the oldest boring-infrastructure success stories: a trivial idea that only survives if the read path is bulletproof. The companies that ran it at scale each learned a different lesson — and interviewers love hearing which lesson applies where.

The through-line: nobody’s write path is interesting. Every lesson — dedup at Bitly, the t.co wrap, goo.gl’s six-year redirect afterlife, the go/ intranet — is about the read path being fast, permanent, and trustworthy.

Work the storage math by hand

100 million new URLs a day, kept for 5 years, roughly 500 bytes per record (the code, the long URL, timestamps, owner). Run the numbers before the interviewer asks.

Five numbers, one story: the dataset is modest (~91 TB), the write rate is tame (~1.2K/sec), the read rate demands a cache (~11.6K/sec), and the key space needs 7 characters minimum. Derive them in this order and the interview runs itself.

Counter, KGS, and Flask — in Python

Base62 encode/decode, the Key Generation Service handing out range blocks, the dedup-on-write shortener, and the two HTTP endpoints — create with POST, follow with a 301. This is the whole system in under a hundred lines.

import hashlib
import threading

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
BASE = len(ALPHABET)  # 62


def base62_encode(n: int) -> str:
    """Counter value -> short code. Deterministic: no two inputs share an output."""
    if n == 0:
        return ALPHABET[0]
    out = []
    while n:
        n, rem = divmod(n, BASE)
        out.append(ALPHABET[rem])
    return "".join(reversed(out))


def base62_decode(s: str) -> int:
    n = 0
    for ch in s:
        n = n * BASE + ALPHABET.index(ch)
    return n


class KeyGenerationService:
    """Hands each app server a private block of keys. One RPC per million writes."""

    def __init__(self, block_size=1_000_000):
        self.counter = 0
        self.block_size = block_size
        self.lock = threading.Lock()

    def next_block(self):
        with self.lock:
            start = self.counter
            self.counter += self.block_size
            return start, start + self.block_size - 1


class Shortener:
    def __init__(self, kgs: KeyGenerationService):
        self.kgs = kgs
        self.lo, self.hi = kgs.next_block()  # our private range
        self.store = {}  # code -> long url (the sharded mapping table)
        self.dedup = {}  # sha256(long url) -> code

    def _mint(self) -> str:
        if self.lo > self.hi:  # block exhausted — fetch another
            self.lo, self.hi = self.kgs.next_block()
        code = base62_encode(self.lo)
        self.lo += 1
        return code

    def create(self, long_url: str) -> str:
        digest = hashlib.sha256(long_url.encode()).hexdigest()
        if digest in self.dedup:  # seen it — reuse, don't mint
            return self.dedup[digest]
        code = self._mint()
        self.store[code] = long_url
        self.dedup[digest] = code
        return code

    def resolve(self, code: str):
        return self.store.get(code)


# --- HTTP layer: create with POST, follow with a 301 ---
from flask import Flask, request, redirect, abort

app = Flask(__name__)
shortener = Shortener(KeyGenerationService())


@app.post("/api/shorten")
def shorten():
    long_url = request.json["url"]
    code = shortener.create(long_url)
    return {"short_url": f"https://sho.rt/{code}"}, 201


@app.get("/<code>")
def follow(code):
    long_url = shortener.resolve(code)
    if long_url is None:
        abort(404)
    # 301: browsers cache it — repeat visits never reach us.
    # Swap to 302 when every click must be counted.
    return redirect(long_url, code=301)

Four ideas, one file: the counter never collides so minting needs no database check; the KGS amortizes coordination to one RPC per million writes; the dedup table turns the most common write into a cache hit; and the redirect flavor — 301 versus 302 — is a business decision wearing an HTTP status code.

Six questions that test the real understanding

Key takeaways

1. Counter to base62 for the keys: deterministic, collision-free, ~5.95 bits per character — and 62⁶ provably runs out at 182.5B records, so 7 characters is the minimum.
2. Dedup on the write path: hash the URL, return the existing code — the same viral link gets shortened thousands of times, and duplicates are the norm.
3. The KGS removes the counter bottleneck: range blocks per server, one RPC per million writes, zero coordination on the hot path.
4. The read path is the product: 10:1 read ratio, cache the hot keys, answer 301 so browsers stop asking entirely.
5. Shard the mapping with consistent hashing — adding a node moves ~1/N of the keys, not the whole dataset.
6. A shortener is a trust-laundering machine: rate-limit creation, scan every target, keep a kill-switch — trust is the actual product.