Design a URL Shortener (TinyURL/bit.ly)

A URL shortener looks trivial — map a long URL to a short code and redirect. That simplicity is exactly why interviewers love it: there is nowhere to hide. A strong candidate turns “map a string to a string” into a crisp conversation about unique ID generation, base62 encoding, caching a read-heavy workload, and the subtle 301-vs-302 trade-off.

Understanding the Problem

Functional Requirements

1. Shorten a URL — Given a long URL, return a short one (e.g. bit.ly/3xYz9Ab)
2. Redirect — Visiting the short URL redirects to the original long URL
3. Custom alias — Optionally let users pick their own short code
4. Expiration — Optionally let a link expire after a date
5. Analytics (stretch) — Count clicks per short URL

Non-Functional Requirements

Storage estimate: 100M URLs/day × 365 days × 5 years ≈ 180 billion URLs. At ~500 bytes per record (long URL + metadata), that is roughly 90 TB over five years. Entirely manageable for a sharded key-value store.

The defining characteristic is the read skew: creating a link is rare, following it is constant. Every design decision optimizes the redirect.

Core Entities and APIs

Data Model

A single mapping table, stored in a key-value database (the short code is the key):

CREATE TABLE urls (
    short_code   VARCHAR(10) PRIMARY KEY,   -- "3xYz9Ab"
    long_url     VARCHAR(2048) NOT NULL,
    user_id      BIGINT,
    created_at   TIMESTAMP DEFAULT NOW(),
    expires_at   TIMESTAMP                  -- NULL = never
);

There are no joins, no range scans — only point lookups by short_code. That is a perfect fit for a distributed key-value store (DynamoDB, Cassandra, or even a sharded SQL table), which shards cleanly on the short code.

API Design

POST   /api/v1/shorten
  body: { long_url, custom_alias?, expires_at? }
  response: { short_url: "https://bit.ly/3xYz9Ab" }

GET    /{short_code}
  response: 301/302 redirect → long_url

High-Level Design

Write path (POST /shorten): The API acquires a unique integer ID from the ID generator, base62-encodes it into a short code, stores the short_code → long_url mapping, and returns the short URL.

Read path (GET /{short_code}): The API looks up the short code — first in the cache, then in the database on a miss — and returns an HTTP redirect to the long URL. Because the mapping is immutable once created, it is extremely cacheable; the vast majority of redirects are served straight from cache.

Deep Dive: Short Code Generation

This is the most important deep dive. The short code must be unique, short, and collision-free. There are three common approaches.

Approach 1: Unique ID + base62 (recommended)

Generate a globally unique integer ID, then encode it in base62 using the alphabet [0-9a-zA-Z]. Each base62 character carries log₂(62) ≈ 5.95 bits, so:

• 6 characters → 62⁶ ≈ 56 billion URLs
• 7 characters → 62⁷ ≈ 3.5 trillion URLs

Seven characters comfortably covers our 180-billion estimate. Because every integer maps to exactly one code, there are no collisions by construction — no need to check the database before writing.

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def encode_base62(num):
    if num == 0:
        return ALPHABET[0]
    chars = []
    while num > 0:
        num, rem = divmod(num, 62)
        chars.append(ALPHABET[rem])
    return "".join(reversed(chars))

# encode_base62(1_000_000_007) -> "15FTGH7"

Where does the unique integer come from? Two good options:

• A distributed counter / ticket server — simple and gives the shortest codes, but a single counter is a bottleneck and a single point of failure. Mitigate by handing out ranges (each app server pre-claims a block of, say, 1,000 IDs).
• A Snowflake-style ID — timestamp + machine + sequence, generated locally with no coordination. The IDs are larger (so codes are a bit longer) but there is no central bottleneck. (See the dedicated lesson on unique ID generation.)

Approach 2: Hash the URL, take a prefix

Hash the long URL (MD5/SHA-256), base62-encode it, and take the first 7 characters. Simple, but two different hashes can collide in the first 7 chars, so you must check the database and retry on collision — adding a read to every write and making the write path non-deterministic.

Approach 3: Pre-generated key database

A background job generates millions of unique random codes in advance and stores them in a “available keys” table. On each write, pop one key. This removes any runtime generation cost but adds operational machinery (the key-DB itself must be managed and replenished).

Recommendation: Unique-ID + base62. It is collision-free, deterministic, and the shortest. Lead with it.

Deep Dive: The Read Path, Caching, and 301 vs 302

Caching the redirect

Mappings are immutable (a short code always points to the same URL), which makes them ideal cache entries. A Redis/Memcached tier in front of the database absorbs the overwhelming majority of reads:

def resolve(short_code):
    long_url = cache.get(short_code)          # ~90%+ hit rate
    if long_url is None:
        long_url = db.get(short_code)         # miss → DB
        if long_url:
            cache.set(short_code, long_url, ttl=86400)
    return long_url

With a hot set of popular links, cache hit rates above 90% are normal, so the database sees only a trickle of the 100K reads/sec.

301 vs 302 — a real trade-off

The redirect status code is a genuine design decision, not a detail:

If analytics matter (bit.ly’s whole business), use 302 so every click flows through your system. If you only care about raw redirect speed and cost, 301 lets the client cache it.

Click analytics (stretch)

For counting clicks, do not update a counter synchronously on the hot path. Emit a click event to a queue (Kafka) and aggregate asynchronously, so analytics never slow down the redirect.

Deep Dive: Custom Aliases, Expiry, and Scale

Custom aliases. When a user supplies their own code (bit.ly/my-launch), you do need a uniqueness check — attempt an insert with the alias as the primary key and fail if it already exists. Keep custom and generated codes in the same table; generated codes come from the ID space, custom ones from user input.

Expiry. Store expires_at and check it on read (treat an expired link as a 404). A background job (or a database TTL, if supported) reclaims expired rows. Expired codes can even be recycled back into the key pool.

Scale-out. The database shards cleanly on short_code (hash partitioning), and the stateless API tier scales horizontally behind a load balancer. The cache tier scales independently. Because there are no joins or cross-key transactions, this system scales almost linearly — the only shared chokepoint is the ID generator, which you remove with ID ranges or Snowflake.

Key Takeaways

The URL shortener rewards clarity over cleverness. Nail the base62 math, explain why unique-ID beats hashing (no collision checks), optimize the read path with caching, and raise the 301-vs-302 trade-off unprompted — that combination is what separates a strong answer from a merely correct one.