Sharding a KV store across Raft groups, and the consistency spectrum

Every week so far made one cluster more correct — more fault-tolerant, more consistent, more durable.
This week asked a different question: one cluster has a ceiling, since every write still funnels through
one leader’s one log. How do you scale out without giving up what the last three weeks earned? The
answer turned out to be smaller than I expected: sharding isn’t a new consensus mechanism, it’s
composition on top of the one already built.

What I built

A thin routing and migration layer on top of unmodified replica groups — each one a complete Week 5
cluster that has no idea it’s “a shard.”

         Controller (config: shard -> group, NOT Raft-replicated)
                    |
        key "apple" -> shard 7 -> Group B
                    |
        +-----------+-----------+
        |                       |
    Group A                 Group B
  (shards 0-6, 8-9)        (shard 7)
  [full Raft + KV       [full Raft + KV
   cluster, Week 5]       cluster, Week 5]

The concepts that made it work

• Sharding and consensus are orthogonal. I kept expecting sharding to require touching Raft or the
  KV layer. It didn’t, once I separated the questions: “who owns this key” (a routing problem, solved by
  the controller) is completely independent of “how does that owner stay correct” (already solved,
  inside each replica group, by Weeks 3-5). You can shard a linearizable system — what I built — or
  shard an eventually-consistent one, like Dynamo. The sharding mechanism doesn’t care which.
• Copy the data, then flip the config — never the other order. Moving a shard means reading every
  matching key from the current owner and writing it to the new owner before the controller’s config
  changes. A client always asks the controller for the latest config, so it structurally cannot be routed
  to a new owner before that owner actually has the data. Get this order backwards and there’s a window
  where a client gets routed to an empty destination.
• Quorums (R+W>N) are a genuinely different mechanism from what I’d built, not a variation on it.
  Raft serializes everything through one elected leader. A quorum system has no leader at all — any W
  nodes acking a write and any R nodes agreeing on a read, with R+W>N guaranteeing those sets overlap, is
  enough to guarantee a read sees the latest acknowledged write. No election, no log — and no free lunch
  either: without a leader to order things, concurrent writes to the same key can produce versions that
  genuinely conflict, which is what vector clocks exist to detect.
• CAP only describes a partition; PACELC is the fuller picture. My system, partitioned so no majority
  exists on one side, chooses Consistency over Availability for that side — by design, it refuses to
  answer rather than risk a wrong answer. But even with NO partition at all, it’s still trading Latency
  for Consistency on every single read, which is exactly what next steps like ReadIndex exist to claw
  back. CAP alone wouldn’t have surfaced that second tradeoff.

The thing that bit me

I almost shipped the ListKeys migration call going through the Raft log, the same way Get does —
“consistency,” I told myself. But that’s solving a problem I don’t have: migration already requires the
shard to be quiescent (no concurrent writes during the move), so there’s nothing for log ordering to
protect against. Routing an admin-only, already-safe-by-assumption read through the full replication
path would have been the over-engineered version, not the correct one. The harder discipline wasn’t
adding the safety — it was correctly identifying that this one spot didn’t need it, and writing down
why, so “no log here” reads as a decision instead of an oversight.

Tradeoffs & the road not taken

• The controller isn’t fault-tolerant. A real system makes it its own tiny Raft group (MIT 6.824’s
  shardctrler does exactly this). I left it as a single in-memory config service — the done bar this
  week was routing and migration, not building a second consensus service from scratch.
• Migration is a blocking, controller-orchestrated snapshot-copy, not a live transfer. It assumes the
  moving shard is quiescent. A production system can’t assume that — it needs a versioned config and a
  pull-based protocol where the gaining group requests the shard as part of normal operation, and
  correctly handles a client request arriving mid-transfer instead of requiring the world to hold still.
• key2shard hashes on the first byte — deliberately crude, not consistent hashing. It makes the
  point (partition the keyspace, route by shard) without the added machinery; the real cost shows up the
  moment a group joins or leaves, when this scheme reshuffles almost everything instead of the ~1/N
  consistent hashing would move.

Where this sits in the system

Weeks 3-5 made one cluster correct under every failure I could throw at it. This week showed that
correctness composes: scale-out didn’t require rebuilding consensus, just a routing layer that respects
what the layer below already guarantees. Next, the finale: reframe the replicated log itself as a
Kafka-style broker — the same append-only structure that’s been doing election, replication, and now
state-machine application this whole time, revealed as a message queue underneath.

Part of a series building a distributed database from scratch.