Distributed Systems Consensus: Raft Protocol

Raft

A consensus protocol in a distributed system

Raft Applications

  • Consul
  • etcd
  • InfluxDB

A naive explanation of Raft is as follows:

Fundamental Idea

  • Replicated logs
  • Leader
  • Follwers
  • Candidates

Leader

The leader serves writes and the client gets an ack after reliably storing the write with followers.
Each follower expects a heartbeat from the leader. If no heartbeat, a follower chooses to be a leader and ask for majority votes.

Log Replication

Each change to the system goes through the leader. There are three phases of a commit:

  1. The leader appends the change in its log. A log entry has a term number & an index.
  2. It then sends the change to followers.
  3. A follower applies the change(not commit) in its log and ack the leader.
  4. If the leader gets acknowledgment from the majority of the followers, leader commits the change and acknowledges the client.
  5. In the next heartbeat, the leader notifies followers.
  6. Followers apply the change.

Leader Election

  1. Each leader gets a term. The term remains a unique, non-decreasing number in the cluster. The term number increases with each successful leader election.
  2. A node can vote for only one candidate node in a term.
  3. A node votes for a candidate whose log is at least the same index.
  4. The candidate with maximum vote wins.

Network Partition

The leader with a higher term always wins. If there was a leader in a partition, the leader steps down and sync its log with the winner leader.

References

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

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

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: