合意アルゴリズム - Raft・Paxos・ZABの原理と実装

合意アルゴリズム（Consensus Algorithm）は、ネットワーク遅延やノード障害が発生する分散環境で、複数のノードが同じ値に合意するための技術です。本記事では、Raft、Paxos、ZAB などの代表的な合意アルゴリズムの原理、違い、実装例を体系的に解説します。

概要

合意問題とは

分散システムにおいて、複数のプロセスが提案した値のうち1つを選び、全プロセスがその決定に同意する必要がある問題を合意問題（Consensus Problem）と呼びます。

合意が必要な場面

• リーダー選出（Leader Election）
• 分散ロックの獲得
• トランザクションのコミット決定（2PC / 3PC）
• レプリケートされたログの順序付け

flowchart LR
    subgraph Cluster["分散クラスタ"]
        N1["Node 1<br/>提案: A"]
        N2["Node 2<br/>提案: B"]
        N3["Node 3<br/>提案: A"]
    end

    Consensus["合意アルゴリズム"]
    Result["合意結果: A"]

    N1 --> Consensus
    N2 --> Consensus
    N3 --> Consensus
    Consensus --> Result

FLP 不可能性定理

1985年にFischer、Lynch、Patersonが証明した定理で、非同期分散システムでは、たった1つのノード障害でも決定性のある合意は不可能であることを示しています。実用的な合意アルゴリズムはタイムアウトや故障検出器を使って現実的な解決を図ります。

原則・定義

合意アルゴリズムの3条件

正しい合意アルゴリズムは以下を満たす必要があります。

1. Agreement（一致性）

すべての正常なプロセスが同じ値に合意する。

2. Validity（妥当性）

合意された値は、いずれかのプロセスが提案した値である（ランダムな値ではない）。

3. Termination（停止性）

すべての正常なプロセスが有限時間内に合意に達する。

故障モデル

構成要素

主要アルゴリズムの比較

flowchart TB
    Problem["合意問題"]
    CrashOnly{"Crash Faultのみ?"}
    Complexity{"複雑性は許容?"}
    Order{"厳密な順序保証?"}

    Paxos["Paxos"]
    Raft["Raft"]
    ZAB["ZAB"]
    PBFT["PBFT/BFT"]

    Problem --> CrashOnly
    CrashOnly -->|Yes| Complexity
    CrashOnly -->|No| PBFT
    Complexity -->|許容| Paxos
    Complexity -->|回避| Order
    Order -->|必要| ZAB
    Order -->|不要| Raft

実装例

1. Raft の基本動作（TypeScript 風 Pseudocode）

Raft はリーダーベースのアルゴリズムで、リーダー選出とログレプリケーションの2フェーズで動作します。

enum NodeState {
  Follower = "FOLLOWER",
  Candidate = "CANDIDATE",
  Leader = "LEADER",
}

interface LogEntry {
  term: number;
  index: number;
  command: string;
}

class RaftNode {
  private state: NodeState = NodeState.Follower;
  private currentTerm = 0;
  private votedFor: string | null = null;
  private log: LogEntry[] = [];
  private commitIndex = 0;
  private electionTimeout: number;

  constructor(
    private readonly nodeId: string,
    private readonly peers: string[],
  ) {
    this.resetElectionTimeout();
    this.startElectionTimer();
  }

  // リーダー選出フェーズ
  private startElectionTimer(): void {
    setTimeout(() => {
      if (this.state !== NodeState.Leader) {
        this.startElection();
      }
    }, this.electionTimeout);
  }

  private startElection(): void {
    this.state = NodeState.Candidate;
    this.currentTerm++;
    this.votedFor = this.nodeId;
    let votes = 1;

    // 全ピアに投票リクエスト
    for (const peer of this.peers) {
      this.sendRequestVote(peer).then((granted) => {
        if (granted) votes++;
        if (votes > (this.peers.length + 1) / 2) {
          this.becomeLeader();
        }
      });
    }

    this.resetElectionTimeout();
    this.startElectionTimer();
  }

  private async sendRequestVote(peer: string): Promise<boolean> {
    // RPC: RequestVote(term, candidateId, lastLogIndex, lastLogTerm)
    // 応答: { term, voteGranted }
    const lastLog = this.log[this.log.length - 1];
    const response = await this.rpc(peer, "RequestVote", {
      term: this.currentTerm,
      candidateId: this.nodeId,
      lastLogIndex: lastLog?.index ?? 0,
      lastLogTerm: lastLog?.term ?? 0,
    });

    if (response.term > this.currentTerm) {
      this.currentTerm = response.term;
      this.state = NodeState.Follower;
      return false;
    }

    return response.voteGranted;
  }

  // リーダーになった場合
  private becomeLeader(): void {
    this.state = NodeState.Leader;
    console.log(`${this.nodeId} became LEADER for term ${this.currentTerm}`);
    this.sendHeartbeats();
  }

