📁 topics / 01-url-shortener.md

#Design a URL Shortener (Bitly Scale)

#1. Problem Statement & Clarifications

A URL shortening service converts long URLs into short, unique aliases (e.g., short.ly/aB3xK9) that redirect users to the original URL. The system is read-heavy, latency-sensitive, and requires globally unique, non-predictable short codes.

#Functional Requirements

  1. Shorten URL — Given a long URL, generate a unique short URL (6–7 chars)
  2. Redirect — Given a short URL, redirect to the original long URL with minimal latency
  3. Custom Aliases — Users can optionally specify a custom short code
  4. Expiration — URLs can have configurable TTL (default: never expires)
  5. Analytics — Track click counts, referrer, geo, device per short URL

#Non-Functional Requirements

Requirement Target
Read Latency P99 < 10ms for redirects
Write Latency P99 < 100ms for URL creation
Availability 99.99% — redirects must always work
Scale 100M new URLs/day, 10B redirects/day (100:1 read:write)
Durability No data loss for non-expired URLs
URL Length 6–7 characters (base62)

#Out of Scope

#Assumptions

#2. Back-of-Envelope Estimation

#Traffic Estimates

New URLs/day:           100M
Redirects/day:          10B (100:1 read:write)
Write QPS (avg):        100M / 86400 ≈ 1,160 QPS
Write QPS (peak 3x):   ~3,500 QPS
Read QPS (avg):         10B / 86400 ≈ 115,740 QPS
Read QPS (peak 3x):    ~347,000 QPS

#Storage Estimates

Record size:            short_url (7B) + long_url (200B) + metadata (100B) ≈ 310B
New storage/day:        100M × 310B = 31GB/day
New storage/year:       31GB × 365 = 11.3TB/year
5-year total:           ~56.5TB
Total URLs (5yr):       100M × 365 × 5 = 182.5B URLs

#Bandwidth

Read bandwidth (avg):   115,740 × 310B = 35.9 MB/s
Read bandwidth (peak):  ~107 MB/s
Write bandwidth (avg):  1,160 × 310B = 0.36 MB/s

#Cache Estimates

Hot URLs (24h):         100M URLs × 310B = 31GB
Top 20% (Pareto):       20M × 310B = 6.2GB
Cache size:             ~30GB Redis cluster
Cache hit ratio target: 95%+ (power-law distribution)

#3. API Design

#Create Short URL

POST /api/v1/urls
Authorization: Bearer <token>    // optional for anonymous

{
  "long_url": "https://example.com/very/long/path?with=params",
  "custom_alias": "my-link",        // optional
  "expiration": "30d",              // optional: 1h|1d|7d|30d|1y|never
  "domain": "short.ly"             // optional: custom domain
}

Response 201:
{
  "short_url": "https://short.ly/aB3xK9",
  "short_code": "aB3xK9",
  "long_url": "https://example.com/very/long/path?with=params",
  "created_at": "2025-05-29T12:00:00Z",
  "expires_at": "2025-06-28T12:00:00Z"
}

Response 409: { "error": "alias_taken" }     // custom alias conflict
Response 400: { "error": "invalid_url" }

#Redirect (The Hot Path)

GET /{short_code}
Host: short.ly

Response 301 (permanent) / 302 (temporary):
Location: https://example.com/very/long/path?with=params

Response 404: { "error": "url_not_found" }

301 vs 302 decision: Use 302 (temporary) — allows analytics tracking since browsers won't cache the redirect. Use 301 only if analytics aren't needed and CDN caching is desired.

#Get URL Analytics

GET /api/v1/urls/{short_code}/stats
Authorization: Bearer <token>

Response 200:
{
  "short_code": "aB3xK9",
  "total_clicks": 45230,
  "clicks_today": 1203,
  "top_referrers": ["twitter.com", "reddit.com"],
  "top_countries": ["US", "IN", "UK"],
  "created_at": "2025-05-29T12:00:00Z"
}

#Delete URL

DELETE /api/v1/urls/{short_code}
Authorization: Bearer <token>

Response 204: No Content

#4. Data Model

#URL Mapping Store (PostgreSQL — sharded by short_code hash)

CREATE TABLE urls (
  short_code    VARCHAR(10) PRIMARY KEY,
  long_url      TEXT NOT NULL,
  user_id       BIGINT NULL,              -- NULL for anonymous
  domain        VARCHAR(100) DEFAULT 'short.ly',
  expires_at    TIMESTAMP NULL,           -- NULL = never
  created_at    TIMESTAMP DEFAULT NOW(),
  click_count   BIGINT DEFAULT 0,
  is_active     BOOLEAN DEFAULT true
);

