Raft入門

Raft入門 プラットフォームG 宮崎 泰輔

Raftとは何なのか

Raftとは何なのか Raftは安全な State Machine Replication (SMR) を実装するための 分散合意アルゴリズムである Paxos系のアルゴリズムの代替として設計された。 Paxosの理解が難しすぎる、実装によってどこまで保証されているか かなり異なっていたので、 「理解可能性」を重視しつつ、有用な性質は維持するように設計された

State Machine Replicationとは 耐障害性を備えるためにデータを複数のサーバーでコピーを持ち合う。 複数のサーバーにデータのコピーを作る方法の一つ。 複数のサーバーで同じ初期状態から開始した有限状態機械(FSM)に同じコ マンドを同じ順序で適用することで、すべてのサーバーが 同じ状態遷移をする。 「同じ状態から同じ状態遷移すれば、同じ状態になる」

そうは言っても複数のマシンで同じ状態遷移をさせるのは難しい

なぜ難しいのか サーバーたちはネットワークを介してやり取りを行う。 そしてネットワークでのメッセージの伝播速度はバラバラなので、 複数のサーバーが同時にメッセージを送っても、順番が変わってしまう 初期状態A サーバー1: A -> Bに状態遷移させたい(時刻 t1) サーバー2: A -> a に状態遷移させたい(時刻t1) サーバー3: 時刻t2にB, aどちらになっているべき？

なぜ難しいのか リーダーを置いて、リーダーがメッセージの順序を決める 複数のサーバーがそれぞれ新しい状態に遷移させようとしない。 リーダー以外は受け取ったメッセージを自分の状態機械に適用するだけ これで順序を決められるからOK？ NO

障害が発生しうる - Crash-Stop - ネットワークから突然消えて復帰しない - Omission - メッセージがロストする - Performance, Timing - タイムアウトまでに応答がない(タイムアウトを過ぎて応答があるかも - Crash-Recovery - 止まっていたインスタンスが復帰してくる（状態が古い） - Byzantine, Arbitrary - 悪意ある行動

障害が発生しうる しかも、ネットワーク越しだと 相手サーバーがクラッシュしたのか、メッセージがロストしたのか、 それともそのうち復帰してくるのかはわからない 自分視点だと単に応答がないようにしか見えない

Raftの話 Raftは複数サーバーで何かを合意するときに quorum (定足数) に達している かで物事を決める。 Raftのクラスタは、1つのリーダーとリーダー以外のフォロワーによって構成さ れる。（Raftがやり取りするメッセージはログと呼ばれる） 重要な動作 - リーダー選挙 - ログ複製

リーダー選挙 それぞれのサーバーはリーダーか、フォロワー、そして選挙時には 候補者のどれかの役割を必ず持っていて、最初はみんな候補者として リーダーを決めることから始まる。 状態遷移図

リーダー選挙 リーダーには任期（term）が存在する termは単調増加で、リーダーを選ぶタイミングごとにインクリメント 選ぶタイミングごとなので、リーダーが決定しない任期が存在する ※後述

リーダー選挙の流れ 1. 全員候補者から開始 2. 自分のtermをインクリメントする 3. RequestVote を全サーバーに送る 4. 過半数以上のレスポンスを受け取ったらLeaderになる 5. その後Leaderは定期的にハートビートを送ってLeaderを維持する

リーダー選挙の流れ 4で票が別れた場合(複数の候補者がRequestVoteを送ると起き得る) 1. タイムアウトまで待っても票が集まらなかったらリトライする （リトライの時にtermがインクリメントされる） リトライまでにランダムな時間waitする 自分より大きなtermのRequestVoteが届いたら - 自分はフォロワーになる

リーダー選挙の流れ 遷移図再掲

リーダー選出の流れ 全員Followerから始め ハートビートを受け取るタイムアウトまで待つ F F F

リーダー選出の流れ 1. タイムアウトして候補者になる (タイムアウトする時間はランダムにちょっと違う) 2. 自分を含め全員にRequestVoteを送る F C RequestVote (term=1) C

リーダー選出の流れ 過半数の投票（応答）を得たため、リーダーになる F C OK (term=1) L

リーダー選出の流れ 1. 全員に自分がリーダーであることを通知する(AppendEntries) 2. CandidateはFollowerになる(元々Followerでも、termを設定し直す) 3. ハートビートは定期的に送られる F F AppendEntries (term=1) L

ログのレプリケーション 「Leaderが保持しているログがマスター」 「コミットされた」データは絶対に改変されない 1. リーダーがクライアントからのリクエストを受け取る 2. リーダーのログのエントリに追加 3. Followerに対して、AppendEntries でエントリを送信 4. 過半数からエントリを保存した応答があれば リーダーのエントリをコミットする 5. コミット内容をクライアントに送信する

まとめ リーダー選出の大まかな流れを説明した ログレプリケーションの大まかな流れを説明した ただし、ここで説明しただけだと実は不十分な箇所がある 気になる人は調べてみてください - コミットされた通知をFollowerが受け取ってくれる前にLeaderが 死んだら、コミットされたのに他のFollowerにLeaderが変更されると変更 内容が失われる

まとめ - サーバーを止めずにクラスタの構成を更新したい場合 - ログが肥大化してしまう - スナップショットを使う