分散システム概論

分散システムは、ネットワークで接続された複数のノードが協調して1つのシステムのように振る舞う仕組みだ。1台のマシンでは起きない問題、たとえば部分的な故障、ネットワーク分断、メッセージの遅延や順序の入れ替わりが常態化するため、単一プロセスの設計とは前提から異なる。

この分野は書籍や論文の蓄積が厚く、断片的に学ぶと全体像を見失いやすい。そこでこの記事では、代表的な教科書や論文の章立てを参考にしながら分散システムの主要トピックを俯瞰し、その中でも実装量が多く誤解されやすい Raft（分散合意アルゴリズム） を、他の合意アルゴリズムとの比較を交えながら掘り下げる。

Kubernetesなど最近のシステムは、可用性を高めるために分散システムの理論に基づいた設計がされている。それらを理解するために、この記事では分散システムを体系的にまとめる。

目次と参考にした構成

分散システムの教科書（Tanenbaum & Van Steenの Distributed Systems、Kleppmannの Designing Data-Intensive Applications、van Steenの Distributed Systems（無料公開版）など）は、おおむね次の順序で章を構成することが多い。この記事もその流れを踏襲する。

1. 分散システムとは何か、なぜ難しいか
2. 分散システム理論の歴史
3. システムモデル（同期・非同期、故障モデル）
4. 時刻と順序（物理時計・論理時計）
5. 通信の信頼性（RPC、べき等性、配送保証）
6. 一貫性モデルとCAP/PACELC
7. レプリケーションとパーティショニング
8. 分散合意（Consensus）の基礎、Paxos、FLP不可能性
9. Raftアルゴリズム詳解（合意アルゴリズム全体の中での位置づけを含む）
10. 分散トランザクション（2PC/3PC、Sagas）
11. 障害検出とメンバーシップ管理（Gossip、SWIM）
12. 実システムに見る組み合わせ（etcd、ZooKeeper、Kafka、Spanner）

1. 分散システムとは何か

分散システムとは、独立して故障しうる複数のコンピュータが、ネットワークを介してメッセージだけをやり取りしながら、利用者から見ると1つの首尾一貫したシステムであるかのように協調動作する仕組みを指す。

単一プロセスの設計と決定的に違う点は、次の3つに集約できる。

この3点があるため、分散システムの設計では「常に正常に動く」ことを前提にせず、「一部が壊れても全体として妥当な振る舞いを保てるか」を軸に考える。

2. 分散システム理論の歴史

分散システムの理論は、実際に直面した課題が変わるたびに、新しい考え方やアルゴリズムが生まれてきた分野だ。年表で並べると、何が課題でどう解決されてきたかの流れが見える。

この年表を俯瞰すると、分散システムの理論はおおむね3段階の課題を順番に扱ってきたと整理できる。

1. 順序をどう定義するか（1970年代後半〜）: 単一の時計がない中でイベントの前後関係を定義する（Lamportタイムスタンプ、ベクタークロック）
2. 合意をどう安全に・分かりやすく実現するか（1980年代〜2014年）: 故障やネットワーク分断があっても複数ノードが1つの値に合意する（Paxos、Raft）
3. 合意をどうスケールさせるか（2010年代後半〜）: 単一Leaderの合意グループがボトルネックになる問題への対処（Multi-Raft、EPaxosなど）

以降の章は、この3段階の課題がそれぞれどう解決されているかという観点で読み進めると理解しやすい。

3. システムモデル（同期・非同期、故障モデル）

議論を厳密にするため、まず「どんな前提を置くか」を明示する。それが分散システムの作法だ。

同期モデルと非同期モデル

• 同期モデル: メッセージ配送とプロセス実行に既知の上限時間がある。タイムアウトで「故障」を確実に判定できる
• 非同期モデル: 配送時間や実行時間にも上限がない。原理的には「遅いだけ」なのか「壊れている」のかを区別できない

現実のネットワークは厳密な同期モデルではないため、多くの分散アルゴリズムは「実用上はおおむね同期的に振る舞う」という部分同期モデル（partial synchrony）を前提にする。RaftやPaxosの安全性の議論も、この現実的な前提の上に成り立っている。

故障モデル

PaxosやRaftをはじめ、ミドルウェア向けの合意アルゴリズムの多くは crash-stop/crash-recovery を前提にしており、ビザンチン故障（嘘をつくノード）までは扱わない。これは設計をシンプルに保つための意図的な割り切りであり、「合意アルゴリズムは万能の耐障害アルゴリズムではない」という点として覚えておくとよい。それぞれの合意アルゴリズムが全体の中でどう位置づけられるかは、8章の比較表で整理する。

4. 時刻と順序

分散システムには単一の正しい時計が存在しない。各ノードの物理時計にはずれ（クロックドリフト）があり、NTPで同期してもミリ秒〜数十ミリ秒単位の誤差が残る。そのため、多くの分散アルゴリズムは物理時刻ではなく 論理的な順序 を使う。

Lamportタイムスタンプ

Lamportの論理時計は、各ノードが持つカウンタを次のルールで進めるだけの単純な仕組みだ。

1
2
3
4
5
6
7
8
9

on local event:
  counter = counter + 1

on send message:
  counter = counter + 1
  attach counter to message

on receive message(msg):
  counter = max(counter, msg.counter) + 1

このルールにより、「イベントAがイベントBより先に起きた（happens-before）」関係がある場合は必ず

ベクタークロック

Lamportタイムスタンプの限界（因果関係の有無まで判定できない）を補うのがベクタークロックだ。ノードごとにカウンタを持つ配列を管理し、メッセージ送受信のたびに自ノード分を増やし、受信時は要素ごとの最大値を取る。2つのタイムスタンプを比較したとき、片方が全要素で他方以上であれば「先に起きた」と判定でき、そうでなければ「並行（concurrent）」と判定できる。DynamoスタイルのKVSが、コンフリクト検出にベクタークロックを使う例として知られている。

5. 通信の信頼性とRPC

分散システムのノード間通信は、メッセージの喪失・重複・遅延が起こりうる前提で設計する必要がある。配送保証には主に3種類がある。

「本当のExactly-once配送」は、ネットワークを完全に信頼できない以上、原理上難しい。多くの実システムは重複除去用のリクエストIDやべき等性のある操作設計を使って、疑似的に実現している。Raftのクライアント対話でも、リクエストごとに一意なIDを持たせて重複コマンドの二重適用を防ぐ設計がよく使われる。

6. 一貫性モデルとCAP/PACELC

「一貫性」という言葉は文脈によって指す内容が大きく異なるため、まずレベル分けを押さえておくと会話がかみ合いやすい。

CAP定理とPACELC

CAP定理は「Consistency（一貫性）・Availability（可用性）・Partition tolerance（分断耐性）の3つを同時には満たせない」という定理として知られるが、ネットワーク分断は現実に起こりうる以上、実質的には「分断時にCを取るかAを取るか」の選択として理解したほうが実務的だ。CAP定理の基本的な考え方や、Webシステムを例にした具体的な説明は、以前書いた システムの高可用性の担保と etcd, Raft について でも扱っているので、あわせて参照してほしい。

PACELCはこれを拡張し、「分断時（Partition）はConsistencyとAvailabilityのどちらを優先するか、それ以外（Else）の平常時はLatencyとConsistencyのどちらを優先するか」という2軸で整理する。RaftやPaxosベースのシステムは、分断時・平常時を問わず一貫性（C）を優先し、その代償としてリーダーに到達できない間は書き込みの可用性を落とす設計だ。

7. レプリケーションとパーティショニング

大規模データを扱うシステムは、レプリケーション（複製による耐障害性）とパーティショニング（分割によるスケールアウト）を組み合わせる。

• シングルリーダー方式: 1つのノードだけが書き込みを受け付け、他は読み取り専用レプリカになる。一貫性の管理がしやすく、Raftのリーダーもこの方式に近い
• マルチリーダー方式: 複数拠点で書き込みを受け付け、後から競合を解決する。地理分散での書き込みレイテンシを下げやすい反面、コンフリクト解決が複雑になる
• リーダーレス方式: Dynamoのように、クォーラム（
  $W + R > N$
  ）で読み書きの整合性を担保する

パーティショニングでは、ノード追加・削除時の再配置コストを抑えるために Consistent Hashing がよく使われる。ハッシュ空間をリング状に扱い、担当範囲の変更を一部のノードだけに局所化する考え方だ。

8. 分散合意（Consensus）の基礎

分散合意とは、複数ノードが提案した値の中から、故障や通信障害があっても ただ1つの値に全員が合意する ための手続きを指す。レプリケーションされたログ、リーダー選出、分散ロックなど、多くの分散システムの土台になっている。

FLP不可能性

Fischer、Lynch、Paterson（1985年）は、次の3条件をすべて満たす環境では、どんな決定的アルゴリズムであっても合意を成立させられないケースが必ず存在することを証明した（FLP不可能性）。

• 非同期モデル（メッセージ配送に上限時間がない）
• 1つ以上のプロセスがクラッシュしうる（Fail-stop）
• アルゴリズムが決定的（同じ入力なら常に同じ出力になる）

証明の直感は次のようなものだ。非同期モデルでは、メッセージが単に遅れているだけなのか、送信元プロセスが故障してもう届かないのかを、受信側は原理的に区別できない。合意アルゴリズムがある時点で結論を確定させようとしても、メッセージの配送タイミングを最悪の順序で操作できる敵対的なスケジューラを想定すると、決定を確定させる直前の1通のメッセージだけを狙って遅延させ続けることで、合意の確定をいつまでも先延ばしにできてしまう。これは特定の実装の欠陥ではなく、上記3条件を満たす限りどんなアルゴリズムにも当てはまる理論的な限界だ。

これは「分散合意は不可能」という意味ではない。PaxosやRaftは実際に正しく動作している。FLP不可能性が示しているのは、あくまで「非同期モデルという前提を崩さない限り、最悪ケースまで含めて『必ず有限時間で終了する』ことを保証する決定的アルゴリズムは存在しない」という点に限られる。実用的な合意アルゴリズムは、次に扱うPaxos・Raftのように、ランダム化されたタイムアウトや部分同期という前提を持ち込むことで、この理論的な壁を実務上は問題にならない形へ回避している。

Paxos

Paxos（Lamport, 1998/2001）は分散合意の古典的な解で、処理を次の3つの役割に分解する。

• Proposer: 値を提案する
• Acceptor: 提案を受理するかどうか投票する（過半数の受理で合意成立）
• Learner: 合意された値を学習する

基本形（Basic Paxos）は次の2フェーズで進む。

1. Prepare/Promiseフェーズ: Proposerが一意な提案番号を採番してAcceptorにPrepareを送る。Acceptorは、それより小さい番号の提案はもう受理しないと約束（Promise）し、すでに受理済みの値があればそれをProposerに返す
2. Accept/Acceptedフェーズ: Proposerは、Promiseで返ってきた値があればそれを、なければ自分の提案値を、過半数のAcceptorにAcceptとして送る。過半数がAcceptedを返せば合意成立

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

# Proposer側の擬似コード（簡略化）
n = generate_unique_proposal_number()
promises = send Prepare(n) to majority of acceptors, wait for promises

if len(promises) < majority:
  retry with a higher n

# すでに受理された値があれば、それを引き継ぐ（安全性の要）
value = highest_numbered_accepted_value(promises) or my_own_value

accepted = send Accept(n, value) to majority of acceptors, wait for accepted
if len(accepted) >= majority:
  value is chosen

Paxosが難解と言われる理由は、大きく2点ある。

1. 1つの値を合意するだけでも2フェーズの往復が必要で、しかも提案番号の衝突により再試行が発生しうる。安全性の証明（過半数のAcceptorがいれば矛盾しないことの証明）は堅牢だが、直感的に追いにくい
2. 実運用でログ全体を複製するには、Paxosのインスタンスを繰り返し実行する Multi-Paxos が必要になるが、原論文はここを詳細に規定しておらず、安定したリーダー選出やログの穴埋めなど、実装者が独自に設計を補う部分が多い

Raft（Ongaro & Ousterhout, 2014）は、Paxosと等価な安全性を保ちながら、この「実装者が補わなければならない部分」まで含めて最初から仕様化し、理解しやすさ（Understandability）を第一目標 に設計し直したアルゴリズムだ。具体的には、Multi-Paxosでは曖昧だった「強いリーダーを常に1人立てる」ことを前提として固定し、リーダー選出・ログレプリケーション・安全性という3つの独立した問題に明示的に分解した。論文タイトルも “In Search of an Understandable Consensus Algorithm” であり、教育目的での比較実験でもRaftの方が理解されやすいという結果が報告されている。

分散合意アルゴリズムの全体比較

Paxos以降、目的や前提の違いによって複数の派生・代替アルゴリズムが生まれている。全体の中でRaftがどこに位置するかを整理すると次のようになる。

こう整理すると、Raftは「Paxos系の安全性を持ちながら、理解しやすさと実装のしやすさを優先した、強いリーダー方式の合意アルゴリズム」という立ち位置にあることが分かる。単一リーダーゆえに書き込みのスケーラビリティには限界があり、これを補うために後述のMulti-RaftやEPaxosのようなリーダーレス方式が生まれている。

9. Raftアルゴリズム詳解

前節で比較したとおり、Raftは数ある分散合意アルゴリズムの中でも「Paxos相当の安全性を保ちながら、強いリーダーを前提に理解しやすさを最優先した」設計だ。ここからは、そのRaftの内部動作を掘り下げる。Raftは大きく3つの独立したサブ問題に分解して設計されている。

1. リーダー選出（Leader Election）: クラスタの中から1台のリーダーを選ぶ
2. ログレプリケーション（Log Replication）: リーダーが受けたコマンドを他ノードへ複製する
3. 安全性（Safety）: 上記2つがどんな障害の組み合わせでも矛盾した状態にならないことを保証する

9.1 サーバの状態遷移

Raftのノードは、常に次の3状態のいずれかにある。

• Follower: 通常状態。リーダーやCandidateからのRPCに応答するだけの受動的な役割
• Candidate: リーダー不在を検知して立候補している状態
• Leader: クライアントからの書き込みを受け付け、ログを他ノードへ複製する役割

起動直後は全ノードがFollowerから始まり、一定時間（election timeout）リーダーからの信号（heartbeat）が来なければCandidateに遷移する。

9.2 Term（任期）

Raftは論理時計として term（任期） という単調増加の整数を使う。各termにはリーダーが最大1人しか存在しない（存在しないtermもありうる）。ノードはRPCのたびに相手のtermと自分のtermを比較し、自分より高いtermを見つけたら即座にFollowerへ降格して自分のtermを更新する。この単純なルールだけで、「同時に2人のリーダーが両方とも書き込みを受け付け続ける」状態を防いでいる。

9.3 リーダー選出（RequestVote RPC）

election timeoutが発生したFollowerは、自分のtermを1つ増やしてCandidateになり、他の全ノードにRequestVote RPCを並列に送る。

投票側の判定ロジックは擬似コードで書くとおおよそ次の通りになる。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

on receive RequestVote(term, candidateId, lastLogIndex, lastLogTerm):
  if term < currentTerm:
    return VoteGranted=false

  if term > currentTerm:
    currentTerm = term
    become Follower
    votedFor = null

  # 「まだこのtermで投票していない」かつ「相手のログが自分と同じか新しい」場合のみ投票
  if (votedFor is null or votedFor == candidateId) and
     candidateLogIsAtLeastUpToDate(lastLogIndex, lastLogTerm):
    votedFor = candidateId
    reset election timer
    return VoteGranted=true

  return VoteGranted=false

ポイントは2つある。

• 1つのtermにつき、1ノードは高々1票しか投じない（votedForで保証）。これにより、同一termで過半数を取れるCandidateは最大1人に限られる
• 投票する側は、Candidateのログが「自分と同じくらい新しいか、それ以上新しい」場合しか投票しない。これがのちに説明する安全性の要になる

一定時間内に過半数の票が集まらない場合（票が割れた、ネットワーク遅延など）は、election timeoutが再度発生してtermをさらに増やし、再選挙になる。Raftはこの再選挙のタイミングをノードごとにランダム化することで、票の分裂が連続する確率を実用上十分低く抑えている。

9.4 ログレプリケーション（AppendEntries RPC）

Leaderに昇格したノードは、クライアントから受けたコマンドを自分のログに追記し、AppendEntries RPCで他ノードへ複製する。AppendEntriesは空でも定期的に送られ、これがそのままheartbeatとして機能する（heartbeatとログ複製は同じRPCで統一されている）。

Follower側の整合性チェックは、次の擬似コードのように「1つ前のエントリが一致しているか」を必ず確認する。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

on receive AppendEntries(term, leaderId, prevLogIndex, prevLogTerm, entries, leaderCommit):
  if term < currentTerm:
    return Success=false

  if log[prevLogIndex].term != prevLogTerm:
    # 直前のエントリが食い違っている -> このAppendEntriesは拒否
    return Success=false

  # 矛盾するエントリがあれば削除して上書き
  for entry in entries:
    if log has conflicting entry at same index:
      truncate log from that index
    append entry to log

  if leaderCommit > commitIndex:
    commitIndex = min(leaderCommit, index of last new entry)

  return Success=true

prevLogIndex/prevLogTermによる一貫性チェックのおかげで、Followerのログが1つでも欠けていたり食い違っていたりすると、そのFollowerへの複製は失敗し続ける。Leaderは失敗を検知すると、そのFollower用のnextIndexを1つずつ遡らせながら再送し、最終的に一致するところまで巻き戻してから正しい内容で上書きする。

9.5 安全性（Safety）

Raftの論文が特に力を入れているのが、この安全性の議論だ。代表的な性質を3つ挙げる。

Leader Completenessが成り立つ理由は直感的には次のように説明できる。あるエントリがコミットされたということは、過半数のノードがそのエントリを持っている。次にLeaderになるためには過半数の票が必要であり、Election Restrictionにより「ログが古いノード」は投票を得られない。したがって、過半数の票を得た新しいCandidateは、必ずコミット済みエントリを持つノード群と1つ以上重なる。これにより、新しいLeaderのログには既存のコミット済みエントリが必ず含まれることになる。

9.6 コミットルールの落とし穴

Raftでは「過半数に複製できたら即コミット」という単純なルールに、1つだけ例外がある。Leaderは、自分の現在のtermで作成したエントリしか、複製数だけを根拠にコミットしてはいけない。 過去のtermのエントリを間接的にコミットする場合は、それより後の自termのエントリが先にコミットされることを条件にする。

この制約がない場合、過半数に複製されたのに後から上書きされてしまう反例がRaft論文の中でも図解されている。ここはRaftの正しさの中でも直感に反しやすい部分であり、実装時にありがちなバグの温床でもある。

9.7 メンバーシップ変更

クラスタのノード構成（追加・削除）を変更する操作自体も、合意を壊さずに行う必要がある。設定変更を単純に一括切り替えすると、新旧の構成で別々の過半数が同時にLeaderを選んでしまう「二重Leader」が起こりうる。

• Joint Consensus方式（原論文の方式）: 旧構成
  $C_{old}$
  と新構成
  $C_{new}$
  の両方の過半数合意を要求する中間状態
  $C_{old,new}$
  を経由してから、最終的に
  $C_{new}$
  のみへ切り替える。安全だが実装がやや複雑
• 単一サーバ変更方式: 1台ずつしかノードを追加・削除しないという制約を課すことで、
  $C_{old}$
  と
  $C_{new}$
  の過半数集合が必ず重なることを保証し、中間状態を省略する。etcdなど多くの実装がこちらを採用している

いずれの方式でも、「新旧構成の過半数集合が必ず1つ以上重なる」ことが安全性のポイントになる。

9.8 ログ圧縮とスナップショット

ログは無限に増え続けるため、実運用では定期的に スナップショット を取り、それ以前のログエントリを破棄する。スナップショットには「その時点までのステートマシンの状態」「最後に含まれるログのindexとterm」を保持し、遅れているFollowerにはログの代わりにInstallSnapshot RPCでスナップショットそのものを送る。

スナップショット導入後は、prevLogIndexがスナップショット境界より古い場合の扱いなど、実装上の分岐が増える。この境界処理は多くのRaft実装でバグが出やすい箇所として知られている。

9.9 クライアント対話とlinearizable read

Raftは「書き込みはLeader経由でログにコミットする」ことで一貫性を保つが、読み取り をそのままLeaderのローカル状態から返すと、実は問題が起こりうる。すでに新しいLeaderが選ばれているのに、自分がまだLeaderだと思い込んでいる旧Leader（ネットワーク分断で孤立したノード）が古い値を返してしまう可能性があるためだ。

これを避けるための代表的な手法を2つ挙げる。

• Read Index方式: 読み取り要求を受けたLeaderが、その時点のcommitIndexを記録した上で、過半数に対して自分がまだLeaderであることを確認するheartbeatを1往復してから応答する
• Lease方式: Leaderが一定時間（クロックのずれを考慮したリース期間）内は他にLeaderが存在しないとみなし、heartbeatなしでローカル読み取りに応答する。実装が軽い代わりに、クロックの精度に安全性が依存する

どちらも「線形化可能な読み取り」を実現するための工夫であり、素朴にLeaderのメモリを読むだけでは足りないという点がRaft運用でよく見落とされる。

9.10 Multi-Raft

単一Raftグループでは、Leaderが全コマンドを順番に処理するため、書き込みスループットはLeader1台の処理能力を上限とする。これを解消するために、データをキー範囲などで分割し、範囲ごとに独立したRaftグループ（レンジ/リージョンと呼ばれることが多い）を多数並列に走らせる構成が Multi-Raft だ。

• 各Raftグループは独立してLeader選出・ログ複製を行うため、グループ数を増やすことで書き込みスループットを水平にスケールできる
• 1台のノードが複数のRaftグループのLeaderとFollowerを混在して担当するため、ハートビートやスナップショット転送を束ねて通信オーバーヘッドを抑える最適化が必要になる（CockroachDBのcoalesced heartbeatsなど）
• グループ間をまたぐトランザクション（複数レンジにまたがる書き込み）は、Raftの合意だけでは完結せず、次章で扱う分散トランザクションと組み合わせる必要がある

CockroachDBやTiKVは、この Multi-Raft 構成によって分散SQLデータベースとしてのスケーラビリティと一貫性を両立させている。8章の比較表で挙げたEPaxos（リーダーレス方式）が単一リーダーのボトルネック自体を無くす方向の解だとすれば、Multi-Raftは「単一リーダーの合意グループを水平に増やす」方向の解だと位置づけられる。

9.11 代表的な実装

いずれの実装も基本アルゴリズムはRaft論文に忠実だが、性能のためにパイプライン化、バッチ化、Multi-Raftのような独自最適化が積まれている点は留意しておくとよい。

10. 分散トランザクション

複数のパーティションやサービスにまたがる書き込みを、原子的に（全部成功または全部失敗のいずれか）行いたい場面で使われる手法群。

• 2フェーズコミット（2PC）: コーディネータがPrepare（準備できるか確認）→Commit（確定指示）の2段階で進める。仕組みはシンプルだが、コーディネータがPrepare後に落ちると参加者がロックしたまま待ち続ける「ブロッキング」問題がある
• 3フェーズコミット（3PC）: 2PCのブロッキング問題を緩和するために段階を1つ増やした方式だが、非同期ネットワークでは完全には解決しきれず、実運用での採用例は限定的
• Sagas: 各ステップをローカルトランザクションとして実行し、失敗時は補償トランザクション（打ち消し操作）で巻き戻す方式。原子性は厳密には保証しないが、マイクロサービス間の長時間トランザクションでよく使われる

GoogleのSpannerは、TrueTime（誤差範囲付きの時刻API）とPaxosベースのレプリケーションを組み合わせ、地理分散環境でも外部一貫性（external consistency）を持つ分散トランザクションを実現している例として知られている。

11. 障害検出とメンバーシップ管理

クラスタ内で「どのノードが生きているか」を把握する仕組みも分散システムの重要な要素だ。

• Heartbeat方式: 一定間隔で生存確認を送り合う。単純だが、ノード数が増えると通信量が線形以上に増える
• Gossip（うわさ話）プロトコル: 各ノードがランダムに選んだ少数のノードとだけ状態を交換し、それが伝播していくことでクラスタ全体に情報が広がる。通信量を抑えつつスケールしやすい
• SWIM: Gossipに加えて、間接的な生存確認（他のノード経由でのping）を組み合わせ、誤検知を減らしながら検出時間を抑えるプロトコル
• Phi Accrual障害検出器: 「生きている/死んでいる」の二値ではなく、疑わしさを連続値（phi値）で表現し、閾値をアプリケーション側で調整できるようにする方式。Cassandraなどで採用されている

Raftを含むConsensusアルゴリズムは「誰がLeaderかを決める」ことを専門としており、クラスタ全体で行う数百〜数千ノード規模の緩やかなメンバーシップ管理（生存監視）にはGossip系のプロトコルを使うことが多い。役割が異なる技術として併用されるのが一般的だ。

12. 実システムに見る組み合わせ

最後に、ここまでの要素技術が実際のシステムでどう組み合わさっているかを整理する。

同じ「合意」や「レプリケーション」という言葉でも、前提にしている一貫性モデル・障害モデルはシステムで異なる。ミドルウェアを選定するときは、アルゴリズム名だけでなく「どの一貫性モデルを、どの障害モデルの下で保証しているか」まで確認したほうがよい。

実務へ持ち込むときの見方

• 「なぜこの処理は遅いのか」で詰まったら、まず一貫性モデルを疑う。線形化可能な読み取りにはリーダーへの往復や過半数確認が必要で、これがレイテンシの主要因になっていることが多い
• 「なぜこのノードだけ古いデータを返すのか」は、多くの場合ネットワーク分断で孤立したノードがローカル読み取りに応答している状態を疑うとよい
• Raftベースのミドルウェアで書き込みが詰まったら、まずLeaderが安定して選出されているか（頻繁な再選挙が起きていないか）を確認する。election timeoutの設定値とネットワーク遅延の関係を見直す価値がある
• 分散トランザクションが必要な場面でも、まずは1つのパーティション内で完結するよう設計を見直せないか検討するとよい

注意点

• Raftを含む多くの合意アルゴリズムはcrash-stop/crash-recoveryを前提としており、ビザンチン故障（嘘をつくノード）までは扱わない
• Raftの安全性は「過半数（majority）」の重なりに依存する。ネットワーク分断でクラスタが分割されたとき、過半数を確保できない側は書き込みを受け付けなくなる（可用性より一貫性を優先する設計）
• FLP不可能性は理論的な限界であり、実装が「絶対に止まらない」ことを意味するわけではない。実運用では十分低い確率まで抑えられているという理解が実態に近い
• スナップショットやメンバーシップ変更まわりは、教科書的な擬似コードだけでは実装しきれない境界条件が多い。実装する場合は、原論文の付録（TLA+による形式仕様）や既存OSS実装のテストケースを参照したほうが安全

参考文献

書籍

• Kleppmann, M. Designing Data-Intensive Applications. O’Reilly, 2017
• van Steen, M. and Tanenbaum, A. S. Distributed Systems, 3rd edition（著者サイトで無料公開）
• Vitillo, R. Understanding Distributed Systems, 2nd edition, 2023

論文

• Ongaro, D. and Ousterhout, J. “In Search of an Understandable Consensus Algorithm (Raft)”. USENIX ATC, 2014
• Lamport, L. “Paxos Made Simple”. ACM SIGACT News, 2001
• Lamport, L. “Time, Clocks, and the Ordering of Events in a Distributed System”. Communications of the ACM, 1978
• Fischer, M. J., Lynch, N. A., and Paterson, M. S. “Impossibility of Distributed Consensus with One Faulty Process”. Journal of the ACM, 1985
• Oki, B. M. and Liskov, B. “Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems”. PODC, 1988
• Brewer, E. “CAP Twelve Years Later: How the ‘Rules’ Have Changed”. IEEE Computer, 2012
• Junqueira, F. P., Reed, B. C., and Serafini, M. “Zab: High-performance broadcast for primary-backup systems”. DSN, 2011
• Moraru, I., Andersen, D. G., and Kaminsky, M. “There Is More Consensus in Egalitarian Parliaments”. SOSP, 2013
• Das, A., Gupta, I., and Motivala, A. “SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol”. DSN, 2002
• Corbett, J. C. et al. “Spanner: Google’s Globally-Distributed Database”. OSDI, 2012
• DeCandia, G. et al. “Dynamo: Amazon’s Highly Available Key-value Store”. SOSP, 2007

一次情報

• Raft Consensus Algorithm 公式サイト
• The Raft Paper (PDF)
• etcd Documentation

関連記事

• システムの高可用性の担保と etcd, Raft について — CAP定理とRaftについて、Webシステムの具体例をもとに説明した記事