CREATE INDEX idx_urls_user ON urls(user_id, created_at DESC)
  WHERE user_id IS NOT NULL;
CREATE INDEX idx_urls_expiry ON urls(expires_at)
  WHERE expires_at IS NOT NULL AND is_active = true;
CREATE INDEX idx_urls_long ON urls(long_url)
  WHERE is_active = true;   -- for dedup lookups

#URL Cache (Redis — cluster mode)

Key:   url:{short_code}
Value: "https://example.com/very/long/path?with=params"
TTL:   24h (LRU eviction for cold URLs)

Key:   url:clicks:{short_code}
Value: <integer counter>       -- buffered, flushed to DB periodically

#Analytics Events (Kafka → Async Processing)

{
  "short_code": "aB3xK9",
  "timestamp": "2025-05-29T12:00:00Z",
  "ip": "203.0.113.1",
  "user_agent": "Mozilla/5.0...",
  "referrer": "https://twitter.com",
  "country": "US"
}

#Access Patterns

Query Store Index/Key
Redirect: get long URL by short code Redis cache → PostgreSQL PK: short_code
Check if long URL already shortened PostgreSQL IX: long_url
List user's URLs PostgreSQL IX: user_id + created_at DESC
Record click event Kafka topic Partition by short_code
Cleanup expired URLs PostgreSQL IX: expires_at

#5. High-Level Design (HLD) & Scale Evolution

#Stage 1: MVP / Single Server (100K URLs/day)

#Stage 2: Growth Scale (10M URLs/day)

#Stage 3: Bitly Scale (100M URLs/day, 10B redirects/day)

#Architecture Diagram

                    ┌──────────────┐
                    │     CDN      │ ← Optional: cache 301 redirects at edge
                    │ (CloudFront) │
                    └──────┬───────┘
                           │
                ┌──────────▼──────────┐
                │   Load Balancer     │
                │   (L7 — Nginx)     │
                └──────────┬──────────┘
                           │
              ┌────────────┼────────────┐
              ▼            ▼            ▼
     ┌──────────────┐ ┌──────────────┐ ┌──────────────┐
     │  Redirect    │ │ URL Create   │ │ Analytics    │
     │  Service     │ │ Service      │ │ Service      │
     │              │ │              │ │              │
     │ • Cache-first│ │ • Validate   │ │ • Aggregate  │
     │ • 302 + log  │ │ • Key assign │ │ • Dashboard  │
     └──────┬───────┘ └──────┬───────┘ └──────┬───────┘
            │                │                │
       ┌────▼────┐      ┌───▼────┐      ┌────▼────┐
       │  Redis  │      │ Key Gen│      │  Kafka  │
       │  Cache  │      │ Service│      │ (clicks)│
       │ (30GB)  │      │        │      │         │
       └────┬────┘      └───┬────┘      └────┬────┘
            │               │                │
       ┌────▼───────────────▼────┐      ┌────▼──────────┐
       │     PostgreSQL          │      │  ClickHouse / │
       │     (URL mappings,      │      │  Analytics DB │
       │      sharded by code)   │      └───────────────┘
       └─────────────────────────┘

#Component Breakdown

Component Responsibility Tech Choice
Load Balancer L7 routing, SSL, rate limiting Nginx / AWS ALB
Redirect Service Cache-first URL lookup + 302 redirect + click event Go (low latency)
URL Create Service Validate URL, assign key, persist Go / Node.js
Key Generation Service Pre-generate unique base62 keys in batches Standalone + ZooKeeper
Analytics Service Consume click events, aggregate stats Python / Flink
Redis Cache Hot URL mappings; click count buffering Redis Cluster (30GB)
PostgreSQL URL mappings, user data Hash-sharded by short_code
Kafka Click event stream for async analytics Partitioned by short_code

#Data Flow

Write Path (Create Short URL):

Client → LB → URL Create Service
  → 1. Validate long URL (format, reachability check)
  → 2. Check if long URL already shortened (optional dedup)
  → 3. Fetch pre-generated key from Key Gen Service
  → 4. INSERT into PostgreSQL (short_code → long_url)
  → 5. SET in Redis cache
  → 6. Return short URL to client

Read Path (Redirect — THE hot path):

Client → LB → Redirect Service
  → 1. GET url:{short_code} from Redis
  → 2. HIT  → long_url found → skip to step 5
  → 3. MISS → SELECT from PostgreSQL → populate Redis cache
  → 4. Not found / expired → return 404
  → 5. Publish click event to Kafka (async, non-blocking)
  → 6. Return 302 redirect to long_url

