URL Shortener

Problem Statement & Requirements

Functional Requirements

• Given a long URL, generate a short, unique alias (e.g., https://short.ly/abc123)
• When a user hits the short URL, redirect them to the original long URL (HTTP 301/302)
• Users can optionally pick a custom short alias
• Links can have an expiration time (TTL)
• Analytics: track click count, referrer, geo, device (optional but expected in interviews)

Non-Functional Requirements

• High availability — redirections must never go down
• Low latency — redirect in < 10 ms (p99)
• URL should not be guessable — no sequential IDs
• Consistency — same long URL can map to multiple short URLs (user-specific), but a short URL must always resolve to exactly one long URL
• Durability — once created, a short link must survive infrastructure failures

Out of Scope

• User authentication/accounts (simplify for interview)
• Link editing after creation
• Bulk URL shortening API

Scale Estimations

Traffic

Storage

Bandwidth

Cache

• 80/20 rule: 20% of URLs generate 80% of traffic
• Cache 20% of daily read requests: 10B × 0.2 × 1 KB = ~2 TB cache
• Fits in a Redis cluster

This first layer defines the system boundary. The next chapters add application logic and data dependencies. After examining the request paths and tradeoffs, we will add operational safeguards and bring the complete architecture together.

API Design

Create Short URL

POST /api/v1/urls
Content-Type: application/json

Request:
{
  "long_url": "https://www.example.com/very/long/path?q=something",
  "custom_alias": "my-brand",     // optional
  "expires_at": "2026-12-31T00:00:00Z"  // optional
}

Response (201 Created):
{
  "short_url": "https://short.ly/abc123",
  "short_key": "abc123",
  "long_url": "https://www.example.com/very/long/path?q=something",
  "expires_at": "2026-12-31T00:00:00Z",
  "created_at": "2026-04-03T10:00:00Z"
}

Redirect (Read)

GET /:short_key
→ HTTP 301 (permanent) or 302 (temporary) redirect to long_url

301 vs 302 Tradeoff:
  - 301: Browser caches the redirect → less load on our servers,
         but we lose analytics visibility (browser skips us on repeat visits)
  - 302: Browser always hits us → more load but full analytics tracking
  → Use 302 if analytics matter; 301 if pure performance is the goal

Delete URL

DELETE /api/v1/urls/:short_key
→ 204 No Content

Data Model

URL Table (Primary)

Database Choice

Recommendation: DynamoDB or Cassandra — this is a key-value lookup workload with high write throughput. No joins, no complex queries.

Key Generation — The Core Design Decision

This is the most important part of the design. How do we generate a short, unique, non-guessable key?

Option 1: Hash the Long URL (MD5/SHA-256 + Base62 Truncation)

Key space: Base62 with 7 characters = 62^7 = 3.5 trillion unique keys

Collision handling:

Option 2: Pre-Generated Key Pool (Key Generation Service — KGS)

How it works:

1. Offline job generates random 7-char Base62 keys, stores in unused_keys table
2. App server requests a batch (e.g., 1,000 keys) at startup, caches them in memory
3. On URL creation, pop a key from the in-memory batch
4. When batch runs low (< 200), fetch another batch asynchronously
5. Mark keys as "used" in the DB atomically

Concurrency safety:

• Use a two-table approach: unused_keys and used_keys
• Move key from unused → used in a single transaction
• If an app server crashes, its unused in-memory keys are "lost" — acceptable given the 3.5T key space

Option 3: Counter-Based with Encoding (Snowflake-style)

Recommendation

Use Option 2 (KGS) for production systems:

• No collisions, no coordination overhead per request
• O(1) amortized key generation
• Easy to make non-guessable (random keys, not sequential)
• Can be made highly available with standby KGS replicas

Detailed Flow Diagrams

Write Flow (URL Creation)

Read Flow (Redirection)

Analytics Flow (Async)

Caching Strategy

Cache Architecture

Caching Patterns

Recommendation: Cache-Aside with Write-on-Create for popular URLs

• On URL creation: don't populate cache (most URLs are rarely accessed)
• On first read: query DB, populate cache
• Exception: if we detect a URL going viral (high click rate), proactively cache it

Cache Warming

• Preload the top 1% most-accessed URLs into cache on service startup
• Use a daily batch job scanning analytics to identify hot URLs

Database Sharding & Partitioning

Sharding Strategy

Recommendation: Consistent Hashing on short_key

• Even distribution
• Adding/removing DB nodes only requires moving ~1/N of the keys
• Use virtual nodes (vnodes) for better balance — 150-200 vnodes per physical node

Replication

Handling Edge Cases

Duplicate Long URLs

• Same user, same URL: Return existing short URL (dedup query on long_url + user_id index)
• Different users, same URL: Generate separate short URLs (user isolation)

Expired URLs

• Lazy deletion: On read, check expires_at → if expired, return 410 Gone
• Background cleanup: Cron job deletes expired records, recycles keys back to KGS

Custom Aliases

• Validate: 3-16 chars, alphanumeric + hyphens only
• Check uniqueness in DB
• Reserve a set of blacklisted words (profanity, reserved paths like /api, /admin)

Hot URLs (Viral Links)

• A single URL getting millions of hits/second
• Solution: Cache replication — replicate hot keys across multiple cache shards
• Application-level: detect hot keys (e.g., > 1000 RPS) and fan out reads across replicas

Tradeoffs & Design Decisions Summary

Reliability & Fault Tolerance

Single Points of Failure & Mitigations

Graceful Degradation

• If cache is down → serve directly from DB (higher latency, still functional)
• If KGS is down → app servers use remaining in-memory keys; alert for manual intervention
• If analytics pipeline is down → buffer events locally, replay later

High-Level Architecture

Component Breakdown

Full System Architecture (Production-Grade)

What changes if one short link appears on a live television broadcast? Follow that single hot key through the cache, database, and analytics pipeline. Then consider a link whose owner changes its destination: decide how quickly existing cache entries must stop returning the old address.

Interview Tips

1. Start with requirements clarification — Don't jump into design. Ask about scale, custom aliases, analytics, expiration.

2. Lead with the key generation discussion — This is the core algorithmic challenge. Discuss all three approaches, tradeoffs, and recommend KGS.

3. Separate read and write paths — They have very different scale (100:1 ratio). This shows you think about system characteristics.

4. Don't forget caching — With 100:1 read:write ratio, caching is critical. Discuss eviction, warming, and hot key handling.

5. Mention 301 vs 302 — This is a subtle but important tradeoff that shows depth.

6. Discuss cleanup of expired URLs — Shows you think about long-term system health and operational concerns.

7. End with reliability — Walk through failure scenarios. "What happens if X goes down?" for each component.