Raft
lastmod 2024-06-15created 2018-07-275 edits
Description of the Raft distributed consensus algorithm.
About
Raft is a consensus algorithm designed as an alternative to Paxos. It was meant to be more understandable than Paxos by means of separation of logic, but it is also formally proven safe and offers some additional features. Raft offers a generic way to distribute a state machine across a cluster of computing systems, ensuring that each node in the cluster agrees upon the same series of state transitions. It has a number of open-source reference implementations, with full-specification implementations in Go, C++, Java, and Scala.
What is Raft?
Raft is a consensus algorithm that is designed to be easy to understand. It's equivalent to Paxos in fault-tolerance and performance. The difference is that it's decomposed into relatively independent subproblems, and it cleanly addresses all major pieces needed for practical systems. We hope Raft will make consensus available to a wider audience, and that this wider audience will be able to develop a variety of higher quality consensus-based systems than are available today.
How it works
In a distributed system using the Raft Consensus Algorithm, every node is in one of the three states below. Typically there is one leader and the rest are followers; candidates exist only temporarily, when there is no leader or the leader is unresponsive.
- Leader
- The single node that represents the cluster. The leader is solely responsible for receiving, propagating, and responding to all commands that clients send to the cluster. The leader also periodically propagates its status message (heartbeat) to all followers.
- Follower
- As long as a leader exists, the remaining nodes stay in this state. They are only responsible for processing commands propagated from the leader.
- Candidate
- The state a follower switches to in order to choose a new leader when there is no leader. A follower that has not received a status message (heartbeat) from the leader for a certain amount of time becomes a candidate.
Why three or more nodes are needed
See The quorum problem in consensus algorithms for details.
Forming a quorum
- In a distributed system, a quorum is the minimum number of servers in a cluster needed to approve an operation. For example, if a cluster has 5 etcd servers, the quorum requires the agreement of more than half of the servers, that is, 3 or more. This keeps the data consistent and allows agreed changes to be applied.
- With an odd number of servers, a majority of the cluster can always agree and form a quorum. This plays an important role in keeping the cluster working normally even during failures such as network partitions.
Leader election
- An etcd cluster always maintains one leader server. The leader manages data write operations and replicates changes to the other servers (followers).
- With an odd number of servers, a single leader can reliably be elected even if the servers are split in two by a network partition or the like. For example, with 5 servers, if 2 servers are separated, the remaining 3 can form a quorum and elect a leader.
Fault Tolerance
- With an odd number of servers, the cluster can keep working as long as more than half of the servers have not failed. For example, in a 3-server cluster, even if 1 server fails, the remaining 2 servers can maintain a quorum.
- If a cluster has an even number of servers, it can be split into equal halves by a network partition or similar. In that case, maintaining a quorum becomes difficult and leader election may become impossible.