nwave-ai/nw-sd-case-studies

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 segment

Distributed Message Queue (Kafka)

Core: topics divided into partitions (unit of parallelism + ordering) | Storage: append-only log segments, sequential I/O, zero-copy, batching | Producer: partition via round-robin/key-hash, ack modes (0/1/all) | Consumer groups: each partition to one consumer in group, offset tracking | Replication: leader + ISR followers, elect from ISR on failure | Why fast: sequential writes (~600MB/s), zero-copy, page cache, batching

Metrics Monitoring

Data model: (metric_name, tags, timestamp, value) | TSDB: specialized for high write throughput + time-range queries | Compression: delta-of-delta timestamps, XOR values (Gorilla) | Storage tiering: hot (raw, memory) -> warm (1-min aggregates) -> cold (1-hour aggregates) | Ingestion: pull (Prometheus) or push (Datadog), buffer with Kafka | Alerting: rules against TSDB, dedup, escalation

Ad Click Aggregation

Scale: 1B clicks/day, 10K-50K QPS | Architecture: Kafka -> Flink (stream) -> Aggregation DB + Reconciliation (batch) | Windows: tumbling (1-min for billing) or sliding (rolling) | Exactly-once: Kafka transactions + Flink checkpointing | Late events: watermarks with trade-off (longer delay = more accuracy) | Reconciliation: batch corrects stream inaccuracies for billing

Hotel Reservation

Scale: low QPS (~35), HIGH correctness | Core challenge: concurrency control, not scale | Solution: optimistic locking + DB constraint: UPDATE WHERE version=? AND reserved < total | Flow: select -> PENDING -> payment -> CONFIRMED/CANCELLED, 10-min timeout | Idempotency: client-generated key prevents double-booking | Overbooking: business decision (~110%), built into model

Email Service

Scale: 1B users, 460K receive QPS, ~10 EB storage | Architecture: SMTP for send/receive, separate metadata (relational/wide-column) from body/attachments (blob) | Labels: Gmail-style (not folders), email can have multiple | Search: Elasticsearch, indexed async, per-user scope | Sync: push-then-pull (notification triggers device pull), per-device cursor | Anti-spam: ML + sender reputation + SPF/DKIM/DMARC + rate limiting

S3 Object Storage

Scale: 100 PB, 11 nines durability | Architecture: API Service + Metadata Service + Data Service (separate metadata from data) | Durability: replication + erasure coding + checksums + cross-AZ + self-healing | Write: replicate data first, then commit metadata | Versioning: version chain in metadata, each PUT = new version, soft delete | Listing: prefix queries on flat namespace with '/' convention

Gaming Leaderboard

Scale: 250M score updates/day ~ 2,900 QPS | Solution: Redis Sorted Set (ZADD, ZREVRANGE, ZREVRANK -- all O(log N), sub-ms) | Why Redis: purpose-built data structure, correct complexity, single instance handles millions | Periodic: separate sorted set per period (leaderboard:2024-01-15) | Scaling: single Redis sufficient for most cases; shard by score range for billions

Payment System

Scale: 12 TPS (LOW throughput, HIGH reliability) | Core: idempotency key per payment (non-negotiable) | Flow: receive -> PENDING -> call PSP -> SUCCESS/FAILED + webhook confirmation | Ledger: double-entry (every tx = debit + credit, SUM(debits) = SUM(credits)) | Reconciliation: nightly batch compare internal ledger vs PSP settlement | Failures: retry with same idempotency key, event sourcing for replay

Digital Wallet

Core challenge: distributed transactions (debit A + credit B must be atomic) | Approach 1: single DB with ACID (simple, limited scale) | Approach 2: event sourcing (immutable events, balance = sum, perfect audit) | Approach 3: CQRS + event sourcing (write: append events, read: materialized balance) | Cross-shard: Saga (debit then credit, compensate on failure) or TCC (try-confirm/cancel) | Key: balance derived from transaction history, not stored independently

Stock Exchange

Scale: microsecond latency, millions of orders/day | Architecture: Gateway -> Sequencer -> Matching Engine -> Execution Reports | Sequencer: single-threaded, monotonic sequence numbers, deterministic processing | Order book: per-symbol, buy max-heap + sell min-heap, FIFO at each price level | Latency: single-threaded (no locks), pre-allocated memory (no GC), kernel bypass (DPDK) | Recovery: replay from sequencer log (deterministic = same sequence -> same state)

---

Cross-Cutting Themes

1. Start simple, scale incrementally -- every system starts as monolith
2. Decouple with queues -- async processing in nearly every design
3. Cache is king -- Redis/Memcached in every high-read system
4. Consistent hashing everywhere -- data distribution's universal tool
5. Monitor everything -- logging, metrics, alerting in every design
6. Trade-offs are the answer -- never one right architecture
7. Numbers matter -- estimation validates or kills a design choice
8. Data model drives architecture -- get it right first
9. Event sourcing appears everywhere -- payments, wallets, exchanges
10. Exactly-once via idempotency -- idempotency keys + deduplication
11. Right data structure wins -- Redis Sorted Set, append-only log, heap