The earlier system design posts leaned ML / large-scale distributed. This one returns to two must-practice classics — small but complete, the best material for warming up and building fundamentals, and often used as "30-minute quick" questions:
- Rate Limiter: protects the backend from being overwhelmed; the focus is the trade-offs among four algorithms and the distributed implementation.
- URL Shortener (TinyURL): turns long URLs into short codes; the focus is key generation, read-heavy scaling, and the redirect choice.
Both use the usual layered breakdown + interviewer follow-ups.
Part 1 — Designing a Rate Limiter
Step 1 — Clarify Requirements
- Limit what: per user? per IP? per API key?
- Limit how much: e.g. "100 requests per minute."
- What on exceed: return HTTP 429 (Too Many Requests), optionally with
Retry-After. - Scale: single-machine or distributed (many servers sharing one count)?
- Precision vs performance: strict accuracy, or tolerate small boundary error for speed?
🎤 Interviewer follow-up: "Which layer does rate limiting live in?" (Usually the API Gateway / middleware, blocking before requests hit business logic to save backend resources.)
Step 2 — Four Algorithms and Their Trade-offs ⭐
| Algorithm | How it works | Pros | Cons |
|---|---|---|---|
| Fixed Window | one counter per window (e.g. per minute), block over the limit | simplest, low memory | window boundary can let 2× traffic through |
| Sliding Log | store every request's timestamp, count those in the window | most accurate | memory-heavy (stores every timestamp) |
| Sliding Window Counter | weighted estimate of previous + current window | best balance of accuracy and performance | approximate, not 100% exact |
| Token Bucket | tokens refill at a fixed rate, each request spends one; empty → block | allows bursts (saved tokens), smooth | params (capacity/refill) need tuning |
| Leaky Bucket | requests queue, drain at a fixed rate | absolutely smooth output | no bursts, possible queueing delay |
How to choose:
- Need to allow short bursts (most APIs) → Token Bucket (the industry favorite).
- Need absolutely smooth output (strict downstream protection) → Leaky Bucket.
- Need simplicity and tolerate boundary error → Fixed Window.
- Need accuracy without much memory → Sliding Window Counter.
🎤 Interviewer follow-up: "What's the fixed-window problem?" (The boundary: 100 at second 59 + 100 at second 0 of the next minute = 200 within one second. Sliding window or token bucket mitigates it.) "How does Token Bucket allow bursts?" (Saved tokens can be spent at once, permitting a brief spike above the average rate.)
Step 3 — Distributed Implementation (Redis) ⭐
Single-machine can just count in memory; multiple servers must share the count via centralized storage:
- Redis as the shared counter:
INCR+EXPIRE(fixed window), or a Lua script / atomic op so the "read-modify-write" doesn't race. - Race condition: many servers read 99 simultaneously and each +1 → over-allow. Use atomic ops (Redis INCR is atomic, or wrap in a single atomic Lua script).
- Performance vs consistency: strict → hit Redis every time (an extra round trip); relaxed → block the obvious locally and sync periodically.
🎤 Interviewer follow-up: "How do you avoid races on the distributed count?" (Redis atomic INCR or a Lua script; don't do "read then write" in the app layer.) "What if Redis goes down?" (fail-open (allow, keep availability) vs fail-close (block, keep safety) — a business trade-off; rate limiting usually leans fail-open so the limiter doesn't become the point of failure.)
Part 2 — Designing a URL Shortener (TinyURL)
Step 1 — Clarify Requirements
- Core functions: ① long URL → short URL; ② visit short URL → redirect to long URL.
- Scale estimate: write-light, read-heavy (typically read:write ≈ 100:1); assume tens of millions of new URLs/day; the QPS estimate drives caching and sharding.
- Short-code length: base62 (a-z A-Z 0-9); 7 chars ≈ 62⁷ ≈ 3.5 trillion, plenty for a long time.
- Bonus: custom alias, expiration, click analytics.
🎤 Interviewer follow-up: "How short should the code be — how do you size it?" (Compute capacity with base62: figure how many URLs you must support, back out the digit count — 62⁷ is already trillions.)
Step 2 — Key Generation: Producing Unique Short Codes ⭐
| Method | How it works | Pros | Cons |
|---|---|---|---|
| Counter + Base62 | global incrementing ID → base62 | no collisions, short | predictable (sequential); the generator must be distributed (ID segments / Snowflake) |
| Hash (MD5/SHA) prefix | hash(long URL), take first 7 chars | simple, same URL → same code | may collide (detect + retry); unordered |
| Pre-generated KGS (Key Generation Service) | pre-generate a large pool of unique keys offline, hand one out on use | zero online collision/compute | needs an extra service to manage the key pool |
How to choose:
- No collisions, sequential is fine → Counter + base62 (with distributed generation).
- Want unpredictable codes → hash or KGS (KGS is the most robust, widely used).
- Custom alias → a separate table, check uniqueness before writing.
🎤 Interviewer follow-up: "How do you handle hash collisions?" (After generating, check the DB; on collision, salt / take more bits and retry.) "How do you avoid a single point for counter generation in a distributed setup?" (ID-segment pre-fetch (each server grabs a range) or Snowflake-style distributed IDs.)
Step 3 — Storage and Scaling (read-heavy) ⭐
- Storage: essentially key-value (short code → long URL + metadata) — a NoSQL store (DynamoDB/Cassandra) or sharded SQL.
- Sharding: at large volume, shard by short-code hash (consistent hashing).
- Caching (the crux, since read-heavy): put hot URLs in Redis / CDN; most reads hit the cache, dropping DB load sharply. Evict with LRU.
- Architecture: user → LB → app → check cache → miss → DB → backfill cache.
🎤 Interviewer follow-up: "Read:write is 100:1 — where's the architectural focus?" (Caching — shield the DB from the vast majority of reads; see the fundamentals post.)
Step 4 — Redirect: 301 vs 302 ⭐
Which redirect to return on visiting a short URL is the classic gotcha here:
- 301 Permanent: the browser caches it and jumps directly next time, never reaching your server → saves server load, but you lose click analytics.
- 302 Temporary: every visit returns to your server to redirect → lets you collect click/analytics data, but higher server load.
How to choose: doing click analytics (the selling point of most shortener services) → use 302; purely saving load and don't care about stats → 301.
🎤 Interviewer follow-up: "Why do shortener services mostly use 302, not 301?" (302 routes through the server every time, so you can record click data; once a 301 is browser-cached, you're blind to that traffic.)
Closing Comparison
| Rate Limiter | URL Shortener | |
|---|---|---|
| Core focus | trade-offs among four algorithms | key generation + read-heavy |
| Key component | Redis atomic counter | KV store + cache |
| Classic follow-up | fixed-window boundary, fail-open/close | 301 vs 302, collision handling |
| Best default | Token Bucket (allows bursts) | KGS or counter+base62 + heavy cache |
The Answer Framework Cheat
- Rate limiter: clarify "limit whom, how much, what on exceed" → cover the four algorithms' trade-offs (Token Bucket allows bursts; fixed window has the boundary problem) → distributed via Redis atomic ops → close on fail-open/close.
- URL shortener: estimate scale (read-heavy) → key generation (counter+base62 / hash / KGS trade-offs) → KV storage + sharding + heavy caching → close on 301 vs 302 (302 for analytics).
These two are small but exercise the core muscles of system design: algorithmic trade-offs, atomicity and races, key generation and uniqueness, read-heavy caching, and one deceptively detailed but probing trade-off (301/302). Master them and the foundation for the big questions is solid.