Paper · Distributed Systems

In Search of an Understandable Consensus Algorithm

D. Ongaro, J. Ousterhout · USENIX ATC · 2014

Raft, the consensus algorithm designed to be understood. A great first distributed systems paper.

Summary

Replicated systems need their servers to agree on a sequence of commands even when some servers fail. Paxos solves this but is famously hard to understand and to turn into a complete system. The authors designed Raft with understandability as an explicit goal.

Raft splits consensus into leader election, log replication and safety. A single leader, elected for a numbered term, accepts commands and replicates them to followers. An entry is committed once a majority stores it, and election rules guarantee that a new leader has every committed entry. The paper also covers membership changes and log compaction.

Raft is now used in systems such as etcd, CockroachDB, TiKV and Consul. For database engineers, it is the most accessible way to understand how replicated state machines keep copies of data consistent.

Key ideas

  • Consensus split into leader election, log replication and safety.
  • A single leader per term, with randomised election timeouts.
  • Entries commit once replicated to a majority of servers.
  • Election restrictions ensure new leaders hold all committed entries.
  • Joint consensus for safe cluster membership changes.

More Distributed Systems papers