Chapter 67: Design URL Shortener Service

1. Requirements

Functional Requirements

• Shorten URL: Given a long URL, generate a unique short URL (e.g., short.ly/aBc123)
• Redirect: Given a short URL, redirect to the original long URL
• Custom aliases: Allow users to specify custom short codes (e.g., short.ly/apple-event)
• Expiration: Support TTL (time-to-live) for temporary short URLs
• Analytics: Track click counts, referrers, geolocation, devices

Non-Functional Requirements

• Scale: Support 100 billion URLs with 1000:1 read/write ratio
• High availability: 99.99% uptime (redirects must work reliably)
• Low latency: Redirects must be fast (< 50ms P95)
• Short URLs: Keep short codes compact (6-8 characters)
• Unpredictability: Short codes should not be easily guessable (security)

Capacity Estimation

Write: 1K URLs/sec (100M per day, 36B per year)
Read: 1M redirects/sec (1000:1 read/write ratio)
Storage: 100B URLs * 500 bytes/URL = 50 TB
Bandwidth: 1M RPS * 500 bytes = 500 MB/sec egress

2. High-Level Design

API Endpoints

POST /api/v1/shorten
Request: { "url": "https://example.com/very/long/url", "customAlias": "my-link", "ttl": 86400 }
Response: { "shortUrl": "https://short.ly/aBc123", "longUrl": "...", "expiresAt": "2026-05-13T12:00:00Z" }

GET /{shortCode}
Response: HTTP 301/302 redirect to long URL

GET /api/v1/stats/{shortCode}
Response: { "clicks": 123456, "countries": {...}, "referrers": {...} }

Data Flow

1. Shorten: User submits long URL → API generates short code → Store mapping in DB → Return short URL
2. Redirect: User visits short URL → Check cache → If miss, query DB → Redirect to long URL → Log analytics

3. ID Generation: Short Code Creation

The core challenge is generating unique, short, unpredictable IDs. We need 6-7 character codes to support 100B URLs.

Base62 Encoding

Use alphanumeric characters: a-z, A-Z, 0-9 (62 possible characters)

62^6 = 56 billion combinations
62^7 = 3.5 trillion combinations (sufficient for 100B URLs)

Approach 1: Counter-Based Generation

Use a distributed counter and encode it in base62.

// Pseudo-code
long id = getNextIdFromDistributedCounter();
String shortCode = base62Encode(id);

// Example:
// ID: 125 → Base62: "cb"
// ID: 1234567890 → Base62: "1LY7VK"

Pros and Cons

• Pros: Simple, no collisions, sequential IDs are efficient for database indexing
• Cons: Sequential codes are predictable (security issue), need distributed coordination for counter

Distributed Counter Implementation

• Option A: Database auto-increment (single point of bottleneck)
• Option B: Redis INCR (fast, but Redis is single point of failure)
• Option C: Range allocation (each server pre-allocates a range, e.g., Server 1: 1-1000, Server 2: 1001-2000)

Approach 2: Hash-Based Generation

Hash the long URL and take the first N characters.

// Pseudo-code
String hash = sha256(longUrl);
String shortCode = base62Encode(hash).substring(0, 7);

// Example:
// sha256("https://example.com") → "5d41402abc4b2a76b9719d911017c592"
// base62(0x5d41402abc) → "aBc123D" (take first 7 chars)

Pros and Cons

• Pros: No coordination needed, deterministic (same URL always gets same short code)
• Cons: Collision possible (different URLs can hash to same short code), need collision resolution

Collision Handling

1. Append a salt to the URL and rehash: sha256(url + salt)
2. Try multiple hash functions (MD5, SHA256, SHA512)
3. Append a counter: sha256(url + attemptNumber)

Approach 3: Hybrid (Recommended)

Combine counter-based generation with randomization to avoid predictability.

// Use distributed counter for uniqueness
long id = getNextIdFromRangeAllocator();

// XOR with a random salt to shuffle bits (unpredictability)
long shuffledId = id ^ RANDOM_SALT;

// Base62 encode
String shortCode = base62Encode(shuffledId);

4. Redirect: 301 vs 302

HTTP Status Codes

Decision Criteria

• Use 301 if long URL never changes (reduces server load, but analytics may miss repeat visits)
• Use 302 if you need analytics on every click (every click hits your server, allowing tracking)

Recommendation: Use 302 for URL shortener to track all clicks and support analytics.

Caching Strategy

Cache hot short URLs in Redis to avoid DB lookups on every redirect.

// Redirect flow with cache
String shortCode = extractFromRequest(request);

// Check Redis cache first
String longUrl = redis.get("short:" + shortCode);

if (longUrl == null) {
    // Cache miss: query database
    longUrl = db.query("SELECT long_url FROM urls WHERE short_code = ?", shortCode);

    // Cache for 1 hour
    redis.setex("short:" + shortCode, 3600, longUrl);
}

// Log analytics asynchronously
analyticsQueue.publish(new ClickEvent(shortCode, userAgent, ip, referrer));

// Redirect
return redirect(longUrl, 302);

5. Analytics: Click Tracking

Data Collection

On every redirect, capture click metadata asynchronously to avoid blocking the redirect.

{
  "shortCode": "aBc123",
  "timestamp": "2026-05-12T14:23:45Z",
  "ip": "203.0.113.42",
  "country": "US",
  "city": "San Francisco",
  "userAgent": "Mozilla/5.0...",
  "device": "mobile",
  "os": "iOS",
  "browser": "Safari",
  "referrer": "https://twitter.com/post/123"
}

Pipeline Architecture

Aggregation Strategy

• Real-time: Update counters in Redis (total clicks, clicks per day) for dashboard
• Batch: Store raw events in Kafka/S3, process in batches for detailed reports
• Pre-aggregation: Use stream processing (Flink) to compute aggregates (clicks by country, device, hour)

Analytics Schema (Data Warehouse)

-- Fact table (append-only, partitioned by date)
CREATE TABLE click_events (
    click_id BIGINT,
    short_code VARCHAR(10),
    timestamp TIMESTAMP,
    ip_address VARCHAR(45),
    country VARCHAR(2),
    device_type VARCHAR(20),
    referrer VARCHAR(500),
    user_agent VARCHAR(500),
    PRIMARY KEY (click_id, timestamp)
) PARTITION BY RANGE (timestamp);

-- Aggregate table (updated by batch job)
CREATE TABLE url_stats (
    short_code VARCHAR(10) PRIMARY KEY,
    total_clicks BIGINT,
    last_clicked_at TIMESTAMP,
    top_countries JSONB,
    top_referrers JSONB
);

6. Database Design

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,
    INDEX idx_short_code (short_code),
    INDEX idx_user_id (user_id),
    INDEX idx_created_at (created_at)
);

CREATE TABLE custom_aliases (
    alias VARCHAR(50) PRIMARY KEY,
    short_code VARCHAR(10) REFERENCES urls(short_code)
);

-- Separate table for mutable click counts (avoid write contention)
CREATE TABLE url_stats (
    short_code VARCHAR(10) PRIMARY KEY,
    click_count BIGINT DEFAULT 0,
    last_updated TIMESTAMP
);

Key-Value Store Alternative

For ultra-high scale, consider a NoSQL key-value store (DynamoDB, Cassandra) for the main lookup:

// DynamoDB schema
Table: urls
Partition Key: short_code (string)
Attributes: {
    long_url: string,
    created_at: timestamp,
    expires_at: timestamp,
    user_id: number
}

// Redirect query (single-digit millisecond latency)
GET /urls/aBc123 → { long_url: "https://..." }

Expiration Handling

• Lazy deletion: Check expires_at on redirect, return 404 if expired
• TTL: Use database TTL features (DynamoDB TTL, Redis EXPIRE) to auto-delete expired URLs
• Background job: Daily cron job to delete expired URLs (cleanup old data)

7. Scalability

Caching Hot URLs

• 80/20 rule: 20% of URLs account for 80% of traffic (viral links, popular campaigns)
• Cache these hot URLs in Redis with TTL (1 hour)
• Use LRU (Least Recently Used) eviction policy
• Monitor cache hit rate (target > 90%)

Database Sharding

Shard the database by short code hash for horizontal scaling:

// Shard selection
int shard = hash(shortCode) % NUM_SHARDS;
String longUrl = shards[shard].query("SELECT long_url FROM urls WHERE short_code = ?", shortCode);

Read Replicas

• Redirects are read-heavy (1000:1 read/write ratio)
• Add read replicas to each shard (e.g., 1 primary + 5 replicas)
• Route reads to replicas, writes to primary

CDN for Static Assets

• If short URLs serve a static landing page (e.g., preview with thumbnail), cache it in CDN
• Reduces latency for global users

Geographic Distribution

• Deploy API servers in multiple regions (US, EU, Asia)
• Use GeoDNS to route users to nearest region
• Replicate data across regions (eventual consistency acceptable for analytics)

8. Additional Considerations

Security

• Rate limiting: Prevent abuse (e.g., 100 URL shortens per user per day)
• Spam detection: Block malicious URLs (phishing, malware) using URL reputation services
• CAPTCHA: Require CAPTCHA for anonymous users to prevent bot abuse
• URL validation: Sanitize and validate long URLs before storing

Custom Domains

• Allow users to use custom domains (e.g., go.company.com/link)
• Store domain mapping in database, use it during redirect
• Requires DNS configuration and SSL certificate management

QR Code Generation

• Generate QR codes for short URLs (useful for print media)
• Store QR code image in S3, return URL in API response

Summary

A scalable URL shortener at 100B URLs and 1M RPS requires:

• Short code generation: Counter-based with randomization (or hash-based with collision handling)
• Database: NoSQL (DynamoDB) or sharded SQL for horizontal scaling
• Caching: Redis for hot URLs (90%+ cache hit rate)
• Redirect: 302 status for analytics tracking
• Analytics: Async click logging via Kafka/stream processing to data warehouse
• Scalability: Sharding, read replicas, CDN, multi-region deployment

The design is read-heavy (1000:1), so focus on caching and read scaling. Write path (shortening) is less critical but must ensure unique ID generation.