Analysis — db-23 capstone

Goal restated

Build the smallest possible thing that is honestly a replicated KV database, port it to three languages with byte-identical state, and prove convergence under a deterministic failure scenario.

Design choices

Why synchronous in-process replication?

A real Raft cluster uses goroutines/threads, network RPC, election timeouts, and randomized jitter — all of which are sources of nondeterminism. For a capstone whose entire point is cross-language byte-equality, that would defeat itself.

So instead the "network" is a function call. The Cluster's submit synchronously: appends on the leader, appends on every live follower, and commits if quorum reached. This is provably equivalent to a Raft cluster running in lockstep with no message reordering.

Why majority = 2?

3 nodes, so a quorum is 2. The leader counts itself. As long as either follower is up, the cluster commits. When follower 1 is marked down, follower 2 + leader still form a quorum. If both followers were down simultaneously, writes would block — but our fault schedule never does that, so submit never wedges.

Why a single deterministic leader?

Leader election adds randomness (timeouts) and protocol surface (terms, RequestVote). We pin node 0 as the perpetual leader. The lab still shows the replication half of Raft faithfully; election is left as a follow-on (see broader-ideas.md).

Why three RNG draws per op, including for Del?

If we drew fewer words on Del branches, the RNG stream would advance differently for runs that happen to produce more Dels, and frozen hashes would depend on the kind distribution. By always consuming exactly three words we ensure the stream depends only on seed and ops, not on what kinds happened.

Why drop last_applied from the wire format?

After the final catch_up (which runs unconditionally if follower 1 ended down), every node satisfies last_applied == commit_index. Including it in the encoding would waste bytes and risk a Rust/Go/C++ divergence if one of them computed it slightly differently mid-run. It is a derived quantity, so we omit it.

Failure model

The only fault we inject is a single follower going down for one quarter of the run:

[0, ops/2)              all three nodes replicate
[ops/2, 3·ops/4)        follower 1 down; quorum is {0, 2}
[3·ops/4, ops)          follower 1 up + caught up; all three replicate
end                     final catch_up if still mid-down (handles ops%4)

This produces a clean, hashable post-condition: every node has the same log, the same commit_index, and the same kv map.

Why two scenarios?

  • normal (no fault) shows the happy path and stresses the commit path under a small workload.
  • fault (with the follower window) stresses replication under partial availability and the catch-up code path. The 2000-op size makes the fault window long enough to accumulate hundreds of entries that the recovering follower must replay.

Both must produce the same hash on all three languages.