みなさまこんばんわ。
ガンダムベースがついに福岡にもオープンして行ってきましたが、最高でした・・・

さて、実はConsulの概要や機能について発表させてもらったりしてました。
今回は、Consulに使われている技術について自分用に必要なとこだけまとめておこうと思います。
今更となるかもしれないですが、Consulを使っておきながらRaftとGossipの棲み分けがよくわかってなかったので書こうと思いました。

ではでは。
今回の話題は、Raftです。
これは、Consul内部で使われている技術なんですが、
ざっくり言うと、
RaftはServer ModeのConsulで分散KVSを構築するためのアルゴリズムです。
ちなみに、Raftはetcdにも採用されています。
このKVSには、ConsulのCatalogのサービスやノード、DNSの情報が保存されています。 イメージは以下です。

Raft

Raft(Raft Consensus Algorithm)は分散合意アルゴリズムというアルゴリズムなんですね。
Consulの場合だと一貫性を持ったKVSを提供するために使用されています。
Raftの基本実装は以下の通りです。

Raftの基本実装
1. Leader選出
2. ログレプリケーション
3. 安全性の保証


Raftを知るにはこちらの資料がわかりやすいんですが、ざっくりこの基本実装を1つずつ説明していきます。

1. Leader選出

プロセスは以下の3つの状態を持ちます。
・Leader: KVSの更新処理を受け付ける状態
・Follower:Leaderからの更新を受け付ける状態
・Candidate:Leaderになりたい状態

Raftは、1つのLeaderと複数のFollowerを持ちます。
Leaderは、名前の通り先導者ですね。DBクラスターとかでいうMaster的なやつです。
LeaderとFollowerの関係はログレプリケーションの説明で書きます。

1-1. Leaderの選出方法

※ めちゃくちゃわかりやすかったので、こちらのサイトの動画をアニメーションを使わせていただいております。(すいません)

1. サーバは起動直後は、みんなFollowerになっています。

2. Followerはelection timeoutを過ぎると、candidateになります。
Raftには制御用のTimeoutが存在します。
それが、election timeoutです。
candidateになるための、Followerの待機時間で、
タイムアウトは、150ミリ秒から300ミリ秒の間のランダムな値になります。

下記のGIFを見ると、丸の周りで減っていっている部分が、このelection timeoutです。
GIFの中では、Node Bが一番早いですね。(つまり早いもん勝ち)
Node Bは、election timeoutを終えるとcandidateになりました。
3. candidateになると自分に投票(Vote)して自分のtermをインクリメントします。
Vote Countは投票数

4. Candidate(NodeB)は、Follower(NodeA,C)に投票リクエスト(RequestVoteRPC)をブロードキャストする。投票リクエストを受け取ったFollowerは、自分のelection timeoutをリセットして投票レスポンスを返す。(このタイミングで投票していない場合)
5. candidateが過半数以上(自分含む)の得票(レスポンス)を受け取った時点でCandidate-> Leaderになる。

6. Leaderは定期的にハートビート(AppendEntriesRPC)を各ノード(Follower)にブロードキャストする。Followerはハートビートを受け取ると自分のTimeoutをリセットする。
このハートビートは、ハートビートタイムアウトで指定された間隔で送信される。
つまり、timeout前にハートビートを送ることでCandidateにさせなくする
(Leaderになりたいですと言わせなくする感じ)
これ以降Followerは、Leaderからの追加エントリーメッセージに応答する。
この流れで最初のLeader Electionが行われます。

1-2. Leaderの再選出(Leaderがダウン)

1. Leaderがダウン

2.Followerはelection timeoutを過ぎると、candidateになります。
ここからは、Leaderの選出方法のStep2から繰り返す。

1-3. Candidateの投票数が複数Nodeで同じになった場合

1. 2つのNodeが同時にelectionを開始した場合それぞれが単一のフォロワーノードに到達します。(同じelection timeoutになった場合)

