In Search of an Understandable Consensus Algorithm(Extended Version) を読んだ
[In Search of an Understandable Consensus Algorithm(Extended Version)(https://raft.github.io/raft.pdf)を読んだ時のメモ。
どんなもの?
- わかりやすさを重視して開発された合意アルゴリズム
- Paxosよりもわかりやすいが、Paxosよりも効率的
先行研究とくらべて何がすごい?
- Paxosに比べてわかりやすい
- 何故動くのかまでを開発者が理解しやすい
- 3つの特徴
技術や手法の肝は?
- Replicated state machines
処理の流れ
- 1: サーバ上のConsensus Moduleがclientからコマンドを受け取る
- 2: ログにコマンドを追加、他のサーバのConsensus Moduleをやりとりをして、コマンドを同じ順になるようにする
- 3: replicateを行い、完了すると、serverのstatemachineがログの順にコマンドを実行していく
- 4: outputがclientに送られる
What’s wrong with Paxos?
- 2つの問題
- 理解するのが難しすぎる
- 実際に実装するとなると理論と現実とのギャップがある
- 2つの問題
Designing for understandability
- 直感的に理解しやすいことを目標にした
- 開発者が拡張しやすい
- 問題を分割してわかりやすくした
- Paxosに比べて状態の数を減らした
- 直感的に理解しやすいことを目標にした
The Raft consensus algorithm
- リーダを選び、リーダにreplicated logを管理する権限を与える
- リーダはclientからログを受けとって、他のサーバにreplicateする
- 各サーバに対して、statemachineにログを適用するのに良いタイミングを通知する
- consensus problemを3つの独立した問題に分割した
- Leader election
- 新しいリーダは既存のリーダが死ぬと選ばれる
- Log replication
- リーダがclientからログを受け取ってから、クラスタに流す
- Safety
- Figure 3
- Leader election
- Raft basics
Raft cluster
- 5台のサーバで構成される(2台死んでもOK)
- それぞれのサーバは以下のいずれかのstateを持つ
- Leader
- clientからのrequestを受ける
- follower
- 自身でrequestは受けずに、leaderかcandidateからのrequestに対して、responseを送る
- candidate
- 新しいリーダの選出時に使われる
- Leader
Term
- 特定のleaderが活動していた論理時間
- termにはシーケンシャルなIDが振られる
- 各termはリーダの選出から始まる
- leaderが死んだらcandidateが次のtermを開始する
- 各サーバはcurrent termの情報を持ち、stale requestをrejectしたりするのに使う
Leader election
- ハートビートをリーダの選出を開始するトリガーにする
- followerが一定期間leaderからハートビートを受け取っていない場合(election timeout)にcandidateとなり選出が始まる
- 自分のcurrent term numberを増やして、RequestVoteRPCを発行する
- candidateは下記の3つのうちの1つが起こるまで続ける
- electionに勝つ
- 同タームで過半数のサーバから投票されるとリーダになる
- 他のサーバがリーダになる
- 誰も選出されない状態で一定期間が経つ
- ランダムなelection timeoutを用いるのでリーダーがずっと選ばれないことはめったにおこらない
- electionに勝つ
Log replication
- リーダは受け取ったコマンドを新しいentryとしてログに追加していく
- entryがreplicateされたら、そのentryを自身のstate machineに適用し、clientに結果を返す
- replicateの途中でfollowerがcrashしても、全てのfollwerにreplicateされるまでおくり続ける
- leaderは過半数のfollowerからresponseがあったら、それらのstate machineにログを適用させる(commit)
Cluster membership changes
- 新旧のconfigが混ざった状態を間に挟むことで、無停止でconfigの変更を行えるようにした
- 流れ
- 古いconfigのリーダが新旧のconfigが混ざった状態に遷移するように指示
- 新旧混ざった状態がcommitされると、joint consensusに移行
- 新しい状態がcommitされると古い状態のプロセスは消える
どうやって有効と検証した?
- RaftとPaxosのクイズの正答率を比較したところ、どちらを先に勉強してもRaftの方が得点が良かった
- RaftとPaxosを実装する/説明するのにどちらが簡単かを聞いたところRaftの方が簡単という答えが多かった
timeoutの時間をランダムに変化させた時のリーダ選出にかかった時間
- 150ms-151msだとsplit voteが起きて10秒くらいかかるが、5ms長くすると中央値が287msになった
- 150ms-200msくらいが良い
timeoutの時間をもっと減らしてみた
- 12-24msだと平均35msだったが、Raftの要件に合わない
- 他のサーバが新たな投票を開始する前に、リーダがハートビートをbroadcastをできない
- 150ms-300msくらいが良い
- 12-24msだと平均35msだったが、Raftの要件に合わない
議論はある?
次に読むべき論文は?
ZooKeeper: Wait-free coordination for Internet-scale systems