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
137
6.7k
Elixir and Ecto
vanstee
5
870
Bootstrap
vanstee
8
740
HTTP API Design for iOS Applications
vanstee
11
580
Convergent Replicated Data Types
vanstee
4
710
Pour Over Brewing Method
vanstee
1
320
Celluloid & DCell
vanstee
4
510
Map Reduce & Ruby
vanstee
10
740
Other Decks in Programming
See All in Programming
自動で //nolint を挿入する取り組み / Gopher's Gathering
utgwkk
1
110
ASP.NET Core の OpenAPIサポート
h455h1
0
130
はてなにおけるfujiwara-wareの活用やecspressoのCI/CD構成 / Fujiwara Tech Conference 2025
cohalz
3
2.9k
サーバーゆる勉強会 DBMS の仕組み編
kj455
1
310
どうして手を動かすよりもチーム内のコードレビューを優先するべきなのか
okashoi
3
910
Lookerは可視化だけじゃない。UIコンポーネントもあるんだ!
ymd65536
1
130
chibiccをCILに移植した結果 (NGK2025S版)
kekyo
PRO
0
160
QA環境で誰でも自由自在に現在時刻を操って検証できるようにした話
kalibora
1
140
CNCF Project の作者が考えている OSS の運営
utam0k
3
450
Внедряем бюджетирование, или Как сделать хорошо?
lamodatech
0
950
asdf-ecspresso作って 友達が増えた話 / Fujiwara Tech Conference 2025
koluku
0
1.5k
盆栽転じて家具となる / Bonsai and Furnitures
aereal
0
2k
Featured
See All Featured
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
251
21k
Into the Great Unknown - MozCon
thekraken
34
1.6k
4 Signs Your Business is Dying
shpigford
182
22k
Writing Fast Ruby
sferik
628
61k
Speed Design
sergeychernyshev
25
740
Scaling GitHub
holman
459
140k
Faster Mobile Websites
deanohume
305
30k
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
113
50k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
33
2k
Building Applications with DynamoDB
mza
93
6.2k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
49k
GitHub's CSS Performance
jonrohan
1030
460k
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