Design: URL Shortener¶

Difficulty: Foundation | Time: 45–60 minutes

1. Problem Statement¶

Design a URL shortening service (like bit.ly). Users submit a long URL and receive a short URL (e.g., https://sho.rt/abc123). Anyone with the short URL is redirected to the original URL.

2. Clarifying Questions¶

Practice asking these before designing:

3. Functional Requirements¶

• User submits a long URL → receives a unique short URL
• Anyone with the short URL is redirected to the original URL
• Short URLs should be as short as possible
• Optional: custom aliases, expiration, click analytics

4. Non-Functional Requirements¶

5. Capacity Estimation¶

Writes (URL creation):
  100M total URLs
  Growing at ~1M new URLs/day
  1M / 86,400s ≈ 12 writes/second

Reads (redirects):
  1B redirects/day
  1B / 86,400s ≈ 11,500 reads/second (avg)
  Peak (10×): ~115,000 reads/second

Storage:
  Long URL: avg 200 bytes
  Short code: 7 bytes
  Metadata: ~100 bytes
  Per URL: ~300 bytes
  100M URLs × 300 bytes = 30 GB total
  (very manageable — easily fits in RAM for caching)

Bandwidth:
  Read: 11,500 req/s × 200 bytes (URL) ≈ 2.3 MB/s
  Write: 12 req/s × 200 bytes ≈ 2.4 KB/s

6. API Design¶

POST /api/v1/shorten
Request:  { "long_url": "https://...", "custom_alias": "optional", "ttl_days": 365 }
Response: { "short_url": "https://sho.rt/abc123", "short_code": "abc123", "expires_at": "..." }
Status: 201 Created

GET /{short_code}
Response: 301/302 Redirect to long_url
Status: 301 (permanent — browser caches) or 302 (temporary — we control)

DELETE /api/v1/urls/{short_code}
Response: 204 No Content

GET /api/v1/urls/{short_code}/analytics
Response: { "total_clicks": 42000, "clicks_by_day": [...] }

7. Short Code Generation¶

How do we generate abc123?

import random, string
def generate():
    chars = string.ascii_letters + string.digits  # 62 chars
    return ''.join(random.choices(chars, k=7))
    # 62^7 = 3.5 trillion combinations — enough

def encode(num: int) -> str:
    chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    result = []
    while num > 0:
        result.append(chars[num % 62])
        num //= 62
    return ''.join(reversed(result)).zfill(7)

# DB auto-increment: ID=1 → "0000001", ID=577313869870 → "aaaaaaa"
# (577,313,869,870 is "aaaaaaa"'s actual base62 value — 7 a's, where
# 'a' is digit 10 in this charset)
# 62^7 = 3.5 trillion unique 7-character codes (IDs 0 through 62^7 - 1);
# the ID 3,521,614,606,208 (=62^7 itself) is the first ID that
# DOESN'T fit in 7 digits — it needs an 8th character

import hashlib
def generate(long_url: str) -> str:
    h = hashlib.md5(long_url.encode()).hexdigest()
    return h[:7]  # take first 7 hex chars

Recommended: Option B (auto-increment + Base62) with ID generation service. Hash-based is fine only after encoding enough bits; 7 hex chars is not a short-code scheme.

8. Data Model¶

-- Core URL table
CREATE TABLE urls (
    id          BIGINT PRIMARY KEY AUTO_INCREMENT,
    short_code  VARCHAR(10) UNIQUE NOT NULL,
    long_url    TEXT NOT NULL,
    user_id     BIGINT,
    created_at  TIMESTAMP DEFAULT NOW(),
    expires_at  TIMESTAMP,
    is_deleted  BOOLEAN DEFAULT FALSE,
    INDEX idx_short_code (short_code)
);

-- Optional: click analytics (separate service)
CREATE TABLE clicks (
    id          BIGINT PRIMARY KEY AUTO_INCREMENT,
    short_code  VARCHAR(10) NOT NULL,
    clicked_at  TIMESTAMP DEFAULT NOW(),
    country     VARCHAR(2),
    device      VARCHAR(20),
    referer     TEXT,
    INDEX idx_short_code_time (short_code, clicked_at)
);

9. Basic Architecture (Version 1)¶

graph LR
    Client -->|POST /shorten| WS[Write Service]
    Client -->|GET /{code}| RS[Read Service]
    WS -->|INSERT| DB[(PostgreSQL\nPrimary)]
    RS -->|SELECT| Cache[(Redis Cache\nHot URLs)]
    RS -->|Cache miss| DB
    DB -->|Replication| DR[(Read Replica)]
    RS -->|Read replica| DR

This handles moderate load. Identify the bottleneck before adding more components.

10. Identify Bottlenecks¶

11. Scaled Architecture (Version 2)¶

graph TD
    subgraph CDN["CDN (CloudFront/Cloudflare)"]
        CDN1[Edge Cache\nfor popular redirects]
    end
    subgraph LB["Load Balancer"]
        L[L7 Load Balancer]
    end
    subgraph WriteService["Write Service (stateless)"]
        W1[Write Pod 1]
        W2[Write Pod 2]
    end
    subgraph ReadService["Read Service (stateless)"]
        R1[Read Pod 1]
        R2[Read Pod 2]
        R3[Read Pod 3]
    end
    subgraph IDGen["ID Generation"]
        IDS[Snowflake ID Service\nor DB sequences per shard]
    end
    subgraph Cache["Redis Cluster"]
        RC1[Shard 1]
        RC2[Shard 2]
        RC3[Shard 3]
    end
    subgraph Database["Database"]
        PG1[Primary]
        RR1[Read Replica 1]
        RR2[Read Replica 2]
    end

    Client --> CDN1
    CDN1 -->|Cache miss| L
    L --> W1
    L --> R1
    W1 --> IDS
    W1 --> PG1
    R1 --> RC1
    R1 -->|Cache miss| RR1
    PG1 --> RR1
    PG1 --> RR2

12. Failure Modes¶

13. Consistency Considerations¶

• Eventual consistency acceptable: If a new URL takes 1–2 seconds to become visible, that's fine
• Read-your-writes required: The user who created a URL should immediately be able to use it
• Solution: Write to primary, invalidate cache; reads go to replica except for the creator's next immediate request (route by cookie/session to primary for 1–2 seconds)

14. Observability¶

Key metrics:
- redirect_latency_p50/p95/p99 (SLO: p99 < 100ms)
- cache_hit_rate (target: > 90%)
- url_creation_rate (writes/second)
- 404_rate (invalid short codes — could indicate enumeration attack)
- redis_memory_usage (eviction risk)
- db_connection_pool_utilization

Alerts:
- p99 redirect latency > 200ms
- Cache hit rate drops below 80%
- Error rate > 0.1%

15. Cost Analysis¶

Redis (3-shard cluster, 30 GB cache):   ~$500/month
PostgreSQL (Multi-AZ, r5.xlarge):       ~$400/month
2 read replicas:                         ~$400/month
Application servers (10 pods):           ~$200/month
CDN (~30B HTTP requests/month, at 1B/day):
  CloudFront-class request pricing is ~$0.0075 / 10K HTTP requests
  30B / 10K × $0.0075 ≈ $22,500/month (request charges dominate;
  redirect bodies are tiny, so egress is a rounding error next to this)
  At Pastebin's $0.005/1K blended rate, 30B would be ~$150K/month —
  treat ~$20K–$150K as the realistic band, not ~$100.
Total:                                   ~$24,000/month (CDN-dominated)

Cost per redirect:
  1B redirects/day × ~30 days/month ≈ 30B redirects/month
  $24,000 / 30,000,000,000 ≈ $0.0000008 per redirect
  (a month has ~2.6M seconds; 1B/day ÷ 86,400s ≈ 11,500 rps average)

16. Alternative Architectures¶

17. Staff Engineer Extensions¶

18. Interview Follow-ups¶

1. "How would you handle custom aliases colliding?" — Check uniqueness before accepting, return error with suggestion if taken
2. "What if we need to support analytics per URL?" — Separate analytics service, async writes via Kafka, time-series DB (ClickHouse/Druid)
3. "How do you handle URL scanning (phishing links)?" — Async scanning pipeline; don't block creation; mark unsafe and serve warning page
4. "How do you prevent enumeration attacks?" — Rate limit on short code lookups by IP; monitor 404 rate spikes; use random codes not sequential

Self-Assessment¶

• [ ] Can I explain why Base62 over random UUIDs for URL generation?
• [ ] Can I justify the 301 vs 302 decision for the analytics requirement?
• [ ] Can I walk through what happens when Redis goes down?
• [ ] Can I estimate the cost within 2× accuracy?
• [ ] Can I design the analytics feature without impacting redirect latency?

Five-Level Self-Assessment¶

1. Explain: What problem does the short-code counter + base62 approach solve that a random hash doesn't?
2. Predict: Traffic doubles while Redis capacity stays fixed. What happens, and what's the cheapest fix?
3. Diagnose: 404 rate on redirects spikes 20× overnight with no deploy. What's the likely cause?
4. Design: Add per-URL click analytics without adding latency to the redirect's hot path.
5. Defend: Why is fan-out-on-write for analytics preferable to querying an analytics DB synchronously on every redirect?