Raft: Consensus for Rubyists

Transcript

1. Raft
   Consensus for Rubyists
   

   View Slide

2. @vanstee
   Big Nerd Ranch
   

   View Slide

3. Coffee Snob Scenario
   

   View Slide

4. Matt Amy
   Kim Dan
   

   View Slide

5. Matt Amy
   Kim Dan
   

   View Slide

6. Matt Amy
   Kim Dan
   Want to
   meet for
   coffee?
   

   View Slide

7. Matt Amy
   Kim Dan
   Totally!
   I’m in.
   zzzzz…
   

   View Slide

8. Matt Amy
   Kim Dan
   Ok, let’s
   meet at
   Octane.
   

   View Slide

9. Matt Amy
   Kim Dan
   Sounds
   good.
   I’ll be
   there.
   …
   

   View Slide

10. Matt Amy
    Kim Dan Who
    wants
    coffee?
    *wakes up
    

    View Slide

11. Matt Amy
    Kim Dan Who
    wants
    coffee?
    

    View Slide

12. Matt Amy
    Kim Dan
    Oh, we’re
    going to
    Octane.
    

    View Slide

13. Delicious Coffee Consensus
    

    View Slide

14. What did we just do?
    

    View Slide

15. • Leader election
    • State replication
    • Partition tolerance
    

    View Slide

16. Now write an algorithm.
    

    View Slide

17. Humans > Computers > Congress
    

    View Slide

18. Why Ruby
    

    View Slide

19. Multiple db servers?
    Multiple app servers?
    Multiple clients?
    

    View Slide

20. Multiple db servers? Distributed
    Multiple app servers?
    Multiple clients?
    

    View Slide

21. Multiple db servers? Distributed
    Multiple app servers? Distributed
    Multiple clients?
    

    View Slide

22. Multiple db servers? Distributed
    Multiple app servers? Distributed
    Multiple clients? Distributed
    

    View Slide

23. If you build webapps,
    you build distributed systems.
    

    View Slide

24. Raft
    

    View Slide

25. @ongardie
    Diego Ongaro
    John Ousterhout
    and
    

    View Slide

26. con·sen·sus
    /kənˈsensəs/
    !
    Agreeing upon state across
    distributed processes even
    in the presence of failures.
    

    View Slide

27. When should I use it?
    

    View Slide

28. • Distributed locks
    • Configuration
    • Background jobs
    

    View Slide

29. Why not Paxos?
    

    View Slide

30. Laying the Groundwork
    

    View Slide

31. {…}
    Log
    State
    Machine
    Consensus
    Module
    

    View Slide

32. Leader
    Follower Follower
    Follower
    

    View Slide

33. Leader
    Follower Follower
    Follower
    

    View Slide

34. Leader
    Follower Follower
    Follower
    

    View Slide

35. Follower
    

    View Slide

36. Leader Election
    Log Replication
    Safety
    

    View Slide

37. Follower Candidate Leader
    

    View Slide

38. Follower Candidate Leader
    

    View Slide

39. Follower Candidate Leader
    Times out,
    Starts election
    

    View Slide

40. Follower Candidate Leader
    Times out,
    Starts election
    Wins election
    

    View Slide

41. Follower Candidate Leader
    Times out,
    Starts election
    Times out,
    Restarts election
    Wins election
    

    View Slide

42. Follower Candidate Leader
    Times out,
    Starts election
    Times out,
    Restarts election
    Wins election
    Discovers current
    or new leader,
    Steps down
    

    View Slide

43. Follower Candidate Leader
    Times out,
    Starts election
    Times out,
    Restarts election
    Wins election
    Discovers new leader,
    Steps down
    Discovers current
    or new leader,
    Steps down
    

    View Slide

44. RequestVote
    Used by candidates to ask for votes during
    an election. Log information included for
    comparison.
    !
    AppendEntries
    Used by leaders to tell followers which
    entries to replicate and commit. Also used
    as a heartbeat to remain leader.
    Follower
    Candidate
    Vote for me please.
    Follower
    Here are some entries for your log.
    Oh, and btw I’m still the leader.
    Leader
    

    View Slide

45. Term
    Higher numbers are used to determine
    leaders and check log entries. The term is
    incremented each time an election is
    started. Any command with an old term is
    ignored.
    Term 1 Term 2 Term 3
    Election Normal Operation Split vote
    

    View Slide

