Designing a URL Shortener (TinyURL/Bit.ly)

This is a classic system design question. It seems simple, but scaling it to handle billions of links reveals interesting challenges in ID generation and concurrency.

1. Requirements

Functional

1. Shorten: Given a long URL, return a unique short alias (e.g., http://tiny.url/j7d92).
2. Redirect: Clicking the short URL redirects to the original.
3. Expiry: Links might expire after a set time.
4. Custom Alias: Users should be able to pick http://tiny.url/MyResume.

Non-Functional

1. Read Heavy: Ratio is likely 100:1 (100 redirects for every 1 new link creation).
2. Low Latency: Redirect should take < 20ms.
3. High Availability: If the redirect fails, the internet feels "broken".

2. Capacity Estimates

Assumptions:

• 100 Million new URLs per month.
• 5 Year retention.
• Total URLs = 100M * 12 * 5 = 6 Billion.

Storage Calculation

• Average URL length = 100 bytes.
• 6 Billion * 100 Bytes = 600 GB.
• This fits easily into a modern distributed database (Cassandra/DynamoDB) or even a sharded SQL setup.

3. The Core Algorithm: Generating Short IDs

We need a 7-character string. [a-z, A-Z, 0-9] gives us 62 characters. $62^7 \approx 3.5 \text{ Trillion combinations}$. This is plenty sufficient for our 6 billion target.

Approach 1: Hashing (MD5/SHA256)

Calculate Hash(Long_URL) -> MD5("google.com") = 5d41402abc4b2a76b9719d911017c592. Take the first 7 characters: 5d41402.

• Problem (Collision): What if two URLs hash to the same first 7 chars?
• Fix: Check DB. If exists, append a salt and re-hash. This creates extra DB latency.

Approach 2: Online ID Generator (UUID)

Generate a UUID: f47ac10b-58cc-4372-a567-0e02b2c3d479.

• Problem: Too long (36 chars). Even if we base62 encode it, it's still too long for a "short" URL.

Approach 3: Offline ID Generator (Key Generation Service - KGS)

This is the preferred approach. We don't need to generate IDs on the fly. We can pre-generate them.

1. KGS: A standalone service generates 6-character strings offline and puts them into a "Unused IDs" database or queue.
2. App Server: When a user shortens a URL, the server pops a key from the "Unused IDs" queue.
3. Assignment: Assign the Key to the URL and write to the "Used IDs" table.

• Pros: Zero collision probability. Extremely fast.

Approach 4: Counter-Based (Base62 Encoding)

If we use a database AUTO_INCREMENT ID, we get a unique integer. ID = 10 -> a ID = 1000000 -> 4c92 ID = 999999999 -> buh84x

• Distributed Counter: In a distributed system, a single MySQL auto-increment fails.
• Solution: Use Zookeeper to assign ranges.
  • Server A: Claim range 1 - 1,000,000
  • Server B: Claim range 1,000,001 - 2,000,000
  • Each server increments in memory. No collision.

4. Redirects: 301 vs 302

When sending the user to the destination, which HTTP status code do we use?

301 Moved Permanently

• Behavior: Browser caches the response.
• Pros: Fastest for user. Reduces load on our server.
• Cons: No Analytics. We don't know the user clicked a second time because the browser handles it locally.

302 Found (Temporary Redirect)

• Behavior: Browser always hits our server first.
• Pros: Full Analytics. We can track click location, time, device.
• Cons: Higher server load and slight latency increase.
• Verdict: Use 302 if you sell analytics (Bit.ly business model). Use 301 if you just want to save money.

5. Storage Layer

Since we need massive read scales and key-value lookups:

• Redis: Place a Cache in front of the DB. 20% of links generate 80% of traffic. Evict using LRU.
• Database:
  • Cassandra (Wide Column): Great for massive writes.
  • DynamoDB: Managed, scales automatically.
  • SQL (Sharded): Valid choice if using Counter-based ID generation.

Summary

1. ID Gen: Base62 conversion of a unique distributed counter (Zookeeper ranged).
2. DB: DynamoDB or Cassandra.
3. Cache: Redis (LRU) for hot links.
4. Redirect: 302 for analytics, 301 for speed.