System Design Case Studies
What you’ll learn. How to apply the toolkit from System Design Fundamentals and Distributed Systems to six classic problems. Each case follows the same template: requirements, estimates, API and data model, architecture, deep dive, and trade-offs. The numbers are illustrative assumptions; the reasoning is the point. Code is Python or TypeScript, labelled.
1. URL shortener
Section titled “1. URL shortener”Requirements
Section titled “Requirements”Functional: create a short link for a long URL; redirect from short to long; optional custom alias, expiry and click analytics. Non-functional: redirects must be fast (p99 under ~50 ms server side) and highly available; links must not collide; short codes should not be trivially guessable if links are private.
Estimates
Section titled “Estimates”Assume 100 million new links per month and a 100:1 read:write ratio.
- Writes: /s average. Reads: ~4,000 /s average, ~12,000 /s peak.
- Storage: 5 years x 12 months x 100M = 6 billion links. At ~500 bytes per record (long URL, metadata), ~3 TB. Modest.
- Key length: base62 (
[0-9a-zA-Z]) with 7 characters gives codes, comfortably above 6 billion.
Conclusion: a read-heavy, small-data system. A cache and a simple key-value lookup do nearly all the work.
API and data model
Section titled “API and data model”POST /links {long_url, alias?, expires_at?} -> 201 {short_url}GET /{code} -> 301/302 Location: long_urllinks(code PK, long_url, created_at, expires_at, owner_id). A key-value store (DynamoDB, Cassandra) or a sharded SQL table keyed by code fits, since all access is by key.
Generating codes
Section titled “Generating codes”| Approach | How | Pros | Cons |
|---|---|---|---|
| Hash and truncate | base62(MD5(url))[:7] | Same URL gives the same code | Collisions need detection and retry; truncated hashes collide at scale |
| Random | 7 random base62 chars | Unguessable, no coordination | Collision check required (probability small but nonzero) |
| Counter and base62 | Global incrementing ID encoded | No collisions, short | Needs coordination; sequential codes are enumerable |
| Pre-generated key service | Offline generator fills a pool; app servers grab batches | Fast, no collisions, no hot counter | Extra component |
A solid choice: a counter with range allocation: each app server leases a block of, say, 10,000 IDs from a coordination service (or a DB sequence), then encodes IDs locally without further coordination. To avoid enumerable codes, pass the ID through a reversible permutation or encryption (a format-preserving cipher, or a Feistel network) before base62 encoding.
# Python: base62 encoding of an integer IDALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
def base62(n: int) -> str: if n == 0: return ALPHABET[0] out = [] while n: n, r = divmod(n, 62) out.append(ALPHABET[r]) return "".join(reversed(out))
assert base62(125) == "21" # 125 = 2*62 + 1Architecture
Section titled “Architecture”Client -> CDN/LB -> redirect service (stateless) -> Redis cache --miss--> KV store | +--(async, via queue)--> analytics pipeline (click counts)Writes -> create service -> ID allocator -> KV storeDeep dive and trade-offs
Section titled “Deep dive and trade-offs”- 301 vs 302. 301 (permanent) lets browsers and CDNs cache the redirect, cutting load but hiding later clicks from analytics and making edits or expiry ineffective. 302/307 keeps every click flowing through your service. Choose per product needs; many shorteners use 302 for analytics.
- Caching. Popularity is heavily skewed (Zipf): caching the hottest 20% of codes can yield a hit rate above 90%. Cache-aside with TTL; negative-cache missing codes.
- Analytics must not slow redirects: emit click events to a queue/log (Kafka) and aggregate asynchronously; accept eventual consistency in counters.
- Abuse: malware/phishing links need scanning, rate limiting per user (case 2) and a takedown path.
- Availability: reads are served from replicas and caches; a brief write outage is tolerable; replicate the KV store across zones.
- Custom aliases need a uniqueness check (conditional put) and a reserved-word list.
2. Rate limiter
Section titled “2. Rate limiter”Requirements
Section titled “Requirements”Limit each client (API key, user or IP) to a number of requests per time window; reject excess with 429 and Retry-After. Must add negligible latency (under a millisecond or two), work across many API servers, and fail safely if its store is down. Rules are configurable per endpoint and tier.
Algorithms
Section titled “Algorithms”- Fixed window counter: count per window (
user:123:minute:2026-11-17T10:05). Simple, but allows bursts of up to twice the limit at window boundaries. - Sliding window log: store timestamps of recent requests; exact but memory-heavy.
- Sliding window counter: weighted blend of current and previous windows’ counts; approximate, cheap.
- Token bucket: a bucket holds up to tokens and refills at rate per second; each request consumes one. Allows bursts up to while enforcing average rate . The most common choice (used by many API gateways and cloud providers).
- Leaky bucket: requests queue and drain at a constant rate; smooths output, good for shaping.
# Python: token bucket (single process); store (tokens, last_refill) per keyimport time
class TokenBucket: def __init__(self, rate: float, capacity: float): self.rate, self.capacity = rate, capacity self.tokens, self.last = capacity, time.monotonic()
def allow(self, cost: float = 1.0) -> bool: now = time.monotonic() self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate) self.last = now if self.tokens >= cost: self.tokens -= cost return True return FalseDistributed design
Section titled “Distributed design”With many API servers, per-process counters are inaccurate (limit multiplied by server count). Use a shared store, typically Redis, with an atomic operation so concurrent servers do not race. A Lua script executes atomically on the Redis server:
// TypeScript (ioredis): atomic token bucket in Redis via Luaconst script = `local key, rate, cap, now, cost = KEYS[1], tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3]), tonumber(ARGV[4])local d = redis.call('HMGET', key, 't', 'ts')local tokens = tonumber(d[1]) or caplocal ts = tonumber(d[2]) or nowtokens = math.min(cap, tokens + (now - ts) * rate)local ok = 0if tokens >= cost then tokens = tokens - cost; ok = 1 endredis.call('HMSET', key, 't', tokens, 'ts', now)redis.call('EXPIRE', key, math.ceil(cap / rate) * 2)return ok`;const allowed = await redis.eval(script, 1, `rl:${userId}`, rate, capacity, Date.now() / 1000, 1);Client -> API gateway / middleware --(rate check)--> Redis (sharded by key) | allowed v backend service 429 + Retry-After on rejectTrade-offs
Section titled “Trade-offs”- Where: at the edge/gateway (protects everything, coarse) vs in services (fine-grained, per-resource). Often both.
- Accuracy vs cost: global exact counting needs a network hop per request; alternatives: local token buckets with periodic synchronization (approximate, fast) or sticky routing of a key to one node.
- Failure mode: if Redis is unreachable, fail open (allow; protects availability, risks overload) or fail closed (protect backend, hurts users). Usually fail open with a local fallback limit.
- Hot keys/clock skew: shard Redis by key; use the Redis server’s clock or monotonic logic rather than client clocks.
- Communicate limits with headers (
RateLimit-Limit/Remaining/Reset) so clients can back off; this pairs with client-side retry and backoff (Reliability). - Limits on dimensions: per user, IP, API key, endpoint, and global concurrency (limit in-flight requests, which protects against slow-request overload better than QPS alone).
3. News feed
Section titled “3. News feed”Requirements
Section titled “Requirements”Users follow others and see a reverse-chronological or ranked feed of recent posts. Posting should be quick; feed reads must be fast (p99 under ~200 ms); a feed should be fairly fresh (seconds), but not strictly real-time. Ranking, media and ads are out of scope for the core design.
Estimates
Section titled “Estimates”300 million DAU, each opening the feed 5 times per day and posting 0.3 times per day; average user follows 200 accounts; a few celebrities have 50 million followers.
- Feed reads: /s (peak ~50,000/s).
- Posts: /s.
- Naive fan-out on write: each post goes to ~200 followers: 200,000 feed insertions/s, manageable. But a celebrity post would trigger 50 million insertions at once.
Core decision: fan-out on write vs on read
Section titled “Core decision: fan-out on write vs on read”- Fan-out on write (push model): when a user posts, insert the post ID into each follower’s precomputed feed (a list in Redis/a wide-column store). Reads become a cheap single lookup. Cost: write amplification and wasted work for inactive followers; huge for celebrities.
- Fan-out on read (pull model): on feed load, fetch recent posts of everyone followed and merge. Writes are cheap; reads are expensive (200 queries merged) and slow.
- Hybrid: push for normal users, pull for celebrities (above a follower threshold). At read time, take the precomputed feed and merge in recent posts from the few celebrities the user follows. Also skip pushing to inactive users (compute their feed on demand when they return). This is the widely used compromise.
Post ──> Post Service ──> Posts DB (source of truth, sharded by author) | └──> queue ──> Fan-out workers ──> Feed cache: feed:{user} = [post_id, ...] (capped, e.g. 800) ^ skips celebrities / inactive users
Read: Feed Service ──> feed:{user} (IDs) + celeb posts (pull) ──> hydrate from post cache ──> rank ──> returnData model and deep dive
Section titled “Data model and deep dive”posts(post_id, author_id, content, created_at)sharded byauthor_idor time-based IDs (Snowflake-style 64-bit IDs encode time, so sorting by ID is sorting by time).follows(follower_id, followee_id)in both directions (who I follow; who follows me), sharded by the lookup key.- Feed store: a capped list per user of
(post_id, score/time); store IDs only and hydrate content from a post cache, so edits and deletes need no feed rewrites. - Pagination: cursor by post ID/time, not offset (API Design).
- Ranking: a ranking service scores candidates (recency, affinity, engagement), usually a machine-learned model run over a few hundred candidates; this is out of the core design but affects what is cached.
- Deletes and privacy changes: mark posts deleted and filter at hydration time; remove lazily.
Trade-offs
Section titled “Trade-offs”Freshness vs cost (push is fresh but expensive); consistency is eventual (a new post may take seconds to reach followers); memory cost of feed caches (800 IDs x 8 bytes x 300M users = ~1.9 TB, fine for a sharded cache cluster); the celebrity threshold is a tunable tuning problem; the follow graph itself is a scaling challenge (graph stores or heavily denormalized tables).
4. Chat system
Section titled “4. Chat system”Requirements
Section titled “Requirements”One-to-one and group chat (up to a few hundred members), real-time delivery, delivery/read receipts, online presence, message history across devices, offline delivery on reconnect. Message ordering within a conversation. End-to-end encryption is a major extra (out of scope here).
Estimates
Section titled “Estimates”50 million DAU, 40 messages sent per user per day: 2 billion messages/day, ~23,000 /s average, ~70,000 /s peak. At 100 bytes average: 200 GB/day, ~73 TB/year of text before replication. Concurrent connections: assume 10 million simultaneous WebSocket connections; at ~100 KB of memory per connection that is ~1 TB of connection state, spread across e.g. 200 gateway servers at ~50,000 connections each.
Transport
Section titled “Transport”HTTP polling is wasteful; WebSockets (persistent bidirectional connections) are the standard for real-time chat; Server-Sent Events work for one-way push; mobile apps also integrate OS push notifications for offline devices (case 5).
Architecture
Section titled “Architecture”Client <==WebSocket==> Chat Gateway servers (stateful connections) | Session/presence store: user_id -> gateway_id (Redis) | Message service ----> Message queue/log (partitioned by conversation_id) | |-> Delivery workers -> target gateway -> recipient's socket v |-> Push notification service (if recipient offline) Message store (wide-column, partitioned by conversation_id)1:1 message flow. Sender’s client sends over its WebSocket to its gateway; the message service assigns an ID and timestamp, persists it, then routes: look up the recipient’s gateway(s) in the session store and push; if the recipient is offline, store it and send a push notification, then deliver on reconnect (sync from the last seen message ID). Clients ack receipt; the server retries until acked, and clients dedupe by message ID (at-least-once plus idempotence, per Distributed Systems).
Group chat. Fan-out per member on write for small groups (store one copy in the conversation and per-member delivery/unread pointers rather than N message copies). For huge channels (Slack/Discord scale), push to online members only and let others pull history.
Ordering. Global ordering is unnecessary and expensive; require order within a conversation. Partition the log by conversation_id so one partition (one leader) sequences it. Assign monotonically increasing per-conversation sequence numbers; clients detect gaps and re-fetch. Do not rely on client clocks.
Storage. Access pattern: “latest N messages in a conversation”, “messages after ID X”. A wide-column or key-value store with primary key (conversation_id, message_id) clustering by message ID suits (Cassandra, ScyllaDB, DynamoDB, HBase were all used in well-known chat systems). Keep recent messages hot; archive old ones. User metadata and group membership go in a relational DB.
Presence. Heartbeats from connected clients refresh a TTL key in Redis (presence:{user}); expiry means offline. Broadcasting presence changes to every friend does not scale; instead fetch presence on demand for visible contacts, or subscribe only to those in the open view.
Trade-offs
Section titled “Trade-offs”Stateful gateways complicate deploys and failover (reconnect storms after a gateway dies: use jittered reconnect backoff and connection draining); consistency vs availability is mostly resolved toward availability with per-conversation ordering; multi-device sync requires per-device cursors; read receipts add write load; end-to-end encryption (Signal protocol) moves complexity to clients and prevents server-side search or moderation.
5. Notification system
Section titled “5. Notification system”Requirements
Section titled “Requirements”Send notifications (push via APNs/FCM, SMS, email, in-app) triggered by events or schedules: transactional (password reset, order shipped: must be reliable and quick), and marketing/bulk (can be delayed). Respect user preferences, quiet hours, and opt-outs; avoid duplicates; support templates and localization; provide delivery status and analytics.
Estimates
Section titled “Estimates”10 million notifications per day average, with bursts (a campaign of 20 million in an hour: ~5,500 /s). Third-party providers impose their own rate limits and have variable latency, so a queue is needed.
Architecture
Section titled “Architecture”Producers (services) --event/API--> Notification Service validate, dedupe (idempotency key), check preferences/opt-outs, rate-cap per user | v Priority queues per channel: [push-high] [push-bulk] [email] [sms] (per-channel workers) | v Channel workers: render template + localize -> provider adapter (FCM / APNs / SES / Twilio) | |-- retry with backoff, circuit breaker v v Delivery log / status store <-- provider webhooks (delivered, bounced, unsubscribed)Key design points:
- Decoupling via queues: producers get an immediate acceptance (
202); workers scale per channel and isolate failures (a slow SMS provider must not delay push). Separate queues by priority so a bulk campaign cannot starve password-reset codes. - Provider adapters (Adapter pattern) hide vendor differences and allow failover between providers.
- Reliability: at-least-once delivery from the queue; dedupe by
(user, notification_id)so retries do not send twice (SMS and email duplicates annoy users and cost money); dead-letter queue for permanent failures; exponential backoff with jitter; circuit breakers around providers (Reliability & Performance). Remember true exactly-once is impossible: a crash after the provider accepted but before recording leads to a possible duplicate; use provider idempotency keys where available. - Preferences and compliance: per-user, per-channel, per-category settings; global frequency caps; legal requirements (unsubscribe links, consent records, regional rules such as GDPR and anti-spam laws).
- Scheduling: a delayed-job store (timestamp-ordered index or delayed queue) for “send at 9am local time”.
- Templates: versioned templates and a rendering service; render at send time with user’s locale and time zone.
- Device tokens: store tokens per device, handle invalid-token feedback from APNs/FCM by pruning.
- Batching/digests reduce noise (collapse 20 likes into one notification).
# Python: idempotent enqueue with preference check (sketch)def notify(user_id: str, kind: str, dedupe_key: str, payload: dict) -> str: if not preferences.allows(user_id, kind): return "suppressed" if not redis.set(f"notif:{dedupe_key}", 1, nx=True, ex=86400): # SET NX = first writer wins return "duplicate" queue.publish(topic=f"{channel_for(kind)}-{priority_for(kind)}", message={ "user": user_id, "kind": kind, "payload": payload}) return "queued"Trade-offs
Section titled “Trade-offs”Latency vs batching, strict dedupe vs possible loss (deduping before send risks dropping if the send then fails; mitigate by marking after success or tracking states: queued, sent, failed), cost of SMS, spam risk when many services can notify (centralize caps), and observability (end-to-end delivery rate, time-to-deliver per channel, provider error rates).
6. Search autocomplete (typeahead)
Section titled “6. Search autocomplete (typeahead)”Requirements
Section titled “Requirements”As the user types a prefix, suggest the top (say 5-10) completions, ranked by popularity (and optionally personalization/freshness), with very low latency: a response under ~100 ms end to end, ideally ~20-50 ms server side, since it is called on nearly every keystroke. Suggestions need not be perfectly fresh (hourly or daily updates are acceptable; trending queries may need faster paths). Filter offensive or illegal suggestions.
Estimates
Section titled “Estimates”100 million DAU, 10 searches each, ~5 keystrokes issuing requests per search (with debouncing): 5 billion requests/day, ~58,000 /s average, ~150,000-200,000 /s peak. The data set: say 100 million distinct popular queries, ~30 characters each: ~3 GB of raw strings, so the entire index fits in memory on one machine; the challenge is QPS and latency, solved by replication and caching rather than sharding for capacity.
Data structure: the trie
Section titled “Data structure: the trie”A trie (prefix tree) stores strings by shared prefixes. Each node corresponds to a prefix; walking the prefix leads to a subtree containing all completions. Naively, finding top- requires traversing the subtree, which is slow. The standard optimization: store the precomputed top- suggestions at every node (query string and score), so lookup is for prefix length with no subtree traversal.
# Python: trie with precomputed top-k per nodeimport heapqfrom dataclasses import dataclass, field
@dataclassclass Node: children: dict = field(default_factory=dict) top: list = field(default_factory=list) # list of (score, query), best first
class Autocomplete: def __init__(self, k=5): self.root, self.k = Node(), k
def add(self, query: str, score: int) -> None: node = self.root for ch in query: node = node.children.setdefault(ch, Node()) node.top.append((score, query)) node.top = heapq.nlargest(self.k, node.top) # keep only top k
def suggest(self, prefix: str) -> list[str]: node = self.root for ch in prefix: node = node.children.get(ch) if node is None: return [] return [q for _, q in sorted(node.top, reverse=True)]
ac = Autocomplete()for q, s in [("system design", 90), ("system call", 40), ("sysadmin", 25)]: ac.add(q, s)print(ac.suggest("sys")) # ['system design', 'system call', 'sysadmin'](This builder keeps duplicates simple; a production builder aggregates scores per query first.) Space cost: storing top- at each node multiplies storage by roughly ; compress with IDs referencing a shared query table, radix/compact tries, or finite-state transducers (FSTs, as in Lucene). Alternatives: an inverted index with edge n-grams in Elasticsearch/OpenSearch; sorted arrays with binary search for prefix ranges.
Architecture: two paths
Section titled “Architecture: two paths”Online (read) path: Browser (debounce ~100-200 ms, cache locally) -> CDN/edge cache (popular prefixes) -> LB -> Suggestion servers (in-memory trie snapshot, replicated) -> top-k
Offline (build) path: Query logs --> stream/batch aggregation (counts per query, time-decayed, filtered) --> build new trie/index snapshot --> publish to blob store --> servers hot-swap atomically (optional) trending stream: fast path adding/boosting fresh queries within minutes- Query logs flow through Kafka into aggregation jobs; sample if volume is huge. Weight recent counts higher (exponential decay) to capture trends.
- Snapshots are immutable and swapped atomically (build, validate, then switch a pointer), avoiding online mutation of structures under heavy read load.
- Caching: short prefixes (“a”, “ab”) dominate traffic and have identical answers for everyone: cache at the CDN, with TTL of minutes. Client-side: debounce keystrokes and cache previous prefix results (when the user types “sys” then “syst”, you can often filter already-fetched results locally).
- Sharding (if the index outgrows memory): by first characters or hashed prefix with a routing layer; hot prefixes need replicas.
- Personalization and context (language, location, history) are applied by re-ranking a larger candidate set (say top 50 global plus user-specific) at request time.
- Safety: blocklists, removing PII-like queries (emails, numbers), and handling typo tolerance (fuzzy matching, edit distance) as an extension.
Trade-offs
Section titled “Trade-offs”Freshness (batch rebuilds are simple but slow to reflect trends) vs complexity (streaming updates); memory vs latency (precomputed top- trades space for speed); relevance quality vs latency budget; consistency across replicas during snapshot rollout is relaxed (users may briefly see slightly different suggestions), which is fine for this feature.
Cross-cutting lessons
Section titled “Cross-cutting lessons”- Start from access patterns and numbers. Autocomplete: tiny data, huge QPS; chat: many long-lived connections; shortener: read-heavy key lookups; feed: write amplification.
- Precompute vs compute on demand: feed fan-out, autocomplete top-, cached redirects, all shift work from the read path to the write or offline path.
- Queues buy decoupling: notifications, click analytics, feed fan-out.
- Hot spots and skew (celebrities, popular prefixes, viral links) are the norm; design for the skew, not the average.
- Choose consistency per feature: unique alias creation needs strong guarantees; feed freshness and presence do not.
- Plan degraded modes: fail open vs closed, serve stale cache, drop non-critical work.
Key takeaways
Section titled “Key takeaways”- A repeatable template (requirements, estimates, API/data model, architecture, deep dive, trade-offs) turns open-ended prompts into tractable designs.
- URL shortener: counter-range IDs plus cache; 301 vs 302 shapes analytics.
- Rate limiter: token bucket with atomic Redis operations; decide fail-open or closed.
- News feed: hybrid push/pull fan-out handles celebrity skew; store IDs and hydrate.
- Chat: WebSocket gateways, per-conversation ordering via partitioning, at-least-once delivery with client dedupe, TTL-based presence.
- Notifications: priority queues per channel, provider adapters, dedupe and preferences, retries with circuit breakers.
- Autocomplete: precomputed top- per trie node, offline build, atomic snapshot swap, aggressive caching.
Exercises
Section titled “Exercises”- Hands-on (Python). Extend the URL shortener with a Feistel-based permutation so sequential IDs yield non-guessable 7-character codes; verify it is bijective on a small range.
- Hands-on (Python). Implement a sliding-window-counter rate limiter and compare its behavior with a fixed window at boundary bursts using simulated traffic.
- Conceptual. Choose a push/pull threshold for the news feed. Given a push cost of inserts per post (F = followers) and a pull cost of lookups per read, derive when pull is cheaper for a user who posts times per day and whose followers collectively read the feed times per day.
- Conceptual. Design how a chat system handles a user with three devices, one of which is offline for two days.
- Hands-on. Estimate the memory needed for an autocomplete trie with 50 million queries (30 chars average), storing top-5 per node. Where could you cut cost?
Solutions (sketch)
- A Feistel network on 42-bit values (62^7 is about 2^41.7) with a keyed round function and cycle-walking to stay within range keeps the mapping a bijection; test by mapping a range and checking uniqueness and invertibility.
- Weighted estimate = previous_count x (1 - elapsed_fraction) + current_count; show that a fixed window admits ~2x the limit across a boundary while the sliding counter admits close to the limit.
- Push cost is about writes per day; pull cost is about extra lookups per day. Pull is cheaper when , e.g. very large (celebrity) with a modest read volume or small . In practice use a follower-count threshold and activity-based skipping.
- Per-device sync cursor (last acknowledged sequence number per conversation); on reconnect, fetch messages after the cursor; store messages server-side so history is the source of truth; push notification wakes the device.
- Raw characters: 50M x 30 = 1.5 GB at minimum, but a trie shares prefixes; nodes might number a few hundred million with pointers and top-5 lists, so perhaps tens of GB uncompressed. Cut via query-ID indirection, compressed/radix tries, FSTs, pruning rare queries, and limiting the indexed prefix length.
Further reading
Section titled “Further reading”- Alex Xu, System Design Interview: An Insider’s Guide (Vol. 1, 2020; Vol. 2 with Sahn Lam, 2022), covering most of these cases.
- Martin Kleppmann, Designing Data-Intensive Applications (2017).
- Donne Martin, “The System Design Primer” (open-source GitHub repository).
- Engineering blog posts from companies on feeds, messaging and rate limiting (for example, Instagram, Twitter, Discord, Stripe’s “Scaling your API with rate limiters”).
- Jeff Dean, “Challenges in Building Large-Scale Information Retrieval Systems” and related talks.
- Giuseppe DeCandia et al., “Dynamo” (SOSP 2007).