Design a URL Shortener (TinyURL / bit.ly)

medium

Scale: 10K writes/s sustained; 1M reads/s peak Storage: ~500 B/URL × 100B = 50-200 TB lifetime Bit.ly, Twitter (t.co), Google

Case StudyKey GenerationKV Store

A URL shortener takes a long URL and returns a short alias; visits to the alias HTTP-redirect to the original. The interview value is in the classic distributed-systems skills it exercises: capacity estimation, key generation, read-heavy caching, and abuse defense at billions-of-rows scale.

Scale10K writes/s sustained; 1M reads/s peak

Storage~500 B/URL × 100B = 50-200 TB lifetime

Key Concepts

1. The numbers shape the design. Assume 100M new URLs/day → ~1,200 writes/s sustained, ~10-30K/s peak. Reads are 100-1000x writes: 1B redirects/day → ~12K reads/s sustained, ~120K-1M peak. Storage per URL ~500 B → ~180 GB/yr → ~50 TB at 10 yr. Dominant goal: keep the redirect under 50 ms p99 globally.

1. The numbers shape the design.

2. Key generation: counter or hash. Counter: ZooKeeper / etcd hands out ranges of N IDs to each shortener instance; encode to base62 (7 chars = 62^7 ≈ 3.5T URLs). Predictable enumeration risk — mitigate with random shuffling or salt. Hash: SHA256(url + salt)[:7] in base62 — idempotent (same URL → same key), collisions need retry. Production designs often mix: counter for auto-generated, reservation for custom aliases.

2. Key generation: counter or hash.SHA256(url + salt)[:7]

3. Read path is mostly cache. Edge CDN caches the 301/302 response → most redirects never reach your origin. Regional Redis warms the long tail. Primary KV (DynamoDB, Cassandra, sharded Postgres) holds the cold canonical data. Zipfian access distribution makes a tiny cache (5-10 GB) handle 80%+ of traffic.

3. Read path is mostly cache.

4. The hot-path details that matter. 301 vs 302: 301 caches downstream aggressively (faster), 302 keeps every redirect flowing through your stack (analytics, change destination later). Pick 302 if you need both. Analytics async via Kafka — never block the redirect with a synchronous DB write. Abuse defense (phishing, malware): check submissions against Safe Browsing, soft-delete flagged URLs (respond 410 Gone), rate-limit creation per IP/user. Custom aliases: atomic reservation with conditional put (INSERT IF NOT EXISTS or SETNX).

4. The hot-path details that matter.SETNX

5. Component map. API gateway + rate limiter → URL service → key generator → KV store. CDN/edge in front of redirect. Kafka click stream → ClickHouse / Druid for analytics. Admin tools for revoke / expire. Production references: Bit.ly, Twitter t.co, TikTok vm.tiktok.com — all variants of this design.

5. Component map.

High-level design

Write path: client → API gateway → URL service → key generator → KV store → return short URL.
Read path: client → CDN/edge (cache check) → API gateway → URL service → KV store → 302 redirect.
Async: click events → Kafka → aggregator → analytics store.
Abuse: URL submission → safe browsing check → tag/block as needed.
Edge: CDN caches both the create response and the redirect.

Key generation

Counter-based: ZooKeeper/etcd hands out 1M-ID ranges to each shortener instance. Instance encodes counter to base62 (7 chars = 62^7 ≈ 3.5T). Predictable, mitigated by random shuffling or salt.

Hash-based: SHA256(url + salt)[:7] in base62. Idempotent — same URL gives same key. Collisions are rare but real; retry with extended hash or increment.

Hybrid (production-grade): batched ranges + hash for custom aliases.

Reservation for custom: conditional put — fail if taken.

Components

API gateway with rate limiter (per IP, per API key).
Key generator service (counter or hash).
KV store (DynamoDB, Cassandra, or sharded Postgres) keyed by short alias.
Edge cache (Cloudflare, Fastly) on the 302 redirect.
Redis warm-tier cache for very hot links.
Kafka + analytics pipeline (Spark / Flink → ClickHouse).
Abuse / phishing filter (Safe Browsing API).
Admin tools: revoke, expire, search.

Trade-offs

Counter vs hash: counter is predictable but coordinates well; hash is idempotent but collisions need retry.

301 vs 302: 301 caches more aggressively downstream (faster). 302 keeps requests flowing through your stack (better analytics, ability to change destination).

In-band vs async analytics: in-band is simple but slows the hot path. Async via Kafka is the production answer.

Sharded SQL vs KV: SQL gives joins and ad-hoc queries (helpful for ops); KV scales further with simpler ops.

Custom aliases vs auto-generated: customs need reservation; auto avoids collisions trivially.

Scale numbers

100M new URLs/day = 1200 writes/s sustained, ~30K/s peak.
1B reads/day = 12K reads/s sustained, ~1M/s peak.
Storage: 500 B/row × 100B rows × 10 yr = ~180 TB raw, ~500 TB with replicas. Easily holds in a 10-20 shard KV.
Cache hit rate (Zipfian): 5-10 GB of hot data handles 80%+ of redirects.

Common pitfalls

Synchronous click count update on every redirect. Hammers the DB.
301 with frequently changing destinations. Downstream caches break the change.
No abuse check on submission. Become a phishing relay overnight.
Counter without sharding. Single global counter is a bottleneck.
No edge cache on the redirect. Origin sees 100% of traffic.