#6. Deep Dive — Core Components

#Key Generation Service — Detailed Design

Approach Pros Cons
Auto-increment + Base62 Simple, unique Predictable, single-point bottleneck
MD5/SHA hash → truncate Deterministic Collision risk at 6-7 chars
Random Base62 Non-predictable Must check DB for collision each time
UUID → Base62 Globally unique 22+ chars (too long)
Pre-generated Key Ranges Fast, no collision, short, non-predictable Extra service to maintain

Chosen: Pre-generated Key Range Service

1. Background job generates millions of random 7-char base62 keys
2. Stores in key_pool table with status = 'available'
3. Each app server requests batch of 1000 keys → marked 'assigned'
4. App server uses keys from local in-memory pool
5. When pool < 200 → request new batch
6. ZooKeeper coordinates range assignments (no overlap)

#Redirect Service — Detailed Design

The redirect is the critical hot path at 347K QPS peak. Every millisecond matters.

Cache-First Strategy:

Redis GET url:{short_code}
  → HIT (95%):  Return 302 immediately (<2ms total)
  → MISS (5%):  PostgreSQL SELECT → populate Redis → return 302

Click Tracking (Non-Blocking):

Strategy: Fire-and-forget Kafka publish on redirect
  → Redirect returns BEFORE analytics event is confirmed
  → Kafka consumer aggregates clicks → flush to analytics DB
  → Redis INCR for real-time approximate count

#Scaling Strategy

Component Strategy
Redirect Service Stateless; horizontal scale behind LB; auto-scale on QPS
URL Create Service Stateless; 100x fewer instances than Redirect (100:1 ratio)
PostgreSQL Hash-shard by short_code across 8–16 shards; read replicas per shard
Redis Cluster mode, 30GB across 6 nodes; LRU eviction
Kafka Partition by short_code hash; scale consumers independently
Key Gen Service Single leader + standby; pre-generates in background

#Caching Strategy

┌──────────────────────────────────────────────────────┐
│ Layer 1: CDN (Optional — only for 301 redirects)      │
│ • If analytics NOT needed: 301 + CDN edge cache       │
│ • Tradeoff: lose click tracking for lower latency     │
├──────────────────────────────────────────────────────┤
│ Layer 2: Redis Cluster (30GB)                          │
│ • short_code → long_url mapping                       │
│ • TTL: 24h default, matches URL expiration            │
│ • 95%+ hit rate (power-law access pattern)            │
├──────────────────────────────────────────────────────┤
│ Layer 3: Application-Level                             │
│ • Key pool (pre-generated IDs in local memory)        │
│ • Bloom filter for "URL already shortened?" check     │
└──────────────────────────────────────────────────────┘

#Consistency Models

Data Model Rationale
URL mapping Strongly consistent (write-once, immutable) Once created, short→long never changes
Cache Eventually consistent (< 5s) Redis may briefly miss newly created URLs
Click counts Eventually consistent (< 60s) Buffered in Kafka; exact real-time count not critical
Expiration Eventually consistent (< 10 min) Cron cleanup; expired URLs checked at read-time too

#7. Low-Level Design — Core Functionality

#Key Algorithms

1. Base62 Encoding

CHARSET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def base62_encode(num):
    """Convert integer to base62 string."""
    if num == 0:
        return CHARSET[0]
    result = []
    while num > 0:
        result.append(CHARSET[num % 62])
        num //= 62
    return ''.join(reversed(result))

# 7-char range: 62^7 = 3.5 trillion unique URLs
# At 100M/day → sufficient for 95+ years

2. URL Creation Flow

def create_short_url(long_url, custom_alias, expiration, user_id):
    # 1. Validate URL format + optional reachability
    if not is_valid_url(long_url):
        raise InvalidURL()

    # 2. Handle custom alias
    if custom_alias:
        if db.exists("urls", short_code=custom_alias):
            raise AliasAlreadyTaken()
        short_code = custom_alias
    else:
        # 3. Optional dedup: check if long_url already shortened
        existing = db.query("urls", long_url=long_url, user_id=user_id)
        if existing:
            return existing.short_code

        # 4. Get pre-generated key
        short_code = key_pool.get_next()

    # 5. Persist
    expires_at = compute_expiry(expiration)
    db.insert("urls", {
        "short_code": short_code, "long_url": long_url,
        "user_id": user_id, "expires_at": expires_at
    })

    # 6. Warm cache
    redis.setex(f"url:{short_code}", ttl=86400, value=long_url)

    return short_code

