URL Shortener — System Design Interview

Phase 1: Clarify, Scope & Constraints

Interviewer: "Design a URL shortening service like bit.ly. Users submit a long URL and get a short 6–8 character code back; clicking it redirects to the original. Where do you start?"

Candidate: "Let me make sure I understand the scope. I see three core user journeys:

1. Shorten: A user submits a long URL, receives a unique short URL (e.g., sho.rt/aB3xY9).
2. Redirect: A user visits the short URL and is transparently redirected to the original.
3. Analytics (optional): The URL creator sees click counts, geographic breakdown, referrer data.

Before I go further — are analytics in scope? And do users need accounts to shorten, or is it open to anonymous use?"

Interviewer: "Analytics are optional for V1. Anonymous shortening is fine. What do you think the core complexity is?"

Candidate: "The core complexity is the redirect path. Shortening happens rarely — maybe once per URL, ever. But every shortened URL potentially receives millions of redirects over its lifetime. The system is read-heavy by design: the ratio is roughly 100:1 reads to writes. The dominant challenge is making redirects fast globally — P99 under 20ms for users in the same region — and the secondary challenge is generating unique, short, and collision-free codes.

WHY: If redirect latency is high, users notice directly — they're sitting in front of a browser waiting for the page to load. A slow shorten operation is annoying; a slow redirect is a broken product.

Non-goals for V1:

• Custom vanity URLs (e.g., sho.rt/my-brand) — adds complexity around uniqueness conflicts
• Link expiry policies — assume links live forever for now
• Multi-region active-active replication — we'll design for one primary region with CDN caching at the edge
• URL previews / safety scanning — important but not core"

Interviewer: "Fair. What non-functional requirements are you targeting?"

Candidate: "

• Availability: 99.99% (4 nines). A broken redirect is revenue loss for any customer embedding our link.
• Consistency: Eventual is acceptable. If a new short URL takes a few seconds to propagate to all read replicas, that's fine — users don't shorten and immediately share within milliseconds.
• Latency: Redirect P99 < 20ms in-region (most traffic is repeat visits to cached URLs). Shorten P99 < 100ms.
• Durability: URLs must never be lost or silently corrupted.

Back-of-envelope math:

Assumptions:

• 100M DAU
• Average user shortens 0.1 URL/day, redirects 10x/day
• Average long URL = 500 bytes

Write QPS (shorten): $100M \times 0.1 = 10M \text{ URLs/day}$ $10M \div 86{,}400 \approx 116 \text{ writes/s average}$ $\text{Peak writes} = 116 \times 5 = 580 \text{ writes/s}$

Read QPS (redirect): $100M \times 10 = 1B \text{ redirects/day}$ $1B \div 86{,}400 \approx 11{,}574 \text{ reads/s average}$ $\text{Peak reads} = 11{,}574 \times 3 = \approx 35{,}000 \text{ reads/s}$

Read-to-write ratio: $35{,}000 : 580 \approx 60:1$ — strongly read-heavy.

Storage (5 years):

• Record = 8B (ID) + 500B (long URL) + 7B (short code) + 8B (created_at) + 4B (user_id) ≈ 530 bytes/record
• Records/year: $10M/day \times 365 = 3.65B$ records/year
• Raw storage/year: $3.65B \times 530B \approx 1.9 \text{ TB/year}$
• 5-year storage: $\approx 10 \text{ TB}$

WHY: 10 TB of text data is comfortable for a single large PostgreSQL instance (with read replicas). No sharding needed for storage capacity at this scale. The 35K peak read QPS is the dimension that demands a caching layer — PostgreSQL handles ~50K indexed reads/s but that leaves zero headroom.

Short code length:

• Using Base62 (a-z, A-Z, 0-9): $62^7 = 3.52 \text{ trillion}$ unique codes
• At 10M new URLs/day, 7-character codes won't be exhausted for $3.52T \div 10M = 352{,}000 \text{ days}$ ≈ 965 years
• 6 characters gives $62^6 = 56.8B$ — exhausted in 15+ years; 7 is safer"

Interviewer: "35K peak read QPS doesn't sound that intense. Why do you need a cache at all?"

