Raft Distributed Consensus Protocol

[benbjohnson]

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]

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

[benbjohnson]

@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]

Looks really great! But, I want arrow keys!

[benbjohnson]

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

[ongardie]

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]

@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]

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]

@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]

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]

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]

@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