System Design #13: Design a URL Shortener

Traffic Estimation:

  Write (new URLs created): 100 million per day
  Read (redirections):      10 billion per day (100:1 read-to-write ratio)

  Writes per second: 100M / 86,400 = ~1,160 writes/sec
  Reads per second:  10B / 86,400  = ~115,740 reads/sec

  Peak: 2-3x average
  Peak writes: ~3,000/sec
  Peak reads:  ~350,000/sec

Storage Estimation:

  Each URL mapping: ~500 bytes (short code + long URL + metadata)
  Per day: 100M * 500 bytes = 50 GB/day
  Per year: 50 GB * 365 = ~18 TB/year
  5 years (retention): ~90 TB total

Short Code Length:

  Using Base62 (a-z, A-Z, 0-9) = 62 characters
  6 characters: 62^6 = 56.8 billion combinations
  7 characters: 62^7 = 3.5 trillion combinations

  At 100M URLs/day for 5 years = 182.5 billion URLs
  7 characters is enough (3.5 trillion >> 182.5 billion)

REST API:

  POST /api/shorten
  Request:
  {
    "long_url": "https://example.com/very/long/path?query=value",
    "custom_code": "my-link",     // optional
    "expiration": "2031-01-01"    // optional
  }
  Response:
  {
    "short_url": "https://short.ly/Ab3xK9",
    "long_url": "https://example.com/very/long/path?query=value",
    "expires_at": "2031-01-01T00:00:00Z"
  }

  GET /{shortCode}
  Response: HTTP 301 Redirect to the long URL
  Location: https://example.com/very/long/path?query=value

Hash and Truncate:

  long_url = "https://example.com/long/path"
  hash = MD5(long_url) = "a1b2c3d4e5f6a7b8c9d0e1f2a3b4c5d6"
  short_code = Base62(first 43 bits of hash) = "Ab3xK9z"

  Problem: Collisions!
  Two different URLs might produce the same 7-character code.

  Solution: Check the database. If the code exists, append
  a counter and rehash.

  Attempt 1: hash("https://example.com/path")     = "Ab3xK9z" (exists!)
  Attempt 2: hash("https://example.com/path" + 1) = "Xy7mP2q" (unique!)

Counter-Based:

  Counter: 1000000001
  Base62 encode: 1000000001 --> short code (6-7 chars)

  Counter: 1000000002
  Base62 encode: 1000000002 --> next short code

  Problem: Sequential codes are predictable.
  A user can guess other URLs by incrementing the code.

  Problem: Single counter is a bottleneck in distributed systems.

Pre-Generated Key Pool:

  Key Generation Service (offline):
    Generates millions of random 7-character Base62 codes
    Stores them in a "key pool" database

  Key Pool Table:
    | key      | used |
    |----------|------|
    | Ab3xK9z  | no   |
    | Xy7mP2q  | no   |
    | Mn8kL4w  | yes  |
    | ...      | ...  |

  When a new short URL is requested:
    1. Take an unused key from the pool
    2. Mark it as used
    3. Create the URL mapping with this key

  Two servers requesting keys at the same time:
    Each server takes a BATCH of keys (e.g., 1000 keys)
    from the pool into local memory.
    No contention — each server uses its own batch.

package main

import "fmt"

const base62Chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

func encode(num int64) string {
    if num == 0 {
        return string(base62Chars[0])
    }
    result := []byte{}
    for num > 0 {
        remainder := num % 62
        result = append([]byte{base62Chars[remainder]}, result...)
        num = num / 62
    }
    return string(result)
}

func main() {
    fmt.Println(encode(1000000001)) // outputs a 6-char Base62 string
    fmt.Println(encode(99999999999)) // outputs a 7-char Base62 string
}

URL Mapping Table:

  | Column      | Type         | Description              |
  |-------------|-------------|--------------------------|
  | short_code  | VARCHAR(7)  | Primary key, the short code |
  | long_url    | TEXT        | The original long URL     |
  | created_at  | TIMESTAMP   | When the URL was created  |
  | expires_at  | TIMESTAMP   | When the URL expires      |
  | click_count | BIGINT      | Number of redirections    |

Database Choice:

  SQL (PostgreSQL):
    + Strong consistency
    + ACID transactions
    + Indexes on short_code for fast lookups
    - Harder to scale horizontally

  NoSQL (DynamoDB, Cassandra):
    + Easy horizontal scaling
    + High write throughput
    + Key-value lookup is the primary access pattern (perfect for NoSQL)
    - Eventual consistency (acceptable for URL shortener)

  Recommendation: NoSQL (DynamoDB or Cassandra)
    - The access pattern is simple: key-value lookup by short_code
    - Write-heavy with 100M writes/day
    - Horizontal scaling is needed for 90 TB of data

