Designing a URL Shortener

The URL shortener is one of the most commonly asked system design questions because it appears simple on the surface but reveals your understanding of hashing, database design, caching, and scalability under the hood. You are designing a service like bit.ly that takes a long URL and returns a short alias, then redirects anyone who visits that alias back to the original URL.

Requirements Gathering

Functional Requirements

• Given a long URL, generate a unique short URL.
• When a user visits the short URL, redirect to the original long URL.
• Users can optionally choose a custom alias.
• Short links expire after a configurable TTL (default: 5 years).

Non-Functional Requirements

• The system is read-heavy. The ratio of reads (redirects) to writes (URL creation) is approximately 100:1.
• URL redirection must have low latency (< 50ms at p99).
• Short URLs should be as short as possible.
• High availability. A URL shortener going down breaks every link ever created.

Capacity Estimation

Assumptions:
  - 100 million new URLs per month
  - 100:1 read-to-write ratio → 10 billion redirects per month

Writes: 100M / (30 × 24 × 3600) ≈ 40 URLs/sec
Reads:  10B / (30 × 24 × 3600) ≈ 3,850 redirects/sec

Storage (5-year retention):
  - 100M × 12 months × 5 years = 6 billion URLs
  - Average URL length: 500 bytes (long URL) + 7 bytes (short code) + metadata ≈ 600 bytes
  - Total: 6B × 600 bytes ≈ 3.6 TB

Cache (for hot URLs):
  - 20% of URLs generate 80% of traffic (Pareto principle)
  - Daily redirects: 10B / 30 ≈ 333M/day
  - Cache 20% of daily URLs: 333M × 0.2 × 600 bytes ≈ 40 GB (fits in memory)

Short URL Generation

The core challenge: how do you generate a short, unique code for each URL?

Base62 Encoding

Use the characters `[a-zA-Z0-9]` (62 characters). A 7-character code gives you 62^7 ≈ 3.5 trillion unique combinations, far more than the 6 billion URLs we need to store.

Approach 1: Hash and Truncate

Hash the long URL (e.g., MD5 or SHA-256) and take the first 7 characters of the base62 encoding.

import hashlib
import base64

def generate_short_code(long_url):
    hash_bytes = hashlib.md5(long_url.encode()).digest()
    base62 = base64.b64encode(hash_bytes).decode()
    # Take first 7 alphanumeric characters
    code = ''.join(c for c in base62 if c.isalnum())[:7]
    return code

Collision handling: Different URLs may produce the same 7-character code. When a collision is detected (the code already exists in the database for a different URL), append a counter or timestamp to the input and rehash. Alternatively, probe: try characters 1-7, then 2-8, then 3-9, and so on.

Pros: Deterministic. The same long URL always produces the same short code (useful for deduplication). Cons: Collision resolution adds complexity and database round-trips.

Approach 2: Counter-Based (Pre-generated IDs)

Use a global auto-incrementing counter. Convert the counter value to base62.

BASE62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def to_base62(num):
    if num == 0:
        return BASE62[0]
    result = []
    while num > 0:
        result.append(BASE62[num % 62])
        num //= 62
    return ''.join(reversed(result))

# to_base62(1000000) → "4c92"
# to_base62(3500000000000) → "zzzzzz" (still only 6 chars)

Pros: No collisions by construction. Simple and fast. Cons: Sequential IDs are predictable (security concern). Requires a centralized counter, which becomes a bottleneck.

Approach 3: Distributed ID Generation

To avoid the single-counter bottleneck, use a distributed ID generator:

• Snowflake-style IDs: Combine timestamp + machine ID + sequence number into a 64-bit integer. Convert to base62.
• Range-based allocation: A coordination service (like ZooKeeper) assigns ranges to each server. Server 1 gets IDs 1-1,000,000, Server 2 gets 1,000,001-2,000,000, etc. Each server increments within its range without coordination.
• UUID approach: Generate a UUID and take a portion, but this wastes characters and increases collision risk.

The range-based approach is the best balance of simplicity and scalability for interviews.

301 vs 302 Redirects

This is a detail that separates strong candidates from average ones.

• 301 (Moved Permanently): The browser caches the redirect. Subsequent visits go directly to the long URL without hitting your server. Reduces server load but you lose analytics data.
• 302 (Found / Temporary Redirect): The browser does not cache. Every visit hits your server first. Higher server load but you can track every click.

