Raft Consensus

Overview

Consensus means getting several servers to agree on a value, and keep agreeing, even when some of them crash or the network loses messages. Systems use it to keep a replicated log: an ordered list of commands that every server applies in the same order to its own copy of the data. If every copy starts the same and applies the same commands in the same order, every copy ends the same. That is a replicated state machine.

Raft is a consensus algorithm published by Diego Ongaro and John Ousterhout at USENIX ATC in 2014. It gives the same result as Multi-Paxos but was designed to be easier to understand: it has one strong leader, splits the problem into leader election, log replication and safety, and uses randomized timers to settle elections. In the authors' study of 43 students who learned both algorithms, 33 answered questions about Raft better than questions about Paxos.

Raft is inside much of the infrastructure you will draw in an interview. etcd, which stores all of the Kubernetes API server's data, uses it. So do Consul, CockroachDB and TiKV (one Raft group per range of keys), and Kafka's KRaft controller quorum uses a Raft dialect in place of ZooKeeper.

What you will be able to do

• Explain how a Raft cluster elects exactly one leader per term, and why the timeouts are random.
• Walk through a write from the client to commit, and say which entries in a set of logs are committed.
• Explain the safety rules: the election restriction and why a leader only counts replicas for entries from its own term.
• Describe what happens in a partition, how to serve linearizable reads, and how to change the cluster's members.
• Choose a cluster size and say what Raft costs in latency and availability.

Key concepts

• Replicated state machine
• Majority quorum
• Terms
• Leader election
• Randomized election timeouts
• AppendEntries and the log
• Commit index
• Election restriction
• Linearizable reads
• Membership changes

Interview questions

• Walk me through how Raft elects a leader.
• How does a write get committed in Raft?
• Here are five logs. Which entries are committed?
• What happens in Raft during a network partition?
• Why can a Raft leader not commit an entry from an earlier term just because it is on a majority?
• How do you serve linearizable reads from a Raft cluster?
• How many servers should a Raft cluster have?
• Raft or Paxos: what is the difference, and which would you choose?

More System Design topics

• Price Comparison Engine
• Price Tracking Service
• Primary-Replica vs Peer-to-Peer
• Proxies
• Proximity Service
• Quorum Consensus
• RAG System (Retrieval-Augmented Generation)
• Rate Limiter
• Rate Limiting
• Read Repair
• Read-Heavy vs Write-Heavy Systems
• Real-Time AI Translation System