system-design

name	system-design
description	Knowledge base from "System Design Interview - An Insider's Guide (Vol 1 & 2)" by Alex Xu. Use when applying Alex Xu's frameworks for the 4-step interview method, back-of-envelope estimation, scaling, consistency/CAP, sharding, caching, fanout, queues, or designing systems (rate limiter, KV store, news feed, chat, payment, etc.), studying the book, or referencing its concepts.

System Design Interview — An Insider's Guide (Vol 1 & 2)

Author: Alex Xu (Vol 2 with Sahn Lam) | Chapters: 28 | Generated: 2026-06-22

How to Use This Skill

• Without arguments — load core frameworks below for reference
• With a topic — ask about rate limiting, fanout, consistent hashing, exactly-once; I find and read the relevant chapter
• With a chapter — ask for ch11; I load that specific chapter file
• Browse — ask "what chapters do you have?" for the full index

When you ask about a topic not in Core Frameworks below, I read the relevant chapter file (Topic Index → chapter) before answering.

---

Core Frameworks & Mental Models

The 4-Step Interview Framework (Ch3) — the spine of every design.

1. Understand problem & scope (3–10 min): ask clarifying questions, pin down functional + non-functional requirements, scale. Never design before scoping.
2. Propose high-level design (10–15 min): box diagram, get interviewer buy-in, do back-of-envelope estimation.
3. Deep dive (10–25 min): pick the components that matter, explore bottlenecks, edge cases, trade-offs.
4. Wrap up (3–5 min): recap, failure modes, monitoring, what you'd do with more time.

Back-of-Envelope Estimation (Ch2). Drive the design with numbers. QPS = DAU × actions/user/day ÷ 86,400; peak ≈ 2× average. Memorize Jeff Dean latency numbers (memory 100ns, SSD 150µs, disk seek 10ms, intra-DC RTT 500µs, cross-region 150ms) and availability nines (99.9% = 8.8h/yr down, 99.99% = 52min/yr). Label units; round liberally; process > precision.

Scaling spine (Ch1). Stateless web tier → horizontal scale behind a load balancer. Master-slave DB replication for read scale. Cache read-heavy data (LRU). CDN for static. Shard when one DB isn't enough. Message queues to decouple + async. Multi-DC + GeoDNS for geo & failover.

CAP + Quorum (Ch6). Partition tolerance is mandatory → choose CP (consistency) or AP (availability). Tune with quorum: W + R > N ⇒ strong consistency (common N=3, W=R=2). Detect conflicts with vector clocks, sync replicas with Merkle trees, detect failure via gossip, survive failures with sloppy quorum + hinted handoff.

Consistent Hashing + Virtual Nodes (Ch5). Hash servers & keys onto a ring; a key is owned by the next server clockwise. Adding/removing a node only remaps keys in one segment (not all, unlike modulo hashing). Virtual nodes per server → even load + capacity-weighting. Recurs in Ch1, Ch17, Ch20, Ch24.

