pa-06 — The Hitchhiker's Guide to Partitioning & Consistency

Companion to CONCEPTS.md, with the runnable code in src/go/partition/. Two distributed-systems fundamentals the JD names, made measurable.

bash scripts/verify.sh runs the demo:

key movement when removing 1 of 3 nodes:
  consistent hashing: 32% of keys moved
  mod-N hashing:      67% of keys moved  <- reshuffles almost everything
quorum overlap (N=3): R+W>N => read sees latest write
  W=2 R=2  overlap=true   read=v2  STRONG
  W=1 R=1  overlap=false  read=v1  STALE

Two numbers and a table that encode the whole lab.

1. Consistent hashing vs mod-N (ring.go)

The headline distributed-systems result every architect should be able to derive: how much data moves when the cluster changes size.

ModHashGet is the naive node = sortedNodes[hash%N]. It's perfectly even — until N changes, when the modulus changes and almost every key remaps. TestModHashMovesEverything measures ~67% moved going 3→2 nodes. That's a full data shuffle = an outage-grade migration on every scaling event.

Ring places each node at vnodes positions on a hash circle; Get finds the next position clockwise. Removing a node deletes its positions, so only the keys that pointed there move — to the next node clockwise. TestConsistentHashingMinimalMovement measures ~32% (≈ the departed node's 1/3 share) and TestConsistentHashingBalance confirms 200 vnodes keep each node within ~25% of the ideal load. The vnodes are what make it both balanced (no lumpy arcs) and smooth (a departure spreads across all survivors, not dumped on one neighbor).

This is the same minimal-movement-under-membership-change problem as Kafka consumer rebalancing (pa-04) and gateway subsetting (gw-04) — recognizing the shared pattern is the synthesis an architect brings.

2. Quorums and R+W>N (quorum.go)

Replication gives fault tolerance; quorums give consistency. With N replicas, you write W and read R. Cluster.Write(W, version) updates W replicas; ReadWorstCase(R) reads the R replicas least likely to have the write — the adversarial staleness case. The result:

  • TestQuorumStrongWhenOverlap: W=2,R=2,N=3 → R+W>N → the read sees v2 (strong / read-your-writes).
  • TestQuorumStaleWhenNoOverlap: W=1,R=1,N=3 → R+W≤N → the read can see v1 (stale / eventual).

The proof is pigeonhole: if W+R>N, the write set and read set can't be disjoint within N replicas, so they share at least one replica — and it holds the latest write. This single inequality is the dial between strong and eventual consistency, exposed directly by Dynamo-style systems (Cassandra, DynamoDB) as tunable per query.

3. The architect's decisions

The code is small; the decisions are the seniority:

  • Partition key — decides skew (hot shards) and what's co-located. Same weight as pa-04's key choice.
  • Partition strategy — range (scans, hotspots), hash (even, bad reshard), consistent hashing (elastic). The reshard cost is the deciding factor.
  • Consistency per dataset — the weakest model that's still correct. Strong for balances (W=R=quorum), eventual for counters (W=1,R=1). Not "strong everywhere."
  • CAP/PACELC posture — under a partition, C or A; otherwise, L or C. Consistency costs latency always (a strong read waits for a quorum), so spend it deliberately.
  • Convergence — eventual systems need read-repair, anti-entropy, and hinted handoff to actually converge; quorums alone don't heal stale replicas.

4. Hands-on

cd src/go
bash ../scripts/verify.sh
go run ./cmd/partsim

Vary the vnode count and watch balance/movement change; vary N/W/R and watch the overlap flip.

5. Exercises

  1. Vnode sweep: plot load imbalance (max/min per node) vs vnode count (1, 10, 100, 1000) and find where it flattens.
  2. Weighted nodes: give a bigger node more vnodes and show it takes proportionally more load (heterogeneous clusters).
  3. Replication on the ring: store each key on the next R distinct physical nodes clockwise (Dynamo-style preference lists), then layer the W/R quorum on top.
  4. Read-repair: when ReadWorstCase sees a newer version on some replica, write it back to the stale ones; show convergence.
  5. CAP under partition: split the replicas into two groups and show a quorum write fails in the minority side (choosing C over A).