URL Shortener (bit.ly)

System Design Concepts Used

Load Balancer · CDN · Consistent Hashing · Base62 Encoding · Snowflake ID · Cache-Aside (Redis) · Database Sharding · Async Processing (Kafka) · OLAP (ClickHouse) · Power Law Distribution · 301 vs 302 Redirects · Horizontal Scaling

1. Functional Requirements

1. Shorten URL — given a long URL, return a unique short URL (7 characters)
2. Redirect — given a short URL, redirect to the original long URL (301/302)
3. Custom aliases — user can optionally pick a custom short name (e.g., /my-promo)
4. Expiration — optional TTL per URL (auto-delete after N days)
5. Analytics — click count, geographic distribution, referrer tracking

2. Non-Functional Requirements

3. Capacity Estimation

/* ━━━ NAPKIN MATH: Start From Monthly URLs ━━━ */
New URLs/month: 100M
New URLs/day: 100M / 30 = 3.3M/day
Write QPS (avg): 3.3M / 86,400 ≈ 40 writes/sec
Write QPS (peak 5x): ~200 writes/sec

/* ━━━ READS (100:1 ratio) ━━━ */
Read QPS (avg): 40 × 100 = 4,000 reads/sec
Read QPS (peak 10x): 40,000 reads/sec
Read QPS (viral spike 50x): 200,000 reads/sec  ← CDN must absorb this

/* ━━━ STORAGE ━━━ */
Per URL: short_url (7B) + long_url (500B avg) + metadata (100B) = ~600 bytes
5-year storage: 100M × 12 × 5 × 600B = 3.6 TB
Total unique URLs (5yr): 6 billion
Base62 with 7 chars: 62^7 = 3.5 TRILLION (sufficient for centuries)

/* ━━━ CACHE ━━━ */
80/20 rule: 20% of URLs get 80% of traffic (power law)
Hot URLs to cache: 3.3M/day × 20% = 660K URLs
Cache memory: 660K × 600 bytes = ~400 MB  (tiny! Redis handles easily)
Generous cache: 10M URLs × 600 bytes = 6 GB Redis

/* ━━━ BANDWIDTH ━━━ */
Incoming (reads): 40K req/sec × 600 bytes = 24 MB/sec
Outgoing (redirects): 40K × 300 bytes (HTTP 301 header) = 12 MB/sec

4. "Why X, Not Y?" — Tradeoff Analysis

Why Base62 encoding and not MD5/SHA hash?

Base62 wins because it guarantees a fixed, short length with no collision risk when paired with a unique counter. MD5 produces 128 bits — truncating to 7 characters gives you only 62^7 / 2^42 collision probability, which at 6 billion URLs means thousands of collisions requiring DB lookups to resolve. Base62-encoding a unique integer (from a counter or Snowflake ID) produces a guaranteed-unique 7-character string with zero collision checks.

MD5 advantage: Same long URL always produces the same short URL (deduplication for free). Use if dedup is a hard requirement.

Why Redis cache and not Memcached?

Redis supports data structures (TTL, sorted sets for analytics) and persistence. If a Redis node restarts, it can reload from an RDB snapshot and resume serving within seconds. Memcached loses all data on restart — during the cold-start window, every request hits the database.

Memcached advantage: Multi-threaded, marginally faster for pure key-value gets at extreme scale (Netflix uses it at 30M req/sec). For a URL shortener at 40K reads/sec, Redis is more than enough.

Why sharded PostgreSQL and not DynamoDB?

PostgreSQL gives us transactions for the write path (insert URL + check custom alias atomically) and is free from vendor lock-in. Sharding by hash(short_url) distributes reads evenly. At 3.6 TB / 5 years, 6 shards handle ~600 GB each — well within PostgreSQL's comfort zone.

DynamoDB advantage: Zero-ops, auto-scaling, single-digit ms reads at any scale. Use if you want managed infra and accept AWS lock-in and higher cost at scale.

Why 301 redirect and not 302?

301 (Permanent) lets browsers and CDNs cache the redirect, reducing load on our servers. Once a browser sees a 301 for /abc123 → https://example.com/long-page, it never asks us again — it goes directly. This offloads massive traffic.

302 advantage: Every click comes through us, enabling accurate analytics (click count, geo, referrer). Use 302 if analytics is the primary revenue model (bit.ly uses 302).

