How would you design a URL shortener service that handles 100M+ URLs with sub-100ms redirect latency?

High-Level Architecture

Client → Load Balancer → API Servers → Cache (Redis) → Database
                ↓
           CDN (for analytics)

---

1. URL Key Generation

Option A: Base62 Encoding of Auto-Increment ID

ID: 1 → Key: "1"
ID: 1000000 → Key: "4c92"  
ID: 3521614606208 → Key: "zzzzzzzz" (8 chars = 218 trillion keys)

Pros: Simple, guaranteed unique, sortable Cons: Predictable (competitor can estimate total URLs)

Option B: Pre-generated Key Pool (Recommended)

# Key Generation Service (KGS)
# Pre-generates millions of keys, stores in two tables:
# - available_keys
# - used_keys

CHARS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
KEY_LENGTH = 7  # 62^7 = 3.5 trillion unique keys

KGS runs as a separate service, hands out key ranges to API servers. Each API server gets a batch of 10K keys and uses them locally. No coordination needed.

Why this is better:

• No single point of failure (each server has a local key pool)
• Keys are random-looking (can't estimate total count)
• No distributed lock contention

---

2. Database Selection

Write Path (creating short URLs)

MongoDB or PostgreSQL with sharding:

-- PostgreSQL schema
CREATE TABLE urls (
    id BIGSERIAL,
    short_key VARCHAR(7) UNIQUE,
    original_url TEXT NOT NULL,
    created_at TIMESTAMP DEFAULT NOW(),
    expires_at TIMESTAMP,
    click_count BIGINT DEFAULT 0
);
CREATE INDEX idx_short_key ON urls(short_key);

Read Path (redirecting)

Redis as the primary read store. Every redirect hits Redis first.

Redis: short_key → original_url
TTL: 24 hours (or URL's expiry time)

---

3. Handling Read-Heavy Traffic (1000:1 ratio)

Layer 1: Client-side caching

Cache-Control: public, max-age=300
Location: https://original-url.com

Layer 2: CDN edge caching

• Cloudflare/Fastly caches redirects at the edge
• 90%+ of redirects never hit your servers

Layer 3: Redis cluster

• Hot keys cached in Redis with 99%+ hit rate
• GET abc123 → https://original-url.com in <1ms

Layer 4: Database (only for cache misses)

• Read replicas for horizontal scaling
• Sharded by short_key hash

---

4. Viral URL Handling

When a URL "goes viral" (millions of hits/min):

Thundering Herd Problem

If 10K requests hit simultaneously and the key is expired from cache, all 10K would try to fetch from DB.

Solution: Cache Warmup + Request Coalescing

// Using singleflight pattern
const inflightRequests = new Map();

async function getUrl(key: string): Promise<string> {
    // Check cache first
    const cached = await redis.get(key);
    if (cached) return cached;

    // If another request is already fetching this key, wait for it
    if (inflightRequests.has(key)) {
        return inflightRequests.get(key);
    }

    // This request fetches from DB
    const promise = db.query('SELECT original_url FROM urls WHERE short_key = $1', [key])
        .then(result => {
            redis.setex(key, 86400, result.original_url);
            inflightRequests.delete(key);
            return result.original_url;
        });

    inflightRequests.set(key, promise);
    return promise;
}

Rate Limiting

• Per-IP rate limit: 100 req/min
• Global rate limit on write endpoint: 10K req/min
• Return cached redirect for reads regardless of rate

---

5. Data Modeling for Scale

Sharding Strategy

Shard = hash(short_key) % num_shards

Each shard is independent — can be on different servers/regions.

Hot Partition Mitigation

If one shard gets too hot (viral URL), use consistent hashing to redistribute.

---

6. Capacity Estimation

Metric	Value
Total URLs	100M
URL size (avg)	200 bytes
Total storage	~20 GB (easily fits on one server)
Short key size	7 bytes
Cache entry size	~210 bytes
Cache for hot 1M URLs	~200 MB
QPS (reads at peak)	~11,500/sec

At this scale, one Redis node + one DB primary + 2 replicas handles everything comfortably.

---

Summary

Component	Technology	Why
Key Generation	Pre-generated pool (KGS)	No coordination, no contention
Database	PostgreSQL (sharded) or MongoDB	Strong consistency for writes
Cache	Redis Cluster	Sub-ms reads for redirects
CDN	Cloudflare	Edge caching, DDoS protection
Load Balancer	Nginx/HAProxy	Distribute traffic
Monitoring	Prometheus + Grafana	Latency tracking at p99