46. Follower
    Follower Follower
    Follower
    

    View Slide

47. Candidate
    Follower Follower
    Follower
    Votes
    Times out,
    starts election
    

    View Slide

48. Candidate
    Follower Follower
    Follower
    Votes
    Votes for self
    

    View Slide

49. Candidate
    Follower Follower
    Follower
    Votes
    Sends out
    RequestVotes
    

    View Slide

50. Candidate
    Follower Follower
    Votes
    Responds
    with success
    

    View Slide

51. Leader
    Follower
    Votes
    Yay! I won!
    Follower
    

    View Slide

52. Leader Election
    Log Replication
    Safety
    

    View Slide

53. Log Entries Explained
    

    View Slide

54. SET X = 1 SET Y = 2 SET Z = 3 SET X = 4 SET X = 5
    1 1 1 2 2
    SET X = 1 SET Y = 2 SET Z = 3 SET X = 4
    1 1 1 2
    Leader
    Follower
    1 2 3 4 5 6
    

    View Slide

55. {
    :entries => [{ 4 => 'SET X = 4' }],
    :term => 1,
    :prev_log_term => 1,
    :prev_log_index => 3,
    :leader_commit => 3,
    :leader_id => '192.168.1.101/7238'
    }
    APPEND ENTRIES EXAMPLE
    

    View Slide

56. SET X = 1 SET Y = 2 SET Z = 3
    1 1 1
    Before
    1 1 1 1
    After
    SET X = 1 SET Y = 2 SET Z = 3 SET X = 4
    1 2 3 4 5 6
    1 2 3 4 5 6
    

    View Slide

57. Log entries are always
    committed in the same order
    and are never uncommitted.
    

    View Slide

58. Happy Log Entry
    

    View Slide

59. Leader
    Follower Follower
    

    View Slide

60. Leader
    Follower Follower
    

    View Slide

61. Leader
    Follower Follower
    

    View Slide

62. Leader
    Follower Follower
    

    View Slide

63. Leader
    Follower Follower
    

    View Slide

64. Sad Log Entry
    

    View Slide

65. Leader
    Follower Follower
    

    View Slide

66. Leader
    Follower Follower
    

    View Slide

67. Leader
    Follower Follower
    

    View Slide

68. Leader
    Follower Follower
    

    View Slide

69. Leader
    Follower Leader
    

    View Slide

70. Leader
    Follower Leader
    

    View Slide

71. Leader
    Follower Leader
    

    View Slide

72. Leader
    Follower Leader
    

    View Slide

73. Leader
    Follower Leader
    

    View Slide

74. Follower
    Follower Follower
    Leader
    

    View Slide

75. Facepalm Log Entry
    

    View Slide

76. Leader
    Follower Follower
    

    View Slide

77. Leader
    Follower Follower
    

    View Slide

78. Leader
    Follower Follower
    

    View Slide

79. Leader
    Follower Follower
    

    View Slide

80. Leader
    Follower Follower
    

    View Slide

81. Leader
    Follower Follower
    

    View Slide

82. Leader
    Follower Leader
    

    View Slide

83. How do we guard against
    losing log entries?
    

    View Slide

84. Leader Election
    Log Replication
    Safety
    

    View Slide

85. Only cast votes for nodes with
    logs that contain at least as
    many entries as your own.
    1
    

    View Slide

86. New leaders must commit a
    log entry form their new term
    before committing old entries.
    2
    

    View Slide

87. Bonus Round
    

    View Slide

88. • Cluster changes
    • Log compaction
    • Client specifics
    

    View Slide

89. Why Ruby
    

    View Slide

90. View Slide

91. Ruby is great for expressing
    complex problems.
    

    View Slide

92. Then why doesn’t the academic
    community love it?
    

    View Slide

93. • Community
    • Understandability
    • Learning Material
    

    View Slide

94. • Read Papers
    • Go To Conferences
    • Talk To People
    

    View Slide

95. Raft Paper
    Raft Implementations
    Raft Website
    ThinkDistributed
    Ricon
    Google Scholar
    

    View Slide

96. Question Time
    Make sure I repeat your questions.
    

    View Slide