2.各candidateのNode(NodeA&NodeB)は2票ずつ獲得しており、それ以上の票を獲得することはできません。(この構成の場合4台しかいないので)

3.Nodeは新しいelectionを待って再投票します。
(NodeAはNodeBが2票持っていることを知っているため)
再投票が行われると今度は1台のNode(NodeA)が過半数票を獲得しLeaderになります。


2.ログレプリケーション

Leaderが選出されると、システム全ての変更を全てのノードに同期する必要があります。
ハートビートに使用されたのと同じエントリの追加メッセージを使用して行われます。
  1. Leaderがクライアントからの更新処理を受け付ける(5をセット)
  2. Leaderはそれをログとして一時保存
  3. Leaderは変更を次のハートビート(AppendEntriesRPC)でFollowerに送信
  4. Followerは送られて来た更新を一時保存
  5. 過半数のFollowerからレスポンスが返ってくるとLeaderは更新をコミットする
  6. Leaderはクライアントに成功したステータスを返す
  7. Leaderは次のハートビートでコミットしたことをFollowerに通知し、
    Followerも更新をコミット

3.安全性の保証(ネットワークが切れてクラスタが分断されたら?)

複数台構成のクラスター(今回は5台)があった場合に、ネットワークが分断され、以下のように複数台のリーダー(今回はNodeBとNodeC)が存在してしまうことがあります。
しかし、分断されたNodeBとNodeAはクライアントから更新リクエストがきても過半数のFollowerからレスポンスを受け取れないため、更新をコミットすることができません。
NodeCがリーダーのクラスターでは、過半数のレスポンスが受けれているため更新をコミットしクライアントに返すことができている。
ネットワークの分断が解消されると、新しいLeaderによってTermの大きい数値のデータが同期される。
こうして一貫性のデータを担保する。
NodeBとNodeAのデータは、未コミットのためロールバックされる。

Termについてもうちょい

LeaderとFollowerの情報に差分がある場合どうするのか。
以下の例では、LeaderがLog Index 10まで持っている状態で、
Followerはそれぞれバラバラな状態だとします。
この差分を修正するのはLeaderの責任なので、Leaderは以下の流れで差分の修正を実施します。
1. お互いのログを比較し、共通のポイントを探します。
・Leaderと(A)の場合、Log Index 8
・Leaderと(E)の場合、Log Index 3
2. Followerのログのうち、共通のポイント以後の情報(Leaderが持っていない情報)を削除します。
・Leaderと(D)の場合、Log Index 10以降を削除
・Leaderと(E)の場合、Log Index 4以降を削除
3. Followerのログのうち、共通のポイント以後の情報(Leaderのみが持っている情報)をFollowerのログに追記
・Leaderと(B)の場合、Log Index 5以降にLeaderのログを追記
・Leaderと(E)の場合、Log Index 4以降にLeaderのログを追記

(おまけ) ConsulコマンドでRaftの状態を確認

# consul operator raft list-peers
Node     ID              Address         State     Voter  RaftProtocol
NodeA    127.0.0.1:8300  127.0.0.1:8300  follower  true   2
NodeB    127.0.0.2:8300  127.0.0.2:8300  leader    true   3
NodeC    127.0.0.3:8300  127.0.0.3:8300  follower  true   2
Nodeの名前やState(誰がLeaderで、誰がFollowerなのか)を確認できます。
ref: https://www.consul.io/docs/commands/operator/raft.html

まとめ

Raftの動作について簡単にまとめさせてもらいました。
Raftは、ここまでざっくり説明させてもらった実装により一貫性の担保をしています。
Consulを勉強していて、Raft実装の内部動作がよくわからないような方の参考になれば幸いです。
次の記事で、Consulで使われているもう一つのSWIM(GossipProtocol)について書こうと思っています。

こちらの記事を参考にさせて頂きました。
http://thesecretlivesofdata.com/raft/
https://gist.github.com/sile/ad435262c17eb79f133d