Design a URL Shortener

System Design Interview•~35 min read•medium

Design a URL shortening service similar to bit.ly or TinyURL. Users submit a long URL and receive a short alias (e.g., https://short.ly/aB3xY). When a user visits the short URL, the service redirects them to the original. The service must handle high read traffic, provide low-latency redirects, and allow optional analytics per short URL.

1. Understand Requirements & Scope

Core requirements: generate short alias → store mapping → resolve + redirect. Key constraints: 100M writes/day ≈ 1,160 writes/sec; 100:1 read ratio ≈ 116,000 reads/sec; 62^7 alias space; p99 redirect < 10 ms. Out of scope for base design: per-user authentication, abuse prevention, real-time analytics dashboards.

Functional Requirements:

Given a long URL, generate a unique short alias and return it to the user.
Given a short alias, resolve and redirect to the original URL with low latency.
Short aliases must be unique and collision-resistant.
Optionally support custom aliases chosen by the user.
Optionally record click count and basic analytics per short URL.
Short URLs should not expire by default; expiry is an optional configuration.

2. Back-of-the-Envelope Capacity Estimation

• Write volume: ~100 million new URLs per day (assume 100:1 read-to-write ratio).

• Redirect p99 latency target: under 10 ms.

• Alias length: 7 characters (default) using [a-z, A-Z, 0-9] — 62^7 ≈ 3.5 trillion combinations.

• Data retention: indefinite unless expiry is explicitly set.

• Assume globally distributed read traffic, writes concentrated in a few regions.

3. High-Level Architecture Flow

A global URL shortener handles 100:1 read-to-write ratios using 7-character Base62 encoding (3.5 trillion capacity), a dedicated Key Generation Service (KGS) pre-allocating memory blocks to eliminate database sequence locks, and an HTTP 301/302 edge caching architecture.

[ Web / Mobile Clients ]
          |
          v
[ Cloudflare CDN Edge ] <--- (Caches HTTP 301 Permanent Redirects)
          |
          v
[ API Gateway Tier ]
          |
    +-----+--------------------+
    |                          |
    v (Write Path)             v (Read Path)
[ Key Gen Service (KGS) ]   [ Redis Cluster Cache ] (Hot URLs)
    |                          |
    v                          v (Cache Miss)
[ PostgreSQL / DynamoDB ] <----+

Fig 1. Architecture data flow and component topology.

4. Production Implementation & Code

// Base62 Encoding Primitive (0-9, a-z, A-Z)
const ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

export function encodeBase62(num: bigint): string {
  if (num === 0n) return "0";
  let str = "";
  while (num > 0n) {
    const rem = Number(num % 62n);
    str = ALPHABET[rem] + str;
    num = num / 62n;
  }
  return str;
}

Hardened Implementation Sequence

Client submits POST /shorten with the long URL.
API layer validates and rate-limits the request.
ID Generator creates a unique 7-char Base-62 alias (using a counter with Base-62 encoding or a hash-then-truncate strategy).
Write the mapping {shortId → longUrl, createdAt, userId?} to the KV store. Check uniqueness before committing.
Return the full short URL (https://short.ly/{alias}) to the client.
For redirect: client GET /alias → API checks Redis cache → on miss, reads KV store → returns 301 (permanent) or 302 (trackable) redirect.
Cache the mapping in Redis on first read (TTL-based). Hot URLs stay in cache indefinitely under TTL.

5. Key Decisions & Operational Mitigations

Architectural Decisions & Trade-Offs

•301 (Permanent): Browser caches the redirect, reducing repeat load on the service. Cost: no click analytics on cached requests. Use when analytics are not needed.
•302 (Temporary/Found): Every visit hits the service, enabling click counting. Cost: higher server load for popular links. Use when analytics are required.
•Base-62 vs hash: Base-62 counter gives monotonically increasing, collision-free IDs at the cost of a coordination step. Hash-truncate is simpler but requires a collision retry mechanism.
•Redis as redirect cache: Cold start adds one KV read per alias. Warm state handles virtually all read traffic without touching the persistent store — critical for the p99 < 10 ms target.
•Custom aliases: Require a separate namespace to avoid collisions with generated IDs. Store in the same KV with a reserved prefix or a separate index.

Operational Hazards & Mitigations

•Hot/viral link: Single alias generates millions of cache reads. Redis handles this as a single key — but if that key evicts or Redis restarts, the KV store absorbs a thundering herd. Mitigation: never evict hot keys (LFU eviction policy + keep TTL long for popular links); use probabilistic early refresh.
•ID space exhaustion: 62^7 ≈ 3.5 trillion — at 100M/day it takes ~95 years. Non-issue for MVP. Future: extend alias length to 8 chars (62^8 ≈ 218 trillion).
•ID generator failure: If using a centralized counter, a single-node failure stops ID generation. Mitigation: replicate the counter with leader election (Zookeeper/etcd) or switch to a distributed range-based scheme.
•Cache failure (Redis down): All redirects fall back to KV reads. At 116K reads/sec this can overwhelm KV. Mitigation: circuit breaker on the cache client; read replicas on the KV store; multi-layer edge cache (CDN) for the most popular links.
•Regional outage: Cross-region replication of the KV store with eventual consistency. Reads from the nearest region. Writes: accept last-write-wins for duplicate short alias creation across regions (acceptable given the collision probability is extremely low).

Interactive Knowledge Check • Question 1 of 3↓

Interactive Practice Quiz•Question 1 of 3

intermediate

Single-Thread Execution Bottleneck

Why does Redis execute single-threaded command processing faster than traditional multi-threaded locked data structures?