Q62 — Design a URL shortener

What the system must do

A user submits a long URL. The system returns a short URL (e.g., sho.rt/xK3p2). Anyone who visits the short URL is redirected to the original long URL. That's it. Deceptively simple — but each piece hides depth.

Functional requirements:

• POST /shorten → takes a long URL, returns a short URL
• GET /:code → redirects to the original URL
• (Optional) custom aliases, expiry, analytics

Scale targets to reason about: 100M URLs created per day, 10B redirects per day (100:1 read-write ratio). Redirects are the hot path — they must be sub-20ms.

The core problem: generating a short code

The short code (xK3p2) must be unique across all shortened URLs and compact enough to be short. How do you generate it?

Option A: Hash the URL. Take MD5 or SHA-256 of the long URL, take the first 6 characters of the base62-encoded hash. Problem: collisions (two different URLs might produce the same 6 characters). Resolution: detect collision, append suffix, retry. Problem 2: the same URL always produces the same hash — convenient, but means you need to deduplicate (store hash → URL, check before inserting). At 100M URLs/day, deduplication is a meaningful extra lookup.

Option B: Generate a random 6-character base62 code. 62^6 ≈ 56 billion unique codes. At 100M/day, this lasts ~560 days before exhaustion — too short. 62^7 ≈ 3.5 trillion → 95 years at this rate. Random generation + collision check in the database (unique constraint) works but every insert needs a uniqueness check.

Option C: Use a distributed ID generator (Snowflake — Q61), then base62-encode the ID. Generate a 64-bit ID, encode in base62 → 7-10 characters. IDs are guaranteed unique without collision checking. IDs are monotonically increasing, so codes are approximately time-ordered. This is the cleanest approach at scale: no collision checking, no deduplication lookups, globally unique, and sequential database inserts (efficient B-tree use).

The Snowflake approach: code = base62(snowflake_id). At 7 characters, a Snowflake ID encodes as a URL-safe string that's unique by construction.

Data model

One table dominates everything:

CREATE TABLE urls (
  id         BIGINT PRIMARY KEY,       -- Snowflake ID
  code       VARCHAR(10) UNIQUE NOT NULL, -- base62(id)
  long_url   TEXT NOT NULL,
  created_at TIMESTAMPTZ NOT NULL,
  expires_at TIMESTAMPTZ,              -- optional TTL
  user_id    BIGINT                    -- optional
);

The code column is the lookup key for redirects. One index on code for the redirect path.

The redirect path — and why it must be cached

Every redirect is: GET /xK3p2 → look up xK3p2 in the database → return 301/302 to long_url.

At 10 billion redirects per day = 115,000 redirects/second. A database cannot handle 115,000 queries/second on a single table, especially with the read-your-own-writes latency of a primary database.

The redirect path must be cached. Redis is the right tool: store code → long_url with a TTL matching the URL's expiry (or a default like 24 hours).

Cache-aside pattern (Q17):

1. Client requests GET /xK3p2
2. Server checks Redis: GET xK3p2
3. Cache hit → return redirect immediately. ~1ms latency.
4. Cache miss → query database → write to Redis → return redirect. ~10ms.

With 100:1 read-write ratio and hot URL skew (popular URLs get orders of magnitude more hits), cache hit rates will be >99% for the hot set. The database serves only cold or uncached URLs.

301 vs 302 redirect — a deliberate trade-off

301 Permanent redirect: the browser caches it. Future visits to the short URL skip the server entirely — the browser goes directly to the long URL. Reduces load dramatically for popular URLs.

302 Temporary redirect: the browser does not cache. Every visit hits the server.

If you want accurate analytics (counting every redirect hit), use 302 — 301 would cause repeat visitors to bypass the server and you'd miss counting them. If analytics don't matter and you want minimal server load, use 301. Most URL shorteners use 302 for this reason.

Scaling the write path

100M URL creations per day = 1,150 writes/second. This is easily handled by a single database with connection pooling. Sharding is not needed at this scale — but if it were, shard by code hash (so redirects route to the correct shard) or use a single ID generation service (Snowflake worker) and a partitioned table.

The write path also publishes to the outbox (Q49) for analytics events: "this URL was created by this user at this time."

Analytics

If you need to track clicks: on every redirect, publish an event (user agent, IP, referrer, timestamp, code) to Kafka asynchronously. A stream processor consumes and aggregates. The redirect itself is never slowed by analytics — fire and forget.

The mental model

Core flow:
  POST /shorten: generate code (Snowflake ID → base62) → store in DB → return short URL
  GET /:code: Redis lookup → cache hit: redirect; miss: DB lookup → cache → redirect

Data model:
  urls(id BIGINT PK, code VARCHAR UNIQUE, long_url TEXT, expires_at, user_id)
  One index on code — the entire redirect path

Code generation: Snowflake ID → base62 → 7-10 chars, unique by construction, no collision check

Redirect caching:
  115K redirects/sec → must be Redis (not DB)
  Cache hit rate >99% for hot URLs
  TTL matches URL expiry

301 vs 302:
  301: browser caches → less server load, no analytics accuracy
  302: every hit reaches server → accurate analytics → most URL shorteners use 302

Analytics: async Kafka publish on redirect → stream processor → analytics store

Scale numbers:
  Writes: 1.1K/sec → single DB fine
  Reads: 115K/sec → Redis required
  Storage: 100M URLs/day × 365 × ~500 bytes ≈ 18TB/year (cold storage OK)

A URL shortener is deceptively simple: the interesting problems are the code generation strategy (collision avoidance vs. sequential IDs), the redirect caching architecture (the read path is the entire business), and the 301 vs 302 decision (which trades analytics accuracy for load reduction).