  // ログレプリケーションフェーズ
  private sendHeartbeats(): void {
    if (this.state !== NodeState.Leader) return;

    for (const peer of this.peers) {
      this.sendAppendEntries(peer);
    }

    setTimeout(() => this.sendHeartbeats(), 100); // 100ms ごと
  }

  private async sendAppendEntries(peer: string): Promise<void> {
    // RPC: AppendEntries(term, leaderId, prevLogIndex, prevLogTerm, entries[], leaderCommit)
    const response = await this.rpc(peer, "AppendEntries", {
      term: this.currentTerm,
      leaderId: this.nodeId,
      entries: this.log, // 簡略化: 実際は差分のみ
      leaderCommit: this.commitIndex,
    });

    if (response.success) {
      // 成功: ピアがログをレプリケート
    } else {
      // 失敗: ログの不整合を解消（省略）
    }
  }

  private resetElectionTimeout(): void {
    this.electionTimeout = 150 + Math.random() * 150; // 150〜300ms
  }

  private rpc(peer: string, method: string, args: any): Promise<any> {
    // ネットワークRPCの実装（省略）
    return Promise.resolve({ term: this.currentTerm, voteGranted: true, success: true });
  }
}

2. Paxos（Basic Paxos）の概要

Paxos は Proposer、Acceptor、Learner の3役割に分かれ、2フェーズで合意します。

sequenceDiagram
    participant P as Proposer
    participant A1 as Acceptor 1
    participant A2 as Acceptor 2
    participant A3 as Acceptor 3

    P->>A1: Prepare(n)
    P->>A2: Prepare(n)
    P->>A3: Prepare(n)
    A1-->>P: Promise(n, v_prev)
    A2-->>P: Promise(n, v_prev)
    Note over P: Quorum達成

    P->>A1: Accept(n, v)
    P->>A2: Accept(n, v)
    P->>A3: Accept(n, v)
    A1-->>P: Accepted
    A2-->>P: Accepted
    Note over P: Quorum達成→合意

# Paxos Acceptor の疑似コード
class PaxosAcceptor:
    def __init__(self):
        self.promised_n = None  # 最後に Promise した提案番号
        self.accepted_n = None  # 最後に Accept した提案番号
        self.accepted_value = None

    def prepare(self, n):
        """Phase 1: Prepare リクエスト"""
        if self.promised_n is None or n > self.promised_n:
            self.promised_n = n
            return {"promise": True, "accepted_n": self.accepted_n, "accepted_value": self.accepted_value}
        else:
            return {"promise": False}

    def accept(self, n, value):
        """Phase 2: Accept リクエスト"""
        if self.promised_n is None or n >= self.promised_n:
            self.promised_n = n
            self.accepted_n = n
            self.accepted_value = value
            return {"accepted": True}
        else:
            return {"accepted": False}

3. ZooKeeper Atomic Broadcast（ZAB）

ZAB は Paxos に似ていますが、トランザクションの順序保証を強化しています。

# ZooKeeper のクォーラム設定例（zoo.cfg）
tickTime=2000
dataDir=/var/lib/zookeeper
clientPort=2181
initLimit=5
syncLimit=2

server.1=zoo1:2888:3888
server.2=zoo2:2888:3888
server.3=zoo3:2888:3888

ZooKeeper クライアント操作:

import { createClient } from "node-zookeeper-client";

const client = createClient("localhost:2181");

client.once("connected", () => {
  console.log("Connected to ZooKeeper");

  // リーダー選出用のエフェメラルノード作成
  client.create(
    "/election/leader",
    Buffer.from("node-1"),
    client.CreateMode.EPHEMERAL,
    (error, path) => {
      if (error) {
        console.log("Already exists, I am follower");
      } else {
        console.log("I am the leader!");
      }
    },
  );
});

client.connect();

メリット・デメリット

Raft のメリット

1. 理解しやすさ: 論文が読みやすく、実装が直感的
2. リーダーベース: ログのレプリケーションがシンプル
3. 実績豊富: etcd、Consul、TiKV など多数の採用例

Raft のデメリット

1. リーダー依存: リーダー障害時にダウンタイム発生
2. 書き込み性能: 全てリーダー経由のため、分散書き込み不可
3. ネットワーク負荷: ハートビートによるオーバーヘッド

Paxos のメリット

1. 理論的な完全性: 形式的証明が存在
2. 柔軟性: Multi-Paxos で様々な拡張が可能
3. Google 実績: Chubby、Spanner で大規模運用

Paxos のデメリット

1. 複雑性: 理解・実装が極めて困難
2. 実装のバリエーション: “Paxos Made Simple” でも難しい
3. デバッグ困難: 状態遷移が複雑でバグの再現が困難

ZAB のメリット

1. 順序保証: トランザクションの完全な順序付け
2. ZooKeeper 最適化: 設定管理に特化
3. 枯れた実装: 10年以上の運用実績

ZAB のデメリット

1. ZooKeeper 専用: 汎用合意アルゴリズムとしては使えない
2. 性能限界: 書き込みスループットは数千 ops/sec が上限
3. JVM 依存: Java 実装のみ

