Raft合意アルゴリズム入門 - リーダー選出とログ複製を実装で理解する

サーバが1台しかないシステムは、その1台が落ちた瞬間に止まります。だから複製する。ところが複製した瞬間に、こんどは「どのコピーが正しいのか」という新しい問題が生まれます。ネットワークが遅れ、パケットが落ち、ノードが再起動する世界で、複数のマシンに同じ値を同じ順序で確定させるにはどうすればよいのか。これが合意（consensus）問題であり、その最も広く使われている解法のひとつがRaftです。KubernetesのetcdもConsulもTiKVもCockroachDBも、中核でRaftを回しています。この記事では、Diego OngaroとJohn Ousterhoutの原論文を一次ソースに、リーダー選出・ログ複製・安全性という3つの柱を、実際にpython3で動かして出力を確認したシミュレータとともに追います。CAP定理で扱った「分断時に一貫性と可用性のどちらを取るか」という問いに対して、Raftが具体的にどう答えているのかを見る回だと思ってください。

なぜ分散システムで合意が必要か

出発点は単一障害点（single point of failure）です。1台のサーバに状態を持たせれば、実装はいちばん単純になります。順序は自明で、矛盾も起きません。ただしそのマシンのディスクが壊れれば、サービスは止まり、データは失われます。

そこで状態を複数台に複製します。ここで素朴にやると失敗します。「全ノードに書き込みを送る」だけでは、ネットワークが分断されたときに片方だけ更新が届き、値が食い違います。「1台をマスタにして残りへ非同期にコピーする」だけでは、マスタが落ちた瞬間に、どのレプリカが最新かを誰も断定できません。

この問題を整理する枠組みが状態機械複製（replicated state machine）です。原論文の第2節はこう述べています。合意アルゴリズムは通常、状態機械複製の文脈で登場し、各サーバ上の状態機械が同一のコピーを計算する。各サーバは同じコマンド列を持つログを保持し、決定的な状態機械がそのログを先頭から順に適用する。同じ順序で同じコマンドを適用すれば、全サーバは必ず同じ状態に到達します。

つまり合意アルゴリズムが本当に解いているのは「値をどう共有するか」ではなく、ログの各インデックスにどのコマンドを入れるかを全員で1つに決めることです。順序さえ一致すれば、あとは各自が同じ計算を回すだけで状態は勝手に揃います。

そして原論文は、実用的な合意アルゴリズムが満たすべき性質として次を挙げています。非ビザンチン条件下（ノードは嘘をつかず、停止するだけ）では常に安全であること。サーバの過半数（majority）が生きていて互いに通信できる限り機能し続けること。そして一貫性の保証をタイミングに依存しないこと。原論文は具体例として、5台構成のクラスタは任意の2台の故障に耐えられると書いています。この「過半数」という考え方が、これから見るすべての仕組みの土台になります。

レプリカをどのノードに配置するかという分割の話はコンシステントハッシュ法、複数の操作を1単位として扱う話はトランザクションとACID・分離レベルで扱いました。この記事はその中間、「1つのレプリカ集合の中で順序をどう確定するか」というレイヤーの話です。

Paxosの難しさと、Raftが掲げた「理解しやすさ」

合意アルゴリズムの古典はLeslie LamportのPaxosです。正しさは証明されており、実務でも長く使われてきました。ところがPaxosには、教える側も実装する側も苦しんできたという評判がついて回ります。

Raftの原論文のタイトルがまさにその答えです。In Search of an Understandable Consensus Algorithm、すなわち「理解しやすい合意アルゴリズムを求めて」。著者はOngaroとOusterhoutで、短縮版は2014年のUSENIX Annual Technical ConferenceでBest Paper Awardを受賞しています。論文は冒頭で、自分たちの第一の目標（primary goal）が理解しやすさ（understandability）だったと明言しています。性能でも簡潔さでもなく、理解しやすさを設計目標の筆頭に据えたところがRaftの特異な点です。

そのために採った手法が2つあります。1つは分解（decomposition）で、合意という問題をリーダー選出・ログ複製・安全性という比較的独立した部分問題に切り分けました。もう1つは状態空間の削減で、考えなければならない場合分けそのものを減らす方向に設計を寄せています。面白いのは、論文が「非決定性が理解しやすさを高める場合もある」と書いている点です。後で見るランダム化されたタイムアウトがその例で、乱数を入れることでかえって考えるべき状態が減っています。

著者らはこの主張を検証するために、スタンフォード大学とU.C.バークレーの学生を対象にRaftとPaxosの講義動画とクイズを用意し、理解度を比較する実験まで行っています。合意アルゴリズムの論文としてはかなり異例で、「理解しやすさ」を建前でなく評価対象として扱った姿勢がうかがえます。

Raftの基本構造 — 3つの状態とtermという論理時計

Raftのサーバは、常に次の3つの状態のいずれかにあります。

• Follower（フォロワー）: 受け身。自分からは何も発信せず、リーダーや候補者からのRPCに応答するだけです。起動直後は全員がFollowerです。
• Candidate（候補者）: リーダーからの連絡が途絶えたFollowerが、自らリーダーになろうと立候補した状態です。
• Leader（リーダー）: クライアントの要求をすべて受け付け、ログに追記し、フォロワーへ複製する唯一のノードです。定期的にハートビートを送って自分の生存を知らせます。

状態遷移は次のようになります。

ここで決定的に重要なのがterm（任期）という概念です。Raftは時間を、番号のついた任期の列に分割します。各termは選挙から始まり、選挙に勝ったサーバがそのtermのリーダーとして期間の残りを務めます。termは単調増加する整数であり、Raftにおける論理時計として機能します。

termがあるおかげで、Raftは「古い情報」を機械的に捨てられます。ルールは単純です。

• すべてのRPCは送信元のtermを含む。
• 受け取ったtermが自分より大きければ、自分のtermをそれに更新し、無条件にFollowerへ降りる。
• 受け取ったtermが自分より小さければ、そのRPCを拒否する。

これだけで、ネットワークの遅延で遅れて届いた古いリーダーからの指示や、分断されている間に取り残されたノードの主張を、追加の場合分けなしに排除できます。物理時計の同期は一切不要で、必要なのは番号の大小比較だけです。分断が起きる物理的な背景はTCPと3ウェイハンドシェイクのあたりの話ですが、Raftはそこに時計を持ち込まず、論理的な番号だけで筋を通します。

リーダー選出 — ランダム化タイムアウトが split vote を解く

Followerは、リーダーからのハートビートを一定時間受け取らないとelection timeoutが発火し、Candidateへ移ります。そのときの手順は次のとおりです。

1. 自分のtermを1つ増やす。
2. 自分自身に投票する。
3. クラスタの他の全サーバへRequestVote RPCを送る。
4. 過半数の票を集められたらリーダーになる。

ここで問題になるのがsplit vote（票の分裂）です。複数のFollowerが同時にタイムアウトして同時に立候補すると、票がばらけて誰も過半数に届きません。全員がタイムアウトして、また同時に立候補して、また分裂する。この繰り返しに陥ると、クラスタは永遠にリーダーを選べません。

Raftの解決策は拍子抜けするほど単純で、election timeoutを固定値ではなく、決まった区間からランダムに選ぶというものです。原論文は具体的な区間の例として150-300msを挙げ、この程度の保守的な値であれば不要なリーダー交代を起こしにくいと述べています。誰か1人が先にタイムアウトして票を集め切ってしまうため、分裂はたいてい一巡で収束します。

これが本当に効くのかを確かめるため、5サーバのクラスタを200回ずつ走らせて比較しました。以下は実際に実行したコードの中核部分です。

def fixed_timer(self):
    self.elapsed = 0
    self.timeout = 20            # 全員が同じタイミングで立候補する
 
 
def randomized_timer(self):
    self.elapsed = 0
    self.timeout = self.rng.randint(15, 30)
 
 
def trial(seed, max_ticks=400):
    c = Cluster(5, seed=seed)
    for t in range(1, max_ticks + 1):
        c.tick()
        if c.leader():
            candidacies = sum(1 for line in c.trace if "立候補" in line)
            return t, candidacies
    return None, sum(1 for line in c.trace if "立候補" in line)

実行結果は次のようになりました。

--- 固定タイムアウト (5サーバ x 200試行) ---
  400tick以内にリーダーが決まった試行: 0/200
  無駄になった立候補の平均回数: 100.0
--- ランダム化タイムアウト (5サーバ x 200試行) ---
  400tick以内にリーダーが決まった試行: 200/200
  決まるまでの平均tick数: 18.3
  平均立候補回数: 1.1

固定タイムアウトでは200回すべて失敗し、1試行あたり平均100回も無駄な立候補を繰り返しています。5サーバが完全に同期して立候補し続けるため、永久に決着しません。一方ランダム化すると200回すべてが成功し、立候補回数は平均1.1回、つまりほぼ一発で決まっています。乱数を1行足しただけでライブロックが消える、というのがRaftの選挙設計の要点です。

なお、Raftのタイミング要件は原論文でbroadcastTime << electionTimeout << MTBFという不等式にまとめられています。ノード間の往復時間よりelection timeoutが十分大きく、かつサーバの平均故障間隔よりは十分小さいこと。この関係が崩れると、正常なのにリーダーが頻繁に交代したり、逆に障害検知が遅すぎたりします。

ログ複製 — AppendEntries と commitIndex

リーダーが決まると、クライアントの書き込み要求はすべてリーダーに集まります。リーダーは要求をログエントリとして自分のログ末尾に追記し、AppendEntries RPCでフォロワーへ配ります。同じRPCは、エントリが空の状態でハートビートとしても使われます。

エントリが過半数のサーバに複製された時点で、そのエントリはコミット済み（committed）になります。リーダーはcommitIndexという値でどこまでコミットしたかを覚え、以降のAppendEntriesに載せてフォロワーへ伝えます。フォロワーは自分のcommitIndexをそこまで進め、状態機械へ適用します。

以下は、実際に動かしたシミュレータのコミット判定部分です。

# commitIndex: 自分のtermのエントリが過半数に複製されたら進める
def advance_commit(self, s):
    for n in range(len(s.log), s.commit_index, -1):
        replicated = 1 + sum(1 for p in s.peers if s.match_index[p] >= n)
        if replicated >= self.quorum() and s.log[n - 1].term == s.term:
            s.commit_index = n
            break

注目してほしいのはs.log[n - 1].term == s.termという条件です。リーダーは、過去のtermのエントリを「複製数だけを見て」コミットしてはいけません。原論文が図8で示す有名な反例で、過半数に複製されただけの前任termのエントリは、その後の選挙結果によっては上書きされ得ます。自分のtermの新しいエントリを1つコミットすれば、Log Matching Propertyによりそれ以前のエントリも間接的に確定します。この一行が安全性を支えています。

同じシミュレータで、5サーバのクラスタにリーダーを選出させ、3件のコマンドを流し、その後リーダーを停止させた実行結果が次です。

=== 1. リーダー選出 ===
t= 16 S3 が term=1 で立候補 (RequestVote送信)
t= 17 S3 が term=1 のリーダーに就任 (得票 3/5, 過半数 3)
 
=== 2. ログ複製 ===
t= 17 クライアント要求 'set x=1' を S3 が index=1 に追記
t= 19 S3 が index=1 をコミット (複製 3/5) cmd=set x=1
t= 23 クライアント要求 'set y=2' を S3 が index=2 に追記
t= 25 S3 が index=2 をコミット (複製 3/5) cmd=set y=2
t= 29 クライアント要求 'set x=3' を S3 が index=3 に追記
t= 31 S3 が index=3 をコミット (複製 3/5) cmd=set x=3
 
=== 3. リーダー障害と再選出 ===
S3 (term=1 のリーダー) を停止
t= 48 S4 が term=2 で立候補 (RequestVote送信)
t= 49 S4 が term=2 のリーダーに就任 (得票 3/5, 過半数 3)
 
新リーダー: S4 (term=2)
新リーダーのログ: [(1, 'set x=1'), (1, 'set y=2'), (1, 'set x=3')]
旧リーダーのコミット済み index: 3
新リーダーが保持している index: 3
 
=== 4. 全サーバの最終状態 ===
S0  (follower) term=2 commit=3 log=['set x=1', 'set y=2', 'set x=3']
S1  (follower) term=2 commit=3 log=['set x=1', 'set y=2', 'set x=3']
S2  (follower) term=2 commit=3 log=['set x=1', 'set y=2', 'set x=3']
S3       (停止中) term=1 commit=3 log=['set x=1', 'set y=2', 'set x=3']
S4    (leader) term=2 commit=3 log=['set x=1', 'set y=2', 'set x=3']

リーダーが落ちてもコミット済みの3件は1件も失われず、新リーダーS4がすべてを引き継いでいます。termが1から2へ上がり、残った4台が同じログに収束していることも確認できます。

Log Matching Property とログの不整合の修復

Raftのログ複製を支えるのがLog Matching Propertyです。原論文の記述はこうです。2つのログが同じindexかつ同じtermのエントリを含むなら、そのindexまでの全エントリが同一である。

この強い性質は、AppendEntriesの整合性チェックだけで維持されます。リーダーはエントリを送るとき、直前のエントリのprevLogIndexとprevLogTermを一緒に送ります。フォロワーは自分のログのその位置が一致しなければ、AppendEntriesを拒否します。以下が実装部分です。

# Log Matching: prev_index/prev_term が一致しなければ拒否する
pi, pt = b["prev_index"], b["prev_term"]
if pi > len(s.log) or (pi > 0 and s.log[pi - 1].term != pt):
    self.send(Msg("AppendEntriesResp", s.id, m.src, s.term,
                  {"ok": False, "match": 0}))
    return
if b["entries"]:
    s.log = s.log[:pi] + list(b["entries"])

拒否されたリーダーは、そのフォロワー用のnextIndexを1つ減らして再送します。一致する地点まで遡り、そこから先はリーダーのログで上書きする。フォロワー側の食い違ったエントリは切り捨てられます（s.log[:pi]の部分）。フォロワーのログが余計なエントリを持っていようが欠けていようが、この単純なループだけで必ず収束します。

実際に、リーダーが[(1,a), (1,b), (3,c)]、フォロワーS2が[(1,a), (2,x), (2,y)]という分岐したログを持つ状態から動かしてみました。

修復前 S2 のログ: [(1, 'a'), (2, 'x'), (2, 'y')]
step 1: next_index[S2]=4 S2.log=[(1, 'a'), (2, 'x'), (2, 'y')]
step 2: next_index[S2]=3 S2.log=[(1, 'a'), (2, 'x'), (2, 'y')]
step 3: next_index[S2]=2 S2.log=[(1, 'a'), (2, 'x'), (2, 'y')]
step 4: next_index[S2]=1 S2.log=[(1, 'a'), (1, 'b'), (3, 'c')]
step 5: next_index[S2]=4 S2.log=[(1, 'a'), (1, 'b'), (3, 'c')]
修復後 S2 のログ: [(1, 'a'), (1, 'b'), (3, 'c')]

nextIndexが4から1へ1つずつ下がり、index1のエントリ（term=1のa）で一致が取れた時点で、以降がリーダーのログに置き換わっています。なお応答は1tick遅れて届く実装なので、next_indexの表示値はログが直った瞬間より1step遅れて追随します。

ここで気になるのが、この上書きでコミット済みのエントリが消えないのかという点です。答えは消えません。そしてその保証を与えるのが、次の安全性の議論です。

安全性 — 古いログを持つ候補者はリーダーになれない

Raftは5つの安全性を保証します。原論文が挙げるのは次のとおりです。

このうちLeader Completenessが、「コミット済みが失われない」ことの核心です。そしてこれを実現する仕掛けがElection Restriction（選挙制限）、原論文の5.4.1節です。

仕組みは投票側に置かれています。RequestVoteには候補者のlastLogIndexとlastLogTermが入っており、投票者は、自分のログのほうが候補者のログより新しいと判断したら投票を拒否します。新しさの比較は、まず最後のエントリのtermを比べ、termが同じならindexの大きいほうを新しいとみなします。実装は次のとおりです。

# Election Restriction: 候補者のログが自分より新しくなければ投票しない
up_to_date = (b["last_term"] > s.last_term() or
              (b["last_term"] == s.last_term() and b["last_index"] >= s.last_index()))
granted = (m.term == s.term and s.voted_for in (None, m.src) and up_to_date)

なぜこれで十分なのか。コミット済みのエントリは定義上、過半数のサーバが持っています。リーダーになるには過半数の票が要ります。過半数どうしの集合は必ず1台以上重なるので、コミット済みエントリを持つサーバが必ず投票者の中に含まれます。そのサーバは自分より古いログの候補者に票を投じないため、コミット済みエントリを欠いた候補者は原理的に過半数を取れません。追加のデータ転送も、コミット状況の問い合わせも不要で、投票時の2つの数値の比較だけで完結しています。

実際に、S0からS3が[(1,a), (1,b), (2,c)]を持ち、S4だけが[(1,a)]と遅れている状況でS4を立候補させてみました。

=== A. 古いログを持つ候補者はリーダーになれない ===
t=  0 S4 が term=3 で立候補 (RequestVote送信)
t=  1 S0 が S4 への投票を拒否 (ログが古い)
t=  1 S1 が S4 への投票を拒否 (ログが古い)
t=  1 S2 が S4 への投票を拒否 (ログが古い)
t=  1 S3 が S4 への投票を拒否 (ログが古い)
S4 の得票: 1/5 (過半数 3) -> state=candidate
 
=== B. 最新ログを持つ候補者は選出される ===
t=  3 S0 が term=4 で立候補 (RequestVote送信)
t=  5 S0 が term=4 のリーダーに就任 (得票 3/5, 過半数 3)
t=  6 S4 が AppendEntries を拒否 (prev_index=3 で不一致 -> リーダーが遡る)

S4はtermを上げて立候補したにもかかわらず、自票の1票しか集まらずCandidateのままです。termが大きいだけでは勝てない、というのがElection Restrictionの効き目です。続いて最新ログを持つS0が立候補すると、ただちに過半数を得てリーダーになり、遅れているS4のログ修復が始まっています。

クラスタサイズと耐障害数 — なぜ奇数台なのか

Raftの可用性は「過半数が生きているか」だけで決まります。ここは算術の問題なので、実際に計算させてみます。

def quorum(n: int) -> int:
    # 過半数 = floor(n/2) + 1
    return n // 2 + 1
 
 
def tolerance(n: int) -> int:
    # 残りが過半数を保てる範囲でしか壊れられない
    return n - quorum(n)
 
 
print(f"{'n':>3} {'quorum':>7} {'tolerate':>9}")
for n in range(1, 10):
    print(f"{n:>3} {quorum(n):>7} {tolerance(n):>9}")
 
print()
for f in range(0, 4):
    n = 2 * f + 1
    print(f"f={f}: 2f+1 = {n} servers, quorum = {quorum(n)}")

実行結果です。

  n  quorum  tolerate
  1       1         0
  2       2         0
  3       2         1
  4       3         1
  5       3         2
  6       4         2
  7       4         3
  8       5         3
  9       5         4
 
f=0: 2f+1 = 1 servers, quorum = 1
f=1: 2f+1 = 3 servers, quorum = 2
f=2: 2f+1 = 5 servers, quorum = 3
f=3: 2f+1 = 7 servers, quorum = 4

3台と4台の耐障害数がどちらも1、5台と6台がどちらも2。偶数台に増やしても耐えられる故障数は増えません。増えるのは、書き込みのたびに応答を待つ相手の数と、故障し得る部品の総数だけです。etcdの公式FAQもこの点を明確に述べており、「奇数サイズのクラスタは、偶数サイズのクラスタと同じ数の故障に、より少ないノードで耐える」と説明しています。同じ表がetcdの公式FAQにも掲載されており、3台で1、5台で2、7台で3という値は上の計算と完全に一致します。

Consulの公式ドキュメントにも同種の表があり、サーバ数2でも4でも耐障害数はそれぞれ0と1にとどまることが示されています。Consulは本番デプロイでは3台または5台を推奨し、1台構成は開発用に限るよう明記しています。etcdのFAQも、クラスタは7ノード以下にすべきで、5台あれば2台の故障に耐えられて多くの場合それで十分だとしています。ノードを増やすと故障耐性は上がるものの、データを多くのマシンに複製する必要があるため書き込み性能が落ちる、というのがその理由です。

まとめると、f台の故障に耐えたければ2f+1台。実務ではまず3台、ゾーン障害まで見込むなら5台、というのが公式ドキュメントの推奨に沿った選び方になります。ノードを増やせば増やすほど良いわけではない点は、ロードバランシングのアルゴリズムで台数を増やす話とは事情が異なるので注意してください。

メンバーシップ変更とログ圧縮

稼働中のクラスタからノードを入れ替えたい、という要求は必ず出てきます。ここを雑にやると、一時的に「旧構成の過半数」と「新構成の過半数」が重ならず、2人のリーダーが同時に成立してしまいます。

原論文が示す解法がjoint consensus（共同合意）です。旧構成Coldから新構成Cnewへ直接切り替えるのではなく、両方を含む中間構成を経由します。この中間状態では、ログエントリは旧構成の過半数と新構成の過半数の両方から承認されなければコミットできません。両者の合意が同時に必要になるため、分裂したリーダーが生まれる余地がなくなります。この方式なら、構成変更中もクラスタはクライアント要求を処理し続けられます。

その後Ongaroは博士論文で、より単純なsingle-server change（1台ずつの変更）を主軸に据え直しています。博士論文は「複雑な変更は一連の1台ずつの変更として実装する」と述べ、joint consensusについては「より単純な1台ずつの方式を知った今は、そちらを推奨する」と明記しています。1台ずつであれば、変更前後の過半数は必ず1台以上重なるため、中間構成なしでも安全性が保てます。実装するなら、まずこちらを検討するのが素直です。

もう1つの実務上の必須要素がログ圧縮（log compaction）です。ログは放っておけば無限に伸びます。そこで各サーバは、ある時点までの状態機械の状態をスナップショットとして保存し、それ以前のログエントリを破棄します。ディスクとメモリが節約でき、再起動時のログ再生も短くなります。大きく遅れたフォロワーには、個々のエントリを送る代わりにスナップショットそのものを転送します。

実務でRaftはどこに使われているか

Raftは論文で終わらず、広く実装されています。ここは各プロジェクトの公式ドキュメントで確認できた内容だけを挙げます。

etcdはKubernetesのコントロールプレーンで使われる分散キーバリューストアです。公式のAPI保証ドキュメントは「etcdは既定で他のすべての操作について線形化可能性を保証する」と述べたうえで、「線形化された要求はRaftの合意プロセスを通らなければならないためコストがかかる」とし、レイテンシを下げたい場合はserializableモードを選べると説明しています。運用パラメータも公式に明記されており、既定のハートビート間隔は100ms、既定のelection timeoutは1000msです。ハートビート間隔はノード間の往復時間の0.5倍から1.5倍程度、election timeoutは往復時間の10倍以上が推奨され、上限は50000ms（50秒）で、これは地理分散クラスタでのみ使うべきだとされています。またハートビート間隔とelection timeoutはクラスタ内の全メンバーで同じ値にすべきで、バラバラだとクラスタの安定性を損なうとも書かれています。

ConsulはRaftを「分散データセンタの操作を管理するために実装している合意アルゴリズム」と説明し、クォーラムを(N/2)+1と定義しています。TiKVはデータをRegionという範囲に分割し、各Regionが1つのRaftグループになります。公式のdeep diveは「Multi-raftとは、1ノード上で複数のRaft合意グループを管理することを意味するにすぎない」と述べています。CockroachDBはRangeごとにRaftグループを作り、耐障害数を「(レプリケーション係数-1)/2」と説明したうえで、「Raftリーダーは、リース移譲中の短期間を除き、常にそのRangeのリースホルダである」と明記しています。

逆に、Raftではないものを取り違えないことも重要です。ZooKeeperは公式のInternalsドキュメントで、自身のプロトコルを「custom atomic messaging protocol」と呼び、Multi-Paxosかという問いに対して「いいえ。Multi-Paxosは単一のコーディネータを保証する何らかの手段を必要とするが、我々はそのような保証に依存していない」と答えています。文献ではこのプロトコルをZab（ZooKeeper Atomic Broadcast）と呼びますが、今回確認した公式ページ上ではZabという名称そのものは見つけられませんでした（未確認）。またZooKeeperの一貫性保証も特徴的で、公式ドキュメントは「書き込みは線形化可能」だが「読み取りは古いデータを返し得るため線形化可能ではない」と明言しています。

Redisも混同されがちです。Redis Clusterの公式仕様書は「Redis ClusterはRaftアルゴリズムのtermに似た概念を使う。Redis Clusterではtermの代わりにepochと呼ぶ」と述べており、Raftそのものを実装しているとは書いていません。フェイルオーバーはgossipベースのcluster busとconfigEpochによる仕組みで行われます。「RedisもRaftを使っている」と一括りにしないよう注意してください。

Raftの限界と、よくある誤解

最後に、Raftを採用するときに知っておくべき性質を整理します。

Raftは線形化可能性を提供するが、分断時には可用性を捨てる。過半数が集まらなければ、Raftは書き込みを進められません。少数派側に取り残されたノードは、正常に動いていてもクライアント要求に応えられなくなります。これはCAP定理でいうCP型の振る舞いそのものです。「Raftを入れれば落ちなくなる」のではなく、「矛盾したデータを返すくらいなら止まる」という設計だと理解してください。可用性が要件の中心にあるなら、そもそも合意アルゴリズムが適さない可能性を先に検討すべきです。分断や遅延に対するクライアント側の備えはタイムアウト・リトライ・サーキットブレーカーの領域になります。

Raftは非ビザンチン障害しか想定しない。ノードはクラッシュしたり遅れたりはしますが、嘘のログを送りつけてくることはない、という前提です。悪意あるノードが混ざり得る環境では、Raftは適用範囲外です。

読み取りをどう扱うかは別途設計が要る。素朴にリーダーの手元の状態を返すと、実はすでに新しいリーダーが立っていて、古い値を返してしまう可能性があります。原論文と博士論文はこれに対する手法を示しています。1つがReadIndexで、手順はこうです。

1. リーダーは、自分のtermのエントリをまだコミットしていなければ、まず空のno-opエントリをコミットする。
2. そのときのcommitIndexをreadIndexとして控える。
3. 新たにハートビートを送り、過半数からの応答を待って、自分がまだリーダーであることを確認する。
4. 状態機械がreadIndexまで進むのを待つ。
5. その状態機械に対してクエリを実行し、結果を返す。

ログに書かないので同期ディスク書き込みが不要で、複数の読み取りで1回分のハートビートを共有すればコストを償却できます。もう1つがlease readで、ハートビートの応答をリースとみなし、リースが有効な間は通信なしで読み取りに応答します。ただしこの方式はサーバ間のクロックドリフトに上界があることを仮定します。博士論文の著者自身も、この方式は非同期モデルの安全性を離れるとして慎重な立場を取っています。読み取り性能が要るからといって安易に選ぶ設定ではありません。

Raftは万能の分散ロックでもトランザクションでもない。Raftが保証するのは1つのレプリカ集合内でのログ順序の合意です。複数のRaftグループにまたがる原子性が必要なら、その上に2相コミットのような仕組みを別途載せることになります。TiKVやCockroachDBがやっているのはまさにそれです。

まとめ

Raftは、合意という難しい問題を「理解しやすさ」を第一目標に再設計したアルゴリズムです。要点を振り返ります。

• 合意が必要なのは単一障害点をなくすため。状態機械複製の考え方では、同じログを同じ順序で適用すれば全サーバの状態は自然に一致する。
• Raftの原論文は「In Search of an Understandable Consensus Algorithm」。OngaroとOusterhoutが、理解しやすさを第一の設計目標に掲げ、問題を分解し、状態空間を削減した。
• サーバはFollower・Candidate・Leaderの3状態を取り、termという単調増加の論理時計で古い情報を機械的に排除する。
• リーダー選出はelection timeoutのランダム化でsplit voteを解消する。固定タイムアウトでは5サーバ200試行すべてが決着せず、ランダム化すると平均1.1回の立候補で決まった。
• ログ複製はAppendEntriesの整合性チェックだけでLog Matching Propertyを維持する。不整合はnextIndexを1つずつ遡ることで必ず修復される。
• 安全性の核はElection Restriction。過半数の重なりにより、コミット済みエントリを欠いた候補者は原理的にリーダーになれない。
• 2f+1台でf台の故障に耐える。偶数台にしても耐障害数は増えず、書き込みの待ち相手が増えるだけ。公式推奨は3台か5台。
• メンバーシップ変更はjoint consensus、より単純には1台ずつの変更。ログ圧縮はスナップショットで行う。
• etcd・Consul・TiKV・CockroachDBはRaftを使う。ZooKeeperは独自のatomic messaging protocol、Redis Clusterはepochという「Raftのtermに似た概念」であり、Raftそのものではない。
• Raftは線形化可能性の代わりに分断時の可用性を捨てるCP型。読み取りはReadIndexかlease readで別途設計する。

合意アルゴリズムは、理屈を読むだけだとどうしても抽象的に感じられます。この記事で使ったような200行程度のシミュレータを手元で書いて、リーダーを落としたりログを分岐させたりしてみると、なぜこのルールが必要なのかが一気に腑に落ちます。木構造を実装で理解した二分探索木と平衡二分探索木と同じで、動かしてみるのがいちばんの近道です。

参考リンク

• In Search of an Understandable Consensus Algorithm (Extended Version) - Ongaro & Ousterhout
• The Raft Consensus Algorithm 公式サイト
• Consensus: Bridging Theory and Practice - Diego Ongaro 博士論文
• etcd Documentation: Tuning（heartbeat interval と election timeout の既定値）
• etcd Documentation: FAQ（クラスタサイズと耐障害数）
• etcd Documentation: API guarantees（線形化可能性と serializable 読み取り）
• Consul Documentation: Consensus protocol
• CockroachDB Documentation: Replication Layer
• TiKV Deep Dive: Multi-raft
• Redis cluster specification（epoch と Raft の term の関係）
• ZooKeeper Internals（atomic messaging protocol と一貫性保証）