Design TinyURL — URL Shortening Service

URL shortening services convert a long URL like https://www.example.com/some/very/long/path?with=many&query=params into a short alias like http://tinyurl.com/abc123. Use cases include saving space in social media posts, tracking click analytics, hiding affiliate links, and making URLs human-readable. The service must redirect users instantly and handle billions of short URLs while keeping the system highly available.

Functional requirements: (1) Given a URL, generate a unique short alias. (2) When the short alias is visited, redirect to the original URL. (3) Links can optionally expire after a user-defined timespan. Non-functional requirements: High availability (redirection must always work), low latency redirects (<100ms), URLs should not be predictable.

Traffic estimates: Assume 500M new URL shortenings per month with a 100:1 read/write ratio, giving 50B redirects/month. That's ~200 writes/sec and 20,000 reads/sec. Storage: if each entry is ~500 bytes and we store 5 years of data, we need 500M × 12 × 5 × 500B ≈ 15 TB. Bandwidth: 200 × 500B = 100 KB/s inbound; 20,000 × 500B = 10 MB/s outbound.

Option 1 — Encoding the URL with MD5 or SHA256: Hash the full URL, take the first 6 characters of the Base64-encoded hash. Problem: different users shortening the same URL get the same key; appending user ID or timestamp fixes uniqueness but adds complexity, and we must check DB for each collision.

Option 2 — Key Generation Service (KGS): A standalone service pre-generates random 6-character strings (Base62: a-z, A-Z, 0-9 = 62^6 ≈ 56 billion keys) and stores them in a database with two tables: unused_keys and used_keys. When a new short URL is needed, the app server calls KGS which atomically moves a key from unused to used and returns it. KGS can load a batch of keys into memory to serve requests without hitting the DB each time. KGS is the single point of failure — solve with a standby replica that takes over if the primary dies. This approach eliminates collision checks entirely.

We need two tables: (1) URL table: short_key (PK, varchar 6), original_url (varchar 512), user_id, created_at, expiry_date. (2) User table: user_id (PK), name, email, created_date.

Since we need to store billions of rows with no complex joins and reads dominate, NoSQL (like Cassandra or DynamoDB) is a better fit than RDBMS. We shard by short_key hash across multiple database servers. Each shard owns a range of keys; consistent hashing ensures minimal resharding when adding nodes.

Cache the 20% most-frequently accessed URLs (80-20 rule). Use Memcached or Redis with LRU eviction. Cache size: 20% × 20,000 requests/sec × 500 bytes × 86,400 sec ≈ 170 GB. Multiple cache servers share this load.

Redirect flow: (1) User visits short URL → hits load balancer → app server. (2) App server checks cache; if hit, return 302 redirect. (3) On cache miss, query DB, populate cache, return 302. Use 302 (temporary) rather than 301 (permanent) redirect so browsers always hit the server — this preserves analytics. Use 301 for lower server load when analytics are not needed.

Expired links should be deleted to free up keys. A lightweight background cleanup service runs periodically (daily) and deletes rows where expiry_date < now(), returning their keys to the unused_keys pool in KGS. Lazy deletion is also acceptable: check expiry on each request and return 404 if expired. For very popular links, do not delete immediately — serve from cache for a short grace period.

Application tier is stateless — add more app servers behind a load balancer to scale horizontally. Database tier uses sharding (consistent hashing) plus read replicas per shard. Cache tier uses multiple Memcached nodes. KGS has a hot standby. Use CDN to cache redirect responses at edge nodes for globally low-latency access. Telemetry: log every redirect with country, referrer, and browser — analytics service reads from a separate replica.