Complete Architecture:

  [Client] --> [Load Balancer]
                    |
              [API Servers] (stateless, horizontally scaled)
                    |
              +-----+------+
              |            |
         [Write Path]  [Read Path]
              |            |
    [Key Pool Service] [Cache (Redis)]
              |            |
    [Database Writer]  [Cache Miss?]
              |            |
         [Database]   [Database Reader]
              |            |
         [NoSQL DB] <------+
         (sharded by short_code)

Write Flow:

  1. Client sends POST /api/shorten with long_url
  2. Load balancer routes to an API server
  3. API server gets an unused key from its local batch
     (refills batch from Key Pool Service when running low)
  4. API server writes (short_code, long_url) to the database
  5. API server returns the short URL to the client

  Time: ~10-50ms

Read Flow:

  1. Client visits https://short.ly/Ab3xK9z
  2. Load balancer routes to an API server
  3. API server checks Redis cache for "Ab3xK9z"
     a. Cache HIT: get the long_url from cache
     b. Cache MISS: query the database, store result in cache
  4. API server returns HTTP 302 redirect to the long_url
  5. (Async) Increment click_count

  Time: ~5-20ms (cache hit) or ~20-50ms (cache miss)

Caching Strategy:

  Cache: Redis
  Cache size: 20% of URLs get 80% of traffic (Pareto principle)

  20% of daily URLs: 20M URLs * 500 bytes = 10 GB
  Redis can easily handle 10-50 GB in memory.

  Cache policy: LRU (Least Recently Used)
  TTL: 24 hours (re-cache if accessed again)

  Cache-aside pattern:
    1. Check cache first
    2. If miss, query database
    3. Store result in cache
    4. Return result

  Expected cache hit rate: 80-90%
  (because popular URLs are accessed repeatedly)

Option 1: Always create a new short code
  User A shortens example.com/page --> Ab3xK9z
  User B shortens example.com/page --> Xy7mP2q

  Pros: Simple. Each user gets their own link with separate analytics.
  Cons: Wastes storage.

Option 2: Return the existing short code
  User A shortens example.com/page --> Ab3xK9z
  User B shortens example.com/page --> Ab3xK9z (same!)

  Pros: Saves storage. Deduplication.
  Cons: Need a secondary index on long_url. Analytics are shared.

  Implementation: Add a hash index on long_url.
  Before creating a new mapping, check if the long_url exists.

Recommendation: Option 1 for simplicity. Storage is cheap.

Analytics Data:

  For each redirect, log:
    - short_code
    - timestamp
    - IP address (for geographic data)
    - User-Agent (for device/browser data)
    - Referrer (where the click came from)

  Do NOT update the database synchronously for every click.
  This would create a write bottleneck on hot URLs.

  Instead:
    1. Send click events to a message queue (Kafka)
    2. A consumer service processes events in batches
    3. Aggregate data is stored in an analytics database

  [Click] --> [API Server] --> [Kafka] --> [Analytics Consumer]
                                              |
                                        [Analytics DB]
                                        (time-series: ClickHouse, TimescaleDB)

Shard by short_code hash:

  shard = hash(short_code) % number_of_shards

  With consistent hashing:
    - Adding a shard moves ~1/N of the data
    - Each shard handles ~equal traffic
    - No hot spots (short codes are random)

  Shard count for 90 TB:
    If each shard holds 5 TB --> 18 shards
    Each shard handles ~6,400 reads/sec (115K / 18)
    Easily within a single database server's capacity

Multi-Region Deployment:

  [US Users] --> [US Load Balancer] --> [US API Servers] --> [US Redis + DB]
  [EU Users] --> [EU Load Balancer] --> [EU API Servers] --> [EU Redis + DB]

  Writes: go to the nearest data center, replicated async
  Reads: always served from the nearest data center

  DNS-based routing (GeoDNS) directs users to the closest data center.

                        [GeoDNS]
                       /        \
              [US LB]              [EU LB]
              /    \               /    \
        [API-1] [API-2]     [API-3] [API-4]
           |       |            |       |
        [Redis Cluster]      [Redis Cluster]
           |       |            |       |
        [DB Shard 1-9]      [DB Shard 10-18]
                    \          /
                  [Async Replication]

  Separate paths:
    Write: API --> Key Pool --> DB --> Cache Invalidation
    Read:  API --> Cache --> (miss) --> DB --> Cache
    Analytics: API --> Kafka --> Analytics Consumer --> ClickHouse