Skip to content
Navigation

Type at least two characters. Search covers page titles, headings, tags and database names.

↑ ↓ to navigateEnter to openEsc to close0 pages
Architectureadvanced

Consensus Algorithms

How Raft and Paxos let a group of nodes agree on an ordered log, what a majority actually buys you, and why leader election is the part that shows up in incidents.

3 min readAdvancedUpdated Edit this page
CockroachDBYugabyteDBMongoDB

Consensus lets a group of nodes agree on a sequence of operations despite crashes and network delays. It is the mechanism behind CockroachDB and YugabyteDB ranges, MongoDB elections, etcd, ZooKeeper and ClickHouse Keeper.

Raft replication of a single rangeA client writes to the Raft leader, which appends the entry to its log and replicates it to two followers. Once a majority has persisted the entry it is committed and applied to the state machine, then acknowledged to the client.writeAppendEntriesAppendEntriescommit ackClientLeaderterm 7, log index 42Follower 1log index 42Follower 2log index 41
Raft replication of a single range

What Raft does

Raft splits the problem into leader election, log replication and safety.

  1. One node is leader for a term. All writes go through it.
  2. The leader appends an entry to its log and sends AppendEntries to followers.
  3. When a majority — including the leader — has persisted the entry, it is committed and applied to the state machine.
  4. Followers that fall behind are caught up by the leader; conflicting entries are overwritten.

The majority requirement is what makes it safe. Any two majorities of the same group overlap in at least one node, so a newly elected leader is guaranteed to have seen every committed entry.

What a majority means for availability

Group sizeMajorityFailures toleratedNotes
321Standard minimum
431No better than 3, more expensive
532Common for critical clusters
743Higher commit latency

Even-numbered groups are wasteful: they cost an extra node without tolerating an extra failure. Larger groups tolerate more failures but make every commit wait for more nodes, so latency grows.

Leader Election

When followers stop receiving heartbeats within the election timeout, one becomes a candidate, increments the term and requests votes. A node grants its vote only if the candidate's log is at least as up to date as its own, which prevents a node missing committed entries from winning.

Two properties matter operationally:

  • Unavailability window. Writes stop between leader failure and new leader election — typically the election timeout plus a round trip. Timeouts are tunable, and tuning them down increases the risk of spurious elections when the network hiccups.
  • Election storms. If timeouts are too aggressive or the network is unstable, nodes repeatedly elect and depose leaders, and no work gets done. Randomised timeouts reduce split votes, but persistent instability means the timeout is wrong for the network.

Raft versus Paxos in practice

Multi-Paxos and Raft solve the same problem with the same majority guarantees. Raft constrains the design — a strong leader, an append-only log, no holes — which makes it easier to implement correctly and easier to reason about during an incident. Most systems built after 2014 chose Raft for that reason.

What consensus does not solve

  • Throughput. Every write is serialised through one leader per group. Systems scale by having many independent groups (ranges, tablets, shards), not by making one group faster.
  • Latency across regions. A commit requires a majority, so a group spanning continents pays the inter-region round trip on every write. Place replicas according to where writes originate. See Geographic Distribution.
  • Correctness of your data model. Consensus guarantees agreement on an order of operations, not that the operations were the right ones.