Multi-Raft: Sharding Consensus (CockroachDB Style)

You have read the previous chapters in this build — leader election and terms, log replication, membership changes, safety invariants. You can now build a working three-node Raft cluster that survives a leader crash, replicates a log, and gracefully accepts new members. You can run etcd. That is real progress.

It is also not enough to build a database. The Raft cluster you have built has exactly one leader, and that leader handles every write the cluster will ever serve. Run a benchmark: a modern machine fsyncing batched 4 KB writes to NVMe tops out around 30k–50k commits/second; with replication and the network round trip eating into that, a single Raft group in production is a ~10k–30k writes/sec animal. Compare that to MySQL on a single big box (~50k–100k tps), or a sharded NoSQL deployment (~millions of ops/sec across the cluster). The single Raft group is behind the unsharded single-box database, and that is before we ask it to also handle reads, snapshot transfers, and rebalancing.

This chapter is about the architectural trick — Multi-Raft — that every modern strongly-consistent distributed SQL system uses to break that ceiling. We focus on CockroachDB because its design is the most thoroughly documented, but the same pattern shows up in TiKV (which powers TiDB), YugabyteDB, and Yandex's YDB.

Why a single Raft group cannot scale

Look at the leader's hot path during a write:

1. Client sends Put(k, v) to the leader.
2. Leader appends one entry to its in-memory log.
3. Leader fsyncs the entry to its persistent log on disk.
4. Leader sends AppendEntries(entry) to every follower over the network.
5. Followers fsync, ack.
6. Leader counts acks, advances commitIndex once a majority replies.
7. Leader applies the entry to the state machine and replies to the client.

Every step is serial for that group. Step 2 is one mutex on one log structure. Step 3 is one fsync stream on one disk. Step 4 is one TCP send loop per follower from one process. Step 6 is one counter being advanced. The leader is a single-threaded chokepoint by design — Raft's safety proof depends on the log having a single writer, and that writer is the leader process.

