Paxos

Basic Paxos は1回の合意インスタンスを解決する：提案された値の中から最大でも1つの値を選択する。一度値が chosen されると、その後の正当な提案はこのインスタンスで他の値への変更を許可しない。連続するコマンドログを複製するには、異なるログスロットで関連するインスタンスを実行し、安定したリーダーの下でプロトコルのオーバーヘッドを分散させる。

Paxos の核心は「最多投票者が勝つ」ことではなく、新しい提案が進む際に、過去にすでに形成された決定を保持することにある。

ロールと用語

1台のサーバーが複数の役割を担うことができる。ここでは固定された集合内の多数派 quorum を使用し、ビザンチン障害を許容せず、ダウンからの回復を許可するモデルについて議論する。プロトコルは、acceptor が再起動後も必要な永続状態を保持することを要求する。

なぜ acceptor は最初に見た値だけを受領してはいけないのか

3つの acceptor がそれぞれ最初に X、Y、Z を受け取り、その後一切の提案を受領しないと仮定すると、どの値も多数派を得られない。進捗を続けるために、acceptor はより高い番号の提案を受領することを許可しなければならない。

しかし、「より高い番号のオーバーライドを許可する」ことはセキュリティ上の問題を引き起こす：A、B が X を受け取り、その後 B、C が Y を受け取った場合、2つの多数派は明らかに交差しているにもかかわらず、2つの値が選択されてしまう。交差ノード B が制約された歴史継承ルールを持たなければ、2つの異なる決定に参加し続ける可能性がある。

したがって、2つの補完的なメカニズムが必要である：Promise によって将来受領可能な古い提案を制限し、accepted 記録によって新しい proposer が提案できる値を制約する。

フェーズ1：Prepare と Promise

Proposer は新しい一意の ballot n を選択し、Prepare(n) を送信する。一般的な構成は (ローカルインクリメントカウンター, proposer_id) の辞書式順序であり、再起動後にすでに使用済みの番号を再利用してはならない。

Acceptor が承諾 n を許可する場合、その承諾の下限を永続的に記録し、Promise を返信する：それより低い下限の提案は受領しないこと、および以前に受領した最高番号の提案 (accepted_ballot, accepted_value) を付随させる（ない場合は空を返す）。

Proposer が多数の Promise を受信した後、これらの返信を確認する：受領記録がある場合は、その中で accepted_ballot が最大のものを選択する。すべてが空の場合のみ、自分の新しい値を選択できる。これは任意の値を返すわけでも、最も頻繁に出現する値を選択するわけでもない。

フェーズ2：Accept と Accepted

Proposer は Accept(n,v) を送信する。Acceptor は自分自身が高 ballot への承諾を行っていないか確認し、受領記録を永続的に保存して Accepted を返す。すでに高 ballot への承諾を行っている場合、古いリクエストは拒否される。

同じ (n,v) が多数によって受領されると、v は chosen となる。これは proposer が応答をすべて受信する前にクラッシュした場合でも同様である。Learner が決定を知ることは別のイベントであり、「誰も成功した応答を受信していない」ことは「決定が形成されていない」ことを意味しない。

実装では通常、受領時の承諾下限も対応する ballot に進め、同じ番号のメッセージに対する冪等リトライを処理する。同じインスタンスにおいて、同じ ballot を使って proposer が2つの異なる値を提案することはできない。

完全な継承の例

X が ballot 4 で A、B によって受領されたとする。新しい proposer が ballot 7 で B、C に連絡し、B が (4,X) を報告し、C が空を報告した場合、新しい proposer は X を提案しなければならない。返信にそれより高い accepted ballot が含まれている場合は、その値を継承する必要がある。プロトコルの帰納的な性質により、それがより古い chosen 値を違反しないことが保証される。

逆に、ballot 4 の X が A にしか到達しておらず、ballot 7 で B、C から空の Promise を得た場合、Y を選択できる。その後、B、C は ballot 4 を受領しなくなるため、古い proposer は X を多数派に獲得させることができなくなる。これは、フェーズ1が過去を収集するだけでなく、Promise によってその後に起こり得ることを制約することを示している。

これらの例は、安全性の2つの方向性を示している：すでに chosen された値は変更できず、chosen されていない低い番号の競合者は、新しい多数派の Promise を回避して衝突する決定を形成できない。完全な導出は Paxos Made Simple を参照。

