Web Services12 min read

Design a URL Shortener

Turn long links into tiny ones — at scale

scope:Real-World Systemdifficulty:Intermediate

Understanding the Problem

You know those short links like bit.ly/x7Kp2 that redirect to long URLs? Let's design one from scratch.

First, let's nail down the requirements (remember: always clarify before designing!):

Functional Requirements:

Given a long URL, generate a short, unique URL.
When a user visits the short URL, redirect them to the original long URL.
Users can optionally set custom short URLs.
Links expire after a configurable time (optional).

Non-Functional Requirements:

Read-heavy: Way more reads (redirects) than writes (creating links). Ratio ~100:1.
Low latency: Redirects must be fast (< 100ms). Nobody wants a slow redirect.
High availability: The service should never be down. Broken links are a terrible experience.
Not guessable: Short URLs should not be easily predictable (security).

▸ The idea: long URL → short URL

Estimation

Let's size this system:

100M new URLs per month (writes): ~40 URLs/second
Read:Write ratio 100:1: ~4,000 redirects/second, peak ~12,000/s
Storage per URL: Short URL (7 chars) + Long URL (~200 chars avg) + metadata (~100 bytes) ≈ 500 bytes
Storage for 5 years: 100M × 12 × 5 × 500B = 3 TB
Cache: If we cache the top 20% of URLs (Pareto principle), that's ~600 GB of cache

This is a manageable system. The main challenges are generating unique short codes efficiently and handling the read-heavy workload.

API Design

Keep it simple:

Create Short URL

Endpoint	`POST /api/v1/urls`
Request	`{"long_url": "https://very-long-url.com/...", "custom_alias": "my-link", "expires_at": "2025-12-31"}`
Response	`{"short_url": "https://short.ly/x7Kp2", "long_url": "...", "created_at": "..."}`
Status	`201 Created`

Redirect

Endpoint	`GET /:shortCode`
Response	`301 Moved Permanently` or `302 Found`
Header	`Location: https://very-long-url.com/...`

301 vs 302: A 301 tells the browser to cache the redirect permanently — less server load, but you lose click analytics. A 302 means the browser checks your server every time — more load, but you can count clicks. Most URL shorteners use 302 for analytics.

▸ Write flow: creating a short URL

Click chart to zoom

Write path: the API grabs a pre-generated key from the KGS, stores the mapping, and caches it

▸ Read flow: redirecting to the original URL

Click chart to zoom

Read path: cache-first lookup keeps redirects under 5 ms for hot URLs

Base62 Encoding for Short URLs

import hashlib
import time
import random

BASE62 = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

def base62_encode(num: int) -> str:
    """Convert a number to base62 string."""
    if num == 0:
        return BASE62[0]
    result = []
    while num > 0:
        result.append(BASE62[num % 62])
        num //= 62
    return "".join(reversed(result))

def base62_decode(s: str) -> int:
    """Convert a base62 string back to a number."""
    num = 0
    for char in s:
        num = num * 62 + BASE62.index(char)
    return num

# Approach 1: Hash the URL and take first 7 chars
def hash_approach(long_url: str) -> str:
    """MD5 hash → take first 43 bits → base62 encode."""
    hash_hex = hashlib.md5(long_url.encode()).hexdigest()
    hash_int = int(hash_hex[:11], 16)  # Take first 43 bits
    return base62_encode(hash_int)[:7]

# Approach 2: Auto-incrementing counter → base62
def counter_approach(counter: int) -> str:
    """Global counter → base62 encode. Guaranteed unique!"""
    return base62_encode(counter)

# How many unique URLs can 7 characters hold?
print(f"7-char base62 capacity: {62**7:,} URLs")  # 3.5 trillion!
print(f"6-char base62 capacity: {62**6:,} URLs")  # 56 billion

# Examples
print(f"\nHash: {hash_approach('https://example.com/very/long/path')}")
print(f"Counter 1000: {counter_approach(1000)}")
print(f"Counter 1000000: {counter_approach(1000000)}")

# Decode round-trip
short = base62_encode(123456789)
print(f"\nEncode 123456789 → {short}")
print(f"Decode {short} → {base62_decode(short)}")

Output

7-char base62 capacity: 3,521,614,606,208 URLs
6-char base62 capacity: 56,800,235,584 URLs

