Raft Distributed Consensus Protocol
benbjohnson opened this issue ยท 63 comments
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
Added the "Overview" frame. Still need to add navigation so users can skip ahead.
@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.
Looks really great! But, I want arrow keys!
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
@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.
๐
@ongardie I got the start of an actual simulation going in the Leader Election frame:
Nice, that's slick :)
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. :)
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.
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).
@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
NOTE: I closed the issue for this release but feel free to continue to add additional comments.
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.
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.
@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.
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?
@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.
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?
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:
Excellent !
It makes things very clear. The way you have covered essential scenarios is amazing.
Thanks !
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).
What a wonderful job! It make the algorithms clear to understand, do we have other algorithms to show? I want join in. :)
It'd be nice to be able to step back. Great visualization overall!
wonderful job! It's woud be better to show paxos algorithm in this method ๐
Great work! Very easy to understand. Keep up.
Suggestion - An step back button/arrow will be great.
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 ).
I really liked the simulation! I think it would be clearer if the back arrow said < Previous and the next arrow said Next >. The back arrow is currently the refresh button, and I was a bit confused about what it did.
very great
I hava a question ใif cluster hava 9 machine and then splite to 3-3-3 ใwhat happend ๏ผ
@myonlyzzy If you don't have a quorum (i.e. at least 5 nodes) connected in a group then you won't be able to write entries to your log. You'll lose availability until at least a quorum is connected again.
For example, if you had 9 machines and had a split of 5-2-2 then the group of 5 would still continue to work.
Great animation! As others have mentioned, it would be nice to have navigation. Esp in the Leader Election section, some of the slides went by too fast and I would have liked to go back and review it.
So impressed animation, very great , could I download it from somewhere?
Thanks, for your great work: I love it! Maybe add deep linking by changing the hash in the URL between lessons/chapters. This would make it easier to continue reading after the browser had to reload the page and it would ease citation in blog posts.
That is fantastic work!
Love to have option to step back too(reset current, and one presentation step back).
Great
need backward button๏ผthanks!!
so great work, it will be perfect if leader election and log replication chapters have backward button.
I have some questions about the following sentences:
A client sends a change to the leader , the change is appended to the leader's log.
Then the change is sent to the followers on the Next HeartBeat.
Why on the next heartbeat ? If the clients change the system, we have to wait for the next heartbeat to finish the change? How to make sure the high system perform?
The back button isn't available throughout the entire tutorial (it disappears when we get to the section on Leader Election). Additionally, I would appreciate a bit more explanation as to how nodes keep track of the current election term.
Great work! Thanks!
Need backward button in the last pages.
Just wanted to say you are a hero! Kudos to you for this AMAZING visualisation :) Really waiting for the next ones
Great Visualization! Kudos for the team for spreading knowledge. BTW which tool is used for presentation? I am also looking for similar tool. Thanks in advance
Thank you.
Thank you for the very helpful explanation, I thought I'd let you know that the link to the raft paper in the conclusion is broken, but the paper is available at https://raft.github.io/raft.pdf
this is awesome! thank you for your work
@monotypical Thanks for letting me know. The link's been updated. ๐
Congratullations, excellent initiative. I suggest to out a menu on left side, because I want to view again some views and it was impossible, just restart process (mayce back button can work, but I can not use it) It is the best resourse I see to undertabd raft. Thank you very much
@benbjohnson great work ๐
@benbjohnson great work bro, you made it easy for us. But may be you forgot to add the "go back to previous page" feature on the pages of chapter "Leader Election" and after.
Great work. Extremely easy to understand.
Please add a back button as well.
Great work
Awesome๐ easy to understand, open to share, thank you!
After reading raft lecture, its so confusal. But this annimation show really does great help for me to comprehend the whole flow of Raft! Brilliant!
Thanks for the developer!
World class how you break down a rather complex algorithm into well explained (and well understandable) smaller steps. Really enjoy this documentation/tutorial, great teaching. Like @ongardie I wonder how does the client know who is the leader? Does it just communicate to any node and the node then replies who the current leader is and then the client resends its request to the leader?
In a scenario where A is the leader and B and C followers and a client now sends a message to A, say "x = 8" and the following happens:
A adds uncommited "x = 8" and notifies B and C
B + C add uncommited "x = 8" and notify A that they got the instruction/message/transaction
A commits "x = 8" and notifies B and C but right then a network split occurs and A cannot reach B and C anymore
does A then roll back "x = 8" to uncommited?
Greate demonstration, adding an option to go to specific step would be great.
Back button to previous step please!
Nice work. And I like that sugggestion re: having a Back button, and please arrange for that Back button as well as the Continue button to have one static, predictable location (like top-right corner) rather than having them appear at different locations on the rendered page that depend on other page characteristics/variables. Thx!
Just went through https://thesecretlivesofdata.com/raft/. Thanks for creating this, gives very clear understanding regarding the RAFT protocol covering various scenarios for leader election and WAL replication ๐ฏ
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:
Raft explanation was excellent. Thanks ! Looking forward for new concepts to be implemented with
The Secret Lives of Data :))