Classic Case Studies

Design a URL Shortener

Watch: "Beginner System Design Interview: Design Bitly w/ a Ex-Meta Staff Engineer" — Hello Interview Notes in Google Drive ↗

In simple words

A cloakroom token: you hand over your long coat (the long URL) and get a small numbered token (the short code). Anyone with the token gets your coat back instantly. The whole design is about handing out unique tokens fast and finding coats even faster.

Problem Statement

Design a service like TinyURL or bit.ly: users submit a long URL and get back a short one (sho.rt/aZ3kQ9). Anyone opening the short URL is redirected to the original. It is a small problem with a very read-heavy, latency-sensitive path, which makes it the classic warm-up for the whole method.

Functional Requirements

Create a short URL for a long URL; optionally a custom alias (sho.rt/my-sale).
Redirect a short URL to its long URL.
Optional expiry time per link.
Basic click analytics (count per link, per day).
Out of scope: user accounts UI, link editing, QR codes.

Non-Functional Requirements

Low latency redirects: p99 under ~50 ms (excluding the user's network).
High availability for redirects: a dead link breaks every page that embedded it. Creation can be slightly less available.
Uniqueness: one short code must never map to two URLs.
Unpredictable codes (so links can't be enumerated), and durability for years.

Scale assumptions
  100M new links/month       -> ~40 writes/s  (peak ~100/s)
  read:write = 100:1         -> ~4,000 redirects/s (peak ~10K/s)
  record ~ 500 B             -> 100M x 500 B = 50 GB/month, ~6 TB over 10 years
  links over 10 years        -> ~12 billion -> code space must exceed that

Code length with base62 (a-z, A-Z, 0-9):
  62^6 ~ 57 billion   62^7 ~ 3.5 trillion   -> 7 chars leaves huge headroom

Core Entities

ShortLink: short_code (unique), long_url, created_at, expires_at, owner_id.
User (creator, for quotas and ownership).
ClickEvent: short_code, timestamp, referrer, country (aggregated into daily counts).

API Design

POST /v1/links
  { "long_url": "https://...", "alias": "my-sale"?, "expires_at": "..."? }
  -> 201 { "short_url": "https://sho.rt/aZ3kQ9", "code": "aZ3kQ9" }
  -> 409 if the alias is taken

GET /{code}
  -> 302 Found, Location: https://original.example/...   (or 301, see below)
  -> 404 if unknown, 410 if expired

GET /v1/links/{code}/stats  -> { "clicks": 1234, "by_day": [...] }

High-Level Design (HLD)

Rare writes and very frequent reads take separate paths; clicks are counted asynchronously.

             create                          redirect
client --> LB --> Link service              client --> LB --> Redirect service
                   |  1. validate URL                         | 1. cache.get(code)
                   |  2. get unique id                        | 2. miss -> DB read
                   |     (ID generator / ranges)              | 3. 302 Location
                   |  3. write DB                             | 4. emit click event
                   v                                          v
             [ DB: code -> long_url ] <----------------- [ Redis cache ]
                                                              |
                            [ queue ] <-- click events -------+
                                |
                        [ analytics workers ] -> daily counters

Two separate paths: rare writes and very frequent reads, scaled independently.
A cache in front of the database absorbs most redirects (popular links are read over and over).
Click tracking is asynchronous: the redirect never waits on analytics.

Low-Level Design (LLD)

A leased counter block gives unique ids; a reversible scramble + base62 turns them into short, unguessable codes.

Generating the short code

Option A: hash the URL (MD5/SHA) and take 7 base62 chars
  + same URL -> same code (natural dedup)
  - collisions: must check the DB and re-hash with a salt on conflict

Option B: unique counter -> base62            (chosen)
  id = next_id()          # e.g. 125_000_000_001
  code = base62(id)       # 7 chars at this range
  + no collisions by construction, no read-before-write
  - sequential ids are guessable -> scramble first:
    code = base62(permute(id))   # a reversible bijection, e.g. a keyed Feistel/XOR-multiply

Where ids come from: each Link service instance leases a block of 10,000
ids from a counter (a DB row updated with UPDATE ... RETURNING, or ZooKeeper),
then hands them out from memory. A crash wastes at most one block.

def base62(n):
    chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    s = ""
    while n: n, r = divmod(n, 62); s = chars[r] + s
    return s or "0"

Custom aliases skip the generator: insert with the alias as the key and rely on the unique constraint to reject duplicates (return 409). Reserve the alias namespace so generated codes can't collide with it (e.g. aliases must be ≥ 8 characters or contain a dash).

Data model

links
  code        VARCHAR(10)  PRIMARY KEY     -- the only lookup key on the hot path
  long_url    TEXT         NOT NULL
  owner_id    BIGINT
  created_at  TIMESTAMP
  expires_at  TIMESTAMP    NULL

click_daily
  code, day, clicks        PRIMARY KEY (code, day)

All reads are by code, there are no joins on the hot path, and data grows to a few TB: a key-value/wide-column store (DynamoDB, Cassandra) partitioned by code fits well, and so does sharded Postgres/MySQL. Either is defensible; say why.

Redirect path and caching

Cache-aside in Redis: code → long_url with a TTL; the hot set (a small fraction of links gets most clicks) fits in memory easily.
Negative caching: cache "not found" briefly so scanners hammering random codes don't reach the DB.
301 vs 302: 301 (permanent) lets browsers cache the redirect, cutting load but hiding repeat clicks from analytics and making later changes hard; 302 (temporary) keeps every click visible. Most shorteners use 302 when analytics matter.
Expiry: check expires_at on read (return 410) and purge expired rows with a background job.

Analytics

The redirect service publishes a small click event to a queue (Kafka) and returns immediately. Consumers aggregate counts per code per minute in memory and flush increments to click_daily, so the database sees batched writes instead of one per click.

Follow-up Questions

One link goes viral: 100K redirects/s for one code. What breaks?: That key's Redis shard. Replicate hot keys to several cache nodes or add a small in-process cache on each redirect server (a few seconds' TTL); the CDN can also cache the 302 response briefly.
How do you stop the same long URL creating millions of codes?: Optionally dedupe per user: a secondary index on (owner_id, hash(long_url)) returns the existing code. Global dedup isn't required (and different users may want separate analytics).
How do you prevent abuse (phishing, spam)?: Rate-limit creation per user/IP, check URLs against malware/phishing lists at creation and periodically, and allow takedown (mark the code disabled; return a warning page).
What if the ID counter service is down?: Instances keep issuing from their leased blocks, so creation continues for a while; lease blocks large enough to ride out short outages. Redirects don't depend on it at all.
Why not use the hash approach?: It works, but collisions need a DB check per create and retries, and truncating a hash to 7 characters makes collisions increasingly likely as the table grows. A counter with a scrambling bijection is collision-free by construction.