Why "just shard the work inside the leader" does not save you: you can pipeline AppendEntries (don't wait for ack before sending the next entry), batch writes (one fsync per 1 ms window), and parallelise replication to followers. Production Raft implementations do all of this, and it gets you to the 10k–50k tier. Beyond that the bottleneck moves from disk to CPU — encoding entries, computing CRCs, traversing the log data structure — and the single mutex protecting the log eventually pegs one core. A 2024 etcd benchmark on the etcd team's hardware: ~40k writes/sec at p99=10ms, dropping sharply past that. CockroachDB's per-range ceiling is in the same neighbourhood. You do not break it without parallel groups.

The other constraint is state size. Even if writes were free, a single Raft group's state machine has to fit on every replica, snapshot transfers have to fit through the network, and log compaction has to fit in one process's memory. A 100 TB database in one Raft group means every replica is 100 TB and every snapshot is a 100 TB stream. That is not an architecture; that is a hostage situation.

So you shard. The question is how.

The Multi-Raft architecture

The Multi-Raft idea is straightforward to state and full of subtleties to implement: split the keyspace into many small contiguous ranges, and run an independent Raft group for each range.

A "range" in CockroachDB is a contiguous span of the sorted keyspace, sized at around 64–512 MB by default. (TiKV calls these "regions" and defaults to 96 MB; YugabyteDB calls them "tablets". Yandex YDB calls them "tablets" too.) A 1 TB database is split into roughly 2,000–16,000 ranges. Each range is its own Raft group with three replicas (the typical default), three log streams, three commit indexes, and one leader.

Look at what this buys you. A write to a key in range A goes through range A's Raft group only — its leader appends to A's log, replicates to A's followers, commits. Range B's leader, sitting on node 2, has no idea the write happened and does not care. Each range's log is independent. Each range's commit index is independent. Each range's snapshot is independent. The fsync streams from different ranges on the same disk are typically batched by the storage engine (CockroachDB uses Pebble; TiKV uses RocksDB), so disk throughput is shared, but the consensus work parallelises perfectly.

Why ranges, not hash buckets: contiguous key ranges support efficient range scans — SELECT * WHERE id BETWEEN 1000 AND 2000 reads from a small number of consecutive ranges, not from every shard like in hash-partitioned systems. The cost is hot-spotting: if your application writes monotonically increasing keys (timestamps, autoincrement IDs), the highest-key range becomes a hot spot — which is why CockroachDB recommends UUID primary keys and TiKV has explicit pre-split hints. The split logic (next chapter) handles the rest by detecting load and splitting hot ranges.

Distributing leadership

On a 9-node cluster with 3,000 ranges and replication factor 3, there are 9,000 replicas total. Each node holds 1,000 replicas (9000 ÷ 9). Of those 1,000, the node leads roughly 333 (1000 ÷ 3, since one of each replica trio is the leader). That means every node is doing leader work for about 333 ranges and follower work for about 667 ranges, simultaneously, in 9,000 separate Raft state machines.

Read load distributes the same way: in CockroachDB and TiKV, reads typically go to the leader (for linearizability), so a node leading 333 ranges handles reads for those 333 keyspaces. If reads are uniform across the keyspace, every node handles 1/9 of the read traffic. If reads are skewed toward a hot range, only the node leading that range is hot — and the cluster's response is to split that range further until the heat subsides.

The rebalancer's job is to keep this distribution even. CockroachDB runs a continuous background process that monitors load (CPU, QPS, range count, disk usage) per node and moves replicas — and leaderships — to even things out. Moving a leader is cheap: it is a single Raft TransferLeader message. Moving a replica is more expensive: it is a Raft membership change (add the new replica as a learner, catch it up via snapshot, promote it, remove the old replica).

Heartbeat coalescing

Here is the bug a naïve Multi-Raft implementation hits about ten minutes after deployment.

Each Raft group sends heartbeats: the leader sends an empty AppendEntries to every follower every 50 ms or so. Three replicas means each leader sends to two followers; with 3,000 ranges per node × 2 followers per range × 20 heartbeats/sec = 120,000 RPCs/sec leaving every node, just to say "I'm alive". On a 9-node cluster, that is 1.08 million heartbeat RPCs/sec on the network. Each carries TCP framing, gRPC headers, range ID, term, leader commit index, log index — a few hundred bytes per heartbeat. The network is now fully booked carrying the metaphorical equivalent of "I'm still here, are you still there?".

The fix is heartbeat coalescing. Instead of each Raft group sending its own heartbeats, the host node maintains one heartbeat channel per peer node. Every 50 ms it sends one batched message containing: "I am still leading the following list of ranges with these terms and commit indexes — please ack." The peer node, on receipt, walks the list and updates each Raft group's "I heard from leader" timer in one go. Replies are coalesced symmetrically: "I am still following you on these ranges."

The wire RPC count drops from O(ranges × peers) to O(peers). The CPU cost of heartbeat handling drops too — one TCP read, one batched dispatch, instead of thousands of RPC-framing operations. CockroachDB calls this "Raft transport coalescing"; TiKV's design document refers to "store-level heartbeats". They are the same idea.

Why this is correct: Raft heartbeats only need to convey "leader X is alive in term T for group G" and "leader X believes commit index is C". Bundling many such tuples into one message does not break any safety property — each group's state machine still receives its own update, just delivered in a shared envelope. The optimisation is purely about transport. The only subtlety: if a coalesced heartbeat is dropped, all the groups it covers miss their tick simultaneously — which can cause correlated election timeouts. Production systems jitter election timeouts and add per-group nack tracking to handle this; the issue is empirically rare.

Range splits and merges

Ranges are not static. A range that grows past its target size (CockroachDB defaults to 512 MB; TiKV to 144 MB) is split into two adjacent ranges. A range that gets too hot (high QPS) is split by load even if it is small. Pairs of small adjacent ranges may be merged.

A split is itself a Raft operation. The leader of the parent range proposes a Split(splitKey) entry; once committed by the parent's Raft group, every replica of the parent range performs the split locally — creating two new in-memory Raft groups, copying the relevant key range into each, and starting the new groups with the same replica set. From that moment on, the two new ranges are independent Raft groups with independent leaders (initially the same physical node as the parent's leader, then potentially rebalanced).

We will cover the load-based split logic — when and where to split, not just how — in detail in the next chapter (Build 14). For this chapter the relevant fact is just that splits and merges are coordinated through the parent Raft group's log, so they preserve linearizability across the split point.

The catalogue: routing clients to the right leader

