System Design Problems

Design a URL Shortener

A URL shortener converts a long URL into a short, unique alias. The short URL redirects to the original long URL. Services like TinyURL, bit.ly, and t.co handle billions of redirects daily with sub-millisecond latency.

Core Functionality — Generate short URLs and redirect with minimal latency
Scale — Handle billions of short URLs and high read-to-write ratios
Availability — Redirect service must be highly available (reads >> writes)

The challenge is balancing simplicity with scalability: generating unique IDs efficiently while maintaining fast lookups across a global infrastructure.

Requirements

Functional Requirements

Given a long URL, generate a unique short URL
Given a short URL, redirect to the original URL
Users can optionally set a custom short URL alias
URLs expire after a configurable TTL
Support analytics (click count, referrer, geographic data)

Non-Functional Requirements

Latency: Redirect in < 10ms (99th percentile)
Availability: 99.99% uptime (redirect is read-heavy)
Durability: Short URLs must never be lost
Scalability: 100M new URLs/month, 10:1 read-to-write ratio

The read-to-write ratio is heavily skewed toward reads. A URL created once may be read millions of times. This asymmetry drives the architecture toward read-optimized storage and aggressive caching.

Back-of-the-Envelope Estimation

Short URL Length

L = \lceil \log_b(N) \rceil

Here,

$L$ =Number of characters in the short URL
$b$ =Base of the character set (62 for alphanumeric)
$N$ =Total number of unique URLs needed

Estimating Short URL Space

With a 7-character URL using 62 characters (a-z, A-Z, 0-9):

Capacity = 62^7 ≈ 3.5 trillion unique URLs

At 100M new URLs/month, this lasts ~2,900 years. A 7-character short URL is sufficient.

Storage estimation:

100M URLs/month × 500 bytes/URL × 12 months × 5 years = 3 TB

API Design

Architecture Diagram

POST /api/v1/urls
Request:  { "long_url": "https://...", "custom_alias": "my-link", "ttl_days": 30 }
Response: { "short_url": "https://sho.rt/abc123", "expires_at": "2026-07-20" }

GET /{short_code}
Response: 301/302 Redirect to original URL

DELETE /api/v1/urls/{short_code}
Response: { "status": "deleted" }

GET /api/v1/urls/{short_code}/analytics
Response: { "clicks": 1523, "unique_visitors": 892, "top_referrers": [...] }

Use 301 (Permanent Redirect) for SEO benefits and to reduce server load (browser caches the redirect). Use 302 (Temporary Redirect) if you need to track analytics on every redirect.

High-Level Architecture

Detailed Design

ID Generation Strategies

The critical design decision is how to generate unique short identifiers:

DfBase62 Encoding

Base62 encoding maps a numeric ID to a string using characters [a-zA-Z0-9]. This produces compact, URL-safe strings without special characters.

Strategy	Pros	Cons
MD5/SHA256 Hash	Deterministic, no coordination	Collisions, long strings, slow
Auto-increment ID	Simple, guaranteed unique	Predictable, centralized bottleneck
Pre-generated ID Service	Fast lookup, no collisions	Requires separate service, storage
Snowflake ID	Distributed, time-ordered	Longer IDs, requires coordination
Counter-based (Base62)	Compact, unique, fast	Requires persistent counter

Base62 Encoding

id_{short} = \text{base62}(id_{numeric})

Here,

$id_{short}$ =Short URL code (e.g., 'dK3x7B')
$id_{numeric}$ =Numeric unique identifier
$base62$ =Encoding function using [a-zA-Z0-9]

Base62 Encoding Example

Numeric ID: 1,234,567,890

Base62 encoding: 1234567890 ÷ 62 = 19,912,385 remainder 20 → 'k' 19912385 ÷ 62 = 321,167 remainder 31 → 'v' 321167 ÷ 62 = 5,180 remainder 7 → '7' 5180 ÷ 62 = 83 remainder 34 → 'i' 83 ÷ 62 = 1 remainder 21 → 'l' 1 ÷ 62 = 0 remainder 1 → '1'

Short code: "1li7vk" (6 characters)

Database Schema

CREATE TABLE urls (
    id          BIGINT PRIMARY KEY,
    short_code  VARCHAR(10) UNIQUE NOT NULL,
    long_url    TEXT NOT NULL,
    user_id     BIGINT,
    created_at  TIMESTAMP DEFAULT NOW(),
    expires_at  TIMESTAMP,
    click_count BIGINT DEFAULT 0
);

