Warmup Guide — Production Distributed Systems

Zero-to-expert primer for Phase 07: consensus (Raft) from first principles, hash-based partitioning as used by Kafka, and multi-module build engineering — the systems substrate beneath every Apache data project.

Table of Contents

Chapter 1: Why Distributed — and What It Costs

From zero: one machine bounds you in capacity (disk/RAM), throughput (CPU/NIC), and availability (it will fail). Distribution buys past all three — and the price is that the network is now inside your system: messages are lost, delayed, reordered, and duplicated; clocks disagree; and — the deep one — you cannot distinguish a crashed node from a slow one (the FLP-flavored fact behind every timeout you'll ever tune).

Two design consequences run through everything in this phase:

  • Redundancy requires agreement: copies that can diverge need a protocol to decide whose version is true → consensus (Ch. 2–4).
  • Scale requires partitioning: data/work split across nodes needs a stable, balanced assignment function → hashing (Ch. 5–6).

Chapter 2: The Consensus Problem

The statement: N nodes must agree on a sequence of values (a replicated log) such that — despite crashes and partitions — agreed entries are never lost or reordered (safety), and the system keeps making progress whenever a majority is alive (liveness).

Why a majority (quorum)? Any two majorities of N intersect in ≥1 node. That single intersection node is the carrier of truth between configurations — it's why ⌈(N+1)/2⌉ acknowledgments make a decision durable, and why a 5-node cluster tolerates 2 failures. Memorize the intersection argument; every quorum system reduces to it.

Why it's hard: with asynchronous networks, any protocol can be stalled by adversarial timing (FLP impossibility) — so real systems buy liveness with randomized timeouts and buy safety unconditionally. Paxos solved it first and is notoriously hard to implement; Raft (2014) re-derived equivalent guarantees optimized for understandability — which is why etcd, Kafka's KRaft, and your Lab 01 all speak Raft.

Chapter 3: Raft — Leader Election from Zero

Raft decomposes consensus into leader election + log replication, with a strong leader through whom all writes flow.

The moving parts: every node is follower / candidate / leader; time divides into terms (monotonic integers — Raft's logical clock). Each node persists currentTerm, votedFor, and its log.

The election algorithm (exactly what Lab 01 implements and tests):

  1. Followers expect heartbeats from a leader. No heartbeat within a randomized election timeout (e.g. 150–300 ms) → become candidate: increment term, vote for self, send RequestVote(term, lastLogIndex, lastLogTerm) to all.
  2. A node grants at most one vote per term (persisted — survives crashes), and only to candidates whose log is at least as up-to-date (compare last term, then last index). This election restriction is what guarantees a new leader already holds every committed entry.
  3. Majority of votes → leader; begin heartbeats. Tie/split vote → timeout expires → next term, retry. Randomized timeouts make repeated splits exponentially unlikely.
  4. Any message bearing a higher term instantly demotes a leader/candidate to follower — stale leaders can exist briefly but can't do anything: replication requires follower acks, and followers reject lower terms.

Why no two leaders per term: one-vote-per-term + majority needed → two leaders in one term would require two disjoint majorities — impossible by the intersection argument. Two leaders in different terms: the older one's appends are rejected; it steps down on first contact with the higher term.

Chapter 4: Raft — Log Replication and the Commit Rule

(Lab 01 focuses on election; replication context so the design makes sense.)

  • The leader appends client commands to its log and sends AppendEntries(prevLogIndex, prevLogTerm, entries, leaderCommit). Followers reject if their log doesn't match at prevLogIndex/Term — the consistency check that forces divergent follower logs to back up and be overwritten to match the leader's.
  • An entry is committed once a majority holds it — but only for entries of the leader's current term (the Figure-8 subtlety: an old-term entry on a majority can still be overwritten; committing a current-term entry on top commits everything beneath it). This is the most-asked deep Raft question; have the scenario ready.
  • KRaft (Kafka), etcd, and TiKV are production Rafts; reading any of their vote-handling code after this lab is the recommended follow-up.

Chapter 5: Partitioning — Spreading Data with Hashing

The problem: assign keys (or records) to N partitions, balanced and deterministic.

  • The baseline (Kafka's default, Lab 02): partition = murmur2(key) % N (sign-bit masked). Hash quality matters: a weak hash clusters real-world keys (sequential IDs, common prefixes) onto hot partitions, capping throughput at one broker. Murmur2 is fast, non-cryptographic, and statistically uniform — Lab 02 verifies uniformity with a chi-square test over realistic key distributions, the statistically honest way to evaluate a partitioner (eyeballing histograms lies).
  • Keyless records: round-robin balances perfectly but kills batching; Kafka's sticky partitioner fills one partition's batch then moves on — same long-run balance, far better throughput. Batching-vs-balance is the design tension to remember.
  • The modulo trap: change N and hash % N reassigns ~everything — key→partition affinity (ordering! local state!) breaks. Consistent hashing (ring) or rendezvous hashing moves only ~1/N of keys — that's why caches and Cassandra-style stores use them. Kafka deliberately doesn't: partition count is meant to be fixed per topic, and ordering-per-key is the contract — increasing partitions on a keyed topic is a breaking change you must plan like a migration (Phase 11 thinking).
  • Skew is the practical killer: one celebrity key = one hot partition no algorithm fixes. Mitigations: composite keys (key+salt with consumer-side merge), local aggregation before the shuffle (Spark's map-side combine), or two-phase aggregation.

Chapter 6: Consumer Assignment and Rebalancing

The other half of partitioning: assigning partitions to consumers in a group.

  • Range (per-topic contiguous blocks): aligns co-partitioned topics (needed for joins) but skews when consumers don't divide partitions evenly across many topics.
  • Round-robin: even spread, breaks co-partition alignment.
  • Sticky / cooperative-sticky (modern default): minimize movement on rebalance — every moved partition aborts in-flight work and cold-starts state. Cooperative rebalancing migrates incrementally instead of stop-the-world.
  • The general principle (it recurs from Kafka to YARN to storage shards): assignment quality = balance × stability × locality, and the three trade against each other. Lab 02's RangeAssignor implementation makes the skew case concrete.

Chapter 7: Multi-Module Builds — Engineering the Repo Like a System

Why a build lab sits in a distributed-systems phase: Apache projects are multi-module systems, and their build graph is the first distributed system you touch (Phase 02 navigated it; here you construct one).

  • Module = dependency-graph node: queue-api (interfaces, no deps) ← queue-core (implementation) ← queue-app (wiring + integration tests). The discipline: api modules depend on nothing, implementations depend on api, applications depend on both — cycles are a design smell Maven simply refuses.
  • The reactor computes topological build order; -pl module -am (with upstream) and -amd (with downstream) are the daily flags. Version alignment via the parent POM's dependencyManagement — one place where versions live, modules inherit.
  • Why split at all: independent compilation/test cycles, enforceable layering (api can't accidentally reach into impl), separate artifact publication (clients depend on queue-api only — a compatibility boundary, Phase 04's surface made physical), and parallel CI.
  • CI shape (the lab's ci.yml): build once, test per module, cache the local repo keyed on the POMs — the 80% of build-engineering value in 20 lines.

Lab Walkthrough Guidance

Order: Lab 01 (Raft) → Lab 02 (Kafka partitioning) → Lab 03 (multi-module).

  • Lab 01: read RaftNode's state transitions against Chapter 3's algorithm step by step; run the tests and make them fail informatively — comment out the one-vote-per-term persistence and watch which test catches the double-vote; do the same for the up-to-date check. Negative experiments are how the safety argument becomes yours. Extension: add the AppendEntries consistency check.
  • Lab 02: verify murmur2 against known vectors; run the chi-square uniformity test on (a) random keys, (b) sequential IDs, (c) prefixed keys — compare against a naive hashCode() partitioner and watch it fail (b). Then implement RangeAssignor and construct the skew case from Chapter 6.
  • Lab 03: build the three-module project; deliberately introduce an api→core dependency and read Maven's cycle error; move a version into the parent's dependencyManagement; run -pl queue-core -am and explain what rebuilt and why.

Success Criteria

You are ready for Phase 08 when you can, from memory:

  1. State the quorum-intersection argument and apply it (why 5 nodes tolerate 2 failures).
  2. Walk Raft's election including both safety mechanisms (one vote/term persisted; up-to-date restriction) and the role of randomized timeouts.
  3. Explain why a leader can't commit old-term entries by counting replicas (Figure 8).
  4. Defend murmur2-mod-N, name the modulo trap, and say when consistent hashing is and isn't the answer.
  5. Compare range/round-robin/sticky assignment on balance × stability × locality.
  6. Draw the api/core/app dependency discipline and what each boundary buys.

Interview Q&A

Q: Design leader election without Raft/ZK — what do you need at minimum? Re-derive the essentials: terms (a monotonic tiebreaker), persisted single vote per term (else double-voting under crashes), majority quorum (intersection = uniqueness), randomized timeouts (liveness under symmetry), and a rule that winners hold all committed state (else data loss on election) — at which point you've re-invented Raft's election, which is the answer: "the minimum is Raft's election, and here's why each piece is load-bearing."

Q: A Kafka topic shows one partition at 10× the traffic. Walk through it. First distinguish key skew from partitioner bug: sample keys per partition. Celebrity key → composite key (salt + consumer merge) or local pre-aggregation; bad hash (custom partitioner, hashCode() on sequential IDs) → fix the hash, chi-square it; recently increased partition count → old keys' affinity broke and the imbalance is transitional. Never "add partitions" reflexively — on a keyed topic that's a breaking change to ordering and state (the modulo trap).

Q: Why does Raft persist votedFor to disk before responding? Crash-recovery safety: grant a vote, crash, restart without the record → grant again in the same term → two leaders become possible, violating the intersection argument. The fsync-before-reply on currentTerm/votedFor/log entries is the price of safety under crashes; batching/group-commit is the performance answer, never skipping the write.

References