Design a URL Shortener

Problem Statement

A URL shortener takes a long URL and returns a short alias — for example, turning `https://www.example.com/very/long/path?query=foo` into `https://sho.rt/aB3xQz`. When a user visits the short URL, the service redirects them to the original. This is one of the most frequently asked interview problems because it touches hashing, database design, caching, and high-throughput read optimization all in one compact problem.

Requirements

Functional Requirements

• Given a long URL, generate a unique short URL (alias).
• Redirect users from the short URL to the original long URL.
• Support custom aliases (e.g., `sho.rt/my-brand`).
• Optionally set an expiry time on short URLs.
• Track click analytics (count, geo, device, referrer).

Non-Functional Requirements

• High availability: redirects must succeed even if part of the system is down.
• Low latency: redirect should complete in < 10 ms at the 99th percentile.
• Durability: URLs must not be lost once created.
• Scale: support 100 M new URLs/day, 10 B redirects/day.

Capacity Estimation

High-Level Design

Short Code Generation

The core challenge is generating a unique, compact, URL-safe identifier for each long URL. There are three common approaches:

Recommended approach: use a distributed ID generator (Snowflake-style) and encode the ID in base-62. A 64-bit ID encoded in base-62 produces a 7–11 character code that is collision-free and opaque. For custom aliases, store them directly and check for conflicts at write time.

import string

ALPHABET = string.ascii_lowercase + string.ascii_uppercase + string.digits  # 62 chars

def to_base62(num: int) -> str:
    if num == 0:
        return ALPHABET[0]
    result = []
    while num:
        result.append(ALPHABET[num % 62])
        num //= 62
    return "".join(reversed(result))

# Example: ID 1_000_000_000 → "15ftgG" (6 chars)
print(to_base62(1_000_000_000))  # "15FtGG" (approx)

API Design

Key Flow: Redirect

Database Schema

CREATE TABLE urls (
  id          BIGINT PRIMARY KEY,          -- Snowflake ID
  short_code  VARCHAR(16) UNIQUE NOT NULL, -- base-62 encoded ID or custom alias
  long_url    TEXT NOT NULL,
  user_id     BIGINT,                      -- nullable for anonymous
  created_at  TIMESTAMP DEFAULT NOW(),
  expires_at  TIMESTAMP,                   -- NULL = never expires
  click_count BIGINT DEFAULT 0
);

CREATE INDEX idx_short_code ON urls(short_code);  -- primary lookup path

CREATE TABLE clicks (
  id          BIGSERIAL PRIMARY KEY,
  short_code  VARCHAR(16) NOT NULL,
  clicked_at  TIMESTAMP DEFAULT NOW(),
  ip_hash     VARCHAR(64),
  country     VARCHAR(2),
  user_agent  TEXT
);

Scaling Considerations

• Read replicas: 99% of traffic is reads (redirects). Route all reads to replicas, writes to the primary.
• Redis cluster: cache hot short codes in Redis with a TTL equal to the URL expiry. Eviction policy: `allkeys-lru`.
• CDN edge caching: for non-expiring URLs, cache the 301 redirect at the CDN edge — eliminates origin requests entirely.
• Sharding: shard the `urls` table by `short_code` hash for horizontal scale. Consistent hashing avoids rebalancing pain.
• Analytics pipeline: write click events to Kafka asynchronously; Flink or Spark aggregates into a data warehouse. Never write analytics in the hot redirect path.
• Rate limiting: apply per-user and per-IP limits at the API gateway to prevent abuse.