Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Raft: The Understandable Distributed Consensus ...

benbjohnson
September 20, 2013

Raft: The Understandable Distributed Consensus Protocol

Raft presentation at Strange Loop 2013.

Video: http://www.infoq.com/presentations/raft

This work is licensed under a Creative Commons Attribution 4.0 International License.

benbjohnson

September 20, 2013
Tweet

More Decks by benbjohnson

Other Decks in Technology

Transcript

  1. Paxos In A Nutshell Client Proposer Acceptor Acceptor Acceptor Proposer

    tells Acceptors to get ready for a change Ready?
  2. Paxos In A Nutshell Client Proposer Acceptor Acceptor Acceptor Acceptors

    confirm to Proposer that they’re ready Hell yeah!
  3. Paxos In A Nutshell Client Proposer Acceptor Acceptor Acceptor Learner

    Learner Learner Learner Acceptors propagate change to Learners
  4. Paxos In A Nutshell Client Proposer Acceptor Acceptor Acceptor Learner

    Learner Learner Learner Proposer is now recognized as leader Leader
  5. Paxos In A Nutshell Client Proposer Acceptor Acceptor Acceptor Learner

    Learner Learner Learner Repeat for every new change to the system Leader
  6. C2 F1 F1 Leader Election t(ms) 0 200 400 600

    800 1000 Request Vote 150ms Request Vote (Fails) One follower becomes a candidate after an election timeout and requests votes
  7. C2 F2 F1 Leader Election t(ms) 0 200 400 600

    800 1000 Grant Vote 155ms Candidate receives one vote from a peer and one vote from self
  8. L2 F2 F2 Leader Election t(ms) 0 200 400 600

    800 1000 156ms Two votes is a majority so candidate becomes leader
  9. C2 F1 C2 Leader Election t(ms) 0 200 400 600

    800 1000 F1 Request Vote Request Vote 150ms Two followers become candidates simultaneously and begin requesting votes
  10. C2 F2 C2 Leader Election t(ms) 0 200 400 600

    800 1000 F2 Vote Granted Vote Granted 155ms Each candidate receives a vote from themselves and from one peer
  11. C2 F2 C2 Leader Election t(ms) 0 200 400 600

    800 1000 F2 Request Vote 156ms Each candidate requests a vote from a peer who has already voted
  12. C2 F2 C2 Leader Election t(ms) 0 200 400 600

    800 1000 F2 Vote Denied 160ms Vote requests are denied because the follower has already voted
  13. C2 F2 C2 Leader Election t(ms) 0 200 400 600

    800 1000 F2 Request Vote 161ms Candidates try to request votes from each other
  14. C2 F2 C2 Leader Election t(ms) 0 200 400 600

    800 1000 F2 Vote Denied 165ms Vote requests are denied because candidates voted for themselves
  15. C2 F2 C2 Leader Election t(ms) 0 200 400 600

    800 1000 F2 200ms Candidates wait for a randomized election timeout to occur (150ms - 300ms)
  16. C2 F2 C2 Leader Election t(ms) 0 200 400 600

    800 1000 F2 250ms Still waiting...
  17. C3 F2 C2 Leader Election t(ms) 0 200 400 600

    800 1000 F2 300ms Request Vote Request Vote One candidate begins election term #3
  18. L3 F3 C2 Leader Election t(ms) 0 200 400 600

    800 1000 F3 305ms Vote Granted Vote Granted Candidate receives vote from itself and two peer votes so it becomes leader for election term #3
  19. L3 F3 C3 Leader Election t(ms) 0 200 400 600

    800 1000 F3 306ms Request Vote Request Vote Second candidate doesn’t know first candidate won the term and begins requesting votes
  20. L3 F3 C3 Leader Election t(ms) 0 200 400 600

    800 1000 F3 306ms Vote Denied Vote Denied Peers already voted so votes are denied
  21. L3 F3 F3 Leader Election t(ms) 0 200 400 600

    800 1000 F3 310ms Leader notifies peers of election and other candidate steps down
  22. L1 F1 F1 Log Replication t(ms) 0 200 400 600

    800 1000 0ms <“”> <“”> <“”>
  23. L1 F1 F1 Log Replication t(ms) 0 200 400 600

    800 1000 10ms 1 “sally” <“”> <“”> <“”> A new uncommitted log entry is added to the leader
  24. L1 F1 F1 Log Replication t(ms) 0 200 400 600

    800 1000 20ms <“”> <“”> <“”> 1 “sally” 1 “sally” 1 “sally” Append Entries Append Entries At the next heartbeat, the log entry is replicated to followers
  25. L1 F1 F1 Log Replication t(ms) 0 200 400 600

    800 1000 OK <“sally”> <“”> <“”> 1 “sally” 1 “sally” 1 “sally” 22ms A majority of nodes have written the log entry written to disk so it becomes committed
  26. L1 F1 F1 Log Replication t(ms) 0 200 400 600

    800 1000 <“sally”> <“”> <“”> 1 “sally” 1 “sally” 1 “sally” OK 25ms
  27. L1 F1 F1 Log Replication t(ms) 0 200 400 600

    800 1000 <“sally”> <“sally”> <“sally”> 1 “sally” 1 “sally” 1 “sally” Append Entries Append Entries 40ms At the next heartbeat, the leader notifies followers of updated committed entries
  28. L1 F1 F1 Log Replication t(ms) 0 200 400 600

    800 1000 <“sally”> <“sally”> <“sally”> 1 “sally” 1 “sally” 1 “sally” 50ms
  29. L1 F1 F1 Log Replication t(ms) 0 200 400 600

    800 1000 <“sally”> <“sally”> <“sally”> 1 “sally” 1 “sally” 1 “sally” Append Entries Append Entries 60ms At the next heartbeat, no new log information is sent
  30. L1 F1 F1 Log Replication t(ms) 0 200 400 600

    800 1000 <“sally”> <“sally”> <“sally”> 1 “sally” 1 “sally” 1 “sally” 70ms
  31. L1 F1 F1 Log Replication t(ms) 0 200 400 600

    800 1000 1 “sally” 2 “bob” 1 “sally” 1 “sally” <“sally”> <“sally”> <“sally”> 75ms A new uncommitted log entry is added to the leader
  32. L1 F1 F1 Log Replication t(ms) 0 200 400 600

    800 1000 <“sally”> <“sally”> <“sally”> 1 “sally” 2 “bob” 1 “sally” 2 “bob” 1 “sally” 2 “bob” Append Entries Append Entries 80ms At the next heartbeat, the entry is replicated to the followers
  33. L1 F1 F1 Log Replication t(ms) 0 200 400 600

    800 1000 OK <“bob”> <“sally”> <“sally”> 1 “sally” 2 “bob” 1 “sally” 1 “sally” OK 82ms The entry is committed once the followers acknowledge the request
  34. L1 F1 F1 Log Replication t(ms) 0 200 400 600

    800 1000 <“bob”> <“bob”> <“bob”> 1 “sally” 2 “bob” 1 “sally” 2 “bob” 1 “sally” 2 “bob” Append Entries Append Entries 100ms At the next heartbeat, the leader notifies the followers of the new committed entry
  35. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 0ms <“”> <“”> F1 <“”> F1 <“”> F1 <“”>
  36. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 10ms 1 “sally” <“”> <“”> F1 <“”> F1 <“”> F1 <“”> A new uncommitted log entry is added to the leader
  37. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 20ms 1 “sally” 1 “sally” <“”> <“”> F1 1 “sally” <“”> F1 1 “sally” <“”> F1 1 “sally” <“”> Append Entries On the next heartbeat, the entry is replicated to the followers
  38. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 25ms 1 “sally” 1 “sally” <“sally”> <“”> F1 1 “sally” <“”> F1 1 “sally” <“”> F1 1 “sally” <“”> OK The followers acknowledge the entry and the entry is committed
  39. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 40ms 1 “sally” 1 “sally” <“sally”> <“sally”> F1 1 “sally” <“sally”> F1 1 “sally” <“sally”> F1 1 “sally” <“sally”> Append Entries On the next heartbeat, the committed entry is replicated to the followers
  40. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 1 “sally” 1 “sally” <“sally”> <“sally”> F1 1 “sally” <“sally”> F1 1 “sally” <“sally”> F1 1 “sally” <“sally”> 50ms
  41. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 1 “sally” 1 “sally” <“sally”> <“sally”> F1 1 “sally” <“sally”> F1 1 “sally” <“sally”> F1 1 “sally” <“sally”> A network partition makes a majority of nodes inaccessible from the leader 60ms
  42. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 1 “sally” 2 “bob” 1 “sally” <“sally”> <“sally”> F1 1 “sally” <“sally”> F1 1 “sally” <“sally”> F1 1 “sally” <“sally”> A new log entry is added to the leader 70ms
  43. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 1 “sally” 2 “bob” 1 “sally” 2 “bob” <“sally”> <“sally”> F1 1 “sally” <“sally”> F1 1 “sally” <“sally”> F1 1 “sally” <“sally”> The leader replicates the entry to the only accessible follower Append Entries 80ms
  44. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 1 “sally” 2 “bob” 1 “sally” 2 “bob” <“sally”> <“sally”> F1 1 “sally” <“sally”> F1 1 “sally” <“sally”> F1 1 “sally” <“sally”> The follower acknowledges the entry but there is not a quorum OK 85ms
  45. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 1 “sally” 2 “bob” 1 “sally” 2 “bob” <“sally”> <“sally”> F1 1 “sally” <“sally”> F1 1 “sally” <“sally”> F1 1 “sally” <“sally”> 90ms
  46. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 1 “sally” 2 “bob” 1 “sally” 2 “bob” <“sally”> <“sally”> C2 1 “sally” <“sally”> F1 1 “sally” <“sally”> F1 1 “sally” <“sally”> After an election timeout, one disconnected follower becomes a candidate Request Vote 190ms
  47. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 1 “sally” 2 “bob” 1 “sally” 2 “bob” <“sally”> <“sally”> L2 1 “sally” <“sally”> F2 1 “sally” <“sally”> F2 1 “sally” <“sally”> The candidate receives a majority of votes and becomes a leader Vote Granted 195ms
  48. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 1 “sally” 2 “bob” 1 “sally” 2 “bob” <“sally”> <“sally”> L2 1 “sally” <“sally”> F2 1 “sally” <“sally”> F2 1 “sally” <“sally”> 200ms
  49. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 1 “sally” 2 “bob” 1 “sally” 2 “bob” <“sally”> <“sally”> L2 1 “sally” 2 “tom” <“sally”> F2 1 “sally” <“sally”> F2 1 “sally” <“sally”> A log entry is added to the new leader 210ms
  50. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 1 “sally” 2 “bob” 1 “sally” 2 “bob” <“sally”> <“sally”> L2 1 “sally” 2 “tom” <“sally”> F2 1 “sally” 2 “tom” <“sally”> F2 1 “sally” 2 “tom” <“sally”> The log entry is replicated to the accessible followers Append Entries 220ms
  51. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 1 “sally” 2 “bob” 1 “sally” 2 “bob” <“sally”> <“sally”> L2 1 “sally” 2 “tom” <“tom”> F2 1 “sally” 2 “tom” <“sally”> F2 1 “sally” 2 “tom” <“sally”> A majority of nodes acknowledge the entry so it becomes committed OK 225ms
  52. Append Entries L1 F1 Log Replication t(ms) 0 200 400

    600 800 1000 1 “sally” 2 “bob” 1 “sally” 2 “bob” <“sally”> <“sally”> L2 1 “sally” 2 “tom” <“tom”> F2 1 “sally” 2 “tom” <“tom”> F2 1 “sally” 2 “tom” <“tom”> On the next heartbeat, the followers are notified the entry is committed 240ms
  53. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 1 “sally” 2 “bob” 1 “sally” 2 “bob” <“sally”> <“sally”> L2 1 “sally” 2 “tom” <“tom”> F2 1 “sally” 2 “tom” <“tom”> F2 1 “sally” 2 “tom” <“tom”> 250ms
  54. L1 F1 Log Replication t(ms) 0 200 400 600 800

    1000 1 “sally” 2 “bob” 1 “sally” 2 “bob” <“sally”> <“sally”> L2 1 “sally” 2 “tom” <“tom”> F2 1 “sally” 2 “tom” <“tom”> F2 1 “sally” 2 “tom” <“tom”> The network recovers and there is no longer a partition 255ms
  55. Append Entries L1 F1 Log Replication t(ms) 0 200 400

    600 800 1000 1 “sally” 2 “bob” 1 “sally” 2 “bob” <“sally”> <“sally”> L2 1 “sally” 2 “tom” <“tom”> F2 1 “sally” 2 “tom” <“tom”> F2 1 “sally” 2 “tom” <“tom”> The new leader sends a heartbeat on the next heartbeat timeout 260ms
  56. Append Entries F2 F2 Log Replication t(ms) 0 200 400

    600 800 1000 1 “sally” 2 “bob” 1 “sally” 2 “bob” <“sally”> <“sally”> L2 1 “sally” 2 “tom” <“tom”> F2 1 “sally” 2 “tom” <“tom”> F2 1 “sally” 2 “tom” <“tom”> The leader of term #1 steps down after seeing a new leader in term #2 260ms
  57. Append Entries F2 F2 Log Replication t(ms) 0 200 400

    600 800 1000 1 “sally” 1 “sally” <“sally”> <“sally”> L2 1 “sally” 2 “tom” <“tom”> F2 1 “sally” 2 “tom” <“tom”> F2 1 “sally” 2 “tom” <“tom”> Uncommitted entries from disconnected nodes are discarded 260ms
  58. Append Entries F2 F2 Log Replication t(ms) 0 200 400

    600 800 1000 1 “sally” 2 “tom” 1 “sally” 2 “tom” <“tom”> <“tom”> L2 1 “sally” 2 “tom” <“tom”> F2 1 “sally” 2 “tom” <“tom”> F2 1 “sally” 2 “tom” <“tom”> New log entries are appended to the previously disconnected nodes 260ms
  59. F2 F2 Log Replication t(ms) 0 200 400 600 800

    1000 1 “sally” 2 “tom” 1 “sally” 2 “tom” <“tom”> <“tom”> L2 1 “sally” 2 “tom” <“tom”> F2 1 “sally” 2 “tom” <“tom”> F2 1 “sally” 2 “tom” <“tom”> 260ms
  60. Image Attribution Database designed by Sergey Shmidt from The Noun

    Project Question designed by Greg Pabst from The Noun Project Lock from The Noun Project Floppy Disk designed by Mike Wirth from The Noun Project Movie designed by Anna Weiss from The Noun Project