Design a URL Shortener

Design a URL shortening service that converts long URLs into short, shareable links and redirects users to the original URLs.

Related Concepts: Base62 Encoding, Database Sharding, Caching (Redis/Memcached), Load Balancing, Unique ID Generation, CAP Theorem, Read-Heavy Optimization, TTL/Expiration

Step 1: Requirements and Scope

Functional Requirements

• Given a long URL, generate a unique short URL
• Given a short URL, redirect to the original long URL
• Support custom short aliases (optional)
• Support URL expiration (optional)
• Track click analytics (optional)

Non-Functional Requirements

Requirement	Target	Rationale
Availability	99.99%	Broken links = lost users and revenue
Latency	< 100ms redirect	Users expect instant redirects
Durability	Never lose URLs	Links shared widely must always work
Scalability	Billions of URLs	Service grows over time
Security	Non-guessable URLs	Prevent enumeration attacks

Scale Estimation

• 100 million new URLs per month (~40 URLs/second)
• 10:1 read to write ratio -> 1 billion redirects/month (~400 redirects/second)
• Average URL length: 200 bytes
• Storage for 5 years: 100M x 12 x 5 x 200 bytes = 1.2 TB (excluding metadata)

How Many Characters for Short Code?

Characters	Base62 Combinations	Years to Exhaust (at 100M/month)
6	56.8 billion	47 years
7	3.5 trillion	2,900 years
8	218 trillion	181,000 years

Recommendation: 7 characters provides ample headroom

Step 2: High-Level Design

Loading diagram...

Step 3: API Design

Create Short URL

Field	Type	Required	Description
long_url	string	Yes	Original URL to shorten
custom_alias	string	No	User-specified short code
expires_at	timestamp	No	When the link should expire

Response: Short URL with metadata

Redirect Flow

Loading diagram...

301 vs 302 Redirects

Redirect Type	Browser Behavior	Analytics	SEO
301 Permanent	Browser caches, skips server	Undercounts (cached)	Passes link juice
302 Temporary	Always hits server	Accurate tracking	Link juice may not pass

Recommendation: Use 301 for performance, 302 if analytics are critical

Step 4: Short Code Generation Strategies

Strategy Comparison

Strategy	Uniqueness	Predictability	Coordination	Complexity
MD5/SHA Hash	Needs collision handling	Deterministic	None	Low
Counter (Auto-increment)	Guaranteed unique	Very predictable	Central counter	Low
Random Generation	Needs collision check	Unpredictable	None	Low
UUID to Base62	Very likely unique	Unpredictable	None	Low
Snowflake ID	Guaranteed unique	Semi-predictable	Minimal	Medium
Pre-generated Pool	Guaranteed unique	Unpredictable	Pool management	Medium

Strategy 1: Hash-Based

Loading diagram...

Pros: Same URL produces same code (deduplication possible) Cons: Collisions require handling, predictable pattern

Strategy 2: Counter-Based (Distributed)

Loading diagram...

Pros: No collisions, no DB lookup for uniqueness Cons: Sequential patterns reveal traffic volume

Strategy 3: Snowflake ID (Recommended)

Loading diagram...

Component	Bits	Purpose
Sign bit	1	Always 0 (positive number)
Timestamp	41	Milliseconds since epoch (69 years)
Machine ID	10	1024 unique machines
Sequence	12	4096 IDs per millisecond per machine

Result: ~4 million IDs/second per machine, globally unique, no coordination

Step 5: Database Design

Schema Design

Column	Type	Index	Notes
id	BIGINT	Primary Key	Snowflake ID
short_code	VARCHAR(10)	Unique Index	The short URL code
long_url	TEXT	None	Original URL (could be very long)
user_id	BIGINT	Index	Owner of the URL (if authenticated)
created_at	TIMESTAMP	None	For analytics
expires_at	TIMESTAMP	Index	For cleanup jobs
click_count	BIGINT	None	Denormalized for quick access

Database Choice

Database	Pros	Cons	Best For
PostgreSQL	ACID, mature, indexes	Vertical scaling limits	Moderate scale
MySQL	Well-understood, replication	Similar scaling limits	Moderate scale
DynamoDB	Auto-scaling, managed	Eventually consistent, costly	High scale, AWS
Cassandra	Linear scaling, high write	Eventual consistency	Very high scale

Recommendation: Start with PostgreSQL with read replicas, migrate to Cassandra/DynamoDB at scale

Sharding Strategy

Loading diagram...

AWS Alternative: Use Amazon DynamoDB which handles partitioning automatically based on partition key.

Sharding Key	Pros	Cons
short_code	Even distribution, direct lookups	Requires consistent hashing for scaling
user_id	Good for user-specific queries	Hot users cause hot shards
created_at	Good for time-based cleanup	Recent shards are hot

Step 6: Caching Strategy

Cache Architecture

Loading diagram...

Cache Configuration

Cache Tier	TTL	Size	Hit Rate
CDN	24 hours	Unlimited	60-70%
Local memory	5 minutes	10K URLs	20-30%
Redis	30 days	100M URLs	95%+

URL access follows Zipf distribution - a small percentage of URLs get most traffic.

Cache Invalidation

Strategy	When to Use
TTL-based	Default for all entries
Write-through	Update cache on every write
Delete on expire	When URL expires or is deleted

Step 7: Analytics (Optional)

Real-Time Click Tracking

Loading diagram...

Tracked Metrics

Metric	Storage	Use Case
Total clicks	Counter in main DB	Quick access
Clicks over time	Time-series DB	Graphs
Geographic data	Analytics DB	Country/city breakdown
Referrer	Analytics DB	Traffic sources
Device/browser	Analytics DB	User agent analysis

Step 8: Security Considerations

Preventing Abuse

Threat	Mitigation
Enumeration attacks	Random codes, not sequential
Malicious URLs	URL scanning, blocklist checking
Spam creation	Rate limiting, CAPTCHA, authentication
URL hijacking	Ownership verification for custom aliases

Rate Limiting

Operation	Limit	Scope
URL creation	100/hour	Per user/IP
Redirects	1000/minute	Per short code
Custom alias	10/day	Per user

Real-World Systems

Service	Scale	Notable Features
bit.ly	600M clicks/day	Enterprise analytics, branded links
TinyURL	Original service	Simple, no account needed
Rebrandly	Focused on branding	Custom domains, link management
short.io	API-first	White-label solution
T.co (Twitter)	Billions/day	Integrated malware scanning

Summary: Key Design Decisions

Decision	Options	Recommendation
Code generation	Hash, Counter, Random, Snowflake	Snowflake ID for uniqueness + time ordering
Code length	6-8 characters	7 characters (3.5T combinations)
Database	SQL, NoSQL	PostgreSQL to DynamoDB at scale
Caching	Redis, Memcached	Redis Cluster with 30-day TTL
Redirect type	301 vs 302	301 for performance, 302 for analytics
Analytics	Sync vs Async	Async via message queue