Candidate: "Two reasons. First, 35K QPS is the average peak — viral links create hot-key spikes. A single tweet from a celebrity embedding our short URL can spike one key to 100K+ reads/s. PostgreSQL on a single primary can't absorb that for one key. Second, 95%+ of redirect traffic is to a small fraction of URLs (Pareto principle — top 20% of URLs get 80% of traffic). Redis can serve those entirely from memory, keeping our database for the long tail. It's not just about raw QPS headroom — it's hot-key protection."

Phase 2: High-Level Architecture

Interviewer: "Good framing. Let's talk API design. What does your interface look like?"

Candidate: "I'll use REST — this is a simple request/response API, there's no streaming or bidirectional communication needed, and the redirect endpoint is a standard HTTP redirect pattern that browsers understand natively.

Key endpoints:

POST /api/v1/urls
  Request:  { "long_url": "https://example.com/very/long/path" }
  Response: { "short_code": "aB3xY9", "short_url": "https://sho.rt/aB3xY9", "created_at": "..." }
  Status:   201 Created

GET /{short_code}
  Response: HTTP 302 → Location: https://example.com/very/long/path
  (No body — browsers follow the redirect automatically)

GET /api/v1/urls/{short_code}
  Response: { "short_code": "aB3xY9", "long_url": "...", "created_at": "...", "click_count": 4521 }
  (Stats endpoint — authenticated, for URL owner)

WHY: I'm using 302 (Found) rather than 301. A 301 is cached by browsers permanently — once a user visits the short URL, their browser never contacts our servers again for that URL. That breaks analytics (we never see repeat clicks from the same user) and prevents us from updating the destination. 302 means every redirect goes through our servers, which has a small latency cost but gives us control."

Interviewer: "Why not 301 to reduce load? You'd offload 95% of repeat traffic to browser caches."

Candidate: "It's a valid trade-off. If analytics aren't important — say we're building a pure infrastructure URL shortener — 301 makes sense and dramatically reduces server load. Many commercial shorteners use 302 or 307 for analytics flexibility (some, like bit.ly, use 301 but track clicks server-side before redirecting). If we wanted the best of both worlds, we could offer the URL owner a choice: 'fast mode' (301) or 'analytics mode' (302). For V1 I'll go with 302 since analytics was listed as an optional feature we want to support later."

WHY: 302 vs 301 is a classic trade-off between infrastructure efficiency and business value. The decision depends on whether analytics matter — not a purely technical question.

Candidate: "For the data model, a single urls table in PostgreSQL is sufficient:

Copy
CREATE TABLE urls (
    id          BIGINT PRIMARY KEY,          -- Snowflake ID
    short_code  VARCHAR(8) UNIQUE NOT NULL,  -- Base62 encoded, 7 chars
    long_url    TEXT NOT NULL,
    user_id     BIGINT,                      -- NULL for anonymous
    created_at  TIMESTAMPTZ DEFAULT NOW(),
    click_count BIGINT DEFAULT 0
);

CREATE UNIQUE INDEX idx_short_code ON urls(short_code);
CREATE INDEX idx_user_id ON urls(user_id) WHERE user_id IS NOT NULL;

The lookup is always short_code → long_url. A unique index on short_code makes this an O(log n) B-tree lookup. At 10M URLs/day (from our envelope), that's ~3.65B/year or ~18B rows over 5 years. The 10 TB fits a single instance's capacity, but an 18B-row table makes index maintenance, vacuum, and backups operationally painful — so we partition with hash-based sharding on short_code across multiple shards. The schema itself remains the same per shard.

WHY: Relational because the data is tabular with a natural primary key; ACID guarantees prevent duplicate short codes from being issued under concurrent writes; the data model is simple enough that we gain nothing from a document store.

Let me draw the core architecture:"

-+ResetFullscreen

Candidate: "Let me walk through both paths.

Write path (shorten):

1. Client POSTs long URL to Load Balancer
2. Routes to a Shorten Service instance
3. Shorten Service requests a unique 64-bit ID from the Snowflake service
4. Encodes the ID in Base62 → 7-char short code
5. INSERTs into PostgreSQL primary (short_code, long_url, user_id, created_at)
6. SETs short_code → long_url in Redis with 24-hour TTL (write-through)
7. Returns the short URL to the client

