System Design
Notes on System Design Interview — An Insider's Guide (Volumes 1 and 2): how to scope a problem, size it, and pick the parts that carry the load.
These notes follow Alex Xu’s System Design Interview — An Insider’s Guide, Volumes 1 and 2.
How an interview runs
Requirements
Pin down the functional requirements (what the system does) and the non-functional ones (latency, availability, consistency, scale) before drawing anything.
Estimates
Size the traffic, storage and bandwidth with back-of-the-envelope numbers, so later choices have a reason.
API and data model
Define the endpoints and the entities they read and write.
High-level design
Draw the request path end to end: clients, load balancers, services, caches, stores and queues.
Deep dives
Take the hardest part (a hot key, fan-out, a consistency guarantee) and work through its tradeoffs.
Foundations
Scaling
From one server to millions of users.
Estimation
Back-of-the-envelope QPS and storage.
Interview Framework
The four steps of the interview.
Core designs
Rate Limiter
Token and leaking buckets, windows.
Consistent Hashing
Hash rings and virtual nodes.
Key-Value Store
Quorums, vector clocks, gossip.
Unique ID Generator
Snowflake and its alternatives.
URL Shortener
Base 62 and redirects.
Web Crawler
The URL frontier and politeness.
Notification System
Push, SMS and email at scale.
News Feed System
Fanout on write and on read.
Chat System
WebSockets and presence.
Search Autocomplete
Tries and top-k prefixes.
YouTube
Upload, transcode, stream.
Google Drive
Block storage and sync.
Advanced designs
Proximity Service
Geohash, quadtrees, S2.
Nearby Friends
Live locations over pub/sub.
Google Maps
Tiles, routing and ETAs.
Distributed Message Queue
Partitions and consumer groups.
Metrics Monitoring
Time series and alerting.
Ad Click Aggregation
Exactly-once stream counts.
Hotel Reservation
Inventory without double booking.
Email Service
Mail storage and search.
S3-like Object Storage
Erasure coding and metadata.
Gaming Leaderboard
Redis sorted sets.
Payment System
Ledgers and reconciliation.
Digital Wallet
Distributed transactions, event sourcing.
Stock Exchange
Order books and sequencers.