Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Consensus: An Introduction to Raft
Search
Patrick Van Stee
July 23, 2013
Programming
22
2.9k
Consensus: An Introduction to Raft
Patrick Van Stee
July 23, 2013
Tweet
Share
More Decks by Patrick Van Stee
See All by Patrick Van Stee
Raft: Consensus for Rubyists
vanstee
140
7k
Elixir and Ecto
vanstee
5
930
Bootstrap
vanstee
8
780
HTTP API Design for iOS Applications
vanstee
11
630
Convergent Replicated Data Types
vanstee
4
750
Pour Over Brewing Method
vanstee
1
340
Celluloid & DCell
vanstee
4
540
Map Reduce & Ruby
vanstee
10
790
Other Decks in Programming
See All in Programming
Javaのルールをねじ曲げろ!禁断の操作とその代償から学ぶメタプログラミング入門 / A Guide to Metaprogramming: Lessons from Forbidden Techniques and Their Price
nrslib
3
2k
複数アプリケーションを育てていくための共通化戦略
irof
10
4k
アンドパッドの Go 勉強会「 gopher 会」とその内容の紹介
andpad
0
250
Haskell でアルゴリズムを抽象化する / 関数型言語で競技プログラミング
naoya
17
4.8k
型付きアクターモデルがもたらす分散シミュレーションの未来
piyo7
0
800
GoのGenericsによるslice操作との付き合い方
syumai
2
670
イベントストーミングから始めるドメイン駆動設計
jgeem
4
870
関数型まつりレポート for JuliaTokai #22
antimon2
0
130
Effect の双対、Coeffect
yukikurage
5
1.4k
生成AIコーディングとの向き合い方、AIと共創するという考え方 / How to deal with generative AI coding and the concept of co-creating with AI
seike460
PRO
1
320
実践ArchUnit ~実例による検証パターンの紹介~
ogiwarat
2
280
KotlinConf 2025 現地参加の土産話
n_takehata
0
100
Featured
See All Featured
Gamification - CAS2011
davidbonilla
81
5.3k
Why Our Code Smells
bkeepers
PRO
337
57k
A designer walks into a library…
pauljervisheath
206
24k
Git: the NoSQL Database
bkeepers
PRO
430
65k
Stop Working from a Prison Cell
hatefulcrawdad
270
20k
Imperfection Machines: The Place of Print at Facebook
scottboms
267
13k
Building Better People: How to give real-time feedback that sticks.
wjessup
367
19k
Optimizing for Happiness
mojombo
379
70k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
252
21k
Automating Front-end Workflow
addyosmani
1370
200k
[RailsConf 2023] Rails as a piece of cake
palkan
55
5.6k
4 Signs Your Business is Dying
shpigford
184
22k
Transcript
Consensus An Introduction to Raft
con·sen·sus /kənˈsensəs/ Agreeing upon state across distributed processes even in
the presence of failures.
Problem • Distributed System • Consistency • Partition tolerance
Solution • Quorum • Replicated State Machines
Consensus Data —
We are sacrificing Availability
Why not Paxos? • Difficult to understand • Not practical
enough to implement
Raft A Practical Paxos
Components • Consensus Module • State Machine • Log
Consensus Module • Roles: Leader, Follower, and Candidate • Time
is divided into Terms • Commands: RequestVote and AppendEntries
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
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
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.
Example Happy Log Entry
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: []
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 ˒
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
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
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
Example Sad Log Entry
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: []
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 ˒
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
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
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
Example Leader Failure
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: []
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: []
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: []
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: []
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: []
Extras • Log safety and compaction • Cluster changes
Real-life Application • Distributed lock server • Configuration management •
Background job storage
Smart People • Raft Paper by Diego Ongaro and John
Ousterhout • Raft Implementation • ThinkDistributed