pa-06 — Partitioning Strategies & Consistency Models

The Apple JD asks for a "strong understanding of distributed systems fundamentals: consistency models, fault tolerance, and partitioning strategies." This lab makes two of the three concrete and runnable (fault tolerance threads through the whole book): how you split data across nodes (partitioning) and what guarantees you get when you replicate it (consistency / quorums). The third leg — consensus — you already built in db-16…20.

You build consistent hashing (with virtual nodes) and measure that it moves ~1/N of keys on a membership change versus mod-N's near-total reshuffle; and a quorum model that demonstrates the R+W>N overlap rule that separates strong from eventual consistency.

1. What is it?

Partitioning (sharding) splits a dataset across nodes so it scales beyond one machine and one machine's failure. The strategies:

• Range — contiguous key ranges per node (great for range scans; risk of hotspots at the ends).
• Hash — node = hash(key) % N (even spread; kills range scans; catastrophic resharding when N changes — almost every key moves).
• Consistent hashing — nodes and keys placed on a hash ring; a key belongs to the next node clockwise. Adding/removing a node moves only the keys near it (~1/N), not everything. Virtual nodes (many ring positions per physical node) fix balance and smooth movement.

Replication copies each partition to R nodes for fault tolerance. Consistency models describe what a reader may observe:

strong / linearizable: every read sees the latest committed write (as if one copy).
sequential / causal:   reads respect some/causal order, not necessarily real-time.
read-your-writes:      you always see your own writes.
eventual:              replicas converge "eventually"; reads may be stale.

Quorums tune the strong↔eventual dial: with N replicas, write to W, read from R; R+W>N guarantees the read and write sets overlap, so the read sees the latest write (strong). R+W<=N allows staleness (eventual), with higher availability/lower latency.

2. Why does it matter?

