【2026年7月版】

コンセンサスアルゴリズム・アンダーグラウンド【第1回】 ― 停止と遅延は区別できない

公開日: 2026/07/22
読了時間: 約 10分

コンセンサスは「話し合い」ではない

コンセンサスアルゴリズムは、通常「複数のノードが同じ値に合意する仕組み」と説明される。誤りではないが、実装と運用の現場で対象となるのは、より具体的な障害である。

ノードは突然停止する。応答がないとき、停止したのか遅延しているのかは判別できない。メッセージは遅延し、重複し、順序が入れ替わる。ディスクへの書き込みは完了したように見えて失われることがある。古いリーダーが自身をリーダーだと認識したまま、ネットワーク分断の両側で処理を続けることもある。ブロックチェーンでは、さらに一部のノードが意図的に虚偽の情報を送る。

したがって、コンセンサスの本質は合議による意思決定ではない。

不完全な通信と部分的な障害の下で、どの履歴を正史として残すかを決定することである。

本シリーズでは、Paxos、Raft、Viewstamped Replication、Zab、PBFT、Tendermint、HotStuff、Narwhal、Bullshark、Mysticeti、PoW、PoS、Avalanche 系を、解決対象の問題と実装構造の観点から順に整理する。第1回はその前段として、いずれのアルゴリズムを選んでも回避できない基盤部分を扱う。

一つに見えて、三つある問題

コンセンサスという語は、実際には別個の三つの問題を一括している。

リーダーを決める。どのノードが現在の書き込み窓口かを決定する。
操作順序を決める。SET x=1 と SET x=2 のいずれが先行するかを、全ノードで一致させる。
決定を確定する。確定した操作が、再選挙や障害復旧の後に覆らないことを保証する。

重要なのは、リーダー選出だけではコンセンサスが成立しない点である。

Redis Sentinel、Kubernetes の Lease、ZooKeeper の一時ノードを用いれば、リーダーは選出できる。しかし、そのリーダーが処理した操作が過半数へ永続化されていなければ、フェイルオーバー時に失われる。誰かが選出されていることと、その処理結果が残ることは別の保証である。

逆に、EPaxos や DAG-BFT のように固定リーダーを置かず、操作間の依存関係や証明書から順序を決定する方式もある。リーダーは手段であって、目的ではない。

停止と遅延は区別できない

ノードAからノードBへ要求を送信し、応答がない。原因の候補は次のとおり複数ある。

Bのプロセスが停止した
BのOSが応答しなくなった
Bまでの経路が切断された
GCやI/O待ちで停止している
AからBへの片方向のみ通信できない
応答は送信されたが経路上で失われた

非同期ネットワークでは、有限時間内に停止と遅延を完全に判定することはできない。これが FLP 不可能性の実務的な意味である。完全な非同期系において、少なくとも一つのノードが停止し得る場合、常に終了する決定的なコンセンサスアルゴリズムは存在しない。

実際のシステムは、この制約を次の仮定によって回避する。

タイムアウトを用いて一定の同期性を仮定する
ランダム性を導入する
障害検知器を仮定する
安全性を維持したまま、一時的に進行を停止する

Raft や HotStuff は、ネットワークが一定期間は正常化するという部分同期モデルを実用上の前提とする。すなわち、これらのアルゴリズムは常に進行することを設計時点で放棄している。放棄したのは進行性であり、維持しているのは安全性である。

Split brain と、外へ漏れる副作用

ネットワークが二つに分断され、双方が自身を正当なクラスタと判断した場合、履歴は二つに分岐する。

            partition
   A ─ B   |   C ─ D ─ E
 leader    |   new leader

多数派にのみ書き込みを許可すれば、左は2票、右は3票となり、右側だけが処理を継続できる。これが過半数クォーラムの基本である。

ただし、これによって保護されるのはクラスタの内側に限られる。古いリーダーは、ストレージ、ジョブキュー、外部API、機械設備に対して命令を発行し続けることができる。クラスタ内部の投票結果は、外部資源には到達しない。

そのため実システムでは、単なるリーダーフラグではなく、単調増加する term、epoch、generation といった世代番号（fencing トークン）を、副作用の実行先にも検査させる。

class FencedResource:
    def __init__(self):
        self.highest_token = 0
        self.value = None

    def write(self, token: int, value: str) -> None:
        if token < self.highest_token:
            raise RuntimeError("stale leader")
        self.highest_token = token
        self.value = value

コンセンサスの結果をクラスタ内部に保持するだけでは不十分であり、副作用の実行先まで世代番号を伝播させる必要がある。

合意したログと、適用済みの状態は違う

典型的なレプリケートステートマシンは、次の層に分かれる。

client request
    ↓
 proposal
    ↓
 replicated log
    ↓
 commit
    ↓
 state-machine apply
    ↓
client response

ログへ追加されたこと、過半数へ複製されたこと、状態機械へ適用されたことは、いずれも別の事象である。

if replicated_to_majority(entry):
    commit_index = entry.index

while applied_index < commit_index:
    applied_index += 1
    state_machine.apply(log[applied_index])

この境界を曖昧にすると、次の障害が生じる。

コミット前の値をクライアントへ成功として返す
再起動後に同一コマンドを二重適用する
スナップショットとログの境界がずれる
適用済みだが応答前に停止した要求を、クライアントの再送により再実行する

最後の項目が示すとおり、コンセンサスは exactly-once を自動的には提供しない。提供するのはログの順序と確定のみである。同一要求が二度実行されないことは、クライアント要求IDによる重複排除で別途担保する。

def apply(command):
    if command.request_id in completed:
        return completed[command.request_id]

    result = execute(command)
    completed[command.request_id] = result
    return result

completed もまた状態機械の一部であり、スナップショットへ含める必要がある。これを欠くと、再起動後にのみ二重適用が発生する、再現困難な障害となる。

まとめ

コンセンサスが解いているのは合意そのものではなく、不完全な通信と部分的な障害の下で、どの履歴を正史とするかという問題である。
リーダー選出・順序決定・確定は別個の問題である。リーダーを選出しても、その処理結果が過半数へ永続化されていなければフェイルオーバーで失われる。
非同期系では停止と遅延を区別できない（FLP不可能性）。実用アルゴリズムは部分同期などを仮定し、進行性を放棄して安全性を維持する。
過半数クォーラムはクラスタの内側しか保護しない。外部資源には fencing トークンによって世代番号を検査させる。
ログへの追加・コミット・適用は別の事象である。exactly-once はコンセンサスの外側で、要求IDの重複排除として実装する。

次回は、この基盤の上に立つ最初の系譜として、クラッシュ故障モデルのアルゴリズムを扱う。Paxos が用いる唯一の道具であるクォーラムの交差から始め、Raft がそれを実装可能な形へ分解した方法、および論文に記載されない永続化順序やスナップショットまでを取り上げる。