system-design

Foundational Papers

Behind every concept in this repo is a paper where someone first worked it out. You don’t need to read papers to pass interviews — but reading a few of the classics gives you a depth and confidence nothing else does, and demystifies the systems you’ve been studying. This chapter is a curated, approachable path into the seminal papers, with what each one gave the world.

Time to read: ~11 minutes; the papers themselves are a deeper journey

Do you need to read papers?

🚨 No — not for interviews. This repo and practice are enough. But reading a handful of these:

Deepens understanding far beyond a summary — you see why the design is the way it is.
Impresses in senior interviews — casually and correctly referencing Dynamo or Raft signals real depth.
Is genuinely enjoyable once you have the background this repo gives you.

How to read a paper approachably: don’t grind every equation. Read the abstract, intro, and the design/ architecture sections; skim proofs. Use Adrian Colyer’s The Morning Paper summaries and lecture notes (MIT 6.824 covers many of these) to ease in. 🚨 Read the paper for the idea, not every detail.

The essential papers, by theme

Distributed data stores

🚨 Dynamo (Amazon, 2007) — “Dynamo: Amazon’s Highly Available Key-value Store.” The blueprint for AP, eventually-consistent, highly-available stores: consistent hashing, vector clocks, hinted handoff, read repair, quorums. Directly behind the KV store case study and Cassandra/Riak/DynamoDB. The most interview-relevant paper.
Bigtable (Google, 2006) — the wide-column store model (Cassandra/HBase lineage); how to store petabytes in a sorted, distributed map.
Spanner (Google, 2012) — globally-distributed, strongly-consistent database with synchronized clocks (TrueTime). How you get global consistency at scale.
The Google File System (2003) and MapReduce (2004) — the papers that launched big data; distributed storage and batch processing.

Consensus & coordination

🚨 Raft (2014) — “In Search of an Understandable Consensus Algorithm.” Consensus you can actually understand (leader election, log replication). Behind etcd/Consul. Read this over Paxos first. Pairs with consensus.
Paxos (“Paxos Made Simple,” Lamport, 2001) — the original consensus algorithm; famously subtle. Read after Raft for the classic.
“Time, Clocks, and the Ordering of Events” (Lamport, 1978) — 🚨 the foundational paper on logical clocks and ordering in distributed systems. Short, profound, and behind everything in time and clocks.
The Chubby Lock Service (Google, 2006) — coordination/locking (ZooKeeper’s inspiration).

Streaming & logs

Kafka (LinkedIn, 2011) and “The Log” (Jay Kreps) — 🚨 the log as a unifying abstraction for data systems. “The Log” essay is essential, accessible reading behind the message queue case study.
The Dataflow Model (Google, 2015) — event-time, windows, watermarks for stream processing — behind the ad click aggregator.

Theory & consistency

The CAP theorem (Brewer’s conjecture; Gilbert & Lynch proof) — the foundational impossibility result. See CAP & PACELC.
“Harvest, Yield, and Scalable Tolerant Systems” (Fox & Brewer) — a nuanced take on partial results and availability.

Data structures & scale

Consistent Hashing (Karger et al., 1997) — the paper behind consistent hashing.
Bloom filters (Bloom, 1970) — the classic probabilistic structure (probabilistic data structures).
HyperLogLog — approximate cardinality at scale.

A suggested path (if you want to start)

flowchart LR
    A["The Log" essay<br/>accessible] --> B[Raft<br/>understandable consensus]
    B --> C[Dynamo<br/>the interview classic]
    C --> D[Lamport clocks<br/>short & profound]
    D --> E[Pick by interest:<br/>Spanner, Bigtable,<br/>Dataflow, GFS...]

🚨 Start with the two most approachable and interview-relevant: Jay Kreps’s “The Log” essay and the Raft paper. Then Dynamo (the most interview-cited). After those, follow your interest. Use MIT 6.824 and The Morning Paper as guides so you’re never reading alone.

🛠️ Try it

1. Read “The Log” essay this week. It’s accessible, essay-style (not a formal paper), and it will change how you think about data systems — then reread the message queue case study with fresh eyes.

2. Read the Raft paper with the visualization. Pair the paper with the interactive Raft visualization (raft.github.io) and MIT 6.824’s lecture — consensus finally clicks when you watch it happen.

3. Read Dynamo and map it to the case study. Read the Dynamo paper, then line each mechanism (consistent hashing, quorums, hinted handoff, vector clocks) up against the KV store case study. You’ll understand both far better.