Case Study: Design URL Shortener

Let us apply all the system design concepts we have learned to design a real-world system: a URL Shortener like bit.ly or tinyurl.com.

Step 1: Requirements Clarification

Functional Requirements:

1. Given a long URL, generate a short, unique alias URL.
2. When a user clicks the short URL, redirect them to the original long URL.
3. Short links should expire after a configurable time (optional).

Non-Functional Requirements:

• The system should be highly available. If the redirection service is down, millions of short links on the Internet break.
• Redirection should happen in real-time with minimal latency (under 50ms).
• Short URLs should not be predictable (for security).

Step 2: Back-of-the-Envelope Estimation

• Assume 500 million new URL shortenings per month.
• Read-to-write ratio: 100:1 (100 redirections for every 1 new URL created).
• Reads: 50 billion redirections/month = ~19,000 reads/second.
• Storage: If each URL entry is ~500 bytes, and we store URLs for 5 years: 500M/month * 12 * 5 * 500 bytes = ~15 TB of storage.

Step 3: High-Level Design

API Design:

• POST /shorten - Takes a long URL, returns a short URL.
• GET /{shortCode} - Redirects to the original long URL (HTTP 301 or 302).

Short URL Generation:

A 7-character string using Base62 encoding (a-z, A-Z, 0-9) gives 62^7 = 3.5 trillion possible unique codes.

Approach 1: Hash-Based Hash the long URL using MD5 or SHA-256, take the first 7 characters. Risk of collision (two different URLs producing the same hash). Must check for and resolve collisions.

Approach 2: Counter-Based (Preferred) Use a globally unique counter (like a distributed ID generator or Twitter's Snowflake) to generate a unique integer. Convert the integer to a Base62 string. Guaranteed uniqueness.

Architecture:

1. Load Balancer distributes incoming requests across multiple Application Servers.
2. Application Servers handle the shortening and redirection logic.
3. Database stores the mapping between short codes and long URLs. Use a NoSQL key-value store like DynamoDB or Cassandra for blazing-fast lookups by key.
4. Cache (Redis) sits in front of the database. The most popular short URLs (top 20% of traffic) are cached in memory for sub-millisecond redirection.

Step 4: Deep Dive

Caching Strategy:

Use an LRU cache. When a redirection request arrives:

1. Check Redis cache. If found (Cache Hit), redirect immediately.
2. If not found (Cache Miss), query the database, store the result in Redis, then redirect. Since 20% of URLs generate 80% of traffic (Pareto principle), the cache hit rate should be extremely high.

Database Choice:

A key-value NoSQL database (DynamoDB, Cassandra) is ideal because:

• Every query is a simple key lookup (shortCode -> longURL). No complex JOINs needed.
• NoSQL scales horizontally with ease.
• Massive write throughput for URL creation.

Analytics:

Log every redirection event asynchronously to a message queue (Kafka). A separate analytics service consumes these events to compute click counts, geographic data, and referrer statistics without impacting the real-time redirection performance.