For a URL shortener, use 302 if analytics is a feature (most real-world shorteners). Use 301 if you want to minimize server load and do not need click tracking.

Database Design

Table: urls
┌─────────────┬──────────────┬──────────────────────────────┬─────────────────────┬──────────┐
│ short_code   │ long_url     │ created_at                   │ expires_at          │ user_id  │
│ (PK, CHAR 7) │ (TEXT)       │ (TIMESTAMP)                  │ (TIMESTAMP)         │ (BIGINT) │
├─────────────┼──────────────┼──────────────────────────────┼─────────────────────┼──────────┤
│ "aB3x9Kp"  │ "https://..."│ 2024-01-15T10:30:00Z         │ 2029-01-15T10:30:00Z│ 42       │
└─────────────┴──────────────┴──────────────────────────────┴─────────────────────┴──────────┘

Table: analytics (optional)
┌─────────────┬─────────────────────┬────────────┬──────────────┬───────────┐
│ short_code   │ clicked_at          │ ip_address │ user_agent   │ referrer  │
└─────────────┴─────────────────────┴────────────┴──────────────┴───────────┘

Database choice: A NoSQL key-value store (DynamoDB, Cassandra) is a natural fit since the primary access pattern is a point lookup by short code. However, a relational database (PostgreSQL with proper indexing) works perfectly fine at this scale.

Read-Heavy Optimization

Since redirects dominate the workload, caching is critical.

Client → Load Balancer → App Server → Cache (Redis) → Database
                                         ↑
                                    Cache hit: return immediately
                                    Cache miss: query DB, populate cache

Caching Strategy

• Cache-aside (lazy loading): On a redirect request, check the cache first. On a miss, query the database and store the result in the cache with a TTL.
• Cache hot URLs: The 80/20 rule applies strongly. A small percentage of URLs receive the vast majority of traffic.
• Geographically distributed caches: Deploy Redis clusters in multiple regions so that a user in Tokyo does not need to hit a database in Virginia.

Analytics

For a URL shortener, analytics (click counts, geographic distribution, referrer tracking) is a key feature. The naive approach of incrementing a counter on every click creates a write bottleneck.

Better approaches:

• Batch writes: Buffer click events in memory or a local log, then flush to the database in batches every few seconds.
• Streaming pipeline: Publish click events to Kafka. A downstream analytics service aggregates counts and writes to a time-series database or data warehouse.
• Approximate counting: Use HyperLogLog for unique visitor counts, which uses far less memory than storing every visitor.

High-Level Architecture

                    ┌──────────────┐
   Clients ────────>│ Load Balancer│
                    └──────┬───────┘
                           │
              ┌────────────┼────────────┐
              ▼            ▼            ▼
        ┌──────────┐ ┌──────────┐ ┌──────────┐
        │ App Svc 1│ │ App Svc 2│ │ App Svc 3│
        └────┬─────┘ └────┬─────┘ └────┬─────┘
             │             │             │
             └─────────────┼─────────────┘
                           │
                    ┌──────┴───────┐
                    │  Redis Cache │
                    └──────┬───────┘
                           │ (miss)
                    ┌──────┴───────┐
                    │   Database   │
                    └──────────────┘
                           │
                    ┌──────┴───────┐
                    │ Kafka (clicks│
                    │  for analytics)
                    └──────────────┘

Interview Tips

• Lead with capacity estimation. It shows you think about scale before jumping into code. The numbers drive your design decisions (e.g., "3.6 TB fits on a single large database, but we need caching for 3,850 reads/sec").
• Discuss the trade-off between hash-based and counter-based approaches. Neither is strictly better. Hash-based deduplicates identical URLs. Counter-based avoids collisions entirely.
• Do not forget expiration. Short URLs should expire. Mention a cleanup job (cron or TTL-based deletion) and how you handle redirects to expired URLs (404 or custom error page).
• Mention security. Sequential IDs are enumerable. An attacker could scrape all shortened URLs. Mitigations: use random IDs, rate limit the creation API, or add a private/password-protected option.
• Highlight the 301 vs 302 trade-off. This is a small detail that demonstrates depth.
• Scale the analytics separately. Click tracking is a write-heavy workload on top of a read-heavy system. Decoupling analytics via an event stream prevents it from affecting redirect latency.