6 分で読了 #distributed-systems #コンセンサスプロトコル
このページの目次

Paxos

コンセンサス問題に対する最初の産業レベルの解決策であり、RaftやZABなどの後続プロトコルの理論的根源。Basic Paxosのprepare/promise/acceptという3フェーズのメッセージ交換は一見単純だが、単一の決定から連続するログ（Multi-Paxos）への移行に至るまで、各ステップで陥りやすい落とし穴が存在する――これがRaftが誕生した直接的な動機でもある。

Paxos (Leslie Lamport, 1989/1998) は、コンセンサス問題に対する最初の産業レベルの解決策であり、VR、ZAB、Raftなどの後続のコンセンサスプロトコルの理論的根源です。しかし、Lamportの元の記述はギリシャ議会の比喩を用いて書かれており、「The Part-Time Parliament」というタイトルからもわかるように、難解で理解しにくいものでした。Raftの設計動機は、「Paxosを一般的なエンジニアが理解できるようにすること」にあります。

Basic Paxos

Paxosは単一のコンセンサスを解決します。複数のノードが1つの値について合意する方法を定義します。

ロール

  • Proposer: 提案を発行する（クライアントは通常、Proposerとして機能する）
  • Acceptor: 投票を行い、acceptedな値を保存する（通常、N=2f+1個のノードで構成され、f個の障害に耐える）
  • Learner: Acceptorsから最終的に決定された値を学習する

実際の運用では、各ノードは通常、これら3つの役割を同時に担います。

2フェーズプロトコル

フェーズ1: Prepare/Promise

Proposer:
  proposal number Nを選択する（以前使用したどの番号よりも大きく、かつグローバルに一意でなければならない）
  Prepare(N)をすべてのAcceptorへ送信する（過半数以上の到達が必要）

Acceptor:
  Prepare(N)を受信した場合:
    if N > 自分がこれまで見たどのPrepare番号よりも大きい:
      約束: number < N の提案はこれ以上acceptしない
      Promise(N, 以前にacceptedされた値: {N_highest, V})を返信する
    else:
      無視する（または拒否を返信する）

フェーズ2: Accept/Accepted

Proposer:
  過半数のPromise返信を待つ
  過半数を取得した場合:
    → Acceptを送信する準備をする
    値を選択する:
      if どのPromiseにもacceptedな値が含まれている場合:
        N_highest に対応する V を選択する（つまり、番号が最大のaccepted値） ← 重要！
      else:
        自分が望む任意の値を選択する
    Accept(N, V)をすべてのAcceptorへ送信する

Acceptor:
  Accept(N, V)を受信した場合:
    if N >= このacceptorが約束した最小のN（つまり、Nより大きいPrepareを約束していない場合）:
      accept: (N, V) を保存する
      Accepted(N)を返信する
    else:
      拒否する

なぜ2フェーズなのか

フェーズ1の役割は学習です。ProposerはPrepare/Promiseを通じて、「すでに値が部分的にacceptされているかどうか」を知ります。もし値が存在する場合、Proposerは自分の値ではなく、その値でなければなりません⁠。これにより、異なるProposerの提案が互いに上書きされるのを防ぎます。

反例：フェーズ1をスキップすると、2つのProposerが同時に異なる値を提案し、それぞれが過半数のacceptを取得する可能性があります。しかし、その過半数集合が重なり合わない場合、2つの値がともに「ロック」され、システムは永遠に収束しなくなります。

なぜNは増分しなければならないのか

Proposer Aが N=1 で V1 を提案したが、まだ過半数のacceptを取得していないとする。その間、Proposer Bが N=2 で V2 を提案したとする。2ラウンド目のフェーズ1 Prepare(2) により、Acceptorsは N<2 の提案を受け付けないことを約束するため、Aの Accept(1,V1) は拒否される。

これにより、⁠最終的に1つの値のみが過半数によってacceptされることが保証される。

Multi-Paxos

Basic Paxosは単一のコンセンサスを解決する。複数回の連続するコンセンサス（例えば、レプリケートログの各エントリ）は、Multi-Paxosとして扱われる。

最適化：安定したリーダーの選出

各エントリに対して完全なPrepare + Acceptの2フェーズを行うと、エントリあたり2 RTT（往復時間）かかる。Multi-Paxosでは、安定したリーダーを選出することで、そのリーダーはフェーズ1をスキップできる。なぜなら、リーダーである限り、他のProposerが競合しないからである。

Leaderが最初に選出されたとき: フェーズ1 Prepare/Promise（リーダーの身分と、最も高いacceptedなNを確定）
その後、すべてのエントリ: 直接フェーズ2 Accept → エントリあたり1 RTT
新しいProposerがリーダーになりたい場合: フェーズ1 Prepareを送信し、過半数を取得 → 新しいリーダーになる

Paxos vs Raft

Paxosは中核的なコンセンサスメカニズムを定義しているが、以下は定義していない：

  • リーダー選出アルゴリズム（「区別されたProposerを1人選ぶ」と述べているのみ）
  • ログ圧縮/スナップショットのメカニズム
  • メンバーシップ変更プロトコル

このため、各Paxos実装（Google Chubby、Amazon DynamoDB、Microsoft Azure Storageなど）は、これらの部分を独自に再発明せざるを得ず、実装の複雑さがRaftよりも高くなってしまう。

参考

  • 論文⁠: "The Part-Time Parliament" (Lamport, 1998)
  • 論文⁠: "Paxos Made Simple" (Lamport, 2001) — より読みやすいバージョン
  • 論文⁠: "Paxos Made Live — An Engineering Perspective" (Google Chubbyチーム, 2007)

キーワード: Paxos, Basic Paxos, Multi-Paxos, Prepare/Promise, Accept/Accepted, proposal number, distinguished proposer

関連ページ

© 2026 liz's doc