Agreement is expensive, dissemination is cheap
Which facts should go through consensus and which around it?
There are two ways to spread a fact through a cluster.
| Consensus | Gossip | |
|---|---|---|
| What it delivers | total order over decisions | eventual delivery, no order |
| Which nodes must be alive | a majority, continuously | nobody in particular |
| Messages per fact | O(N), concentrated on the leader | O(N log N) in total, spread evenly |
| Latency to certainty | 1 RTT plus a durable write | O(log N) rounds, probabilistic |
| Fails by | losing availability | losing freshness |
(O(N) means "grows in proportion to the number of nodes N"; O(N log N) grows a little faster than N. Gossip means each node periodically tells a few random peers what it knows, like a rumour spreading.)
These are not competitors. They are two channels with a price ratio of several orders of magnitude. The architecture of every large distributed data system is an allocation between them. The allocation is always the same:
A production Kafka, HDFS or Kubernetes cluster pushes kilobytes per minute through its consensus system and petabytes per day around it. The ratio is about 10⁻⁹. That ratio is the split between control plane and data plane. It is not just one item among the topics of this mechanism; it is the organizing principle.
It is also the first sight of a recurring idea: agreement among n machines is implemented as agreement on one designated sequence, and every other machine's correctness is defined by reference to a position in it. Epochs, terms, generations, configuration versions, ZooKeeper's transaction ids (zxids) and Raft log indices are the same thing: one small, ever-increasing integer against which everything else is checked. We call it the one designated version cell: agreement across several entries is reached by agreeing on one cell, and the leader epoch is its plainest instance.