Consensus Algorithms

How a group of machines agrees on one ordered log even when some of them crash: majorities, Raft, Paxos, safety and liveness, and where etcd, ZooKeeper, Kafka and CockroachDB use them.

Overview

Consensus is the problem of getting several machines to agree on a value, and to keep agreeing, even when some machines crash and messages arrive late or not at all. Databases rarely need to agree on one value. They need to agree on a log: an ordered list of commands, such as set x to 5, that every replica applies in the same order. If every replica starts in the same state and applies the same commands in the same order, every replica ends in the same state. That pattern is called a replicated state machine.

Consensus is what makes automatic failover safe. It elects exactly one leader at a time, and it guarantees that a write confirmed to a client survives any later leader change. etcd (which stores all Kubernetes cluster state), ZooKeeper, Kafka's KRaft controllers, CockroachDB and Google's Spanner are all built on it.

This chapter explains the idea of a majority, then Raft in detail, then Paxos, and then what these algorithms can and cannot promise.

What you will be able to do

  • Explain why majority quorums are the core of consensus, and size a cluster for a number of failures.
  • Walk through Raft's leader election and log replication, including the rules that keep it safe.
  • Describe Paxos's two phases and how Multi-Paxos relates to Raft.
  • Explain safety versus liveness and what the FLP result means in practice.
  • Say which real systems use consensus, for what, and what it costs in latency.

Key concepts

  • Replicated state machine
  • Majority quorum
  • Terms and elections
  • Log replication
  • Commit index
  • Paxos
  • Safety and liveness
  • FLP result
  • Membership changes
  • Snapshots

Interview questions

  • How does Raft work?
  • Why do consensus clusters have an odd number of servers?
  • What is the difference between safety and liveness, and what does FLP say?
  • How does Paxos differ from Raft?
  • Walk through what happens when a Raft leader crashes.
  • How can a Raft cluster serve reads, and which reads are safe?
  • How do systems like CockroachDB scale consensus beyond one leader?
  • When should you not use consensus?

Sign up free to read the full topic

More Databases & SQL topics

Start free on Cariara · Coding problems · System design studio