Raftについて簡単に調べた
仕事でCloud Spannerを触ってから、最近よくDBのことを調べています。
分散システムであるCloud Spannerが各ノードでどのように整合性を保っているのか調べていたら、Paxosという分散合意アルゴリズムを使って整合性や可用性を高めていることを知りました。
ただPaxosは結構難しかったので、同じようにetcdやCockroachDB、TiDBなどで採用されている分散合意アルゴリズムのRaftは理解できそうだったので、こっちを調べてみました。
Raftとは
Paxosと同等の性能を備えた、かつ理解しやすいように設計された合意アルゴリズムだそうです。これを使えば合意ベースのシステムが簡単に作れるよということです。
State Machine Replicationというものに基づいていて、全てのステートマシンに対して同じコマンドを同じ順序に実行することで、それらが同じステートになることが保証されるアルゴリズムです。
つまり全てのノードにReplicationすることで、整合性を保ち可用性を高めます。
登場人物
Raftはステートが3つあり、そのうちの1つを担うことができます。この３つのステートを遷移します。
Leader (リーダー)
- クライアントのリクエストを処理する
- Replicationされたステートマシン(Follower)と通信するクラスタ内のLeader
- 現在のLeaderがクラッシュしたり反応しなくなったりしたら、投票が行われる
Candidate (リーダー候補者)
- どのマシンもCandidate(Leader候補者)になることができる
- LeaderになるためにはCandidateにならないといけない
- 過半数の票が集まればLeaderになることができる
- どのCandidateも過半数の票が得られなければもう一度投票が行われる
Follower
- 全てのマシンはFollowerからステートを開始する
- ログエントリを保存する
- LeaderやCandidateからのリクエストに応える
アルゴリズム
Raftアルゴリズムは下記の3つで構成されています。
Periodic Heartbeats (死活監視)
- LeaderからFollowerに定期的にHeartbeatsを送信する
- FollowerはLeaderから一定期間Heartbeatsを受け取らなければLeaderが停止したものとみなして新しい投票を開始する (Election Timeoutと呼ぶ)
- Heartbeatsの実態は空のログ追加メッセージ (
AppendEntriesRPC)
赤のS1がリーダーで各マシンにHeartbeatsを送る図
Leader Election (リーダー選挙)
- 全てのマシンはFollowerから始まる
- 各マシンがランダムで持っているElection Timeoutの期限が切れると、そのマシンはFollowerからCandidateとなって選挙を開始する
- Candidateは他のマシンに
RequestVoteというRPCをブロードキャストする - 過半数の票を集めたらLeaderとして選出される
1. Leaderが不能になりElection Timeoutが発生する図
2. S2マシンのElection TimeoutによりCandidateとなり、各マシンに
RequestVoteRPCが送られる図
3. 投票で過半数得られればS2がLeaderとなる図
Log Replication (ログ複製)
- Leaderは
AppendEntriesというログにエントリを追加するRPCをFollowerに送る AppendEntriesを受け取ったFollowerは自身のログにエントリを追加したり、ログをコミットしたりする- エントリにはindexなどの情報が含まれている
- Leaderが新しいエントリをログに追加する
- LeaderからFollowerに新しいエントリを
AppendEntriesRPCで送る - 過半数からエントリを追加したと応答があれば、Leaderがログをコミット
- 次のRPCをLeaderから受け取ったらFollowerもログをコミットする
感想
調べたら思ったより理解しやすかったです。ただ今回は正常系のみで異常系をちゃんと調べられていません。調べたところ異常系の時の状態遷移が少し難しかったので、別の記事でまた調べて書きたいと思います。
あとGoとかで簡単に実装してみたいです。
