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.8k
Elixir and Ecto
vanstee
5
890
Bootstrap
vanstee
8
750
HTTP API Design for iOS Applications
vanstee
11
590
Convergent Replicated Data Types
vanstee
4
710
Pour Over Brewing Method
vanstee
1
320
Celluloid & DCell
vanstee
4
520
Map Reduce & Ruby
vanstee
10
750
Other Decks in Programming
See All in Programming
Flutter × Firebase Genkit で加速する生成 AI アプリ開発
coborinai
0
160
メンテが命: PHPフレームワークのコンテナ化とアップグレード戦略
shunta27
0
120
一休.com のログイン体験を支える技術 〜Web Components x Vue.js 活用事例と最適化について〜
atsumim
0
480
Honoをフロントエンドで使う 3つのやり方
yusukebe
7
3.3k
データの整合性を保つ非同期処理アーキテクチャパターン / Async Architecture Patterns
mokuo
47
17k
Lottieアニメーションをカスタマイズしてみた
tahia910
0
130
Boost Performance and Developer Productivity with Jakarta EE 11
ivargrimstad
0
270
DROBEの生成AI活用事例 with AWS
ippey
0
130
1年目の私に伝えたい!テストコードを怖がらなくなるためのヒント/Tips for not being afraid of test code
push_gawa
0
150
仕様変更に耐えるための"今の"DRY原則を考える / Rethinking the "Don't repeat yourself" for resilience to specification changes
mkmk884
0
160
ペアーズでの、Langfuseを中心とした評価ドリブンなリリースサイクルのご紹介
fukubaka0825
2
320
Conform を推す - Advocating for Conform
mizoguchicoji
3
690
Featured
See All Featured
What's in a price? How to price your products and services
michaelherold
244
12k
Build your cross-platform service in a week with App Engine
jlugia
229
18k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
193
16k
Side Projects
sachag
452
42k
Exploring the Power of Turbo Streams & Action Cable | RailsConf2023
kevinliebholz
30
4.6k
Navigating Team Friction
lara
183
15k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
30
2.2k
VelocityConf: Rendering Performance Case Studies
addyosmani
328
24k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
27
1.6k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
129
19k
Intergalactic Javascript Robots from Outer Space
tanoku
270
27k
Stop Working from a Prison Cell
hatefulcrawdad
267
20k
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