Raft Distributed Consensus Protocol #1

Closed
benbjohnson opened this Issue Aug 2, 2013 · 29 comments

Projects

None yet
@benbjohnson
Owner

Overview

The Raft distributed consensus protocol allows a collection of processes to maintain consistency even in the face of multiple node failure. The two main tenants of the protocol are leader election and log replication.

This visualization will lay out the problem of distributed consensus followed by a general overview of leader election and log replication. It will then follow up with details of Leader Election using best case (Single Candidate) and worst case (Split Vote) scenarios. Then it will show details of Log Replication using the best case (Network OK) and worst case (Network Partitions) scenarios. Finally, it will conclude with additional resources on where to learn more.

URL

http://thesecretlivesofdata.com/raft/

Frames

- [x] What is Distributed Consensus?
- [x] Overview
  - [x] States (Follower, Candidate, Leader)
- [x] Leader Election
  - [x] Election Timeout
  - [x] Candidacy
  - [x] Leadership & heartbeat timeout.
  - [x] Re-election
  - [x] Split Vote
- [ ] Log Replication
  - [X] Complex state machine example.
  - [X] Commitment rules
  - [X] Network Partitions
  - [X] Client reads.
- [X] Conclusion & Additional Resources
@benbjohnson benbjohnson was assigned Aug 2, 2013
@benbjohnson
Owner

Added the "Overview" frame. Still need to add navigation so users can skip ahead.

@benbjohnson
Owner

@vanstee Here's the Github Issue for Raft. I'll post to this ticket as I update the visualization so feel free to add yourself as a watcher. Otherwise I'll ping you when I get it done.

I added an "Overview" section that starts right after the "What is Distributed Consensus" section I sent you earlier.

@philips
philips commented Dec 6, 2013

Looks really great! But, I want arrow keys!

@benbjohnson
Owner

@philips Good call. I added #3 to track it.

@ongardie
ongardie commented Dec 7, 2013

Looks awesome. A few bits that'd be great to add:

  • Replying to the client
  • How clients find the leader
  • Larger, more aggressive state machines
  • Terms
  • Checking whether the candidate's log is up-to-date when granting vote
  • Full commitment rule
@benbjohnson
Owner

@ongardie Thanks, Diego. I added those items to the description. I'll go through the paper again and flesh out some more details for each section as well.

@benbjohnson
Owner

I added a few navigation features:

  1. Left / right arrow keys when the buttons are visible.
  2. Top-level menu drop down.
  3. Deep linking.
  4. Replay (aka "back" button).

There are some timing bugs that came from adding snapshots for replay. I'll get those worked out though.

/cc: @philips @andybons

@andybons

👍

@benbjohnson
Owner

@ongardie I got the start of an actual simulation going in the Leader Election frame:

http://thesecretlivesofdata.com/raft/#election

@ongardie

Nice, that's slick :)

@benbjohnson
Owner

Lots of refactoring to the underlying code and to the playback.js library. Here's the "Leader Election" section:

http://thesecretlivesofdata.com/raft/#election

It's more simulation-like now but I think I still need to make the Split Vote section clearer.

Comment welcome. :)

@stig
stig commented Dec 27, 2013

I found a bug (I think) in the slides. When the follower animation finishes it automatically continues with the candidate animation, but without moving the text to say "candidate". This confused me a bit when I skipped to the next slide.

@ongardie

Really cool, @benbjohnson. The leader election section is definitely shaping up now.

One last thing to mention would be that a server updates its term when it hears a message with a newer term. The animations show it, but it's worth pointing out.

Another thing I'm wondering about is the use of a 4-node cluster to show a split vote. The problem is that we don't expect people to ever run 4-node clusters (since their availability is no better than 3-node clusters), and the definition of majority is less obvious in 4-node clusters (we mean 3 servers but noobs may assume only 2).

In general, you need either 3 servers to time out simultaneously for a split vote, or 2 servers and 1 crash or network anomaly. I agree that showing an example with a 3-node cluster is a bit confusing because there's just not enough servers around to show the pattern, but I don't think switching to a 4-node cluster is best.

How about switching to either a 5-node cluster with 3 candidates, or a 5-node cluster with 2 candidates and 1 crash (this would be identical to the current scenario except with an extra grayed out node)? It may also be illustrative to show how you can't get a split vote with only 2 candidates if everything is going well (one will necessarily get a majority).

@benbjohnson
Owner

@stig I think I fixed what you're talking about. Can you check it out and tell me if it's correct now?

@ongardie I pushed out an initial cut without the 5-node split vote configuration. I mostly wanted to get a first version out. I'll come back and fix it after the next round of feedback from people.

The first draft of the visualization is released: https://twitter.com/secretlivesdata/status/420600602498838529

@benbjohnson benbjohnson closed this Jan 7, 2014
@benbjohnson
Owner

NOTE: I closed the issue for this release but feel free to continue to add additional comments.

@seguer
seguer commented Jan 7, 2014

Does the raft protocol outline how clients are meant to find and then interact with leaders? For example, if a client is sending messages to a node that was leader, but becomes a follower after an election, the client needs to know where to send future messages.

@ebroder
ebroder commented Jan 8, 2014

This is really awesome! I've sent this around to the rest of my team.

