Design a URL Shortener

Problem Requirements & Estimation

A URL shortener (like bit.ly) maps a long URL (e.g., a 200-character link) into a short alias (e.g., https://tiny.com/aBc123xyz). Let's establish basic parameters for the interview:

• Scale: 100 million write operations (new short URLs) per day.
• Read-to-Write Ratio: Highly read-heavy. Let's assume 10:1 reads to writes (1 billion reads per day).
• Write throughput: 100M / 86400 seconds ≈ 1,160 writes/sec.
• Read throughput: 1B / 86400 seconds ≈ 11,600 reads/sec.
• Storage Math: 100M writes/day * 365 days * 10 years = 365 billion records. If each record (long URL + short hash) is 500 bytes, total storage required over 10 years is 365B * 500 bytes ≈ 182.5 Terabytes.

Redirection Mechanics: 301 vs 302

When a user visits a short URL, the server responds with a redirect status code. Which one you choose is a vital design trade-off:

Client's browser caches the redirect mapping. 
Subsequent requests bypass the shortener server 
completely, loading the long URL from cache.

✓ Reduces traffic load on your servers.
✗ Prevents real-time analytics collection 
  (clicks, location) after the first request.

Browser always sends the request to the 
shortener server first. The server then returns 
the 302 with the Location header.

✓ Enables accurate click tracking & analytics.
✗ Increases latency and request volume on your 
  servers.

Two Hashing Strategies

Option 1: Hashing with Collision Resolution

Take the long URL, compute a cryptographic hash (like MD5 or SHA-1), and pick the first 7 characters.
The collision issue: Different long URLs can yield the same 7-character hash.
Resolution: If a collision is detected in the database, append a predefined unique salt string to the long URL and re-hash. This requires checking the database on every write, adding write latency.

Option 2: Base62 Encoding with Unique ID generator

Use a distributed ID generator (e.g. Snowflake IDs or Flickr ticket server) to generate a unique 64-bit integer ID for each new URL. Then, convert that base-10 number to a base-62 string.
Base62 uses: [0-9], [a-z], [A-Z] (10 + 26 + 26 = 62 possibilities).
A 7-character Base62 string allows 62⁷ ≈ 3.5 trillion unique URLs, which easily fits our 10-year storage requirements.

System Architecture

Optimizing Redirections with Caching:

Since this is a read-heavy system (reads/writes = 10:1), we cache the mapping of short_hash → long_url in Redis.
Write path: When a new short link is created, save it to the database, and write to Redis optionally (or let it load on the first read).
Read path: The API first checks Redis. If it's a hit, return 302 immediately. On a cache miss, query the DB, store it in Redis, and return.