db-16 — Broader Ideas

Where the primitives in this lab show up in real systems, and what to build on top of them in the rest of the distributed track.

Immediate next labs

  • db-17 — Raft. Reuses the deterministic simulator wholesale. Adds a Role ∈ {Follower, Candidate, Leader}, election timeouts, AppendEntries RPCs, and a commit index. Every step's safety argument ultimately reduces to "this state could not have been reached without a quorum acknowledgement", which is a happens-before statement on the log — exactly what vector clocks make precise.
  • db-18 — Paxos. Same harness, different message types (Prepare/Promise/Accept/Accepted). Paxos's invariants are notoriously hard to reason about by hand; a deterministic simulator that can replay a counterexample seed is the difference between "I think it's correct" and "I have evidence".
  • db-19 — ZAB. Adds a strict total order on broadcasts and a recovery phase. The Lamport clock generalizes to the ZAB epoch + counter pair.
  • db-20 — Distributed KV. Wraps a quorum-replicated key-value store around a chosen consensus engine. Now the simulator's "payload" is a client command, and the event log is auditable per-replica state.

How this lab's pieces map to real systems

  • Lamport clocks are the kernel of Kafka offsets, Spanner's TrueTime (kind of — Spanner adds a real-time uncertainty interval but the underlying scalar is a Lamport-like ID), and Cassandra's per-cell write timestamps.
  • Vector clocks are the kernel of Amazon Dynamo's conflict detection, Riak's siblings, and the CRDT literature's "stable causal delivery" layer.
  • Deterministic discrete-event simulation is how FoundationDB developed and continues to harden its storage and replication code (Will Wilson's Testing Distributed Systems with Deterministic Simulation talk at Strange Loop 2014 is the canonical reference). It is also how TigerBeetle, Polar Signals, and Antithesis test their production code paths.
  • The (time, sender, seq) heap tie-break is the same trick used by every event-loop sim from simpy to game-engine fixed-timestep loops.

Performance experiments worth running later

  • Crank --nodes and --rounds and plot wall time vs. event count for each language. With the current canonical serializer this should be linear in events; any quadratic growth means the wire format or the heap is doing something dumb.
  • Replace the unicast splitmix64 destination with a broadcast and measure the explosion in VC entries per receive (each broadcast forces every other node's VC to grow by one entry).
  • Try a HashMap-based VC in Rust and observe cross_test.sh failing. This is the cheapest possible lesson on why deterministic iteration order matters; do it once and you will never forget it.

What "production-quality" would require beyond this lab

  • A real network layer (TCP or QUIC), with retries, timeouts, and application-level acks rather than the simulator's deliver-and-forget.
  • Lossy / reordering channels and partition primitives. db-17 will add partitions as a Network::partition(a, b) toggle; this lab deliberately omits them so the determinism story is small.
  • Persistent storage for clocks (so a crash-restart doesn't replay Lamport from 0). The Raft lab in db-17 will need this; the WAL we built in db-03 is the obvious substrate.
  • Compact vector clocks (interval tree clocks, dotted version vectors) for systems with > thousands of nodes; the naive map-based VC here becomes a bandwidth problem at that scale.

None of these change the shape of the primitives — they make the same primitives faster, leaner, and tolerant of real-world failures.