2つのメッセージ軌跡の実行：chosen と単一ノードでのみ受領

以下では、メッセージの配信を順序呼び出しとして記述し、acceptor の2つのフィールドは永続保存すべき状態を表す。ballot はグローバルに一意な整数で簡略化される。同じ ballot の Prepare は冪等に応答でき、同じ ballot での値の変更は明示的に拒否される。このコードはネットワーク、永続化、障害回復を実装していない。

class Acceptor:
    def __init__(self):
        self.promised = -1
        self.accepted = None

    def prepare(self, ballot):
        if ballot < self.promised:
            return False, None
        self.promised = ballot
        return True, self.accepted

    def accept(self, ballot, value):
        if ballot < self.promised:
            return False
        if self.accepted and self.accepted[0] == ballot and self.accepted[1] != value:
            raise ValueError("同じ ballot では値を変更できない")
        self.promised = ballot
        self.accepted = (ballot, value)
        return True

def phase1(cluster, names, ballot, proposed):
    replies = [cluster[name].prepare(ballot) for name in sorted(set(names))]
    promises = [accepted for ok, accepted in replies if ok]
    if len(promises) < len(cluster) // 2 + 1:
        raise RuntimeError("多数の Promise を取得できなかった")
    history = [accepted for accepted in promises if accepted is not None]
    return max(history, key=lambda accepted: accepted[0])[1] if history else proposed

# 軌跡1：A、B がすでに X を受領しており、応答が proposer に到達するかどうかは chosen の事実には影響しない。
c = {name: Acceptor() for name in "ABC"}
assert phase1(c, "AB", 4, "X") == "X"
assert c["A"].accept(4, "X") and c["B"].accept(4, "X")
assert sum(a.accepted == (4, "X") for a in c.values()) == 2
chosen_for_7 = phase1(c, "BC", 7, "Y")
assert chosen_for_7 == "X"
assert c["B"].accept(7, chosen_for_7) and c["C"].accept(7, chosen_for_7)
assert not c["B"].accept(4, "X")

# 軌跡2：4/X は A のみに到達し、B は Promise 4 を返したが、accepted 記録はない。
c = {name: Acceptor() for name in "ABC"}
assert phase1(c, "AB", 4, "X") == "X"
assert c["A"].accept(4, "X")
chosen_for_7 = phase1(c, "BC", 7, "Y")
assert chosen_for_7 == "Y"
assert c["B"].accept(7, "Y") and c["C"].accept(7, "Y")
assert not c["B"].accept(4, "X") and not c["C"].accept(4, "X")
assert c["A"].accepted == (4, "X")  # ローカルな古い受領記録は一時的に残る可能性がある

軌跡2において、B が以前に Promise(4) を返したからといって、それが X を受領したことを意味しない。フェーズ1で返すべきは accepted の履歴であり、「承諾した最大の ballot」と「受領した最大の ballot/value」を1つのフィールドに統合してはならない。前者は後のリクエストを制限し、後者は新しい提案の値を制約する。

逆に、軌跡1において B が X の記録を1つ提供するだけで、新しい proposer を制約するのに十分である。B、C の返信で再度投票し、「多数の返信が X である」ことを集計する必要はない。B は新しい quorum と古い chosen quorum の唯一の交点かもしれない。

このモデルは、proposer が phase1 の返却で選択に従い、グローバルに1つの ballot が2人の proposer に割り当てられないことを前提としている。Acceptor のローカルな同じ ballot でのチェックは、自分が見た衝突のみを検出でき、悪意のある proposer が異なる acceptor に異なる値を嘘をつくことを阻止できない。Paxos の障害モデルはビザンチンモデルではない。状態の喪失や不正な proposer の動作は、この安全性の推論の前提に含まれない。Paxos Made Simple

新しい提案はなぜ自由に値を変更できないのか？

新しい Promise の集合の中で X が1つしか見えていなくても、X を継承しなければならない場合がある：この返信がまさに古い chosen 多数派との交点である可能性がある。以下では、「A のみが受領」した場合と「A、B がすでに chosen」した場合の2つの初期履歴を区別し、古い ballot 4 の遅延リクエストを保持する。これにより、フェーズ1が過去をどのように発見し、Promise によって将来の衝突パスをどのように封じるかを同時に確認できる。

安全性が必ずしも高速な値選択を意味しない

2人の proposer が互いに ballot を引き上げ続け、互いを妨害することで、システムは安全性を維持しながらも完了までに時間がかかることがある。そのため、実装では通常、安定したリーダー、バックオフ、または最終的に安定する通信とスケジューリング条件の改善に依存して進捗を図る。

より高い ballot からの拒否後、単純な無限リトライでは低レイテンシが保証されない。障害回復時の競合嵐を避ける必要がある。多数のノード間で通信できない場合、基本多数派方式では新しい値を選択し続けることはできないが、それ故に歴史継承ルールを放棄してはならない。

Multi-Paxos：フェーズ1の結果を複数のスロットに適用する

ログスロット slot と ballot は2つの次元である：slot はログ内でのコマンドの位置を指し、ballot は誰がどの提案世代で競争に参加したかを示す。「新しい ballot」を「次のログ」と理解してはならない。

安定したリーダーが関連するスロットに対して有効なフェーズ1の承諾を確立した後、これらの承諾がカバーする範囲内で、同じ ballot を使って後続のスロットに対してフェーズ2を実行し、Prepare のコストを分散させることができる。「自分がまだリーダーだと信じているから」という理由で回復を任意にスキップするわけではない。新しいリーダーは受領履歴を収集し、スロットごとに制約された値を保持し、欠落したスロットを処理する必要がある。

通常、バッチごとの提案に対して1回の accept リクエストと応答を使用できるが、クライアント通信、永続化、キュー、およびステートマシン適用には依然としてオーバーヘッドが存在する。複数のスロットが並行して決定に達する可能性があるが、ステートマシンは通常、連続する接頭辞に従って適用する必要があり、slot 12 が先に完了したからといって、未決定の slot 11 を飛び越えて依存するコマンドを実行してはならない。

slot 12 が先に chosen されたからといって、先に実行できるわけではない

状態が初期値 10 で、slot 10 のコマンドが +2、slot 11 が -1、slot 12 が ×3 であると仮定する。10、12 が先に知らされ、11 が一時的に欠落している。ステートマシンはまず 10 を実行し、次に 11 で停止する必要がある。そうでなければ、先に掛け算してから引き算すると誤った 35 になり、正しいログ順序では 33 になる。

def apply_prefix(chosen, next_slot, value):
    while next_slot in chosen:
        value = chosen[next_slot](value)
        next_slot += 1
    return next_slot, value

chosen = {10: lambda x: x + 2, 12: lambda x: x * 3}
next_slot, value = apply_prefix(chosen, 10, 10)
assert (next_slot, value) == (11, 12)
chosen[11] = lambda x: x - 1
assert apply_prefix(chosen, next_slot, value) == (13, 33)
assert chosen[11](chosen[12](chosen[10](10))) == 35

「11 がまだ不明」だからといって、「11 を任意の no-op で埋めてよい」わけではない。新しいリーダーは依然として回復プロトコルを通じて該スロットの受領履歴を収集し、すでに値が存在する可能性のある制約に従う必要がある。プロトコルが新しい値の選択を許可する場合のみ、no-op で空洞を埋めることができる。ログ複製サービスは、chosen された集合と適用可能な接頭辞を別々に記録する必要があり、既知の最大 slot で実行進捗を置き換えてはならない。

アルゴリズムからサービスへ至るために不足しているもの

本番環境での実装には、ログの切り捨てとスナップショット、メンバー変更、クライアントリクエストの重複排除、フロー制御、読み取りセマンティクス、および運用上の回復が必要である。これらは「Paxos が許可していない」のではなく、単一値のプロトコルがシステム全体に対して唯一の工学的選択を行っていないからである。

Raft は、選挙の資格とログ接頭辞の制約をより明確なプロトコル構造として整理している。Multi-Paxos の選挙とログ回復の実装の余地はより大きい。比較は、特定の実装と保証に基づいて行うべきであり、あるプロトコルがすべてのレプリカログを常に完全に同一にすると断言してはならない。

参考文献

• Lamport：Paxos Made Simple。
• 実システムにおける合意の実践。

Keywords: Paxos, Multi-Paxos, ballot, prepare, promise, accept, accepted, chosen, quorum