Section 5 of 7 · Systems Foundations
Distributed State, Replication & Streams
Once state crosses machines, time, failure and delivery guarantees become part of the data model. This section builds precise vocabulary and small simulations without turning the foundation into a full consensus course.
8 units 21 topics 0/8
Units
8 in this section
- 5.1 Partial failure, clocks and event ordering explain · derive5 h
- 5.2 Replication, quorums and consensus vocabulary explain · derive4 h
- 5.3 Consistency models and conflict resolution explain4 h
- 5.4 Partitioning, hot keys, rebalancing and stale writers explain3 h
- 5.5 Durable logs, delivery guarantees and idempotent consumers explain · implement4 h
- 5.6 Consumer lag, watermarks and state rebuild explain · implement5 h
- 5.7 Distributed histories and deterministic failure simulation implement · measure6 h
- 5.8 MapReduce execution and data-local scheduling explain2 h
Before moving on
Checkpoint
Run a deterministic replication or durable-stream simulation through lag, duplicate, stale read, ownership change, replay and node loss. Defend the exact consistency, durability and delivery contract with one history that it permits and one it rejects.
Deliberately out of scope
Leave for later
- Full Raft, Paxos or consensus implementation
- Sharded replicated databases
- Production stream-processing frameworks and cross-region operation
Resources for this section
Shared by every unit above
- Designing Data-Intensive Applications, 2nd edition - distributed data path Read the selected chapters on replication, partitioning, distributed-system trouble, consistency and consensus, batch processing and stream processing. For each guarantee, write its assumptions, a confirming history and one counterexample outside the boundary.
- Gossip Glomers - Echo, Unique ID and Broadcast Complete Challenge 1 Echo, Challenge 2 Unique ID Generation and Challenge 3a Single-Node Broadcast. Add 3b Multi-Node Broadcast only after writing the delivery, duplicate and partition assumptions. Preserve protocol histories rather than relying on a success banner.
- MIT 6.5840 - MapReduce, RPC and consistency bridge Use the introductory MapReduce, RPC, GFS and consistency lectures after the local RPC and store gates. The MapReduce lab is optional. Do not begin Raft or sharded KV as foundation work.
- Apache Kafka documentation - design Read Persistence, The Consumer (Consumer Position), Message Delivery Semantics, Using Transactions, Replication and Log Compaction for a concrete log: offsets, consumer positions, the at-most-once, at-least-once and exactly-once boundaries, in-sync replicas and compaction guarantees. Map each guarantee onto your own log before trusting it.
- Building Distributed Systems from Scratch - one challenge path Choose one messaging, durable-log or partitioning challenge that matches a failed checkpoint. State the model, failures and evidence independently because interactive grading behavior has not been verified.
- AlgoMaster System Design - distributed fundamentals slice Use Database Replication, Consistency Models, Logical Clocks, Vector Clocks, Network Partitions, Split Brain Problem, Leader Election, Database Partitioning, Consistent Hashing, Delivery Semantics, Dead Letter Queues, Idempotency, Two-Phase Commit (2PC), Outbox Pattern and Streaming Engines as bounded review after DDIA. Attempt only the exercise that matches your implemented history, then challenge its assumptions with a node-loss, delay or duplicate case.
Apply the section
Mini-project · Deterministic replication and stream-replay simulation over the service log (14 to 20 h)
Simulate the service log replicated and consumed in one process on logical ticks, with ownership transfer, fencing and a replaying consumer group. Drive it through lag, loss and replay, then defend a one-page acknowledgement and consistency contract.
Steps
- Write
kv/sim/scheduler.pyas an event loop over integer ticks with stable tie-breaks and one owned random source, where every fault comes from the schedule and each run writes a client history that repeats exactly. - Model leader and follower replicas with acknowledged modes and configuration IDs on every operation, reproduce failover loss and stale-membership reads, then show persisted majority with coordinated membership keeps acknowledged writes.
- Write
kv/sim/check.pyas a small-history linearizability checker that treats timeouts as possibly applied, classify each history produced, and reproduce last-write-wins loss beside an application merge that keeps removals removed. - Shard keys over fixed partitions, move a few shards and count per-node load under a hot key, then transfer ownership with a persisted fencing token that rejects delayed writes from the old owner, keeping the overwrite that happens without the check as a regression.
- Replay each replica log through a consumer group that checkpoints progress atomically with its effects, crash it at each boundary against a sequential oracle, and add watermarks, bounded retries with dead letters, snapshots, tombstone expiry and external effects with their own keys.
- Run one scenario through lag, duplication, stale reads, ownership change, replay and node loss, defend the contract with one permitted and one rejected history checked by the checker, and optionally trace a batch word count with a failed attempt kept private.
Deliverables
kv/sim/with scheduler, replicas, fencing, consumer and stream state, replaying every scenario exactly.kv/sim/check.pywith linearizability and session checks plus fixtures, and the crash-boundary and stream-state tables.- Scenario histories with the one-page contract and its permitted and rejected history.
Checks
- rubric · Self-grade with the rubric below
Rubric
| Criterion | Pass | Strong |
|---|---|---|
| Determinism and checking | Repeated runs give identical histories from the schedule alone, and the checker accepts and rejects its fixtures. | A randomly found failure is cut down to a short schedule kept as a regression. |
| Replication and ownership | Failover loss and stale reads are reproduced with configuration IDs, and the repaired mode keeps acknowledged writes while fencing rejects stale owners. | The write-up separates quorum intersection, persisted acknowledgement and membership coordination. |
| Replay and contract | Only the atomic consumer matches the oracle at every boundary, and the contract pairs each claim with its permitted and rejected history. | Dead letters and tombstone expiry each state the completeness claim they change. |
Feeds into: Capstone service slice: the offset invariant and deterministic faults. The dossier keeps the distributed history with its two checked cases.