Coda

論文メモ In Search of an Understandable Consensus Algorithm

March 9, 2020

Raftとよばれるコンセンサスアルゴリズムを提案した論文である。 Raftは、Multi Paxosと同様の実行結果をもたらす。 実行するコマンドのログをサーバ間で交換することで、状態を同期し、サーバの一部が落ちてもシステムを継続することができる。

サーバは、Leader, Follwer, Candidateの3つの状態をとりえる。 Leaderだけが、クライアントからのリクエストに応え、ログのエントリをFollowerのサーバに配信する。 FollowerはCandidateを経てLeaderになる。 Leaderは、Followerに、死活監視として空のエントリを定期的に配信する。 Followerはheatbeatが途絶えるとCandidate状態になり、他のサーバに投票を要求し、票を過半数獲得できたらLeaderになる。 サーバは、単調増加する数値で管理される論理的な時刻を管理している。 Candidateは新しいLeaderの時刻が自分のものよりも古くなければ、Leaderを認めてFollowerに戻る。

論文で強調されているのは、分かりやすさである。 Paxosは難解で、また、Multi Paxosの詳細な説明はないため、実装がむずかしい。 分かりやすくするために、Raftでは、コンセンサスの鍵になる要素が分けて扱われている。 例えば、論文ではLeaderの選出方法、ログの複製、アルゴリズムで保証される安全性、クラスタに参加するサーバの変更、ログの圧縮が、それぞれ別の節に分けられ説明されている。 ほかにも、クラスタのとりえる状態数を減らしたり、heatbeatのタイムアウト時間をランダムにしたりすることで、アルゴリズムを単純にしている。 例えば、上のLeader選出では投票が割れるとLeaderの選出が繰り返されてしまう。 サーバは最初に投票をリクエストしたサーバに一度だけ票を投じる。 そのため、サーバーごとに異なるタイムアウト時間を設定し、先にタイムアウトしたサーバがLeaderになりやすくすることで、複雑な仕組みを導入することなく選出が繰り返されにくくされている。