I don't know how you're scoping this particular visualization, but I would have enjoyed more of a discussion on why distributed consensus algorithms are difficult. In the awesome future where everyone just accepts that Raft is the way and the light, that might not be needed, but in the mean time I think there's potentially value to explaining why you should use Raft instead of developing your own (undoubtedly wrong) consensus algorithm.

@benbjohnson
Owner

@seguer Each node has the current leader that it knows about. If a client sends a request to a follower then it will be denied and it will be notified what the current leader is. I was debating whether to include this point in the visualization because I don't want to overload people with information but I've heard that question from a few people so I'll add it in.

@ebroder Thanks! The scope for the visualization was fuzzy. I was mostly trying to explore what a semi-interactive visualization of a distributed system would look like so I went with what I knew best (Raft). One of the hardest parts has been trying to figure out what to put in and what to keep out. Too much information and it's confusing but too little and people don't get a full understanding.

I think the understanding behind why distributed consensus is difficult is a more general problem. I'd like to visualize some other consensus algorithms (Paxos, ZAB) so I may leave these bigger questions as a separate visualization entirely.

@TheWinch

One of the cleanest presentation on distributed consensus I've seen so far! I have 2 questions however:

  • in the split brain scenario, how can node B become a leader of the minority, since it never receives a majority of voters for itself? In my understanding it should just be stuck in election phase, shouldn't it?
  • likewise when the healing occurs, how does B know about the "higher election term"? In your example the terms are the same in both partitions ("2") so maybe a bit of explanation is needed here

I'de like to contribute on the Paxos visualization since I know quite well the algorithm, and I'm working also on a ZAB explanation. How can I help?

@benbjohnson
Owner

@TheWinch To answer your questions:

in the split brain scenario, how can node B become a leader of the minority, since it never receives a majority of voters for itself? In my understanding it should just be stuck in election phase, shouldn't it?

Node B is the leader before the split happens so it stays the leader. However, it can't communicate to a quorum so it's ineffective and can't commit any log entries. You can also implement Raft so that the leader times out if it doesn't hear from a quorum for an election timeout.

likewise when the healing occurs, how does B know about the "higher election term"? In your example the terms are the same in both partitions ("2") so maybe a bit of explanation is needed here

You're right. That could have been clearer. When it receives an AppendEntries request from the new leader or when it tries to send an AppendEntries request and receives a response from any node in the new election term it will know about the new term and step down.

I had a lot of fun building the Raft implementation but it was really time consuming. I'm swamped right now so I don't have the bandwidth to do any additional implementations right now. I'll let you know if I start another one in the future.

@erikbgithub

Sorry if another person asked this before. I'm reading this while working, so I don't have the time to get into it as deep as I like.

The question is this: What happens if I have an equal split between 8 nodes? Inside their subnet they could get a majority (Is that enough?). But neither can achieve a global majority (Do they even know how many nodes they are globally? I haven't seen a request that collects all the nodes). What happens now when two clients send different requests to the two leaders?

@benbjohnson
Owner

@erikb85

What happens if I have an equal split between 8 nodes? Inside their subnet they could get a majority (Is that enough?). But neither can achieve a global majority (Do they even know how many nodes they are globally?

Every node knows what nodes exist in the cluster. The 4-4 split would mean that neither group could achieve cluster majority so no leader could be elected and the cluster would be unavailable.

What happens now when two clients send different requests to the two leaders?

Write requests to the old leader would not be able to replicate to a majority so they would hang until the leader steps down and then an error would be returned. The new leader would be able to complete the write request since it can connect to a majority.

If you want consistent reads, you'll need to send your read through the leader. That's a fairly nuanced topic. There's details in the Raft paper and @aphyr did a great write up of all this on his blog:

http://aphyr.com/posts/316-call-me-maybe-etcd-and-consul

@GauravBuche

Excellent !

It makes things very clear. The way you have covered essential scenarios is amazing.

Thanks !

@lusitania

Some feedback:

  • "Leader election" is missing the back button
  • A "skip animation" would be nice if you wanted to navigate to a particular point in the presentation
  • Also animations don't continue in background.
  • The nav links aren't working when selecting them backwards, i.e. replication -> election
  • I tried to review the last slide (4 nodes) in election but still don't get it entirely (can't go back to check again, too annoyed to skip through all slides again)
  • The continue button is visible but not functional while animation proceeds (partition scenario)
  • The partition isn't visible in a replay
  • Client notification differs between single and multi leader/client scenario: in the first scenario client confirmation is sent prior commit, in partition it is sent post commit. I assume the later is correct (although I've seen both schemes used in practice).
@xuanyuanking

What a wonderful job! It make the algorithms clear to understand, do we have other algorithms to show? I want join in. :)

@davidxia
davidxia commented Jan 7, 2016

It'd be nice to be able to step back. Great visualization overall!

@moremoretree

wonderful job! It's woud be better to show paxos algorithm in this method 👍

@angusng
angusng commented Jul 12, 2016

Great work! Very easy to understand. Keep up.
Suggestion - An step back button/arrow will be great.

@tobyforever

I thought it was prerecorded animation, and then I find out it is dynamic simulation with JS. You are amazing! keep it up! by the way I wonder if I can translate your work into Chinese (I am a developer in China ).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment