URL Shortener

Requirements & Scope

Functional Requirements

1. Shorten URL: Given a long URL, generate a unique short URL (e.g., tinyurl.com/abc123).
2. Redirect: Given a short URL, redirect to the original long URL.
3. Custom Aliases: Users can optionally specify a custom short key (e.g., tinyurl.com/my-brand).
4. URL Expiry: URLs can have an optional TTL (time-to-live) after which they expire.
5. Analytics: Track click counts, geographic data, referrer, and device type for each short URL.
6. Delete URL: Users can delete a short URL before its expiry.

Non-Functional Requirements

Requirement	Target
Latency	Redirect must complete in < 10ms at the 99th percentile
Availability	99.99% uptime (the redirect path must always be up)
Throughput	100M URLs created per day, 10B redirects per day
Durability	URLs must never be lost once created
Read:Write Ratio	~100:1 (reads vastly outnumber writes)

Capacity Estimation

Writes: 100M URLs/day ≈ 1,200 URLs/sec
Reads:  10B redirects/day ≈ 115,000 redirects/sec
Storage (5 years): 100M × 365 × 5 = 182.5B URLs
Per URL record ≈ 500 bytes → ~91 TB total storage
Cache: 20% of reads = 2B/day → store hot 20% in Redis (~18 GB)

Key Clarifying Questions

• What is the expected length of the short URL? → Typically 6-7 characters.
• Can users create custom aliases? → Yes, with uniqueness check.
• Do we need analytics? → Yes, at least click count and timestamp.
• What happens when a short URL expires? → Return HTTP 404.
• Is the system public or authenticated? → Both: anonymous shortening + logged-in dashboard.

API Design & Data Model

REST API Design

Create Short URL

POST /api/v1/urls

Request Body:
{
  "longUrl": "https://www.example.com/very/long/path?query=param",
  "customAlias": "my-brand",    // optional
  "expiry": "2026-12-31T23:59:59Z" // optional, null = never
}

Response (201 Created):
{
  "shortUrl": "https://tinyurl.com/abc123",
  "longUrl": "https://www.example.com/very/long/path?query=param",
  "createdAt": "2026-08-16T10:00:00Z",
  "expiresAt": "2026-12-31T23:59:59Z"
}

Redirect

GET /{shortKey}

Response (301 Moved Permanently):
Location: https://www.example.com/very/long/path?query=param

# 301 = browser caches permanently
# 302 = browser always hits our server (better for analytics)

301 vs 302: Use 302 if analytics matter (every redirect hits your server). Use 301 if you want to reduce server load (browser caches and redirects directly).

Delete Short URL

DELETE /api/v1/urls/{shortKey}

Response (204 No Content)

Get URL Analytics

GET /api/v1/urls/{shortKey}/analytics

Response (200 OK):
{
  "shortKey": "abc123",
  "totalClicks": 15234,
  "clicksByDate": { "2026-08-16": 342, ... },
  "topReferrers": ["twitter.com", "reddit.com"],
  "topCountries": ["US", "IN", "UK"]
}

Data Model

Option A: SQL (MySQL / PostgreSQL)

CREATE TABLE urls (
    id            BIGINT PRIMARY KEY AUTO_INCREMENT,
    short_key     VARCHAR(10) UNIQUE NOT NULL,
    long_url      TEXT NOT NULL,
    user_id       BIGINT,
    custom_alias  VARCHAR(20) UNIQUE,
    created_at    TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    expires_at    TIMESTAMP NULL,
    click_count   BIGINT DEFAULT 0
);

CREATE INDEX idx_short_key ON urls(short_key);
CREATE INDEX idx_custom_alias ON urls(custom_alias);
CREATE INDEX idx_expires ON urls(expires_at);

Option B: NoSQL (DynamoDB)

Table: urls
Partition Key: short_key (String)

Attributes:
  long_url: String
  user_id: String  (optional)
  created_at: String (ISO 8601)
  expires_at: String (ISO 8601, null = no expiry)
  click_count: Number

Analytics Table (Separate for High Write Volume)

CREATE TABLE url_clicks (
    id          BIGINT PRIMARY KEY AUTO_INCREMENT,
    short_key   VARCHAR(10) NOT NULL,
    clicked_at  TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    referrer    VARCHAR(500),
    ip_address  VARCHAR(45),
    country     VARCHAR(2),
    device      VARCHAR(20)
);

CREATE INDEX idx_short_key_time ON url_clicks(short_key, clicked_at);

Why separate analytics table? Click events are high-volume writes. Separating them from the main URLs table prevents write contention on the read-heavy URL lookups.

Architecture & Hash Generation

High-Level Architecture

┌──────────┐     ┌──────────────┐     ┌──────────────┐     ┌────────────┐
│  Client   │────▶│ API Gateway  │────▶│ URL Service  │────▶│  Database  │
│  (Web/    │     │  (Rate Limit,│     │ (Shorten,    │     │ (MySQL/    │
│  Mobile)  │     │   Auth)      │     │  Redirect,   │     │ DynamoDB)  │
└──────────┘     └──────────────┘     │  Analytics)  │     └────────────┘
                                      └──────┬───────┘            │
                                             │                    │
                                             ▼                    │
                                      ┌──────────────┐           │
                                      │    Redis     │◀──────────┘
                                      │   Cache      │
                                      └──────────────┘
                                             │
                                      ┌──────┴───────┐
                                      │   Kafka /    │
                                      │   SQS        │
                                      │ (Analytics)  │
                                      └──────────────┘
                                             │
                                      ┌──────▼───────┐
                                      │  Analytics   │
                                      │  Service     │
                                      │ (Click Data) │
                                      └──────────────┘

Component Responsibilities

Component	Responsibility
API Gateway	Rate limiting, authentication, SSL termination, request routing
URL Service	Business logic for shortening, redirect lookup, expiry checks
Redis Cache	Cache hot short keys → long URL mappings (TTL 24h)
Database	Persistent storage for URL mappings
Kafka/SQS	Async event bus for analytics click events
Analytics Service	Processes click events, updates aggregate stats

Hash Generation Strategies

Strategy 1: MD5/SHA256 + Base62 Encoding

import hashlib
import string

ALPHABET = string.ascii_letters + string.digits  # 62 chars
BASE = len(ALPHABET)

def generate_short_key(long_url: str) -> str:
    # Hash the URL
    hash_hex = hashlib.md5(long_url.encode()).hexdigest()
    # Convert first 8 hex chars to integer
    num = int(hash_hex[:8], 16)
    # Encode to base62
    short_key = []
    while num > 0:
        short_key.append(ALPHABET[num % BASE])
        num //= BASE
    return ''.join(short_key[:7])  # 7 chars = 62^7 ≈ 3.5 trillion combinations

Pros: Deterministic (same URL → same key), simple.
Cons: Collisions possible (two URLs hash to same key → retry with salt).

Strategy 2: Counter-Based (Global or Per-Shard)

# Global auto-increment counter
counter = 0

def generate_short_key() -> str:
    global counter
    counter += 1
    return base62_encode(counter)

# Per-shard counter (avoids single point of contention)
# Shard 1: counter 1-100M, Shard 2: 100M-200M, etc.

Pros: No collisions, sequential = predictable length.
Cons: Requires coordination (Kafka auto-increment, or DB sequence).

Strategy 3: Pre-Generated Key Service

┌─────────────────┐
│  Key Generator   │ (offline service)
│  Pre-generates   │
│  millions of     │
│  unique keys     │
│  → stored in DB  │
└────────┬────────┘
         │
         ▼
┌─────────────────┐
│  Key Pool Table  │ (available_keys, partitioned)
│  key_1 | available│
│  key_2 | available│
│  key_3 | claimed  │
└────────┬────────┘
         │
    URL Service claims
    a key on each request

Pros: No runtime computation, no collisions, keys are random.
Cons: Need to monitor key pool levels, refill pipeline.

Redirect Flow (Read Path)

Client → GET /abc123
    │
    ▼
┌─────────┐   HIT    ┌─────────┐
│  Redis   │────────▶│ Return  │
│  Cache   │         │ 301/302 │
└────┬────┘         └─────────┘
     │ MISS
     ▼
┌─────────┐
│Database │──▶ Lookup short_key → long_url
└────┬────┘
     │
     ▼
┌─────────┐    Populate cache (TTL 24h)
│  Redis   │◀─── Write key: short_key → long_url
│  Cache   │
└─────────┘
     │
     ▼
  Return 301/302 to client
  (Async: publish click event to Kafka)

URL Existence Check with Bloom Filter

When creating a new URL:

1. Check Bloom Filter (fast, in-memory)
   - If DEFINITELY NOT EXISTS → create URL directly
   - If PROBABLY EXISTS → check database for actual collision

