ikemonn's blog

技術ネタをちょこちょこと

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つの特徴
    • Strong leader
      • 他の同意アルゴリズムよりも、リーダの権限が強い
        • 例えばlogのreplicationはリーダーからスレーブへの一方向
      • RPCの呼び出しはリーダのみが行う
    • Leader election
      • リーダの選出のためにrandomized timerを用いる
        • どの同意アルゴリズムにも必要になってくる、ハートビートのメカニズムを簡単にした
    • Membership change
      • joint consensusという手法でmembershipの変更を行う
        • membershipの変更中に新旧の設定がoverlapする
        • membershipの変更中もクラスタは稼働し続ける

技術や手法の肝は?

  • Replicated state machines
  • 処理の流れ

    • 1: サーバ上のConsensus Moduleがclientからコマンドを受け取る
    • 2: ログにコマンドを追加、他のサーバのConsensus Moduleをやりとりをして、コマンドを同じ順になるようにする
    • 3: replicateを行い、完了すると、serverのstatemachineがログの順にコマンドを実行していく
    • 4: outputがclientに送られる f:id:ikemonn:20170727211344p:plain
  • What’s wrong with Paxos?

    • 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
  • Raft basics
    • Raft cluster

      • 5台のサーバで構成される(2台死んでもOK)
      • それぞれのサーバは以下のいずれかのstateを持つ
        • Leader
          • clientからのrequestを受ける
        • follower
          • 自身でrequestは受けずに、leaderかcandidateからのrequestに対して、responseを送る
        • candidate
          • 新しいリーダの選出時に使われる

      f:id:ikemonn:20170727211454p:plain

    • Term

      • 特定のleaderが活動していた論理時間
      • termにはシーケンシャルなIDが振られる
      • 各termはリーダの選出から始まる
      • leaderが死んだらcandidateが次のtermを開始する
      • 各サーバはcurrent termの情報を持ち、stale requestをrejectしたりするのに使う

      f:id:ikemonn:20170727211513p:plain

    • Leader election

      • ハートビートをリーダの選出を開始するトリガーにする
      • followerが一定期間leaderからハートビートを受け取っていない場合(election timeout)にcandidateとなり選出が始まる
        • 自分のcurrent term numberを増やして、RequestVoteRPCを発行する
    • candidateは下記の3つのうちの1つが起こるまで続ける
      • electionに勝つ
        • 同タームで過半数のサーバから投票されるとリーダになる
      • 他のサーバがリーダになる
      • 誰も選出されない状態で一定期間が経つ
        • ランダムなelection timeoutを用いるのでリーダーがずっと選ばれないことはめったにおこらない
  • 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されると古い状態のプロセスは消える f:id:ikemonn:20170727211618p:plain

どうやって有効と検証した?

  • RaftとPaxosのクイズの正答率を比較したところ、どちらを先に勉強してもRaftの方が得点が良かった

f:id:ikemonn:20170727213721p:plain

  • RaftとPaxosを実装する/説明するのにどちらが簡単かを聞いたところRaftの方が簡単という答えが多かった

f:id:ikemonn:20170727213731p:plain

  • timeoutの時間をランダムに変化させた時のリーダ選出にかかった時間

    • 150ms-151msだとsplit voteが起きて10秒くらいかかるが、5ms長くすると中央値が287msになった
    • 150ms-200msくらいが良い
  • timeoutの時間をもっと減らしてみた

    • 12-24msだと平均35msだったが、Raftの要件に合わない
      • 他のサーバが新たな投票を開始する前に、リーダがハートビートをbroadcastをできない
      • 150ms-300msくらいが良い

f:id:ikemonn:20170727213753p:plain

議論はある?

  • Raftのパフォーマンスは他の同意アルゴリズムと同じくらい
    • 他のアルゴリズムに当てはまる最適化の手法はRaftにも使える
      • batchingやpipeline requestなど

次に読むべき論文は?

ZooKeeper: Wait-free coordination for Internet-scale systems