Fanout: write vs read (Ch11). Fanout-on-write (push to followers' caches) = fast reads, expensive for celebrities. Fanout-on-read (pull at read time) = cheap writes, slow reads. Hybrid: push for normal users, pull for high-fanout celebrities. The general "precompute vs compute-on-demand" trade-off (also Ch13, Ch14, Ch18).

Rate limiting algorithms (Ch4). Token Bucket (bursty, most common) · Leaking Bucket (smooth, FIFO) · Fixed Window (simple, edge-spike bug) · Sliding Window Log (accurate, memory-heavy) · Sliding Window Counter (smoothed hybrid). Store counters in Redis.

Money & inventory correctness (Ch21, Ch22, Ch26, Ch27). Idempotency keys prevent double-charge/double-book. Exactly-once (dedup via offset + reconciliation) for billing. Double-entry ledger for payments. Event sourcing + CQRS + Saga/TC-C for distributed wallet transactions (avoid 2PC at scale).

Queues & streaming (Ch19, Ch20, Ch21). Pull model (consumer-paced) over push. Partitions for parallelism + per-partition order; consumer groups; offsets; WAL durability; ISR for replication. Event time ≠ processing time → watermarks for late events; tumbling/sliding windows.

---

Chapter Index

#	Title	Key Frameworks
ch01	Scale Zero → Millions	horizontal scaling, replication, sharding, CDN
ch02	Back-of-Envelope Estimation	QPS/storage math, latency numbers, nines
ch03	Interview Framework	4-step framework
ch04	Rate Limiter	token/leaking bucket, sliding window
ch05	Consistent Hashing	hash ring, virtual nodes
ch06	Key-Value Store	CAP, quorum, vector clock, Merkle, gossip
ch07	Unique ID Generator	Snowflake bit-layout
ch08	URL Shortener	Base62, hash + Bloom filter
ch09	Web Crawler	BFS, URL frontier, politeness
ch10	Notification System	APNS/FCM, queue decoupling, retry
ch11	News Feed	fanout write/read hybrid
ch12	Chat System	WebSocket, presence, service discovery
ch13	Search Autocomplete	trie + cached top-k
ch14	YouTube	DAG transcoding, GOP, CDN tiering
ch15	Google Drive	block storage, delta sync
ch16	Proximity Service	geohash, quadtree, Google S2
ch17	Nearby Friends	Redis pub/sub fanout, geohash channels
ch18	Google Maps	A*, map tiling, routing tiles
ch19	Message Queue	partitions, WAL, ISR, pull model
ch20	Metrics & Alerting	time-series DB, pull/push, downsampling
ch21	Ad Click Aggregation	lambda arch, tumbling window, exactly-once
ch22	Hotel Reservation	optimistic locking, idempotency, overbooking
ch23	Distributed Email	SMTP/IMAP, LSM tree, metadata DB
ch24	S3 Object Storage	erasure coding, WAL, consistent hashing
ch25	Gaming Leaderboard	Redis sorted set, skip list
ch26	Payment System	double-entry ledger, idempotency, PSP
ch27	Digital Wallet	event sourcing, CQRS, saga, TC-C
ch28	Stock Exchange	matching engine, FIX, event sourcing

Topic Index

• A / pathfinding* → ch18
• Availability / nines → ch02, ch06
• Base62 encoding → ch08
• Bloom filter → ch06, ch08
• CAP theorem → ch06
• CDN → ch01, ch14, ch18
• Caching → ch01, ch08, ch11, ch13
• Consistent hashing → ch05, ch01, ch17, ch24
• CQRS / event sourcing → ch27, ch28
• Delta sync / block storage → ch15
• Erasure coding → ch24
• Estimation (QPS/storage) → ch02
• Exactly-once / delivery semantics → ch19, ch21
• Fanout (write/read/hybrid) → ch11, ch17
• Geospatial (geohash/quadtree/S2) → ch16, ch17, ch18
• Gossip / failure detection → ch06
• Idempotency → ch21, ch22, ch26, ch27
• Interview framework (4-step) → ch03
• Latency numbers → ch02
• Locking (optimistic/pessimistic) → ch22
• LSM tree / SSTable → ch06, ch23
• Matching engine / order book → ch28
• Message queue / partitions / WAL → ch19, ch01, ch10
• Payment / double-entry ledger → ch26, ch27
• Quorum (W+R>N) → ch06
• Rate limiting → ch04
• Redis sorted set / skip list → ch25
• Replication (master-slave) → ch01, ch06, ch19
• Saga / TC-C / 2PC → ch27
• Sharding → ch01, ch06, ch22
• Snowflake / unique ID → ch07
• Stateless web tier → ch01
• Time-series / downsampling → ch20
• Transcoding / DAG / GOP → ch14
• Trie / autocomplete → ch13
• Vector clock → ch06
• WebSocket / presence → ch12, ch17
• Windowing (tumbling/sliding/watermark) → ch21, ch19

Supporting Files

• glossary.md — all key terms with definitions
• patterns.md — techniques & design patterns with trade-offs
• cheatsheet.md — decision rules & quick-reference tables
• visualizations.md — when/what to render as interactive Artifact explainers for human study

---

Interactive Visualizations (human study)

When a human is studying an animatable concept — not mid-interview-design or estimation — I can build a self-contained interactive explainer via the Artifact tool (e.g. tokens dripping from a rate-limiter bucket, keys remapping on a consistent-hashing ring). I offer this for catalog concepts and generate on opt-in; an explicit "visualize this" works for any animatable concept. See visualizations.md for the trigger rules, concept catalog, and build spec.

---

Scope & Limits

Covers the book's content only — interview-oriented designs and the reasoning behind them. For production implementation in a real codebase, combine with project-specific tools and current vendor docs. For topics beyond these 28 chapters, ask directly.