Architecture Case Studies

Scale analysis:
  Writes: 10M/day = 115 writes/sec (very manageable)
  Reads:  500M/day = 5,800 reads/sec (6,000 redirects every second!)
  Ratio:  50:1 reads-to-writes → heavily read-optimized

Hot path: the redirect (must be < 10ms)
  GET /abc123 → 301 https://your-long-url.com/...
  This is called billions of times. Every millisecond matters.

Architecture:
  Short URL format: 7 characters [a-z, A-Z, 0-9] = 62^7 = 3.5 trillion combos
  
  Redirect path:
    1. Read short code from URL path (/abc123)
    2. Redis.get("url:abc123") → cache hit? Return 301. Done!
    3. Cache miss → PostgreSQL lookup → cache result → return 301

  Write path:
    1. Receive long URL
    2. Generate unique short code:
       Option A: Base62 encode auto-increment DB ID (simple, no collision)
       Option B: Murmur hash of URL + truncate to 7 chars (need collision check)
       Option C: Pre-generate codes in bulk, pop from a pool table
    3. INSERT INTO urls (short_code, long_url, user_id, created_at)
    4. Return short URL

Cache sizing:
  Top 20% of URLs serve 80% of traffic
  500M × 20% × (7 + 100 bytes) = ~10 GB Redis cache
  → Single Redis node handles all hot URL lookups

Two valid approaches — with different tradeoffs:

Option 1: Always create unique short codes
  Pros:
    - Simple, no deduplication logic
    - Multiple tracking links for same destination (A/B testing)
    - No hash collisions to handle
  Cons:
    - Same URL has many short codes → wasted storage
    - User can't reuse their link for the same destination

Option 2: Deduplicate by URL (Bit.ly's approach for logged-in users)
  Implementation:
    CREATE UNIQUE INDEX ON urls(user_id, long_url_hash);
    -- long_url_hash = SHA-256 of long URL (for fixed-length indexing)
    
    On conflict:
    INSERT INTO urls (short_code, long_url_hash, user_id) VALUES (...)
    ON CONFLICT (user_id, long_url_hash) DO UPDATE SET updated_at = NOW()
    RETURNING short_code;
    
    → Atomic upsert — no race condition, no distributed lock needed

Short code generation — the right approach:
  Auto-increment ID → Base62 encode:
    ID: 1        → "000001"
    ID: 125      → "000021" (5 × 25 + 0)
    ID: 1,000,000 → "4c92"
  
  Advantages:
  - No collisions by definition (IDs are unique)
  - No need to check if code already exists
  - Deterministic, debuggable

  Distributed ID generation (for multi-server):
  - Snowflake ID: 64-bit = 41-bit timestamp + 10-bit machine ID + 12-bit sequence
  - Each server generates unique IDs without coordination

Fan-out on Write (push model):
  Celebrity tweets:
  → Worker reads 100M follower IDs
  → Writes tweet_id to each follower's Redis feed list: LPUSH feed:user_123 tweet_id
  → Each user's feed: pre-computed, read is O(1) cache lookup
  
  Problem: 100M followers × write latency → tweet delivery takes hours!
  Worse: Lady Gaga + BTS both tweet simultaneously → millions of writes at once

Fan-out on Read (pull model):
  User requests feed:
  → Fetch IDs of everyone they follow
  → SELECT * FROM tweets WHERE author_id IN (follow_ids) ORDER BY time LIMIT 20
  
  Problem: User follows 500 people → 500 DB queries per feed load → slow!
  Worse: celebrity's 100M followers all polling → same tweet fetched 100M times

Twitter's actual solution (hybrid):
  Regular users (< 1M followers): fan-out on write
    Fast reads: feed is pre-built in Redis
    Acceptable write load: 1M writes is manageable
  
  Celebrities (> 1M followers): fan-out on read
    Their tweets are NOT pre-pushed to feed caches
    At read time: your pre-built feed + celebrity tweets fetched separately
    Cached at tweet level: tweet_data:tweet_id → same data reused for all 100M readers

Feed assembly at read time:
  pre_built_feed = Redis.lrange("feed:#{user_id}", 0, 20)  # non-celebrity follows
  celeb_tweets   = fetch_celeb_tweets(user's celebrity follows, limit=20)
  merged_feed    = merge_and_sort(pre_built_feed, celeb_tweets, limit=20)