Paxos/Raft/Zab are the different variation of distributed consensus algorithms. They follow two key principles, namely 1) two phase commit, and 2) quorum majority vote. A value is commit only when 1) majority nodes have went through 2-phase commit process.
- There are two roles in the system: proposer, candidate, follower and client. The proposer and follower are the two most important roles in the algorithms.
- Every client can change/set some value through the proposer it connects. If two client want to change same value at the same time, two proposer essentially compete for the majority vote.
- We can think of so called “value” as a particular “key”, whose value we want to change from version X to version X+1.
- Multiple clients/proposals are competing to change the same key’s corresponding value from version X to version X+1 at the same time, which forms a so called “instance” in Paxos algorithm
- Here is good explanation for Paxos algorithm in Chinese. (http://blog.csdn.net/sinat_35172510/article/details/51547388 )
- Raft algorithms simplify Paxos algorithm by requiring there is a Single proposal at any given time in the system. Only this proposer make proposal.
- When leader selection is needed, a random timeout is added to each candidate before it start proposal itself to be the leader. This random timeout helps to minimize competition between different candidate.
Zookeeper atomic broadcasting algorithms (Zab):
- The difference between Zab and Paxos https://cwiki.apache.org/confluence/display/ZOOKEEPER/Zab+vs.+Paxos
Related resources are as follows.