The Consensus Algorithm - Raft

There is only one consensus protocol, and that’s Paxos - all other approaches are just broken versions of Paxos. Ironic, hard enough to understand compared to the Raft. There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system. . . . the final system will be based on an un-proven protocol. --Chubby Implementer

tl;dr: Raft (thesecretlivesofdata.com)

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 sub-problems, 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.

---

Raft decomposes the consensus problem into three relatively independent sub-problems:

1. Leader election: a new leader must be chosen when starting the cluster and when an exsiting leader fails.
2. Log replication: the leader must accept log entries from clients and replicate them across the cluster, forcing the other logs to agree with its own.
3. Safety: if any server has applied a particular log entry to its state machine, then no other server may apply a different command for the same log index. (the State Machine Safety Property)

The basic elements of Raft show as belows:

The main procedure of Raft depicted as follows:

Five things to be determinately implemented:<br/> Election safety, at most one leader can be elected in a given term. Leader append-only, never delete or overwrites entries, only append entries. Log matching, to be perfect Leader completeness, to be complete State machine safety, the only entry for the a given index.

ensure above the five properties are correctly executed, then the Raft is achieved.

A Raft cluster contains several servers, five is a typical number and tolerates two failures at the same time.

At a given time, each server is one of three states: leader, follower, or candidate. In normal operation, only one leader and the others followers. Followers only respond to leader and candidates. Leader handles all the client requests. If a client contacts a follower, the follower will redirects it to the leader. Candidates work when electing a new leader.

Time is divided into terms, and each term begins with election. After election, the leader works for the rest of the term. A new election will begin shortly after a split vote. Raft ensures at most one leader in a given term.

Different severs may observer the transitions between terms at different time, and in some situations a server may not observe an election or entire terms. Terms act a logical clock, which allows servers to detect obsolete information such as stale leaders. Each server stores a current-term number, which increases monotonically.

Raft servers communicate use remote procedure calls (RPCs), two type of RPCs is need for the consensus algorithm: RequestVote RPCs and AppendEntries RPCs.