5. High-Level Architecture

6. Backend Services Explained

Read Service (Redirect)

The most critical service — handles 100x more traffic than writes. Completely stateless — any instance can serve any request. Implements cache-aside: check Redis first, on miss go to the correct PostgreSQL shard (determined by hash(short_url) mod num_shards), then populate the cache before returning.

Write Service (Shorten)

Consumes the next available ID from its pre-allocated range (e.g., IDs 5,000,001 to 5,010,000), Base62-encodes it, writes to PostgreSQL AND proactively warms the Redis cache. If a custom alias is requested, it checks for uniqueness in the database first (atomic INSERT ... ON CONFLICT).

ID Generation Service

Allocates monotonically increasing ID ranges to Write Service instances. Each Write Service gets a block of 10,000 IDs at a time. It locally increments through its block with zero network calls. When exhausted, it requests a new block. The ID service itself is backed by a simple atomic counter in a single-row PostgreSQL table (or ZooKeeper if you need multi-region).

Analytics Service

Publishes click events to Kafka asynchronously — never in the redirect hot path. A separate consumer writes aggregated analytics to ClickHouse every 10 seconds (batch inserts for OLAP performance).

7. Architecture Flow — A Click from Brazil

A user named Carlos in São Paulo clicks a shortened link https://short.ly/Kz8mQ4x in a tweet about a tech conference.

Phase 1 — Edge Resolution

T+0ms: Carlos's browser sends GET /Kz8mQ4x to the nearest CDN PoP in São Paulo. The CDN checks its cache: this URL was first clicked 2 minutes ago by someone else in Brazil, and the 301 response was cached with a 24-hour TTL.

Cache HIT → T+5ms: CDN returns 301 Moved Permanently with Location: https://techconf.io/2026/register. Carlos's browser follows the redirect. Total latency: 5ms. Our origin servers never saw this request.

Carlos (São Paulo) → CDN PoP (São Paulo) → 301 cached → done (5ms)

Phase 2 — Cache Miss (First Click)

Now imagine Carlos is the FIRST person to ever click this link. CDN has no cache entry.

T+0ms: CDN cache miss → forwards to origin (Load Balancer in us-east-1).

T+25ms: Load Balancer routes to a Read Service instance.

T+26ms: Read Service queries Redis: GET url:Kz8mQ4x

