Understanding Paxos/Raft/Zab Algorithm

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.

Paxos algorithms:

  1. 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.
  2. 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.
  3. We can think of so called “value” as a particular “key”, whose value we want to change from version X to version X+1.
  4. 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
  5. Here is good explanation for Paxos algorithm in Chinese. (http://blog.csdn.net/sinat_35172510/article/details/51547388 )

 

Raft algorithms:

  1. Raft algorithms simplify Paxos algorithm by requiring there is a Single proposal at any given time in the system. Only this proposer make proposal.
  2. 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):

  1. The difference between Zab and Paxos https://cwiki.apache.org/confluence/display/ZOOKEEPER/Zab+vs.+Paxos

 

Related resources are as follows.

Raft:

 

Advertisements
Understanding Paxos/Raft/Zab Algorithm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s