Design a URL Shortener (TinyURL / Bit.ly) – System Design Walkthrough

This problem appears in multiple sheets. Depth expectations increase as you progress:

Track	What to demonstrate
Arch 25	The 'simple' problem where interviewers go deepest. Nail KGS vs hashing, 301 vs 302, read-path caching layers, and capacity math with numbers.
Arch 50	Add analytics pipeline depth, abuse prevention, and multi-DC failover narrative.
Arch 75	Staff: discuss URL normalization dedup strategy, GDPR delete propagation, and cost of 10B redirects/month.

Interview Prompt

Design a URL shortening service like TinyURL or Bit.ly. Users submit long URLs and receive short links. Short links redirect to the original URL. Support optional custom aliases and basic click analytics.

Clarifying Questions (ask before designing)

Question	Why it matters
What's the read:write ratio?	100:1 is standard — drives cache-first read path vs write-optimized store.
Do we need per-click analytics or just redirects?	302 vs 301 decision. Analytics requires async pipeline (Kafka → Flink → ClickHouse).
Should the same long URL always map to the same short URL?	Content-addressable hashing vs KGS — fundamentally different design.
Custom aliases — global uniqueness or per-user?	Affects collision handling (LWT vs per-user namespace prefix).

Scope

In scope

Create, redirect, delete URLs
Custom aliases with uniqueness guarantee
Click analytics (aggregate)
Capacity estimation and read-path optimization

Out of scope (state explicitly)

Link preview / unfurling (Open Graph scraping)
User authentication system design (assume API keys exist)
Billing / tier management

Assumptions

100M new URLs/month, 100:1 read:write ratio
7-character Base58 short codes
99.99% availability for redirects (analytics can lag)

