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.9k
Elixir and Ecto
vanstee
5
910
Bootstrap
vanstee
8
770
HTTP API Design for iOS Applications
vanstee
11
610
Convergent Replicated Data Types
vanstee
4
730
Pour Over Brewing Method
vanstee
1
330
Celluloid & DCell
vanstee
4
530
Map Reduce & Ruby
vanstee
10
770
Other Decks in Programming
See All in Programming
これだけは知っておきたいクラス設計の基礎知識 version 2
masuda220
PRO
24
6.3k
CRE Meetup!ユーザー信頼性を支えるエンジニアリング実践例の発表資料です
tmnb
0
640
タイムゾーンの奥地は思ったよりも闇深いかもしれない
suguruooki
1
620
Empowering Developers with HTML-Aware ERB Tooling @ RubyKaigi 2025, Matsuyama, Ehime
marcoroth
2
390
Optimizing JRuby 10
headius
0
270
Making TCPSocket.new "Happy"!
coe401_
1
560
Defying Front-End Inertia: Inertia.js on Rails
skryukov
0
470
MCP世界への招待: AIエンジニアが創る次世代エージェント連携の世界
gunta
4
900
Chrome Extension Techniques from Hell
moznion
1
160
The Evolution of the CRuby Build System
kateinoigakukun
0
690
「影響が少ない」を自分の目でみてみる
o0h
PRO
2
1.1k
新しいPHP拡張モジュールインストール方法「PHP Installer for Extensions (PIE)」を使ってみよう!
cocoeyes02
0
370
Featured
See All Featured
How STYLIGHT went responsive
nonsquared
99
5.5k
Keith and Marios Guide to Fast Websites
keithpitt
411
22k
Put a Button on it: Removing Barriers to Going Fast.
kastner
60
3.8k
How To Stay Up To Date on Web Technology
chriscoyier
790
250k
Building an army of robots
kneath
304
45k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
135
33k
KATA
mclloyd
29
14k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
52
2.4k
Why You Should Never Use an ORM
jnunemaker
PRO
55
9.3k
The Pragmatic Product Professional
lauravandoore
33
6.5k
Java REST API Framework Comparison - PWX 2021
mraible
30
8.5k
StorybookのUI Testing Handbookを読んだ
zakiyama
29
5.6k
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