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

Raft: Consensus for Rubyists

Raft: Consensus for Rubyists

Patrick Van Stee

November 09, 2013
Tweet

More Decks by Patrick Van Stee

Other Decks in Programming

Transcript

  1. Raft
    Consensus for Rubyists

    View full-size slide

  2. @vanstee
    Big Nerd Ranch

    View full-size slide

  3. Coffee Snob Scenario

    View full-size slide

  4. Matt Amy
    Kim Dan

    View full-size slide

  5. Matt Amy
    Kim Dan

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

  11. Matt Amy
    Kim Dan Who
    wants
    coffee?

    View full-size slide

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

    View full-size slide

  13. Delicious Coffee Consensus

    View full-size slide

  14. What did we just do?

    View full-size slide

  15. • Leader election
    • State replication
    • Partition tolerance

    View full-size slide

  16. Now write an algorithm.

    View full-size slide

  17. Humans > Computers > Congress

    View full-size slide

  18. Multiple db servers?
    Multiple app servers?
    Multiple clients?

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

  23. @ongardie
    Diego Ongaro
    John Ousterhout
    and

    View full-size slide

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

    View full-size slide

  25. When should I use it?

    View full-size slide

  26. • Distributed locks
    • Configuration
    • Background jobs

    View full-size slide

  27. Why not Paxos?

    View full-size slide

  28. Laying the Groundwork

    View full-size slide

  29. {…}
    Log
    State
    Machine
    Consensus
    Module

    View full-size slide

  30. Leader
    Follower Follower
    Follower

    View full-size slide

  31. Leader
    Follower Follower
    Follower

    View full-size slide

  32. Leader
    Follower Follower
    Follower

    View full-size slide

  33. Leader Election
    Log Replication
    Safety

    View full-size slide

  34. Follower Candidate Leader

    View full-size slide

  35. Follower Candidate Leader

    View full-size slide

  36. Follower Candidate Leader
    Times out,
    Starts election

    View full-size slide

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

    View full-size slide

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

    View full-size slide

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

    View full-size slide

  40. 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 full-size slide

  41. 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 full-size slide

  42. 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 full-size slide

  43. Follower
    Follower Follower
    Follower

    View full-size slide

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

    View full-size slide

  45. Candidate
    Follower Follower
    Follower
    Votes
    Votes for self

    View full-size slide

  46. Candidate
    Follower Follower
    Follower
    Votes
    Sends out
    RequestVotes

    View full-size slide

  47. Candidate
    Follower Follower
    Votes
    Responds
    with success

    View full-size slide

  48. Leader
    Follower
    Votes
    Yay! I won!
    Follower

    View full-size slide

  49. Leader Election
    Log Replication
    Safety

    View full-size slide

  50. Log Entries Explained

    View full-size slide

  51. 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 full-size slide

  52. {
    :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 full-size slide

  53. 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 full-size slide

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

    View full-size slide

  55. Happy Log Entry

    View full-size slide

  56. Leader
    Follower Follower

    View full-size slide

  57. Leader
    Follower Follower

    View full-size slide

  58. Leader
    Follower Follower

    View full-size slide

  59. Leader
    Follower Follower

    View full-size slide

  60. Leader
    Follower Follower

    View full-size slide

  61. Sad Log Entry

    View full-size slide

  62. Leader
    Follower Follower

    View full-size slide

  63. Leader
    Follower Follower

    View full-size slide

  64. Leader
    Follower Follower

    View full-size slide

  65. Leader
    Follower Follower

    View full-size slide

  66. Leader
    Follower Leader

    View full-size slide

  67. Leader
    Follower Leader

    View full-size slide

  68. Leader
    Follower Leader

    View full-size slide

  69. Leader
    Follower Leader

    View full-size slide

  70. Leader
    Follower Leader

    View full-size slide

  71. Follower
    Follower Follower
    Leader

    View full-size slide

  72. Facepalm Log Entry

    View full-size slide

  73. Leader
    Follower Follower

    View full-size slide

  74. Leader
    Follower Follower

    View full-size slide

  75. Leader
    Follower Follower

    View full-size slide

  76. Leader
    Follower Follower

    View full-size slide

  77. Leader
    Follower Follower

    View full-size slide

  78. Leader
    Follower Follower

    View full-size slide

  79. Leader
    Follower Leader

    View full-size slide

  80. How do we guard against
    losing log entries?

    View full-size slide

  81. Leader Election
    Log Replication
    Safety

    View full-size slide

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

    View full-size slide

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

    View full-size slide

  84. • Cluster changes
    • Log compaction
    • Client specifics

    View full-size slide

  85. Ruby is great for expressing
    complex problems.

    View full-size slide

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

    View full-size slide

  87. • Community
    • Understandability
    • Learning Material

    View full-size slide

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

    View full-size slide

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

    View full-size slide

  90. Question Time
    Make sure I repeat your questions.

    View full-size slide