3. Redirect Flow (Optimized for Latency)

def redirect(short_code):
    # 1. Cache-first lookup
    long_url = redis.get(f"url:{short_code}")

    if not long_url:
        # 2. Cache miss — hit DB
        row = db.query("urls", short_code=short_code)
        if not row or not row.is_active:
            raise NotFound()
        if row.expires_at and row.expires_at < now():
            raise NotFound()  # expired
        long_url = row.long_url
        # 3. Populate cache
        redis.setex(f"url:{short_code}", ttl=86400, value=long_url)

    # 4. Async click tracking (non-blocking)
    kafka.publish("clicks", {
        "short_code": short_code,
        "timestamp": now(), "ip": request.ip,
        "user_agent": request.user_agent,
        "referrer": request.referrer
    })

    # 5. Return redirect
    return HTTPRedirect(302, long_url)

#Design Patterns Used

Pattern Where Why
Cache-Aside Redis for URL lookups 100:1 read:write; 95%+ cache hit on hot path
Pre-computation Key Gen Service Avoid runtime collision checks; O(1) key assignment
Event Sourcing Click events to Kafka Immutable click log; replay for analytics reprocessing
CQRS Separate Redirect/Create services + Analytics 100:1 read:write; scale redirect independently
Bloom Filters "Is URL already shortened?" check Avoid DB lookup for dedup; probabilistic but fast

#8. Failure Handling & Edge Cases

#What Happens When X Fails?

Failure Impact Mitigation
Redis down Redirects hit DB (latency spike to ~20ms) Read replicas absorb load; Redis is cache-only
PostgreSQL primary down Can't create new URLs; redirects from replicas Auto-failover; writes queued for < 30s
Key Gen Service down Can't create new URLs Each server has local pool of ~1000 keys; survives hours
Kafka down Click events lost temporarily Buffer in local disk queue; replay when Kafka recovers
Single shard down ~12% of redirects fail (1/8 shards) Per-shard replicas; automatic failover

#Edge Cases

#9. Monitoring & Observability

#Key Metrics

Metric Target Alert Threshold
Redirect P99 latency < 10ms > 50ms
Create P99 latency < 100ms > 300ms
Cache hit ratio (Redis) > 95% < 85%
Redirect 5xx rate < 0.01% > 0.1%
Key pool remaining > 500/server < 100
Kafka consumer lag < 10s > 60s
DB replication lag < 1s > 10s

#Alerting Strategy

#SLAs / SLOs

Redirect API:        99.99% availability, P99 < 10ms
Create API:          99.95% availability, P99 < 100ms
Analytics freshness: Click data available within 5 minutes
URL durability:      99.999999999% (11 nines via DB replication + backups)

#10. Trade-off Summary

Decision Chose Over Because
URL generation Pre-generated key pool Hash-based / auto-increment No collision, non-predictable, zero runtime overhead
Redirect code 302 (Temporary) 301 (Permanent) Enables click tracking; browsers don't cache 302s
Short code length 7 chars (base62) 6 chars 3.5T keyspace vs 56.8B; future-proof at 100M/day
Metadata DB PostgreSQL (sharded) DynamoDB / Cassandra Relational queries for user URL lists; mature tooling
Cache strategy Cache-aside (Redis) Write-through Simpler invalidation; cache miss is rare and tolerable
Click tracking Async via Kafka Synchronous DB update Non-blocking redirect; exact real-time count not critical
Analytics storage ClickHouse PostgreSQL Column-oriented; optimized for aggregate queries on billions of events
Dedup strategy Optional Bloom filter + DB index Always check DB Bloom filter avoids DB roundtrip for 99% of new URLs

#11. Extensions & Follow-ups

#What Would You Add With More Time?

  1. Link Previews — Generate OG image / title / description for shared links
  2. Custom Domains — White-label short URLs (e.g., amzn.to, youtu.be)
  3. A/B Testing — Route different % of clicks to different destinations
  4. Link Expiration Notification — Email/webhook when URL is about to expire
  5. Geo-based Routing — Redirect to different URLs based on user's country
  6. QR Code Generation — Auto-generate QR code for each short URL

#How Would This Change at 100x Scale?

#12. Cross-References

Topic Connection
Unique ID Generator (#4) Key Gen Service is a specialized unique ID system
Pastebin (#25) Nearly identical URL generation and key management
Key-Value Store (#3) Redis cache design is a simplified KV store
Rate Limiter (#2) API rate limiting protects the create endpoint

#Building Blocks Used

#Concepts Used