• Partitioning decides scalability and hotspots. The partition key (like pa-04's) determines whether load spreads evenly or one shard melts. And the strategy decides what a resharding event costs: mod-N resharding is a full data shuffle (an outage-grade migration); consistent hashing makes it a ~1/N background rebalance. Architects choose this; getting it wrong is a rewrite.

• Consistency is a per-dataset, per-operation decision with real cost. Strong consistency costs latency and availability (CAP/PACELC); eventual buys both back. The architect's job is to pick the weakest model each dataset can tolerate — strong for balances, eventual for a "likes" counter — not to blanket "strong everywhere."

• The R+W>N knob is the practical face of CAP. Dynamo-style systems (Cassandra, Riak, DynamoDB) expose exactly W and R so you tune consistency vs latency/availability per query. Knowing the overlap math cold is a fundamentals checkpoint.

• Minimal-movement-under-change is a recurring architecture theme. Consistent hashing (here), consumer-group rebalancing (pa-04), and gateway subsetting (gw-04) all solve "redistribute work when membership changes without moving everything." Recognizing the shared pattern is senior-level synthesis.

3. How does it work?

Consistent hashing with virtual nodes

hash ring (0 .. 2^32):
   a#3        b#1     c#2      a#1        c#5     b#4
   ──●─────────●───────●────────●──────────●───────●──▶ (wraps)
   key k hashes here ──┘ belongs to the next vnode clockwise -> a#1 -> node a

Ring.AddNode places a node at vnodes positions; Get(key) finds the first position clockwise (binary search + wrap). Removing a node (RemoveNode) deletes its positions; only keys that pointed at those positions move — to the next node clockwise. Measured: removing 1 of 3 nodes moves ~32% of keys; mod-N moves ~67%. Virtual nodes (many per physical node) make the per-node load even and the movement smooth (a removed node's keys spread across all survivors, not dumped on one neighbor).

Quorums and the overlap guarantee

N=3 replicas.  Write W, Read R.
  R+W>N  -> read set ∩ write set ≠ ∅ (pigeonhole) -> read sees latest = STRONG
  R+W<=N -> sets can be disjoint -> read may be STALE = EVENTUAL

Cluster.Write(W, version) updates W replicas; ReadWorstCase(R) reads the R replicas least likely to hold the write — so if even that read sees the new version, overlap is guaranteed. QuorumOverlaps(N,W,R) returns W+R>N. Tunings: W=N,R=1 (fast reads, slow/availability- sensitive writes); W=1,R=N (fast writes, slow reads); W=R=quorum (balanced strong, the common default).

CAP / PACELC (the trade-off you're tuning)

• CAP: under a network Partition you must choose Consistency or Availability. R+W>N with a partition means some reads/writes can't reach a quorum → you sacrifice availability to keep consistency (or relax the quorum to stay available, sacrificing consistency).
• PACELC: even when there's no partition (Else), you trade Latency vs Consistency (a strong read waits for a quorum). So consistency costs latency always, not just during partitions.

4. Core terminology

5. Mental models

• Consistent hashing is musical chairs with assigned seats around a circle. Each key sits in the next occupied chair clockwise. Remove a chair (node) and only the people who were sitting there get up and move to the next chair — everyone else stays put. Mod-N is "renumber every seat," so the whole room shuffles.

• Virtual nodes are giving each player many chairs. One chair per player means uneven gaps (some players hog huge arcs) and a removed player dumps their whole arc on one neighbor. Scatter each player's many chairs around the ring and load evens out and a departure spreads across everyone.

• R+W>N is the overlapping-Venn-diagrams rule. Draw the W replicas you wrote and the R you read as two sets in a universe of N. If their sizes sum to more than N, they must intersect (pigeonhole) — and that shared replica has the latest write. Shrink them so they fit side-by-side (R+W≤N) and a read can miss the write.

• Consistency is a dial, not a switch. Per dataset, pick the weakest model that's still correct: strong for money, causal for comments, eventual for view counts. "Strong everywhere" is paying latency and availability tax you usually don't need.

6. Common misconceptions

• "Hash partitioning (mod-N) is fine." Until you add a node — then ~all keys remap and you move the whole dataset (an outage). Consistent hashing (or a fixed large partition count, Kafka-style) is the scalable choice.

• "More replicas = stronger consistency." Replication is for fault tolerance/availability; consistency comes from the W/R quorum, not the replica count. You can have many replicas and still read stale data if R+W≤N.

• "Strong consistency everywhere." It costs latency on every read (PACELC) and availability under partition (CAP). Most data tolerates weaker models; forcing strong everywhere is over-engineering that hurts p99 and uptime.

• "Consistent hashing balances perfectly." Only with enough virtual nodes. One position per node gives lumpy arcs and a bad departure dumps load on one neighbor. Vnodes (100s) are what make it even.

• "CAP means pick 2 of 3." The modern reading: partitions will happen, so you're really choosing C or A during a partition, and (PACELC) C vs L the rest of the time. It's a per-operation dial, not a one-time architecture badge.

7. Interview talking points

• "How do you partition data?" Strategy by access pattern: range for scans (watch hotspots), hash for even spread (but mod-N reshards badly), consistent hashing with vnodes for elastic membership (~1/N movement). Choose the partition key to avoid skew. Name the resharding cost of each.

• "Explain R+W>N." With N replicas, writing W and reading R, if R+W>N the read and write quorums overlap (pigeonhole) so the read sees the latest write — strong/read-your-writes. R+W≤N permits staleness (eventual) for better latency/availability. Give example tunings (W=N/R=1, W=1/R=N, W=R=quorum).

• "Consistency models, weakest you can use?" Linearizable (money) → causal (chat/comments) → read-your-writes (your own profile) → eventual (view counts/likes). Pick per dataset; strong everywhere is a latency/availability tax.

• "CAP vs PACELC?" CAP: under a partition, choose C or A. PACELC: even without a partition, choose latency or consistency. So consistency costs you always, and the architect decides where it's worth it.

• "Why consistent hashing over mod-N?" Membership changes: mod-N remaps ~all keys (full reshuffle = migration/outage); consistent hashing moves ~1/N. Vnodes give even load + smooth departures. Same minimal-movement goal as Kafka consumer rebalancing (pa-04) and gateway subsetting (gw-04).

• "How do you keep stale replicas converging?" Read-repair (fix stale replicas seen during a read), anti-entropy (background Merkle-tree sync), and hinted handoff (store writes for a down replica) — the Dynamo toolkit on top of quorums.

8. Connections to other labs

• db-16…20 (consensus) — the third fundamental (strong consistency via a replicated log); quorums here are the tunable, Dynamo-style alternative to full consensus.
• pa-04 (log) — partitioning + rebalancing for streams; the same minimal-movement concern.
• gw-04 (subsetting) — the Van der Corput ring is consistent-hashing- adjacent: balanced, minimal-movement assignment under membership churn.
• pa-09 (reliability) — consistency/availability choices are SLO decisions; quorum tuning is a reliability lever.
• db-13 (MVCC) — single-node consistency; this lab is its distributed, replicated counterpart.