A client wants to write to key users/42. Which node leads the range containing that key?

The answer lives in a system catalogue — a sorted index from key range to (range ID, replica list, leader hint). In CockroachDB this is the meta range (and the meta-meta range one level above it, for catalogues large enough to themselves need splitting); in TiKV it is the Placement Driver (PD) server cluster; in YugabyteDB it is the master cluster.

Crucially, the catalogue is itself stored in a Raft group (or, in TiKV, in a separate small Raft cluster). It has all the same guarantees — linearizable updates, leader election, replication — and the same scaling characteristics. It is small (a 100 TB database with 64 MB ranges has ~1.5M ranges; each range descriptor is a few hundred bytes; the whole catalogue is ~hundreds of MB), so a single Raft group suffices. CockroachDB further splits the meta range itself once it grows past size, with a meta-meta range pointing into it; the recursion terminates at the meta-meta range, which is fixed and replicated to a configurable set of nodes.

A client routes a request like this:

1. Client receives a request for key K.
2. Client looks up K in its local cache of range descriptors. Cache hit: it knows range R contains K and node N is the leader hint. Send to N.
3. Cache miss, or stale (N replies "no longer leader, here is the new one"): client queries the meta range for K, gets the current descriptor, retries.
4. Stale on the meta range too: client falls back to the meta-meta range, then to a fixed bootstrap address baked into the binary.

In steady state, the client cache is hot and >99% of requests skip the catalogue entirely. The catalogue's load is low, so its single Raft group is not a bottleneck. When a leader moves (rebalance, failover), clients hit the stale-leader path a few times until their caches refresh; CockroachDB sends piggybacked "actually the leader is N'" hints on the rejection response to make this fast.

Real systems

CockroachDB is the canonical Multi-Raft implementation. Range size targets default to 512 MB. The meta range plus meta-meta range structure is documented in the project's architecture docs. CockroachDB's kv layer wraps an in-tree fork of etcd-io/raft called cockroachdb/raft, with extensive modifications for batched proposals, raft scheduler integration, and leadership transfer. The "Living Without Atomic Clocks" blog post explains how Multi-Raft + HLC replaces what Spanner does with TrueTime [1].

TiKV (the storage layer of TiDB) uses the same design with regions sized at 96 MB by default. It uses a separate process called the Placement Driver (PD) as the catalogue cluster; PD itself runs etcd. TiKV pioneered many Multi-Raft optimisations and the team has presented the tradeoffs publicly [3].

YugabyteDB uses tablets (their term for ranges) and a master service for the catalogue. The architecture is similar; their tablet sizes are typically larger (1 GB+ default).

Yandex YDB uses tablets with a distributed scheduler and a separate metadata service. Public documentation is sparser but the architecture follows the same pattern.

All four trace their lineage back to Spanner (Google) [5], which used Paxos rather than Raft but introduced the "many small Paxos groups, one per tablet" pattern that Multi-Raft generalises.

What you have learned

You now understand why a single Raft group is a throughput dead-end (one leader, one log, one core, ~30k writes/sec) and how Multi-Raft sidesteps that by making a fresh independent Raft group per 64–512 MB range. You can see why heartbeat traffic explodes naïvely and how coalescing fixes it. You know that splits and merges are themselves Raft operations and that a system-table catalogue (also a Raft group) routes clients to the right leader.

The next chapter (Build 14) goes inside the split logic — when does a range split, how is the split key chosen, what does load-based splitting look like, and how do range descriptors update atomically through the catalogue.

References

1. Living Without Atomic Clocks: Where CockroachDB and Spanner Diverge — Cockroach Labs blog explaining Multi-Raft + HLC vs TrueTime.
2. etcd-io/raft library README — the canonical production Raft library, source of the MultiRaft-style fork in CockroachDB.
3. Multi-Raft in TiKV — PingCAP engineering talk — TiKV's heartbeat coalescing, region scheduler, and PD design.
4. CockroachDB raft library documentation — the in-tree fork with batched proposals and quotapool.
5. Spanner: Google's Globally-Distributed Database (OSDI 2012) — origin of the "many small consensus groups per tablet" pattern.
6. In Search of an Understandable Consensus Algorithm (Raft paper) — Ongaro and Ousterhout 2014, USENIX ATC.