Design a URL Shortener

Design a highly scalable URL shortening service like bit.ly or TinyURL. Convert long URLs into short, shareable links while handling massive scale and ensuring low latency access.

1. Functional Requirements

📊 What the System Should Do

Core Requirements:

• Shorten long URLs to 6-7 character codes
• Redirect short URLs to original URLs
• URL expiration after 10 years (default)

Nice-to-Have Features:

• Custom aliases (vanity URLs)
• Analytics & click tracking
• User accounts & URL management
• QR code generation
• Bulk URL shortening
• API rate limiting per user

2. Non-Functional Requirements

⚡ How Well the System Should Perform

Scale Requirements

• 100M URLs shortened per day
• 10:1 read/write ratio
• Store data for 10 years
• Global user base

Performance Requirements

• <100ms redirect latency (P99)
• <200ms URL creation time
• 99.9% availability (3 nines)
• Handle 3x peak traffic

3. Back-of-the-Envelope Estimation

🧮 Capacity Planning

📈 QPS Calculation

Write Operations:

URLs shortened/day = 100M

Write QPS = 100M / 86,400 ≈ 1,200 QPS

Peak Write QPS = 1,200 × 3 = 3,600 QPS

Read Operations (10:1 ratio):

URL redirects/day = 100M × 10 = 1B

Read QPS = 1B / 86,400 ≈ 11,600 QPS

Peak Read QPS = 11,600 × 3 = 34,800 QPS

💾 Storage Requirements

Per URL Storage:

Short URL: 7 chars = 7 bytes

Original URL: ~500 bytes average

Metadata: ~200 bytes (created_at, user_id, etc.)

Total per URL ≈ 700 bytes

10-Year Storage:

Total URLs = 100M/day × 365 × 10 = 365B URLs

Storage = 365B × 700 bytes = 256 TB

With replication (3x) = 768 TB

🌐 Bandwidth Requirements

Write Bandwidth:

Incoming = 3,600 QPS × 500 bytes = 1.8 MB/s

Read Bandwidth:

Redirects = 34,800 QPS × 200 bytes = 7 MB/s

Total Peak Bandwidth = 9 MB/s

4. Core Entities / Data Model

🗂️ Domain Objects & Relationships

Core Entities

1. URL Entity

• short_code: String (Primary Key) - "8KpQ5Wx"

• long_url: String - Original URL

• created_at: Timestamp

• expires_at: Timestamp

• user_id: String (nullable) - For registered users

• click_count: Integer - Analytics

2. User Entity (Optional)

• user_id: String (Primary Key)

• email: String

• api_key: String

• created_at: Timestamp

• rate_limit: Integer

3. Analytics Entity

• short_code: String (Foreign Key)

• timestamp: Timestamp

• ip_address: String

• user_agent: String

• referrer: String

• country: String

Entity Relationships

• User → URLs: One-to-Many (one user can create many URLs)
• URL → Analytics: One-to-Many (one URL has many click events)
• Custom aliases stored in same URL table with special flag

5. API Design

🔌 REST API Endpoints

Core APIs

POST /api/shorten

Create a short URL

Request:

{

"long_url": "https://example.com/very/long/path",

"custom_alias": "mylink" // optional

}

Response (201):

{

"short_url": "https://short.ly/8KpQ5Wx",

"long_url": "https://example.com/very/long/path",

"expires_at": "2034-01-01T00:00:00Z"

}

GET /{short_code}

Redirect to original URL

Response (301):

Location: https://example.com/very/long/path

Cache-Control: public, max-age=3600

Analytics APIs (Nice-to-Have)

GET /api/analytics/{short_code}

Get click analytics

Response (200):

{

"total_clicks": 1234,

"unique_visitors": 890,

"top_referrers": ["google.com", "twitter.com"],

"top_countries": ["US", "UK", "IN"]

}

DELETE /api/urls/{short_code}

Delete a URL (owner only)

Response (204): No Content

6. High-Level Design

🏗️ System Architecture Overview

Write Path

1. Client sends long URL to API
2. Load balancer routes to write service
3. ID generator creates unique Snowflake ID
4. Convert ID to Base62 short code
5. Store in database (sharded by short code)
6. Return short URL to client

Read Path

1. User clicks short URL
2. CDN checks cache first
3. If miss, routes to read service
4. Check Redis cache for hot URLs
5. If miss, query database
6. Return 301 redirect with cache headers

7. Deep Dive - Detailed Design

7.1 URL Generation Strategy

🔢 Snowflake ID + Base62 Encoding

Why This Approach?

Snowflake IDs provide guaranteed uniqueness in a distributed system without coordination. Base62 encoding creates URL-safe, human-readable short codes.

Snowflake ID Structure (64 bits):

• 41 bits: Timestamp (milliseconds since epoch)

• 5 bits: Datacenter ID (32 datacenters)

• 5 bits: Worker ID (32 workers per DC)

• 12 bits: Sequence number (4096/ms)

= 4M unique IDs per second per worker

Base62 Encoding