T+27ms: Redis HIT (the URL creator's Write Service proactively cached it). Returns https://techconf.io/2026/register.

T+28ms: Read Service returns 301 to CDN. CDN caches the response. Browser follows redirect.

Carlos → CDN (miss) → LB → Read Service → Redis (hit) → 301 → CDN caches → done (28ms)

Phase 3 — Full Miss (Cold URL, Never Cached)

A 3-year-old URL that hasn't been clicked in months. Redis evicted it (LRU).

T+0ms: CDN miss → LB → Read Service.

T+26ms: Redis MISS (GET url:Kz8mQ4x → nil).

T+27ms: Read Service computes shard: hash("Kz8mQ4x") mod 6 = shard 3. Queries PostgreSQL shard 3: SELECT long_url FROM urls WHERE short_url = 'Kz8mQ4x'.

T+32ms: PostgreSQL returns the row (index scan, <5ms).

T+33ms: Read Service writes to Redis (SET url:Kz8mQ4x <long_url> EX 86400) and returns 301.

Carlos → CDN (miss) → LB → Read Service → Redis (miss) → PostgreSQL shard 3 → cache populate → 301 (33ms)

Phase 4 — Analytics (Async, Non-Blocking)

T+28ms (parallel): While returning the 301, the Read Service publishes a click event to Kafka:

Kafka.produce("clicks", {
  short_url: "Kz8mQ4x",
  timestamp: "2026-05-19T14:23:07Z",
  geo: "BR-SP",
  referrer: "twitter.com",
  user_agent: "Chrome/126"
})

This is fire-and-forget — it does NOT add latency to the redirect. A ClickHouse consumer batch-inserts these events every 10 seconds.

8. Failure & Recovery Scenarios

Redis Goes Down

Impact: All reads fall through to PostgreSQL. At 40K reads/sec, PostgreSQL (with read replicas) can handle it — but latency increases from 1ms to 5-10ms.

Mitigation: Redis Cluster with 3 replicas per shard. If one master dies, a replica promotes in <5s. During the gap, PostgreSQL serves reads. CDN cache absorbs most viral traffic regardless.

A PostgreSQL Shard Goes Down

Impact: ⅙th of URLs become temporarily unresolvable (only the ones not in Redis cache).

Mitigation: Each shard has synchronous replication to a standby. Automatic failover in <30s. During failover, Redis serves 95%+ of reads — only cold URLs are affected.

ID Service Goes Down

Impact: No new URLs can be created. Existing redirects are unaffected.

Mitigation: Each Write Service holds 10,000 pre-allocated IDs locally. At 200 writes/sec peak, that's 50 seconds of buffer. If the ID service is down for <50s, nobody notices. Beyond that, return 503 Service Unavailable for writes only — reads continue normally.

9. Data Model

/* PostgreSQL — Sharded by hash(short_url) */

CREATE TABLE urls (
    short_url   VARCHAR(7)  PRIMARY KEY,
    long_url    TEXT        NOT NULL,
    user_id     BIGINT,                    -- nullable (anonymous creates allowed)
    created_at  TIMESTAMPTZ DEFAULT NOW(),
    expires_at  TIMESTAMPTZ,               -- NULL = never expires
    click_count BIGINT      DEFAULT 0      -- denormalized, updated async
);

CREATE INDEX idx_long_url ON urls (long_url);  -- for dedup lookups
CREATE INDEX idx_expires  ON urls (expires_at) WHERE expires_at IS NOT NULL;

/* Redis — Key structure */

SET url:Kz8mQ4x "https://techconf.io/2026/register" EX 86400
    ^key         ^value                                ^TTL 24h

/* ClickHouse — Analytics (columnar, append-only) */

CREATE TABLE clicks (
    short_url   String,
    clicked_at  DateTime,
    country     LowCardinality(String),
    referrer    String,
    user_agent  String
) ENGINE = MergeTree()
ORDER BY (short_url, clicked_at);

10. Algorithms Under the Hood

Base62 Encoding

ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

function encode(num):
    result = ""
    while num > 0:
        result = ALPHABET[num % 62] + result
        num = num / 62  (integer division)
    return result.padLeft(7, '0')

encode(1000000000) → "15FTGf"  (6 chars, pad to 7 → "015FTGf")
encode(3500000000000) → max 7 chars used

function decode(str):
    num = 0
    for char in str:
        num = num * 62 + ALPHABET.indexOf(char)
    return num

Cache-Aside Pattern (Read Path)

function redirect(short_url):
    // Step 1: Check cache
    long_url = redis.GET("url:" + short_url)
    if long_url != null:
        return 301(long_url)    // cache hit — 1ms

    // Step 2: Cache miss → database
    shard = hash(short_url) % NUM_SHARDS
    long_url = postgres[shard].query(
        "SELECT long_url FROM urls WHERE short_url = $1", short_url
    )
    if long_url == null:
        return 404("URL not found")

    // Step 3: Populate cache for next time
    redis.SET("url:" + short_url, long_url, EX=86400)

    // Step 4: Async analytics
    kafka.produce("clicks", {short_url, timestamp, geo, referrer})

    return 301(long_url)

ID Range Allocation

/* ID Service (centralized counter) */
function allocate_range(server_id, block_size=10000):
    BEGIN TRANSACTION
    current = SELECT counter FROM id_counter FOR UPDATE
    UPDATE id_counter SET counter = current + block_size
    COMMIT
    return {start: current, end: current + block_size - 1}

/* Write Service (local consumption, no network per ID) */
function next_id():
    if local_counter >= range.end:
        range = id_service.allocate_range(my_server_id)
        local_counter = range.start
    local_counter += 1
    return local_counter

11. Scaling Considerations

12. URL Abuse & Security

URL shorteners are inherently phishing vectors — a malicious destination is hidden behind an opaque short link, and users cannot inspect where they'll land before clicking.

These measures add minimal write-path latency (Safe Browsing lookup is ~20ms) and protect both end users and the platform's domain reputation.

13. What If the Interviewer Pushes Back?

Real interviews test your ability to defend and adapt your design. Here are the most common challenges and how to handle them:

14. Quick Recall