System Design: URL Shortener and Rate Limiter, End to End

Two of the most-asked system design questions, worked end to end with the 4-step framework from the primer: a URL shortener (TinyURL-style) and a rate limiter. Follow along and notice the pattern — requirements, numbers, boxes-and-arrows, then the deep dive where offers are won.

Part 1 — URL shortener

Step 1 — Requirements

Functional: shorten a long URL to a short alias; redirect the alias to the original. Should we support custom aliases? Link expiry? Click analytics? Ask — then scope: "I'll cover core shorten/redirect plus expiry; analytics goes on a queue and out of scope for the deep dive."

Non-functional: short URLs must redirect fast (low latency reads); the system must handle high read:write ratios (a link is created once, clicked many times); high availability — a dead shortener breaks every link ever shared.

Step 2 — Estimation

• 100M URLs shortened per month → ~40 writes/sec average, ~100/sec peak.
• Read:write ratio 10:1 → ~1,000 reads/sec at peak.
• Storage: 100M/month × 500 bytes metadata ≈ 50 GB/month → ~600 GB/year. Trivial for any database — the challenge is reads, not storage.
• Bandwidth: 1,000 redirects/sec × 500 bytes ≈ 500 KB/sec. Negligible.

Key insight from the numbers: this is a read-heavy system. Everything in the design should serve fast reads.

Step 3 — High-level design and API

POST /api/shorten   { "longUrl": "...", "customAlias": "optional", "expiryDays": 30 }
                     -> { "shortUrl": "jvmk.us/aB3x9" }
GET  /{shortKey}     -> 302 redirect to long URL (301 if permanent)

Boxes and arrows: client → load balancer → app servers → cache (Redis) → database. Writes go to the DB; reads check the cache first. The 10:1 read ratio means the cache absorbs the vast majority of traffic.

Step 4 — Deep dive: generating the short key

This is the question inside the question. Three approaches, with the trade-off stated for each:

• Hash the long URL (e.g. MD5, take 7 chars): simple, but collisions need handling, and the same URL always yields the same key (sometimes desirable, sometimes not).
• Counter + Base62: a distributed counter hands out IDs; encode in Base62 (a–z, A–Z, 0–9) → 7 chars gives ~3.5 trillion keys. No collisions, but the counter is a single point of contention — shard it with ranges per server.
• Random 7-char string, retry on collision: stateless and simple; with 62^7 keys, collisions are rare until enormous scale. Many real systems do exactly this.

Recommended answer: "I'd use the counter + Base62 approach for guaranteed uniqueness, accepting the need to manage counter ranges — because duplicate keys are a correctness bug, while counter management is just operations."

What breaks at 10x? The database on reads — answer: cache hit ratio (keep hot keys in Redis, 24h TTL), then read replicas. The single write DB — answer: it handles only ~100 writes/sec, so it survives a long time; when it doesn't, shard by key hash.

Part 2 — Rate limiter

Step 1 — Requirements

Functional: allow at most N requests per window per client (API key, IP, or user ID); reject the excess with HTTP 429. Non-functional: the limiter must be faster than the thing it protects — it sits in the request path, so every millisecond counts; it must work across many app servers (distributed).

Step 2 — The algorithms (know all four, recommend one)

• Token bucket: each client has a bucket refilled at N tokens/sec; a request consumes one. Bursts allowed up to bucket size. The standard answer.
• Leaky bucket: requests queue and leak out at a fixed rate — smooths bursts instead of allowing them.
• Fixed window: count requests per minute; reset at the minute boundary. Simple, but allows 2N requests straddling a boundary.
• Sliding window log/counter: precise, but stores a timestamp per request — expensive at scale.

Recommended answer: "Token bucket — it handles bursty real-world traffic gracefully, needs only a counter and timestamp per client, and I can implement it in Redis."

Step 3 & 4 — Where it lives, and the distributed deep dive

Placement options, in order of preference: API gateway (one choke point, no code changes) → middleware in the app → dedicated microservice (only at very large scale).

The deep dive is distributed counting: with 10 app servers, each server's local counter is useless. Keep counters in Redis — a single INCR plus expiry per client key is atomic and ~1ms. For token bucket precision, a small Lua script does check-and-decrement atomically:

local tokens = tonumber(redis.call("get", KEYS[1]) or ARGV[1])
if tokens > 0 then
  redis.call("decr", KEYS[1])
  return 1          -- allowed
else
  return 0          -- rejected: return HTTP 429
end

Always return rate-limit headers so clients can back off gracefully:

X-RateLimit-Limit: 100
X-RateLimit-Remaining: 97
X-RateLimit-Reset: 1719849600
Retry-After: 42   (on 429 responses)

Follow-ups interviewers love (and one-line answers)

• "What if the Redis cache goes down?" — Fail open (allow traffic, alert loudly) or fail closed (reject) depending on whether availability or protection matters more. State the trade-off.
• "How do you handle 1M requests/sec to the limiter?" — Shard Redis by client key; the limiter itself becomes the distributed system.
• "Short URL analytics?" — Click events go to a Kafka queue, aggregated offline. Never on the redirect path.
• "Malicious users creating millions of links?" — That's what the rate limiter is for. The two designs compose.

In this series

1. System Design Interviews: A Practical Primer — the 4-step framework.
2. System Design: URL Shortener and Rate Limiter, End to End (this post) — the classic warm-up questions.
3. System Design: How to Design a Social Media Feed — fan-out, ranking, and the celebrity problem.