ユースケース

1. 分散ロック（etcd / Raft）

# etcdctl でリーダー選出用ロック
etcdctl lock /my-service/leader

# 別のプロセスは待機
etcdctl lock /my-service/leader  # ブロックされる

2. 設定管理（ZooKeeper / ZAB）

Kafka、HBase、Hadoop などが ZooKeeper を使って設定を共有し、ノード障害を検出します。

3. 分散データベース（TiKV / Raft）

TiDB は TiKV（Raft ベースの KVS）上に構築され、リージョン（データ範囲）ごとに Raft グループを形成します。

4. サービスディスカバリ（Consul / Raft）

Consul は Raft でサービスカタログを管理し、ヘルスチェック結果を全ノードで共有します。

落とし穴

1. Split Brain（脳分裂）

ネットワーク分断時に複数のリーダーが選出される問題です。Quorum（過半数）ベースの投票で防ぎます。

flowchart TB
    subgraph Partition1["ネットワーク分断A"]
        N1["Node 1<br/>Leader?"]
        N2["Node 2"]
    end

    subgraph Partition2["ネットワーク分断B"]
        N3["Node 3<br/>Leader?"]
    end

    Warning["<strong>Split Brain!</strong><br/>2つのリーダーが並存"]

    Partition1 -.X.-> Partition2
    N1 --> Warning
    N3 --> Warning

2. Quorum サイズの誤解

N=5 のクラスタでは、過半数は3です。2台障害までは動作しますが、3台障害で停止します。

3. 時刻同期の誤解

Raft や Paxos は物理時刻に依存しません（論理時刻で順序付け）。NTPズレがあっても合意は成立します。ただし、タイムアウト設定は重要です。

4. ログ圧縮の欠如

ログが無限に増えるとディスクを圧迫します。Snapshot（スナップショット）による圧縮が必須です。

5. ハートビートタイムアウトの調整

短すぎると誤検出が増え、長すぎるとフェイルオーバーが遅れます。150〜300ms が一般的です。

比較表

合意アルゴリズムの特性比較

ベストプラクティス

1. 既存ライブラリを使う: 自前実装は避け、etcd / ZooKeeper を使う
2. Quorum サイズ: 3 または 5 ノードが実用的（2f + 1、f は許容障害数）
3. リージョン分散: データセンター跨ぎでノードを配置（可用性向上）
4. ログ圧縮: Snapshot を定期的に取得
5. 監視: リーダー切り替え回数、選出失敗、Quorum 不足を監視
6. カオステスト: Jepsen でネットワーク分断を注入しテスト
7. 段階的ロールアウト: ノードを1台ずつ更新
8. Pre-Vote 機能: Raft 3.x の Pre-Vote でリーダー不安定を回避

まとめ

合意アルゴリズムは、分散システムにおいてノード間で一貫した決定を行うための基盤技術です。

• Raft: 理解しやすく実装しやすい、etcd・Consul で採用
• Paxos: 理論的に優れるが複雑、Google Chubby・Spanner で使用
• ZAB: ZooKeeper 専用、順序保証が強い
• 選択: 新規実装なら Raft、既存インフラなら ZooKeeper
• 実装: 自前実装は避け、枯れたライブラリを使う

合意アルゴリズムは分散システムの心臓部です。慎重に選択しましょう。

応用トピック

Multi-Raft

TiKV や CockroachDB は、データ範囲（Region）ごとに独立した Raft グループを形成します。これにより、水平スケールが可能になります。

flowchart LR
    subgraph Region1["Region 1<br/>(key: a-m)"]
        R1N1["Node A<br/>Leader"]
        R1N2["Node B"]
        R1N3["Node C"]
    end

    subgraph Region2["Region 2<br/>(key: n-z)"]
        R2N1["Node B<br/>Leader"]
        R2N2["Node C"]
        R2N3["Node D"]
    end

Raft Pre-Vote

Diego Ongaro が提案した拡張で、選出前に事前投票を行い、無駄なリーダー切り替えを防ぎます。

Paxos Made Live

Google が Chubby 実装で得た教訓をまとめた論文です。Paxos の理論と実践のギャップが詳述されています。

Byzantine Fault Tolerance（BFT）

悪意のあるノードが存在する環境での合意アルゴリズムです。ブロックチェーン（PBFT、Tendermint）で使われます。

参考リソース

• In Search of an Understandable Consensus Algorithm (Raft Paper)
• Paxos Made Simple - Leslie Lamport
• Paxos Made Live - An Engineering Perspective (Google)
• ZooKeeper’s atomic broadcast protocol: Theory and practice
• etcd Documentation - Raft Implementation
• Designing Data-Intensive Applications - Chapter 9
• Jepsen - Consistency Analysis

関連記事

• CAP定理入門 - 分散システムの一貫性・可用性・分断耐性のトレードオフ
• 分散トランザクション - 2PC・Saga パターンと合意アルゴリズムの関係