CREATE INDEX idx_short_code ON urls(short_code);
CREATE INDEX idx_expires_at ON urls(expires_at);

Ensure the short_code column has a unique index. Consider partitioning by short_code hash if the table grows beyond a single node's capacity.

Caching Strategy

Given the read-heavy workload, caching is essential:

Cache-aside pattern: Check cache first, fall back to DB, populate cache on miss
LRU eviction: Evict least recently accessed URLs
TTL matching: Cache entries expire when URLs expire
Cache hit ratio target: > 99% for hot URLs

Cache Hit Ratio Impact

Effective\,QPS_{db} = QPS_{total} \times (1 - hit\_ratio)

Here,

$QPS_{total}$ =Total incoming read QPS
$hit_ratio$ =Fraction of reads served from cache
$Effective,QPS_{db}$ =QPS reaching the database

Cache Efficiency

With 100K read QPS and 99.5% cache hit ratio:

DB QPS = 100,000 × (1 - 0.995) = 500 QPS

The cache absorbs 99,500 QPS, reducing database load by 99.5%.

Collision Handling

When generating short codes, collisions must be handled gracefully:

Retry with different salt: Append timestamp or random bits and re-hash
Check before insert: Verify uniqueness before writing to database
Use longer codes: Increase length if collision rate is too high
Database constraint: Let the unique constraint catch collisions and retry

With a 7-character Base62 code space (3.5 trillion combinations) and only 100M URLs, the probability of collision is approximately 10^-5, making retries rare.

Scaling Considerations

Read Path Optimization

The redirect path must be extremely fast:

Client requests short URL
Load balancer routes to nearest app server
App server checks Redis cache
Cache hit → return long URL immediately (sub-millisecond)
Cache miss → query database, populate cache, return

Pre-warm the cache with the most frequently accessed URLs. Monitor cache hit ratios and adjust cache size accordingly.

Write Path Optimization

Creating new URLs is less latency-sensitive:

Client submits long URL
App server requests ID from ID Generator service
App server encodes ID to Base62 short code
Write to database (can be async)
Populate cache proactively
Return short URL to client

Database Sharding

Partition the URL table by short_code hash:

Shard Assignment

shard = hash(short\_code) \mod N_{shards}

Here,

$short_code$ =The generated short URL code
$N_{shards}$ =Total number of database shards

Practice Exercises

Design: How would you implement custom aliases (user-chosen short codes)? What additional constraints and validation are needed?
Scale: If the system handles 1B short URLs and 100K QPS reads, estimate the Redis cache memory needed assuming 500 bytes per entry and 99% cache hit ratio.
Trade-offs: Compare using a Snowflake ID vs a pre-generated ID pool for the URL shortener. What are the latency and complexity trade-offs?
Edge Case: How would you handle a viral URL that suddenly receives 10M requests in one minute? Design a strategy to prevent cache stampede.

Key Takeaways:

URL shorteners are read-heavy; optimize the read path with aggressive caching
Base62 encoding produces compact, URL-safe short codes from numeric IDs
The ID generation strategy is the most critical design decision
Cache-aside pattern with high hit ratios (>99%) reduces database load dramatically
Design for the 10:1+ read-to-write ratio at every layer

What to Learn Next

-> Consistent Hashing Sharding data across nodes with minimal redistribution on scaling.

-> Caching Strategies Cache-aside, write-through, write-behind, and cache invalidation.

-> Databases SQL vs NoSQL, indexing, replication, and sharding strategies.

-> Design Unique ID Generator Snowflake IDs, UUIDs, and distributed ID generation strategies.

-> CDNs Caching static content at the edge for low-latency global access.

-> API Design REST conventions, versioning, and error handling patterns.

Design a URL Shortener

Design a URL Shortener

Requirements

Functional Requirements

Non-Functional Requirements

Back-of-the-Envelope Estimation

Short URL Length

Estimating Short URL Space

API Design

High-Level Architecture

Detailed Design

ID Generation Strategies

DfBase62 Encoding

Base62 Encoding

Base62 Encoding Example

Database Schema

Caching Strategy

Cache Hit Ratio Impact

Cache Efficiency

Collision Handling

Scaling Considerations

Read Path Optimization

Write Path Optimization

Database Sharding

Shard Assignment

Practice Exercises

What to Learn Next

Premium Content

Need Expert System Design Help?