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

Consensus: An Introduction to Raft

Avatar for Patrick Van Stee Patrick Van Stee
July 23, 2013
Programming
21
3k

Consensus: An Introduction to Raft

Avatar for Patrick Van Stee

Patrick Van Stee

July 23, 2013
Tweet

More Decks by Patrick Van Stee

See All by Patrick Van Stee
Raft: Consensus for Rubyists
Avatar for Patrick Van Stee vanstee
140
7.2k
Elixir and Ecto
Avatar for Patrick Van Stee vanstee
5
950
Bootstrap
Avatar for Patrick Van Stee vanstee
8
800
HTTP API Design for iOS Applications
Avatar for Patrick Van Stee vanstee
11
650
Convergent Replicated Data Types
Avatar for Patrick Van Stee vanstee
4
780
Pour Over Brewing Method
Avatar for Patrick Van Stee vanstee
1
360
Celluloid & DCell
Avatar for Patrick Van Stee vanstee
4
560
Map Reduce & Ruby
Avatar for Patrick Van Stee vanstee
10
830

Other Decks in Programming

See All in Programming
Developer Joy - The New Paradigm
Avatar for Holly Cummins hollycummins
1
380
Amazon Verified Permissions実践入門 〜Cedar活用とAppSync導入事例/Practical Introduction to Amazon Verified Permissions
Avatar for MURAKAMI Masahiko fossamagna
2
100
なんでRustの環境構築してないのにRust製のツールが動くの？ / Why Do Rust-Based Tools Run Without a Rust Environment?
Avatar for TOMIKAWA Sotaro ssssota
14
47k
alien-signals と自作 OSS で実現する フレームワーク非依存な ロジック共通化の探求 / Exploring Framework-Agnostic Logic Sharing with alien-signals and Custom OSS
Avatar for aose aoseyuu
3
820
エンジニアインターン「Treasure」とHonoの2年、そして未来へ / Our Journey with Hono Two Years at Treasure and Beyond
Avatar for CARTA Engineering carta_engineering
0
460
CSC305 Lecture 10
Avatar for Javier Gonzalez-Sanchez javiergs
PRO
0
320
One Enishi After Another
Avatar for Koji SHIMADA snoozer05
PRO
0
170
マンガアプリViewerの大画面対応を考える
Avatar for kk__777 kk__777
0
420
EMこそClaude Codeでコード調査しよう
Avatar for shibayu36 shibayu36
0
490
SODA - FACT BOOK（JP）
Avatar for SODA inc. sodainc
1
9k
スキーマ駆動で、Zod OpenAPI Honoによる、API開発するために、Hono Takibiというライブラリを作っている
Avatar for N Akita nakita628
0
330
Using Types to Save Your Code's Future
Avatar for Björn Fahller rollbear
0
100

Featured

See All Featured
Building Adaptive Systems
Avatar for Chris Keathley keathley
44
2.8k
Speed Design
Avatar for Sergey Chernyshev sergeychernyshev
32
1.2k
What’s in a name? Adding method to the madness
Avatar for Product Marketing Alliance productmarketing
PRO
24
3.7k
A Modern Web Designer's Workflow
Avatar for Chris Coyier chriscoyier
697
190k
Helping Users Find Their Own Way: Creating Modern Search Experiences
Avatar for Dan Newman danielanewman
31
2.9k
JavaScript: Past, Present, and Future - NDC Porto 2020
Avatar for David Neal reverentgeek
52
5.7k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
Avatar for Eileen M. Uchitelle eileencodes
140
34k
GitHub's CSS Performance
Avatar for Jon Rohan jonrohan
1032
470k
XXLCSS - How to scale CSS and keep your sanity
Avatar for Zaharenia Atzitzikaki sugarenia
249
1.3M
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
Avatar for Sam Stephenson sstephenson
162
15k
How Fast Is Fast Enough? [PerfNow 2025]
Avatar for Tammy Everts tammyeverts
2
180
CSS Pre-Processors: Stylus, Less & Sass
Avatar for Bermon Painter bermonpainter
359
30k