2. Bloom filter specs for 1B URLs, 1% false positive rate:
   - ~1.2 GB memory (10 bits per element)
   - 7 hash functions
   - 99% accurate for existence checks

# Pseudocode for creation with bloom filter
if not bloom_filter.check(short_key):
    # Definitely not taken — safe to insert
    db.insert(short_key, long_url)
    bloom_filter.add(short_key)
else:
    # Might be taken — check DB to confirm
    existing = db.get(short_key)
    if existing:
        # Collision! Try another key
        short_key = generate_short_key(long_url + salt)
        # Recursive retry
    else:
        # False positive — safe to insert
        db.insert(short_key, long_url)
        bloom_filter.add(short_key)

Scaling & Caching

Scaling Strategy

                    ┌─────────────────────────┐
                    │      Load Balancer       │
                    │    (Round Robin / L7)    │
                    └────────────┬────────────┘
                                 │
              ┌──────────────────┼──────────────────┐
              │                  │                   │
        ┌─────▼─────┐    ┌──────▼──────┐    ┌──────▼──────┐
        │ URL Service │    │ URL Service │    │ URL Service │
        │  Instance 1 │    │  Instance 2 │    │  Instance N │
        └─────┬──────┘    └──────┬──────┘    └──────┬──────┘
              │                  │                   │
              └──────────────────┼──────────────────┘
                                 │
              ┌──────────────────┼──────────────────┐
              │                  │                   │
        ┌─────▼─────┐    ┌──────▼──────┐    ┌──────▼──────┐
        │   Redis    │    │   Redis     │    │   Redis     │
        │  Shard 1   │    │  Shard 2    │    │  Shard N    │
        └─────┬──────┘    └──────┬──────┘    └──────┬──────┘
              │                  │                   │
              └──────────────────┼──────────────────┘
                                 │
              ┌──────────────────┼──────────────────┐
              │                  │                   │
        ┌─────▼─────┐    ┌──────▼──────┐    ┌──────▼──────┐
        │  MySQL     │    │  MySQL      │    │  MySQL      │
        │  Primary   │    │  Replica 1  │    │  Replica 2  │
        └───────────┘    └─────────────┘    └─────────────┘

Database Sharding

Approach: Hash-Based Sharding on short_key

Shard Key = hash(short_key) % number_of_shards

Shard 0: short_keys starting with a-f
Shard 1: short_keys starting with g-l
Shard 2: short_keys starting with m-r
Shard 3: short_keys starting with s-z

# Or use consistent hashing to minimize reshuffling on shard addition

Caching Strategy

Aspect	Decision
What to cache	Short key → long URL mapping (read path)
Cache policy	Cache-aside (lazy loading)
Eviction	LRU with TTL of 24 hours
Cache size	~20 GB (stores hot 20% of URLs)
Hot keys	Top 1% of URLs handle 20%+ traffic → pin to Redis primary shard

# Cache-aside pattern
async def resolve_url(short_key: str) -> str:
    # 1. Check cache
    cached = await redis.get(f"url:{short_key}")
    if cached:
        # Async: publish click event
        kafka.publish("click-events", {"key": short_key, "ts": now()})
        return cached
    
    # 2. Check database
    long_url = await db.query(
        "SELECT long_url FROM urls WHERE short_key = %s AND (expires_at IS NULL OR expires_at > NOW())",
        [short_key]
    )
    
    if long_url:
        # 3. Populate cache
        await redis.setex(f"url:{short_key}", 86400, long_url)  # TTL 24h
        # Async: publish click event
        kafka.publish("click-events", {"key": short_key, "ts": now()})
        return long_url
    
    return None  # URL not found or expired

Analytics Pipeline

┌──────────┐    ┌─────────┐    ┌──────────┐    ┌────────────┐
│ URL Svc  │───▶│  Kafka  │───▶│ Consumer │───▶│ Analytics  │
│ (publish │    │  Topic  │    │  Group   │    │  Database  │
│  click)  │    │         │    │          │    │ (Clickhouse│
└──────────┘    └─────────┘    └──────────┘    │  / Redshift)│
                                               └────────────┘

• Click events are published to Kafka asynchronously (fire-and-forget from the redirect path).
• Analytics consumer aggregates data into time-bucketed tables.
• Dashboard service reads from analytics DB (not the main URLs DB).

URL Expiration

Two approaches:

1. Lazy Expiration (TTL on read):
   - On redirect, check expires_at > NOW()
   - Return 404 if expired, delete asynchronously

