What is the Raft Consensus Algorithm?
Achieve high read performance with single-key linearizability and leader leases
Raft is a consensus algorithm. It allows the members of a distributed system to agree on a sequence of values in the presence of failures. More specifically, it has become the protocol of choice for building resilient, strongly-consistent distributed systems.
A distributed SQL database uses the Raft consensus algorithm for both leader election and data replication. Instead of having a single Raft group for the entire dataset in the cluster, a distributed SQL database applies Raft replication at an individual shard level where each shard has a Raft group of its own.
The below illustration shows the Raft consensus algorithm in action.
Why the Raft Consensus Algorithm?
A distributed SQL database cannot compromise on correctness. There are different levels of this intuitive correctness, represented by different consistency models.
Linearizability is one of the strongest single-key consistency models. It implies that every operation appears to take place atomically and in some total linear order. This means it’s consistent with the real-time ordering of those operations. In other words, the following should be true of operations on a single key:
- Operations can execute concurrently, but the state of the database at any point in time must appear to be the result of some ordered, sequential execution of operations.
- If operation A completes before operation B begins, then B should logically take effect after A.
The Raft consensus algorithm solves the problem described above. Raft is easy to understand and offers some additional features such as the ability to dynamically change membership.
Consensus involves multiple servers agreeing on values. It is a fundamental problem in fault-tolerant, distributed systems. But once the servers agree on a value, that agreement is final.
Typical consensus algorithms accept write requests when any majority (i.e., quorum) of their servers is available. Examples of applications of consensus include:
- Whether to commit a transaction to a database
- Agreeing on the identity of a leader
- State machine replication
- Atomic broadcasts
Consensus protocols can be broadly classified into two categories: leader-based and leaderless. The Raft consensus algorithm is a commonly used leader-based consensus protocol where a “leader” handles the task of data updates and replication. Strongly-consistent distributed databases have standardized onto this protocol.
Leaderless consensus protocols are harder to implement but have higher availability than leader-based protocols. Application of leaderless protocols can be found in blockchain distributed ledgers.
Benefits of Raft-Based Replication
The Raft consensus algorithm is more understandable by means of its separation of logic. The separation of logic stems from Raft making leader election a separate and mandatory step before the leader can get the data replicated. Separating leader election allows dynamic membership changes with ease — re-running leader election handles server additions and removals.
Additionally, in the absence of any unplanned failures or planned membership changes, the leader election step can be skipped. But note that the leader election step is automatic whenever such changes happen, even if no new writes are coming into the system.
Finally, the Raft consensus algorithm imposes the restriction that only the servers with the most up-to-date data can become leaders. These optimizations radically simplify edge use cases.
With approximately 100 open source implementations (and growing), Raft is the de-facto standard today for achieving consistency in modern distributed systems. Popular implementations include those from etcd and consul.
Ensure Consistent Database Replication and Performance
Consensus-based replication has become key to building resilient, strongly-consistent distributed systems. The Raft consensus algorithm has emerged as the leading option given its focus on understandability without sacrificing correctness and performance.
Finally, YugabyteDB uses the Raft consensus algorithm for its leader election and data replication. Learn more about this powerful, open source database today through our free, self-paced courses: Introduction to Distributed SQL and Introduction to YugabyteDB. And join the YugabyteDB community to answer any and all of your distributed SQL questions.