Given a long URL, generate a unique, short URL (e.g., https://short.ly/xK9b2)
Given a short URL, redirect the user to the original long URL (HTTP 301/302)
Users can optionally provide a custom alias for their short URL
Short URLs have a configurable expiration (default: 5 years)
Analytics: track total clicks, geographic data, referrer, device info
Users can delete their own short URLs
Duplicate long URLs by the same user return the existing short URL

Metric	Calculation	Value
New URLs / month	Given	100M
Redirects / month	100:1 read:write	10B
Writes / sec	100M / (30 × 86400)	~38 writes/s
Reads / sec	10B / (30 × 86400)	~3,800 reads/s (peak 5×: ~19K)
Record size	short_code + long_url + metadata	~500 bytes
Storage / year	100M × 12 × 500B	~600 GB
5-year storage		~3 TB
Cache size (20% hot)	0.2 × daily_reads × 500B = 0.2 × 333M × 500B	~33 GB

Short Code Length

Base62 encoding (a-z, A-Z, 0-9).

6 chars → 62⁶ ≈ 56.8 billion (sufficient)
7 chars → 62⁷ ≈ 3.5 trillion (future-proof)
Choose 7 characters for safety margin.

API Gateway

Why: Centralized entry for rate limiting (token bucket per API key), JWT auth, SSL termination, request routing
How: NGINX / Kong / AWS API Gateway. Routes /api/v1/urls to write service, /{short_code} to read service
Fault Tolerance: Multiple instances behind an L4 load balancer; stateless, so horizontally scalable

Key Generation Service (KGS)

Why: Pre-generating keys avoids real-time collision checks, which are expensive at scale
How it works:
1. Offline process generates all possible 7-char Base62 keys and stores them in a key-DB (two tables: unused_keys and used_keys)
2. Each app server requests a batch (e.g., 1,000 keys) from KGS
3. KGS atomically moves keys from unused → used and hands them to the requesting server
4. App server serves keys from its in-memory batch (no DB hit per request)
5. When a server dies, its unused in-memory keys are “lost”: acceptable since we have trillions of keys
Coordination: ZooKeeper or etcd assigns non-overlapping ranges to KGS instances
Fault Tolerance: Multiple KGS replicas with leader election; if leader fails, follower takes over with a fresh range

URL Write Service

Receive long URL + optional custom alias
If custom alias → check uniqueness via Bloom filter (fast negative) then DB conditional write
If no alias → pop a key from the local KGS batch
Write {short_code → long_url, user_id, expiry} to Cassandra
Populate Redis cache
Return short URL

URL Read Service (Redirect Service)

Receive GET /{short_code}
Check Redis cache → if hit, redirect immediately
If cache miss → query Cassandra → populate cache → redirect
Async: publish click event to Kafka

301 vs 302:

301 (Permanent Redirect): Browser caches it → fewer hits to our servers, but we lose per-click analytics
302 (Temporary Redirect): Every click hits our servers → accurate analytics
Recommendation: Use 302 if analytics are important; 301 for pure shortening

Redis Cluster (Cache Layer)

Why Redis: In-memory, sub-millisecond latency, supports TTL natively
Strategy: Cache-aside pattern (read-through). LRU eviction policy
Data: key=url:{short_code}, value=long_url, TTL=24h
Size: ~33 GB fits in a single large Redis instance or a small cluster
Fault Tolerance: Redis Cluster mode (6 nodes = 3 masters + 3 replicas). On master failure, replica auto-promotes

Cassandra (URL Store)

Why Cassandra:
- Single-key lookups (partition key = short_code) → O(1) with Cassandra
- Massive write throughput (LSM-tree based)
- Built-in TTL support → expired URLs auto-deleted by compaction
- Multi-datacenter replication out of the box
- No complex joins or transactions needed
Replication: RF=3, consistency level QUORUM for writes, ONE for reads (fast reads, durable writes)
Compaction: Leveled Compaction Strategy for read-heavy workload

Kafka (Click Event Stream)

Why Kafka: Decouple click ingestion from analytics processing; buffer against traffic spikes
Topic: click-events, partitioned by short_code (ensures all clicks for a URL go to same partition for ordered processing)
Replication: RF=3, min.insync.replicas=2
Retention: 7 days (enough time for Flink to process)

Apache Flink (Stream Processing)

Why Flink: Real-time windowed aggregations (clicks per minute, per hour, per day)
Processing: Consumes from Kafka, aggregates by short_code + time window + geo + device, writes to ClickHouse
Checkpointing: Exactly-once semantics via Flink's checkpoint mechanism

ClickHouse (Analytics Store)

Why ClickHouse: Columnar database optimized for OLAP queries (sum, count, group by) on billions of rows
Queries: “Top 10 URLs by clicks today”, “clicks by country for URL X”

Create Short URL

HTTP

POST /api/v1/urls
Authorization: Bearer <token>
Content-Type: application/json

{
  "long_url": "https://example.com/some/very/long/path?query=param",
  "custom_alias": "my-brand",
  "expires_at": "2031-03-13T00:00:00Z"
}

Response: 201 Created
{
  "short_url": "https://short.ly/xK9b2",
  "long_url": "https://example.com/some/very/long/path?query=param",
  "short_code": "xK9b2",
  "expires_at": "2031-03-13T00:00:00Z",
  "created_at": "2026-03-13T10:00:00Z"
}

Redirect

HTTP

GET /{short_code}

Response: 302 Found
Location: https://example.com/some/very/long/path?query=param

Delete URL

HTTP

DELETE /api/v1/urls/{short_code}
Authorization: Bearer <token>

Response: 204 No Content

Get Analytics

HTTP

GET /api/v1/urls/{short_code}/analytics?period=7d
Authorization: Bearer <token>

Response: 200 OK
{
  "short_code": "xK9b2",
  "total_clicks": 152437,
  "clicks_by_day": [
    {"date": "2026-03-12", "count": 1234}
  ],
  "top_countries": [
    {"country": "US", "count": 50234}
  ],
  "top_referrers": [
    {"referrer": "twitter.com", "count": 30211}
  ]
}

Common Error Responses

400 Bad Request: invalid input, missing fields, or malformed JSON
401 Unauthorized: missing or invalid auth token or API key
403 Forbidden: authenticated but insufficient permissions
404 Not Found: resource ID does not exist
409 Conflict: duplicate write or version conflict; retry with idempotency key
422 Unprocessable Entity: valid syntax but invalid business logic
429 Too Many Requests: rate limit exceeded; honor Retry-After header
500 Internal Error: unexpected server fault; retry with idempotency key
503 Service Unavailable: dependency down or overloaded; use exponential backoff

Cassandra: URL Table

Primary store for URL mappings. Partition key is short_code for O(1) lookups. Built-in TTL auto-deletes expired rows.

SQL

CREATE TABLE url_mappings (
    short_code  TEXT,          -- Partition key
    long_url    TEXT,
    user_id     UUID,
    created_at  TIMESTAMP,
    expires_at  TIMESTAMP,
    is_custom   BOOLEAN,
    PRIMARY KEY (short_code)
) WITH default_time_to_live = 157680000;  -- 5 years in seconds

Cassandra: User URLs Table

Enables listing all URLs created by a user (dashboard view). Clustered by creation time descending.

SQL

CREATE TABLE user_urls (
    user_id     UUID,
    created_at  TIMESTAMP,
    short_code  TEXT,
    long_url    TEXT,
    PRIMARY KEY (user_id, created_at)
) WITH CLUSTERING ORDER BY (created_at DESC);

Cassandra: Click Events Table

Stores raw click events for per-URL analytics queries.

SQL

CREATE TABLE click_events (
    short_code  TEXT,
    timestamp   TIMESTAMP,
    user_agent  TEXT,
    referer     TEXT,
    country     TEXT,
    device      TEXT,
    PRIMARY KEY (short_code, timestamp)
) WITH CLUSTERING ORDER BY (timestamp DESC);

Redis Cache

Key:    url:xK9b2
Value:  "https://example.com/some/very/long/path?query=param"
TTL:    86400 (24 hours)

Kafka Topic: `click-events`

JSON

{
  "event_id": "uuid-v4",
  "short_code": "xK9b2",
  "timestamp": "2026-03-13T10:30:00Z",
  "ip": "203.0.113.42",
  "user_agent": "Mozilla/5.0...",
  "referrer": "https://twitter.com/post/123",
  "country": "US",
  "city": "San Francisco",
  "device_type": "mobile",
  "os": "iOS"
}

ClickHouse: Analytics Table

Columnar OLAP store for aggregated analytics queries. Uses SummingMergeTree for pre-aggregated counts.

SQL

CREATE TABLE url_analytics (
    short_code  String,
    event_date  Date,
    hour        UInt8,
    country     LowCardinality(String),
    referrer    String,
    device_type LowCardinality(String),
    click_count UInt64
) ENGINE = SummingMergeTree()
ORDER BY (short_code, event_date, hour, country);

KGS: Key Store (PostgreSQL)

Tracks pre-generated short code keys and their assignment status.

SQL

CREATE TABLE keys (
    key_value   CHAR(7) PRIMARY KEY,
    status      ENUM('unused', 'assigned', 'used'),
    assigned_to VARCHAR(64),  -- server instance ID
    assigned_at TIMESTAMP
);

General Techniques

Technique	Application
Replication	Cassandra RF=3, Kafka RF=3, Redis Cluster 3M+3R
Health Checks	LB actively health-checks all service instances
Circuit Breaker	Hystrix/Resilience4j between services (e.g., Write Service → KGS)
Retry with Backoff	On transient failures (DB timeout, network blip)
Idempotency	Same long URL + user → returns existing short URL (no duplicates)
Graceful Degradation	If analytics pipeline is down, redirects still work

Problem-Specific Scenarios

1. KGS Failure / Key Exhaustion

Multiple KGS instances with pre-assigned non-overlapping key ranges
Each app server pre-fetches a batch of 1,000 keys → can survive KGS downtime for thousands of requests
If a server crashes, its unused keys are lost: acceptable (trillions of total keys)
Monitor key pool size; alert when < 10% remaining

2. Cache Stampede (Thundering Herd)

When a hot URL's cache expires, thousands of requests simultaneously hit DB
Solution: Use request coalescing (singleflight pattern). Only one thread fetches from DB; others wait for the result
Also: set cache TTL with jitter (e.g., 24h ± 2h) to avoid synchronized expiration

3. Hot URL (Celebrity Problem)

A viral URL gets millions of redirects per second
Solution: Replicate the hot key across multiple Redis shards (read replicas). Use local in-process cache (Caffeine/Guava) with 60s TTL as L1 cache

4. Custom Alias Race Condition

Two users simultaneously request the same custom alias
Solution: Cassandra Lightweight Transaction (LWT): INSERT IF NOT EXISTS. Exactly one succeeds; the other gets an error

5. Datacenter Failure

Cassandra multi-DC replication ensures reads can be served from surviving DC
GeoDNS automatically routes traffic away from the failed DC

URL Normalization

Before storing, normalize the long URL to avoid duplicates:

Lowercase the scheme and host (HTTP://Example.COM → http://example.com)
Remove default ports (:80 for HTTP, :443 for HTTPS)
Sort query parameters alphabetically
Remove trailing slashes
Decode unnecessary percent-encoding

Abuse Prevention

Rate limiting: Token bucket per API key (100 URLs/hour for free tier)
URL Blacklist: Integrate with Google Safe Browsing API to reject malicious URLs
CAPTCHA: For anonymous URL creation
Spam detection: Check if long URL domain is in known spam/phishing databases

Bloom Filter for Duplicate Detection

Before checking DB for custom alias uniqueness, check a distributed Bloom filter
False positive rate ~1% means 99% of non-existent aliases are rejected without DB hit
Bloom filter size: ~1 GB for 1 billion entries with 1% FPR

Monitoring & Alerting

Redirect latency (p50, p95, p99)
Cache hit ratio (target > 80%)
KGS key pool remaining
Kafka consumer lag (analytics pipeline health)
Error rates (4xx, 5xx by endpoint)

GDPR / Privacy

Allow users to delete URLs and all associated analytics data
Anonymize IP addresses in analytics after 30 days
Provide data export functionality

Interview Walkthrough

Open with the read/write split: redirects dominate traffic (100:1 read-heavy), so optimize the redirect path first using Interview Patterns for traffic shaping.
Clarify redirect semantics early — 301 (permanent, cacheable) vs 302 (temporary, analytics-friendly) — interviewers watch for this distinction.
Anchor the ID-generation debate on KGS vs hashing: explain collision handling for hashes and why a pre-generated key pool avoids write-time contention.
Layer Caching Patterns on hot short codes (CDN edge + Redis) and state your cache hit ratio target before diving into DB schema.
Mention Bloom filter for custom-alias uniqueness checks to show you avoid a DB round-trip on every create request.
Offload click analytics asynchronously via a message queue — never block the redirect path for logging.
Run Back-of-the-Envelope Estimation on 7-char Base62 capacity (~3.5 trillion keys) to prove the encoding scheme scales.
Common pitfall: skipping URL normalization, which creates duplicate entries for the same long URL and wastes key space.

Why KGS Over Hashing? (The Key Decision)

Approach	How	Pros	Cons
MD5/SHA256 hash → Base62	Hash the long URL, take first 7 chars	Simple, deterministic, dedup-friendly	Collisions (birthday paradox). Must handle collision retry loop
Counter-based (auto-increment)	Central DB counter → Base62 encode	Guaranteed unique, simple	Single point of failure; sequential → predictable URLs; single-writer bottleneck
KGS (pre-generated keys) ⭐	Offline batch generate keys; app servers fetch batches	Zero collision risk; no runtime computation; non-sequential; no SPOF if multiple KGS; finite key pool (but 3.5T is effectively infinite)	Wasted keys on server crash; requires KGS infrastructure
UUID → Base62	Generate UUID v4, encode	Simple, decentralized	128-bit UUID → 22 Base62 chars (too long for a short URL)
Snowflake ID → Base62	Time-ordered ID	Unique, sortable	64-bit → 11 Base62 chars (still longish); exposes creation time

Why KGS wins for URL shortener specifically: The primary goal is a short URL (7 chars). KGS gives you exactly 7 chars with zero collision overhead. The key waste on crash is negligible (losing 1000 out of 3.5T keys is nothing). The offline generation amortizes all uniqueness-checking cost to batch time.

When would you choose hashing instead? If you need content-addressable dedup: i.e., same long URL always maps to the same short URL globally. Hash-based approach gives this for free. KGS does not (you'd need a separate dedup lookup table).

Why Cassandra Over MySQL/PostgreSQL/DynamoDB?

DB	Strengths for This Use Case	Weaknesses
Cassandra ⭐	Masterless (no SPOF), linear horizontal scaling, tunable consistency, built-in TTL for auto-expiry, multi-DC replication out of the box	No transactions, no joins (not needed here), operational complexity
DynamoDB	Managed, auto-scaling, single-digit ms latency, built-in TTL	Vendor lock-in (AWS), cost at very high scale, throughput provisioning complexity
MySQL	Familiar, ACID, strong consistency	Single-writer primary → write bottleneck at scale, manual sharding required, no built-in TTL
PostgreSQL	Same as MySQL + better JSON support	Same scaling limitations as MySQL

The deciding factors:

Access pattern is pure key-value lookup: no joins, no range queries, no transactions needed
Write volume (~38 writes/s avg but burst to 1000+): Cassandra's LSM-tree write path handles bursts gracefully
TTL auto-expiry: Cassandra's built-in TTL deletes expired rows during compaction: zero application-level cleanup
Multi-DC: Cassandra's multi-datacenter replication is native and well-proven. MySQL multi-DC requires tools like Vitess/ProxySQL and is operationally complex
When to choose DynamoDB: If you're AWS-native and want zero operational overhead. Cost-effective up to ~1B records; beyond that, Cassandra can be cheaper

301 vs 302: The Subtle but Important Choice

Status Code	Behavior	Pros	Cons
301 (Permanent)	Browser caches the redirect	Faster for repeat users; less server load	No per-click analytics; can't change target URL later; hard to invalidate CDN cache
302 (Temporary) ⭐	Browser does NOT cache	Full per-click analytics; can change target URL anytime; full control	Higher server load; extra hop every time
307 (Temporary, preserves method)	Like 302, but POST stays POST	Preserves HTTP method	Only matters for non-GET requests (rare for URL shorteners)

Recommendation: Default to 302 (analytics are valuable). Offer 301 as an opt-in for high-volume, no-analytics use cases. This is what Bit.ly does.

Read Path Optimization: The Real Bottleneck

At 19K reads/sec peak, the read path is the bottleneck. Here's how each layer helps:

Layer 1: CDN (CloudFront/Fastly): For 301 redirects, the CDN caches the Location header. Cache key: short URL path. Hit ratio: ~30% (many URLs are one-time use). Latency: ~5ms (edge).
Layer 2: Local In-Process Cache (Caffeine/Guava): Each app server caches ~10K hottest URLs. Hit ratio: ~20-30%. Latency: ~0.01ms (memory access). TTL: 60 seconds (stale reads OK for redirects).
Layer 3: Redis Cluster: Caches all recently accessed URLs. Hit ratio: ~90% of remaining requests. Latency: ~0.5ms (network + memory). TTL: 24h with jitter.
Layer 4: Cassandra: Only ~5% of requests reach here (cold URLs). Latency: ~2-5ms (SSD + network). Consistency: LOCAL_ONE for reads (fastest).

Layer	Technology	Hit Ratio	Latency	TTL
L1	CDN (CloudFront/Fastly)	~30%	~5ms	CDN cache headers
L2	Local In-Process Cache (Caffeine)	~20-30%	~0.01ms	60 seconds
L3	Redis Cluster	~90% of remaining	~0.5ms	24h with jitter
L4	Cassandra	~5% (cold URLs)	~2-5ms	N/A (persistent)

Effective latency: 0.3 × 5ms + 0.25 × 0.01ms + 0.4 × 0.5ms + 0.05 × 3ms = ~1.9ms average. Well under the 10ms p99 target.

Base62 vs Base58 vs Base64

Encoding	Characters	URL-Safe?	Ambiguity?
Base62	a-z, A-Z, 0-9	✓	0/O and l/1 look similar
Base58	Base62 minus 0, O, l, I	✓	No ambiguous characters (Bitcoin uses this)
Base64	Base62 + / + +	✗ (needs URL encoding)	N/A

Recommendation:

Base58 if users might type URLs manually.

Base62 if URLs are only shared as links (more combinations per character).

SLOs & Error Budgets

Metric	Target	Rationale
Redirect availability	99.99%	Core product — 52 min downtime/month max
Redirect p99 latency	< 10ms	Tied to 4-layer cache math
URL creation success rate	99.95%	Writes can retry; redirects cannot
Analytics pipeline lag	< 5 min	Async path — doesn't block redirects

Incident Scenarios (2am reality)

Scenario	How you detect	Mitigation
Redis cluster failover during viral event	Cache hit ratio drops from 90% to 5%, Cassandra p99 latency spikes	L1 local cache absorbs traffic for 60s; enable read-only mode on analytics; scale Cassandra read replicas; pre-warm Redis from top-10K keys list
KGS key pool exhausted	Alert: unused_keys count < 1M; create URL 503 rate increases	Emergency batch key generation job; extend short code to 8 chars as fallback; rate-limit free tier creation
Malicious URL used in phishing campaign	Abuse report spike + Safe Browsing API flag	Immediate redirect block (tombstone in Cassandra + Redis purge); async scan all URLs from same API key; auto-suspend key

Cost Drivers (Staff lens)

Redirect egress at 10B/month × 500 bytes = ~5 PB/month bandwidth (CDN reduces origin by 70%)
Cassandra storage: ~3 TB at 5 years with TTL compaction
Kafka + Flink for analytics: dominated by click event volume, not URL storage

Multi-Region & DR

Active-passive first: primary DC handles writes (QUORUM), secondary serves reads (LOCAL_ONE). Move to active-active only if write latency to single DC exceeds SLO — accept LWT conflict handling for custom aliases.