2. Active Expiration (Background Job):
   - Cron job runs every hour
   - DELETE FROM urls WHERE expires_at < NOW() LIMIT 10000
   - Batch deletes to avoid DB overload

Rate Limiting

Limits:
  - Anonymous: 10 URLs/hour per IP
  - Authenticated: 100 URLs/hour per user
  - Premium: 1000 URLs/hour per user

Implementation:
  - Sliding window counter in Redis
  - Key: rate_limit:{user_id}:{window}
  - INCR + EXPIRE in pipeline

Deep Dives

1. Custom Aliases — Uniqueness Check

Flow for custom alias:

1. User requests alias "my-brand"
2. Check Bloom Filter → probably exists?
3. If bloom says maybe: SELECT 1 FROM urls WHERE custom_alias = 'my-brand'
4. If exists: return 409 Conflict
5. If not: insert with custom_alias column

DB Index:
  CREATE UNIQUE INDEX idx_custom ON urls(custom_alias) WHERE custom_alias IS NOT NULL;

2. Handling Hot Keys / Thundering Herd

Problem: A viral URL (e.g., during Super Bowl) gets 100K+ requests/sec

Solutions:

1. Cache Replication:
   - Replicate hot key across multiple Redis shards
   - Client reads from random shard → load distributed

2. Request Coalescing:
   - First request populates cache
n   - Subsequent requests within 100ms wait on same result
   - Use Redis SETNX with short TTL as lock

3. Local Cache (Application-Level):
   - Each app server has in-memory LRU cache (e.g., Caffeine)
   - TTL 60s for hot keys
   - Reduces Redis load by 10-100x

3. Database Choice Tradeoffs

Factor	SQL (MySQL)	NoSQL (DynamoDB)
Schema	Fixed schema, ACID	Flexible, eventually consistent
Scaling	Vertical + read replicas	Horizontal by default
Query	JOINs, complex queries	Simple key-value lookups
Cost	Lower at small scale	Predictable at any scale
Best For	When you need analytics joins	When simple key-value is enough

Recommendation: Start with DynamoDB for simplicity. Use SQL if you need complex analytics queries joining URLs with user data.

4. Data Partitioning Strategy

For DynamoDB:
  - Partition Key: short_key (uniform distribution via base62)
  - No hot partitions because hash of short_key is uniform

For MySQL:
  - Shard by hash(short_key) % N
  - Use consistent hashing for resharding
  - Each shard: primary + 2 read replicas

For Redis:
  - Use Redis Cluster (16384 hash slots)
  - Slot = CRC16(short_key) % 16384
  - Automatic sharding + failover

5. Security Considerations

1. Rate Limiting:
   - Per IP: 100 req/min
   - Per API key: 1000 req/min

2. Malicious URL Detection:
   - Check against Google Safe Browsing API
   - Flag URLs with known phishing/malware patterns

3. Abuse Prevention:
   - Block shortening of URLs that redirect to blocked domains
   - CAPTCHA for anonymous users after 5 URLs/hour

4. Input Validation:
   - Validate long URL format (RFC 3986)
   - Sanitize custom aliases (alphanumeric + hyphens only)
   - Max custom alias length: 20 chars

6. Monitoring & Observability

Key Metrics:
  - Redirect latency (p50, p95, p99)
  - Cache hit rate (target > 80%)
  - URLs created per second
  - Database connection pool utilization
  - Kafka consumer lag

Alerts:
  - Cache hit rate drops below 70% → possible hot key issue
  - p99 latency > 50ms → investigate DB slow queries
  - Kafka lag > 10K → scale consumer group

7. Cost Estimation

Per 100M URLs/day:
  - Storage: ~91 TB over 5 years → ~$2,300/month (S3/DynamoDB)
  - Redis: ~20 GB cache → ~$500/month (ElastiCache)
  - Compute: 10 API servers → ~$1,000/month (EC2)
  - Kafka: 3 brokers → ~$600/month
  - Total: ~$4,400/month

Interview Tips

1. Start with requirements — Always clarify read:write ratio first. For URL shortener, it's 100:1.
2. Explain 301 vs 302 — Shows you understand HTTP semantics and analytics tradeoffs.
3. Discuss hash generation tradeoffs — Show you can evaluate approaches (deterministic vs counter vs pre-gen).
4. Bloom filter — Mentioning this shows depth for URL existence checks.
5. Analytics pipeline — Show you can handle async event processing separately from the critical path.
6. Hot keys — Always address the viral URL scenario.