/nw-sd-case-studies

name: nw-sd-case-studies
description: 25 real-world system design case studies condensed from Alex Xu's System Design Interview Vol 1 and 2 - requirements, architecture, deep dive insights, key takeaways
user-invocable: false
disable-model-invocation: true

System Design Case Studies

Reference catalog of 25 real-world designs. Use when designing a similar system or needing precedent for architectural decisions.

---

Volume 1 Case Studies

Rate Limiter

**Scale**: API gateway middleware | **Core**: Token Bucket (industry standard) or Sliding Window Counter | **Storage**: Redis counters with TTL | **Distributed**: Lua scripts for atomic increment | **Key insight**: cross-cutting concern, belongs in middleware/gateway | **Headers**: 429 + Retry-After + X-RateLimit-Remaining

Consistent Hashing

**Core**: hash ring 0 to 2^32-1, servers at positions, keys walk clockwise | **Virtual nodes**: 100-200 per server, reduces load deviation from ~40% to ~5% | **Used in**: DynamoDB, Cassandra, Akamai, Discord | **Key insight**: never deploy without virtual nodes

Key-Value Store (Dynamo-style)

**Core**: consistent hashing for partitioning, N replicas on clockwise nodes, quorum W+R>N | **Conflict**: vector clocks, LWW, app-level merge | **Failures**: sloppy quorum + hinted handoff (temp), Merkle trees + anti-entropy (permanent), gossip for detection | **Write path**: WAL -> memtable -> SSTable (LSM-tree) | **Read path**: memtable -> Bloom filter -> SSTable(s)

Unique ID Generator

**Winner**: Snowflake -- 64-bit, sortable, minimal coordination | `[1 unused | 41 timestamp | 5 DC | 5 machine | 12 sequence]` ~4M IDs/sec/DC | **Weakness**: clock sync (NTP) | **Alt**: UUID (128-bit, not sortable), ticket server (SPOF)

URL Shortener

**Scale**: 100M/day ~ 1,160 QPS write, 11,600 read | **Short URL**: base62 with 7 chars = 3.5T combinations | **Approaches**: hash + collision resolution | base62 from auto-increment ID | pre-generated key service | **Redirect**: 301 (cached, no analytics) vs 302 (every click tracked) -- most use 302 | **Key**: caching critical (heavy-tailed distribution)

Web Crawler

**Scale**: 1B pages/month ~ 400 pages/sec, 500TB storage/month | **Core**: URL Frontier with priority queues (importance) + politeness queues (per-domain rate limit) | **Dedup**: SHA-256 exact, simhash/MinHash near-duplicate | **Traps**: URL length limit, max depth, blacklist | **Key insight**: URL frontier is the most important component

Notification System

**Scale**: 10M push, 1M SMS, 5M email/day | **Architecture**: Services -> Message Queue -> Workers -> Third-party (APNs, FCM, Twilio, SES) | **Reliability**: persist before sending, retry with exponential backoff, dedup via event_id | **Key**: decouple creation from delivery; user preferences are critical

News Feed

**Core**: hybrid fan-out -- push for normal users (<10K followers), pull for celebrities | **Feed cache**: pre-computed for most users, celebrity posts merged at read time | **Ranking**: chronological simplest; ML-based for engagement optimization | **Pagination**: cursor-based (not offset) | **Media**: object storage + CDN

Chat System

**Scale**: 50M DAU | **Protocol**: WebSocket (bidirectional, persistent) | **Storage**: KV store (HBase-like), partition by channel_id | **1-on-1**: message via WebSocket -> store -> push to recipient (or notification if offline) | **Group (<100)**: fan-out on write to member inboxes | **Presence**: heartbeat every 5s, offline after 30s missed, lazy propagation for large friend lists | **Multi-device**: per-device cursor of last-read message

Search Autocomplete

**Scale**: 24K QPS avg, 48K peak | **Core**: trie with cached top-K at each node, O(prefix_length) query | **Update**: offline aggregation (weekly rebuild), NOT real-time; separate trending pipeline | **Scaling**: shard by first character(s), replicate each shard | **Client**: debounce 100-200ms, cache recent results, pre-fetch

YouTube (Video Platform)

**Scale**: 5M DAU, 150TB storage/day | **Upload**: upload -> transcoding queue -> workers (DAG pipeline: split->encode->merge) -> object storage -> CDN | **Streaming**: adaptive bitrate (DASH/HLS), manifest + segment-based | **Transcoding**: multiple resolutions (360p-4K) + formats (H.264, VP9, AV1) | **Cost**: popular videos on CDN, long-tail from origin; encode popular formats eagerly

Google Drive (Cloud Storage)

**Scale**: 50M users, 500PB total | **Core optimization**: block-level sync -- split files into ~4MB blocks, detect changed blocks (delta sync), upload only changed | **Notification**: long polling for sync events | **Dedup**: same block hash = same storage across users | **Versioning**: store block lists per version, not full copies | **Conflict**: first upload wins, second gets notification, user resolves

---

Volume 2 Case Studies

Proximity Service (Yelp)

**Scale**: 100M DAU, 200M businesses | **Core**: geospatial indexing -- geohash (string prefix queries, DB-friendly) or quadtree (adaptive density, in-memory ~1.7GB) | **Boundary problem**: geohash neighbors may have different prefixes -- query target + 8 neighbors | **Architecture**: separate LBS (read-heavy, stateless) from Business Service (CRUD)

Nearby Friends

**Scale**: 10M concurrent, 334K location updates/sec | **Core**: Pub/Sub with geohash-based channels (not per-user -- too many) | **Connection**: WebSocket (bidirectional, persistent) | **Location cache**: Redis with TTL 60s | **Optimization**: subscribe to own geohash cell + 8 neighbors; resubscribe on cell change

Google Maps

**Map rendering**: pre-rendered tile pyramid (zoom N = 4^N tiles), served via CDN | **Tile addressing**: `/tiles/{zoom}/{x}/{y}.png` | **Routing**: hierarchical graph (local -> regional -> interstate), not naive Dijkstra -- Contraction Hierarchies | **ETA**: base distance/speed + real-time traffic + historical patterns + ML | **Traffic**: crowdsourced GPS traces, aggregated per road