Read path (redirect):

1. Client visits sho.rt/aB3xY9, hits CDN first
2. If CDN has it cached (60s TTL): immediately returns 302, done — zero server calls
3. If CDN cache miss: forwards to Load Balancer → Redirect Service
4. Redirect Service checks Redis: GET aB3xY9
5. If Redis hit: returns 302 to client, also sets CDN cache
6. If Redis miss: queries PostgreSQL Read Replica, populates Redis, returns 302"

Interviewer: "What's the single point of failure in this design?"

Candidate: "Two candidates: the Snowflake ID service and PostgreSQL primary. If either goes down, new URL creation fails. The Redis cluster is already distributed. Let's tackle those in the deep dive."

Phase 3: Deep Dive & Evolution

Interviewer: "What breaks first at 10x traffic? Walk me through it."

Candidate: "At 10x we're at 350K peak read QPS and 5,800 peak write QPS. Let's triage:

1. Redis handles 100K–500K commands/s per node — at 350K QPS we might saturate a single Redis node. But with Redis Cluster (6 nodes, 3 shards with replicas), each shard handles ~117K QPS, well within limits.

2. PostgreSQL Read Replica only sees cache misses — with a 95% cache hit rate, 350K QPS → only 17,500 QPS hit the database. A single replica with connection pooling (PgBouncer) handles this.

3. PostgreSQL Primary at 5,800 write QPS is approaching its limit (~10K writes/s). We have some headroom but need to watch this.

4. Snowflake ID service is the most fragile — it's a single-tenant coordination point.

WHY: The read path is well-cushioned by CDN + Redis. The write path is the actual bottleneck at 10x — Snowflake and the PostgreSQL primary.

Scaling the ID generator:

I'll switch from a centralized Snowflake service to embedded Snowflake generation in each Shorten Service instance. Each instance gets a unique worker_id (assigned at startup from a small ZooKeeper ensemble or simply from the instance's IP). No network call needed for ID generation.

Scaling writes — the click_count problem:

I deliberately put click_count in the same urls table, but at 10x traffic, incrementing it on every redirect is 350K writes/s to the database — impossible. I need to decouple click counting from the redirect path.

Solution: Write-behind via Kafka

1. Redirect Service publishes {short_code, timestamp, geo, user_agent} to Kafka topic url-clicks
2. Analytics Consumer batch-aggregates clicks and periodically upserts counts to a separate url_analytics table
3. Main redirect path never touches the database for writes

WHY: This decouples the hot path (redirect) from analytics persistence. Kafka absorbs traffic spikes. The click count shown to users is eventually consistent (a few seconds behind), which is acceptable for analytics.

Sharding strategy (for future scale):

If write QPS exceeds 10K/s, we shard PostgreSQL by short_code prefix (first character). Base62 has 62 first characters — 8 shards of ~8 characters each gives even distribution. Short codes are random (Base62 of a Snowflake ID), so no hot partitions.

Here's the evolved architecture:"

-+ResetFullscreen

Candidate: "Key changes from the initial design:

1. Embedded Snowflake — ZooKeeper assigns worker IDs at Shorten Service startup; no centralized ID service SPOF
2. PgBouncer — connection pooling in front of PostgreSQL; prevents connection exhaustion at high scale
3. Kafka + Analytics Consumer — click counting moved off the redirect hot path entirely
4. ClickHouse / TimescaleDB — time-series-optimized storage for click analytics; separate from the URL mapping data"

Interviewer: "Why ZooKeeper for worker IDs? That seems heavy."

Candidate: "You're right — it's overkill for this use case. A simpler approach: each Shorten Service instance derives its worker_id from its IP address (last 10 bits of the IPv4 address). This is stateless and doesn't require a coordination service. The risk is collision if two instances share the same last 10 bits — in a /16 network that won't happen. For a managed Kubernetes environment, the pod's index from StatefulSet ordering works too.

ZooKeeper is the right choice if you need strict uniqueness guarantees across data centers — otherwise the IP-based approach is simpler and operationally lighter."