Transcript

  1. Consensus An Introduction to Raft

  2. con·sen·sus /kənˈsensəs/ Agreeing upon state across distributed processes even in

    the presence of failures.

  3. Problem • Distributed System • Consistency • Partition tolerance

  4. Solution • Quorum • Replicated State Machines

  5. Consensus Data —

  6. We are sacrificing Availability

  7. Why not Paxos? • Difficult to understand • Not practical

    enough to implement

  8. Raft A Practical Paxos

  9. Components • Consensus Module • State Machine • Log

  10. Consensus Module • Roles: Leader, Follower, and Candidate • Time

    is divided into Terms • Commands: RequestVote and AppendEntries

  11. Leader Accept commands from clients, commit entries, and send heartbeats

    Follower Replicate state from leaders and vote for candidates Candidate Start and handle leader elections

  12. Follower Candidate Leader Times out, Starts election Times out, Restarts

    election Wins election Discovers new leader, Steps down Discovers current leader or new leader, Steps down

  13. 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.

  14. Example Happy Log Entry

  15. A B C Role: Leader Term: 1 Commit Index: 0

    Log: [] Role: Follower Term: 1 Commit Index: 0 Log: [] Role: Follower Term: 1 Commit Index: 0 Log: []

  16. A B C Role: Leader Term: 1 Commit Index: 0

    Log: [˒] Role: Follower Term: 1 Commit Index: 0 Log: [] Role: Follower Term: 1 Commit Index: 0 Log: [] Leader receives command ˒

  17. A B C Role: Leader Term: 1 Commit Index: 0

    Log: [˒] Role: Follower Term: 1 Commit Index: 0 Log: [˒] Role: Follower Term: 1 Commit Index: 0 Log: [˒] Leader sends log entries to followers

  18. A B C Role: Leader Term: 1 Commit Index: 1

    Log: [˒] Role: Follower Term: 1 Commit Index: 0 Log: [˒] Role: Follower Term: 1 Commit Index: 0 Log: [˒] Majority of followers respond with success

  19. A B C Role: Leader Term: 1 Commit Index: 1

    Log: [˒] Role: Follower Term: 1 Commit Index: 1 Log: [˒] Role: Follower Term: 1 Commit Index: 1 Log: [˒] Leader sends commit index to followers and responds to client

  20. Example Sad Log Entry

  21. A B C Role: Leader Term: 1 Commit Index: 0

    Log: [] Role: Follower Term: 1 Commit Index: 0 Log: [] Role: Follower Term: 1 Commit Index: 0 Log: []

  22. A B C Role: Leader Term: 1 Commit Index: 0

    Log: [˒] Role: Follower Term: 1 Commit Index: 0 Log: [] Role: Follower Term: 1 Commit Index: 0 Log: [] Leader receives command ˒

  23. A B C Role: Leader Term: 1 Commit Index: 0

    Log: [˒] Role: Follower Term: 1 Commit Index: 0 Log: [˒] Role: Follower Term: 1 Commit Index: 0 Log: [] Leader sends log entries to followers

  24. A B C Role: Leader Term: 1 Commit Index: 0

    Log: [˒] Role: Follower Term: 1 Commit Index: 0 Log: [˒] Role: Follower Term: 1 Commit Index: 0 Log: [] Majority of followers do not respond

  25. A B C Role: Leader Term: 1 Commit Index: 0

    Log: [˒] Role: Follower Term: 1 Commit Index: 0 Log: [˒] Role: Follower Term: 1 Commit Index: 0 Log: [˒] Leader continues to retry log entry

  26. Example Leader Failure

  27. A B C Role: Leader Term: 1 Commit Index: 0

    Log: [] Role: Follower Term: 1 Commit Index: 0 Log: [] Role: Follower Term: 1 Commit Index: 0 Log: [] D Role: Follower Term: 1 Commit Index: 0 Log: []

  28. A B C Role: Leader Term: 1 Commit Index: 0

    Log: [] Role: Follower Term: 1 Commit Index: 0 Log: [] Role: Follower Term: 1 Commit Index: 0 Log: [] Followers do not receive heartbeat D Role: Follower Term: 1 Commit Index: 0 Log: []

  29. A B C Role: Leader Term: 1 Commit Index: 0

    Log: [] Role: Candidate Term: 2 Commit Index: 0 Log: [] Role: Follower Term: 1 Commit Index: 0 Log: [] First follower to timeout becomes candidate D Role: Follower Term: 1 Commit Index: 0 Log: []

  30. A B C Role: Leader Term: 1 Commit Index: 0

    Log: [] Role: Candidate Term: 2 Commit Index: 0 Log: [] Role: Follower Term: 2 Commit Index: 0 Log: [] Candidate starts election and requests votes D Role: Follower Term: 2 Commit Index: 0 Log: []

  31. A B C Role: Leader Term: 1 Commit Index: 0

    Log: [] Role: Leader Term: 2 Commit Index: 0 Log: [] Role: Follower Term: 2 Commit Index: 0 Log: [] Followers respond with votes D Role: Follower Term: 2 Commit Index: 0 Log: []

  32. Extras • Log safety and compaction • Cluster changes

  33. Real-life Application • Distributed lock server • Configuration management •

    Background job storage

  34. Smart People • Raft Paper by Diego Ongaro and John

    Ousterhout • Raft Implementation • ThinkDistributed