Hash: kPx9dME
Counter 1000: g8
Counter 1000000: 4c92

Encode 123456789 → 8M0kX
Decode 8M0kX → 123456789

Key Generation: Hash vs Counter

The core challenge: how do you generate unique, short, non-guessable keys?

Approach 1: Hash the URL

Hash the long URL (MD5 or SHA-256), take the first 7 characters (base62-encoded).
Problem: Collisions! Two different URLs might produce the same short code. You must check the DB and retry with a salt if there's a collision.
Advantage: Same long URL always generates the same short URL (deduplication).

Approach 2: Auto-incrementing counter + base62

Use a global counter (from a database sequence or a distributed ID generator like Twitter's Snowflake). Convert the counter to base62.
Problem: Sequential IDs are predictable. Attacker can guess /x7Kp3 if they know /x7Kp2 exists. Fix: shuffle bits or add randomness.
Advantage: Guaranteed uniqueness. No collision checks needed.

Approach 3: Pre-generated Key Service (KGS)

A separate service pre-generates millions of random unique keys and stores them. When a URL is created, it grabs a key from the pool.
No collision checking at write time. No sequential patterns. Fast.
The KGS just needs to ensure keys aren't reused (mark them as "used" atomically).
This is often the best approach for interviews — it separates concerns cleanly.

▸ Key generation with Base62 encoding

High-Level Architecture

Let's put the pieces together:

Write path (create short URL):

Client sends POST /api/v1/urls with the long URL.
API server requests a unique key from the Key Generation Service.
API server stores the mapping (short_key → long_url) in the database.
API server writes the mapping to the cache (write-through).
Returns the short URL to the client.

Read path (redirect):

Client visits GET /x7Kp2.
API server checks the cache (Redis). Cache hit? Return 302 redirect immediately.
Cache miss? Query the database, cache the result, return 302.

Components:

Load Balancer — Distributes traffic across API servers.
API Servers (stateless) — Handle URL creation and redirect logic.
Key Generation Service — Pre-generates unique short keys.
Database — Stores URL mappings. NoSQL (DynamoDB, Cassandra) is great here — it's simple key-value lookups with no complex queries.
Cache (Redis) — Caches hot URL mappings. With 80/20 rule, caching the top 20% of URLs handles ~80% of reads.
Analytics Service — Async logging of click events via message queue for tracking.

▸ Full architecture: all components together

Note: Think of the Key Generation Service like a ticket dispenser at a deli counter. It pre-prints thousands of numbered tickets. When a customer arrives, you just hand them the next ticket — no need to think of a new number on the spot. Fast, unique, and simple.

Database Choice and Schema

This is a key-value workload: given a short key, return the long URL. NoSQL databases like DynamoDB or Cassandra are ideal here.

If using SQL (for simplicity or familiarity), the schema is straightforward:

urls table:

short_key (VARCHAR 7, PRIMARY KEY) — The short code
long_url (TEXT) — The original URL
user_id (BIGINT) — Who created it (nullable)
created_at (TIMESTAMP) — When it was created
expires_at (TIMESTAMP) — When it expires (nullable)
click_count (BIGINT) — Number of redirects

Index on long_url if you want to check for duplicates (same URL shouldn't generate two different short codes).

For 3 TB of data, you'll need to shard the database. Hash-based sharding on short_key distributes evenly and makes lookups \(O(1)\) — you know exactly which shard to query.

Extras: Rate Limiting and Analytics

Rate Limiting: Prevent abuse by limiting how many URLs a user can create per hour. Use a token bucket or sliding window algorithm (more details in the Rate Limiter lesson). Unauthenticated users get stricter limits.

Analytics: Track clicks asynchronously. When a redirect happens, publish a click event to a message queue (Kafka). A separate analytics service consumes events and aggregates stats (clicks per day, geographic breakdown, referrer). This keeps the redirect path fast — no synchronous database writes for analytics.

Expiration: Run a periodic cleanup job that deletes expired URLs and returns their keys to the KGS pool for reuse. Don't do this inline during reads — just check expires_at and return 404 if expired.

Note: Interview tip: For URL shortener, the key talking points are: (1) base62 encoding math, (2) key generation strategy (mention the KGS), (3) read-heavy caching strategy, (4) 301 vs 302 trade-off for analytics. These show you understand the unique challenges of this system.