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.8k
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
860
Bootstrap
vanstee
8
730
HTTP API Design for iOS Applications
vanstee
11
570
Convergent Replicated Data Types
vanstee
4
700
Pour Over Brewing Method
vanstee
1
310
Celluloid & DCell
vanstee
4
500
Map Reduce & Ruby
vanstee
10
730
Other Decks in Programming
See All in Programming
開発者とQAの越境で自動テストが増える開発プロセスを実現する
92thunder
1
180
menu基盤チームによるGoogle Cloudの活用事例~Application Integration, Cloud Tasks編~
yoshifumi_ishikura
0
110
モバイルアプリにおける自動テストの導入戦略
ostk0069
0
110
【re:Growth 2024】 Aurora DSQL をちゃんと話します!
maroon1st
0
770
Effective Signals in Angular 19+: Rules and Helpers @ngbe2024
manfredsteyer
PRO
0
130
The Efficiency Paradox and How to Save Yourself and the World
hollycummins
1
440
ドメインイベント増えすぎ問題
h0r15h0
1
260
RWC 2024 DICOM & ISO/IEC 2022
m_seki
0
210
17年周年のWebアプリケーションにTanStack Queryを導入する / Implementing TanStack Query in a 17th Anniversary Web Application
saitolume
0
250
命名をリントする
chiroruxx
1
390
Beyond ORM
77web
4
480
PHPとAPI Platformで作る本格的なWeb APIアプリケーション(入門編) / phpcon 2024 Intro to API Platform
ttskch
0
170
Featured
See All Featured
We Have a Design System, Now What?
morganepeng
51
7.3k
Producing Creativity
orderedlist
PRO
341
39k
Exploring the Power of Turbo Streams & Action Cable | RailsConf2023
kevinliebholz
28
4.4k
The Art of Programming - Codeland 2020
erikaheidi
53
13k
VelocityConf: Rendering Performance Case Studies
addyosmani
326
24k
The MySQL Ecosystem @ GitHub 2015
samlambert
250
12k
Rebuilding a faster, lazier Slack
samanthasiow
79
8.7k
Into the Great Unknown - MozCon
thekraken
33
1.5k
How GitHub (no longer) Works
holman
311
140k
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
656
59k
Building Your Own Lightsaber
phodgson
103
6.1k
Designing Dashboards & Data Visualisations in Web Apps
destraynor
229
52k
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