Character set: [0-9][a-z][A-Z] = 62 chars

7 chars = 62^7 = 3.5 trillion combinations

Example:

Snowflake ID: 1234567890123456789

Base62: "8KpQ5Wx"

7.2 Database Design

💾 NoSQL Database Schema

Why NoSQL (Cassandra/DynamoDB)?

• Simple key-value access pattern
• Horizontal scaling for billions of URLs
• Built-in replication and fault tolerance
• Low latency reads/writes

Table Design

Main Table: url_mappings

Partition Key: short_code (String)

Attributes:

- long_url (String)

- created_at (Timestamp)

- expires_at (Timestamp, TTL)

- user_id (String, optional)

- click_count (Counter)

Custom Alias Table: custom_urls

Partition Key: custom_alias (String)

Attributes: same as above

Sharding Strategy

Shard by first 2 characters of short_code:

• "8K*" → Shard 1

• "pQ*" → Shard 2

• Provides 62^2 = 3,844 logical shards

7.3 Caching Strategy

⚡ Multi-Level Caching

Cache Levels

L1: CDN Cache

• Cache 301 redirects at edge locations

• TTL: 24 hours for popular URLs

• Reduces latency to <10ms for cached hits

L2: Application Cache (Redis)

• Cache top 20% URLs (80% of traffic)

• LRU eviction policy

• TTL: 1 hour, refresh on access

• Cluster with 3 replicas

L3: Database Cache

• Built-in cache in Cassandra/DynamoDB

• Row cache and key cache

• Automatic management

Cache Warming Strategy

• Pre-load trending URLs based on analytics

• Batch job runs every hour

• Queries: SELECT top 10000 by click_count

• Prevents cache stampede on popular URLs

7.4 Performance Optimizations

🚀 Optimization Techniques

Write Optimizations

• Async write to analytics DB
• Batch inserts for bulk operations
• Write-through cache for new URLs
• Connection pooling (100 connections)

Read Optimizations

• Bloom filter to check non-existent URLs
• Read replicas in multiple regions
• HTTP/2 for connection reuse
• Precomputed analytics aggregations

8. Trade-offs and Alternatives

⚖️ Design Decisions & Alternatives

ID Generation Approaches

Approach	Pros	Cons	Our Choice
Snowflake ID	No coordination, Time-ordered	Clock sync needed	✓ Selected
Counter + DB	Simple, Sequential	Single point of failure	-
Random UUID	No coordination	Too long (128 bits)	-
Hash(URL)	Deterministic	Collisions possible	-

Database Choices

NoSQL (Chosen)

✓ Horizontal scaling
✓ Simple key-value pattern
✓ Built-in sharding
✗ No complex queries
✗ Eventual consistency

SQL (Alternative)

✓ ACID guarantees
✓ Complex queries
✓ Mature ecosystem
✗ Harder to scale
✗ More expensive at scale

9. Potential Issues & Solutions

🔧 Challenges & Mitigations

Potential Issues

1. Hotspot URLs

Problem: Viral URLs overwhelm single shard

Solution:

• Aggressive CDN caching
• Read replicas for hot shards
• Separate "viral" cache tier

2. Custom Alias Conflicts

Problem: Two users want same custom alias

Solution:

• First-come-first-served with DB constraint
• Suggest alternatives (mylink1, mylink-2)
• Reserve premium aliases

3. Abuse & Spam

Problem: Malicious URLs, phishing

Solution:

• URL blacklist checking (Google Safe Browsing)
• Rate limiting per IP/user
• ML-based spam detection
• Manual review queue for reports

4. Analytics at Scale

Problem: Billions of click events to process

Solution:

• Stream processing (Kafka + Spark)
• Time-series database (InfluxDB)
• Pre-aggregated materialized views
• Sampling for real-time stats

10. Security Considerations

🔒 Security Measures

Input Validation

• Validate URL format and protocol
• Block private IP ranges
• Limit URL length (2048 chars)
• Sanitize custom aliases

Access Control

• API key authentication
• Rate limiting per user/IP
• HTTPS only
• CORS configuration

11. Monitoring & Observability

📊 Key Metrics to Track

System Metrics

• API latency (P50, P95, P99)
• QPS (reads vs writes)
• Error rates
• Database connections

Business Metrics

• URLs created per day
• Active URLs
• Click-through rates
• User engagement

Infrastructure

• Cache hit ratio
• Database disk usage
• CPU/Memory utilization
• Network bandwidth

Summary

Key Takeaways

Snowflake + Base62 provides scalable, collision-free URL generation without coordination

NoSQL database (Cassandra/DynamoDB) handles billions of URLs with horizontal scaling

Multi-level caching (CDN → Redis → DB) ensures <100ms latency at scale

Sharding by short code prefix distributes load evenly across database nodes

Analytics pipeline uses stream processing for real-time insights without impacting main flow

Security measures include URL validation, rate limiting, and abuse detection

This design handles 100M URLs/day with 34,800 peak read QPS, maintains <100ms latency, and scales to 365B URLs over 10 years while ensuring 99.9% availability.