WHY: Always match complexity to actual requirements. IP-based worker IDs are simpler and sufficient for a single-region deployment.

Phase 4: Robustness & Operations

Interviewer: "What happens if your Redis cluster goes down entirely?"

Candidate: "All redirect traffic falls through to PostgreSQL Read Replicas. At 35K peak read QPS (current scale), that's 35K QPS hitting the replica — it can handle maybe 50K QPS for simple indexed reads, so we're at 70% capacity. It works but it's uncomfortable.

At 10x (350K QPS), a Redis outage would be catastrophic — the database can't absorb it. Mitigations:

1. Redis Cluster with replicas — a node failure triggers automatic failover; we never lose the whole cluster unless all nodes in a shard fail simultaneously
2. Circuit Breaker — if Redis is slow/down, the Redirect Service opens the circuit and queries the database directly, with rate limiting to protect the DB
3. Pre-warming — on Redis restart, a separate worker replays the top 10K URLs from the last 24 hours into Redis before traffic is allowed through (reduces the thundering herd on cold start)"

Interviewer: "What about the celebrity problem — a single short URL going viral and getting 500K hits/s?"

Candidate: "A single Redis key is handled by one node — 500K ops/s on one key would saturate it (Redis typically handles ~100K-500K ops/s total per node). Solutions:

1. Local in-process cache in each Redirect Service instance: a small LRU cache (e.g., Caffeine in Java, or a simple HashMap with TTL) holding the top 1,000 URLs in memory. Most viral traffic hits this before Redis. The tradeoff is slightly stale data (TTL 10–30 seconds).
2. Key replication across Redis nodes for hot keys: detect keys with >10K hits/s and mirror them across multiple shards. Client-side consistent hashing routes reads to any of the replicas.

WHY: For the celebrity problem, pushing the cache closer to the application (in-process) is more effective than Redis replication because it eliminates even the Redis network hop.

Interviewer: "What if an entire availability zone goes down?"

Candidate: "Our architecture is multi-AZ by default:

• ALB distributes across AZs
• Redis Cluster nodes are spread across 3 AZs (one shard primary per AZ)
• PostgreSQL uses Multi-AZ with synchronous replication (AWS RDS Multi-AZ or a manual hot standby)
• CDN edge nodes are geographically distributed — if our origin goes partially down, cached redirects still serve

For a full region failure: active-passive failover to a secondary region with a 5-minute RTO. URL data is replicated asynchronously to the secondary region via PostgreSQL logical replication. In a true region outage, we accept a few seconds of URL creation data loss (RPO ~1 minute) but redirects for existing URLs continue immediately from the secondary."

Interviewer: "Let's wrap up. What are your key trade-offs?"

Candidate: "Three main ones:

1. 302 over 301: Gives analytics capability but adds server load for every redirect. Right call for a commercial shortener — analytics is core business value.

2. Snowflake IDs over random codes: Base62 of a sequential Snowflake ID means codes are slightly predictable (sequential IDs encode to sequential-looking codes). A random code is more opaque. I chose Snowflake for simplicity and guaranteed uniqueness without a counter table — the predictability risk is low for a URL shortener since codes aren't secrets (the long URL is the secret, not the code).

3. Eventual consistency on click counts: Click counts are always a few seconds stale. This is the right call — making click counting synchronous with the redirect would require a distributed counter or a database write on every redirect, neither of which scales.

For V2 at 10x scale, I'd add:

• Geographically distributed read replicas (multi-region read traffic served locally)
• Automatic URL safety scanning (VirusTotal integration before a URL goes live)
• Custom vanity URLs (requires uniqueness check in a Redis set before insertion)"

Interviewer: "Solid design. What are your key SLIs?"

Candidate: "

• Redirect P99 latency < 20ms (CDN + Redis path)
• Shorten P99 latency < 100ms
• Availability > 99.99% (< 52 minutes/year downtime)
• Error rate < 0.01% (invalid short codes, DB write failures)
• Cache hit rate > 95% (if this drops, investigate Redis cluster health)

Distributed tracing (Jaeger/Zipkin) across Shorten → DB and Redirect → Redis → DB to pinpoint latency spikes. Alert on cache hit rate drops — that's the leading indicator of an overloaded database."