2PC - 確定か中止を全参加者で揃える

2PC（Two-Phase Commit、2 相コミット）は、複数の DB にまたがる 1 つの更新について、関わった全員の最終的な判断が確定（commit）か中止（abort）のどちらか一方へ揃うようにする手順です。確定できるかを全員へ問い合わせる準備フェーズと、決めた結果を配る決定フェーズの 2 段階で進む事が名前の由来です。ここでは、参加するプロセスが停止する故障と通信の途絶を扱い、誤った値を返す故障（ビザンチン障害）は対象外とします。

この手順が必要な場面の代表は、1 つの業務処理が複数の DB を書き換える時です。例えば、注文を記録する DB と、支払いに使うポイントの残高を持つ DB が別のサーバにある EC サイトで、ポイント払いの注文を受けるとします。注文が確定したのにポイントの更新は中止された、という食い違った結末は、後から人手で突き合わせて直す作業を生みます。2PC は、ある参加者は確定・別の参加者は中止という最終的な判断の分裂を防ぐ事を目的にしています。

揃うのは最終的な判断であって、複数の DB の変更が同じ瞬間に見え始める事までは保証しません。決定を配っている途中には、片方が確定済みで、もう片方はまだ決定を待っている、という瞬間があり得ます。

登場人物を以下に示します。

  flowchart TD
    C["コーディネータ"] --> P1["参加者 A（注文の DB）"]
    C --> P2["参加者 B（ポイントの DB）"]

上図のコーディネータは確定か中止かを決める役、参加者は自分のローカルトランザクションを実際に確定・中止する役です。

Jim Gray と Leslie Lamport の論文「Consensus on Transaction Commit」（2004 年）は、この 2 つを transaction manager、resource manager と呼び、2PC を単一のコーディネータで合意へ到達する古典的なトランザクションコミットのプロトコルとして説明しています。

なぜコミットの合図を 2 回に分けるのか

素朴な方法は、アプリケーションが 2 つの DB へ順番に COMMIT を送る事です。この方法は、1 つ目の COMMIT と 2 つ目の COMMIT の間に故障が挟まると壊れます。具体的には、以下の流れで片方だけが成立します。

  sequenceDiagram
    participant A as アプリケーション
    participant D1 as 注文の DB
    participant D2 as ポイントの DB
    A->>D1: COMMIT
    D1-->>A: 成功
    A->>D2: COMMIT
    Note over D2: サーバが停止していて<br/>届かない
    Note over D1,D2: 注文だけが確定し<br/>ポイントは減らないまま

上図の注文の確定は取り消せません。ローカルトランザクションの原子性（変更を全て反映するか、全て無かった事にするかの性質）は 1 台の DB の中で閉じており、確定した変更は以後に始まる読み取りから見えます。後から注文を打ち消す更新を入れる事はできるものの、それは新しい別の更新であり、間の時間には片方だけの状態が読まれています。

2 回の COMMIT の間隔は短いため、壊れる事は滅多に無いと考える方がいるかもしれません。それでも、確定の件数が積み上がるほど、この故障は無視できなくなります。しかも、片方だけが成立した事に気付いて直す仕組みは、この構成のどこにもありません。

壊れた原因は、確定という後戻りできない一線を各参加者がばらばらの瞬間にまたいでいる事です。そのため 2PC は、確定の前に「言われればいつでも確定できる」状態を全員に作らせ、全員がそこへ到達した事を見届けてから、確定の合図を一斉に配ります。

準備フェーズ - 確定できる状態を作って投票する

前提として、注文とポイントの更新そのものは、アプリケーションが各 DB のローカルトランザクションとして実行済みです。各参加者は更新対象の行のロックを取り、確定しないまま持っています。2PC が引き受けるのは、この確定の段階だけです。

コーディネータは、全参加者へ prepare（準備の要求）を送ります。受け取った参加者は、トランザクションの変更内容と「準備が完了した」という記録をディスクへ書いてから、確定に応じられるなら yes、応じられないなら no を返します。この返事が投票になります。

先にディスクへ書くのは、返事をした後に自分が再起動しても約束を守るためです。要点は、yes と答える前に、クラッシュしても消えない場所へ約束を残す事にあります。prepare を受けてから yes を返すまでの順序を以下に示します。

  sequenceDiagram
    participant C as コーディネータ
    participant P as 参加者 A
    participant D as 参加者 A のディスク
    C->>P: prepare
    P->>D: 変更内容と prepared を書く
    D-->>P: 書き込み完了
    P-->>C: yes
    Note over P,D: 再起動しても prepared が<br/>残っているので約束を守れる

上図で見てほしいのは、書き込みが yes より先に来る点です。順序が逆だと、再起動した参加者は自分が何を約束したのかを知らないまま、コーディネータから commit を受け取る事になります。

この永続化には DB の WAL などが使われ、PostgreSQL では PREPARE TRANSACTION がこの状態を作ります。公式ドキュメントは、このコマンドの後で「トランザクションはセッションから切り離され、その状態は完全にディスクへ保存される。コミットが要求される前に DB がクラッシュしても、コミットに成功する見込みが非常に高い」と説明しています。

yes と答えた参加者は、自分から中止する権利を手放します。準備の前なら、参加者はいつでも自分の判断で中止できます（制約違反やタイムアウトが典型）。準備の後は、確定か中止かを決める権限がコーディネータに一本化されます。参加者が独断で選ぶ操作は塞がれていないものの、選べば最終的な判断を揃える保証が壊れます。この一本化があるから、コーディネータは全員の yes を見た時点で、勝手に中止した参加者が出る事を心配せずに確定を配れます。

参加者の状態遷移を以下に示します。

  stateDiagram-v2
    [*] --> working
    working --> prepared: prepare を受けて<br/>ディスクへ記録
    working --> aborted: 自分の判断で<br/>中止できる
    prepared --> committed: コーディネータの<br/>commit を受けた時
    prepared --> aborted: コーディネータの<br/>abort を受けた時

上図の prepared から出る 2 本の矢印が、どちらもコーディネータの決定を条件にしている点が 2PC の要です。参加者は、更新対象へのロックを保持したまま prepared に留まり、決定を待ちます。

決定フェーズ - 結果を記録してから配る

コーディネータが確定を選べるのは、全参加者の yes が揃った時だけです。1 台でも no を返すか応答が間に合わなければ中止を選びます。上の論文も、prepare を送った後に返事が揃わなければ、コーディネータは abort を他の参加者へ送ってトランザクションを中止すると述べています。

選んだ決定は、参加者へ配る前に自分のログへ書きます。この書き込みで、トランザクション全体の結果が決まります。書く前にコーディネータが落ちれば、再起動後に中止を選び直せます。書いた後に落ちても、ログを読んで同じ決定を配り直せます。この順序が、決定を 1 度きりにする保証の要になります。

prepare から確定までの全体の流れを以下に示します。

  sequenceDiagram
    participant C as コーディネータ
    participant P1 as 参加者 A
    participant P2 as 参加者 B
    C->>P1: prepare
    C->>P2: prepare
    P1->>P1: 記録して投票
    P2->>P2: 記録して投票
    P1-->>C: yes
    P2-->>C: yes
    C->>C: 確定をログへ書く
    C->>P1: commit
    C->>P2: commit
    P1-->>C: ack
    P2-->>C: ack

参加者は、commit を受け取った時点で自分のローカルトランザクションを確定できます。上図の ack（acknowledgment、受領の応答）は、コーディネータが完了を確かめるための応答で、2 つのフェーズそのものとは別の役割です。ack が返らない参加者には、コーディネータが決定を送り直します。決定はログに残っているので、何度送っても同じ結果です。再起動した参加者も、ディスクに prepared の記録を見付けたらコーディネータへ問い合わせ、決定を受け取り直します。

上図のとおり、確定までには prepare の要求と投票、commit の通知という複数回の通信に加え、参加者・コーディネータ双方のディスクへの書き込みが挟まります。ack で完了を確かめる実装では、その応答も加わります。この遅延は確定のたびに掛かり、参加者が増えるほどメッセージの数も比例して増えます。

コーディネータの停止が参加者を縛る

yes と答えた後、決定が届く前にコーディネータが落ちると、参加者は動けなくなります。確定も中止も自分では選べないためです。この宙吊りは in-doubt と呼ばれます。上の論文は、この弱点を「コーディネータの故障は、修復されるまでプロトコルを塞き止め得る。特に、全参加者が yes を送った直後に故障すると、残された参加者は確定と中止のどちらが選ばれたのかを知る術が無い」と要約しています。

他の参加者へ聞いて回る手はあります。誰かが既に commit か abort を受け取っていれば、決定はその受け取った内容だと分かる筈です。しかし、全員が prepared のままなら決められません。コーディネータが確定をログへ書いた直後に落ちた可能性が残り、その場合、復旧したコーディネータはログの確定を配り直すので、待ち切れずに中止した参加者と食い違います。

in-doubt の間、参加者はロックを保持し続けます。その結果、同じ行に触る後続のトランザクションが次々に詰まります。PostgreSQL のドキュメントも、prepared のトランザクションは保持していたロックを持ち続けると述べ、長時間放置しないよう注意した上で、外部のトランザクションマネージャが速やかに確定か中止を指示する前提の機能だと明記しています。

コーディネータの停止で何が詰まるかを以下に示します。

  sequenceDiagram
    participant C as コーディネータ
    participant P as 参加者 A
    participant O as 後続のトランザクション
    P-->>C: yes（ロックを保持）
    Note over C: 決定を配る前に停止
    O->>P: 同じ行を更新したい
    Note over P: prepared のロックに<br/>阻まれて待つ
    Note over C,P: コーディネータが<br/>復旧するまで解けない

コーディネータが止まっても、確定と中止が食い違う結末にはなりません。壊れるのは進行性（liveness、処理が前へ進む性質）で、決定を知らない参加者は安全に止まったまま待ちます。この待ちが blocking と呼ばれる代償です。

上図の詰まりを解く正攻法は、コーディネータの復旧です。復旧を待てないからといって、参加者が自分の判断でどちらかを選ぶと、最終的な判断の分裂を自分の手で作る事になります。古典的な 2PC では決定を担うコーディネータが単一で、その故障によって blocking が起き得ます。そこへ手を入れる発展形もあります。

blocking を避ける狙いで提案されてきた手順は、non-blocking commit protocol と総称されます。その代表的な系統が 3 相コミット（Three-Phase Commit）で、決定の前に状態を 1 つ足し、コーディネータが止まっても残ったノードだけで判断できる条件を作ろうとします。ただし、成り立つための前提条件と正しさには注意が要ります。上の論文も、それらについて、明確に述べられた正しさの条件を満たすと証明された完全なアルゴリズムを知らないと評しています。

論文が代わりに提案する Paxos Commit は、acceptor が何台まで同時に故障しても進めたいかを F として、2F + 1 台の acceptor（合意の記録役）を使った Paxos で、参加者それぞれの Prepared / Aborted という判断を複製します。1 台の故障まで許すなら F = 1 で、acceptor は 3 台になります。適切な Leader と F + 1 台以上の acceptor が十分な期間通信できていれば、決定まで進められます。

決定の記録がどこにあるのかを 2PC と並べ、以下に示します。

  flowchart LR
    subgraph T["2PC"]
        TP["prepared の参加者"] -. 決定を聞けない .-> TC["コーディネータ<br/>停止中"]
        TC --- TL[("決定のログ")]
    end
    subgraph P["Paxos Commit（F = 1）"]
        PP["prepared の参加者"] --> PA1[("acceptor 1")]
        PP --> PA2[("acceptor 2")]
        PA3[("acceptor 3<br/>停止中")]
    end

上図の 2PC では、決定を持っているのがコーディネータ 1 台だけで、停止すると prepared の参加者は聞く先を失います。Paxos Commit では 3 台のうち 2 台が生きていれば決定を読み出せます。故障に強くなる代わりに、メッセージの数は増えます。

利点

• 最終的な決定が参加者の間で確定と中止に分裂する事を防げる
• 参加者は、ローカルトランザクションの仕組み（WAL とロック）をほぼそのまま流用できる
• X/Open XA として標準化され、対応する DB やミドルウェアを組み合わせて使える

3 番目の XA は、Transaction Manager（コーディネータにあたる役）と Resource Manager（参加者にあたる役）の間のインターフェースを定めた仕様で、標準化団体 X/Open の文書「Distributed Transaction Processing: The XA Specification」として発行されています。例えば MySQL は、XA トランザクションのドキュメントで、実装がこの文書に基づくと明記しています。

同じドキュメントは、複数の DB にまたがるトランザクションの全体をグローバルトランザクションと呼び、「それ自体はトランザクションである複数の処理が、全体として成功するか、全体として巻き戻されるかのどちらかでなければならないもの」と説明しています。

欠点

以下は、最終的な判断を全参加者で揃える事を優先した帰結です。

• 1 台でも準備に失敗すると全体が中止になり、参加者が増えるほど確定へ進める見込みが下がる
• prepared の参加者はロックを持ったまま待ち、決定が遅れるほど後続のトランザクションを巻き込む
• コーディネータが進行性の単一障害点になる。故障しても結果は分裂せず安全に止まる代わりに、prepared のまま決定を知らない参加者が blocking する
• 確定のたびに複数回の通信と、参加者・コーディネータ双方のディスクへの書き込みが掛かる

適さないケース

• 参加者に他の組織のサービスが混ざる統合。相手にロックの保持と in-doubt の受け入れを要求する事になる
• 書き込みの遅延とスループットを最優先する経路
• DB の更新を先に確定し、イベントを介して別のサービスを後から追随させる結果整合で足りる業務。Domain Event で扱った Transactional Outbox は、そのイベント発行を確実にする代表的な方法になる

過半数の合意との違い

2PC も「全員で 1 つの結果を決める」形に見えるため、クォーラムや Leader and Followers で扱った過半数の合意と混同されやすいと考えられます。違いは票の数え方ではなく、解いている問題そのものにあります。

全参加者が prepared である事を求めるのは、参加者がそれぞれ別の資源を管理しているためです。自分のローカルトランザクションを確定できるかという情報は、その参加者しか持っていません。在庫の制約に反する更新は、他の参加者の多数決で確定にできません。参加者が 1 台でも確定できなければ、グローバルトランザクション全体を確定できない、という構造になっています。

Raft のノードは、これとは違い、同じログを複製するレプリカの集まりです。過半数を使うのも、反対意見を押し切るためではありません。過半数どうしが必ず 1 台以上で重なる性質（quorum intersection）を利用して、確定済みのログを次の Leader へ引き継ぎ、履歴を 1 本に保つためです。重なりが効く理屈はクォーラムで扱いました。

言い換えると、atomic commit（原子的な確定）では、確定という結論を選んでよい条件（validity condition）に、全参加者が prepared である事が含まれます。Raft のような合意では、複製された状態について 1 つのログ履歴を安全に保ち続けるために quorum を使います。

上の論文は、この 2 つが別の問題でありながら組み合わせられる事も示しています。参加者に prepared かどうかを判断させる形は 2PC のまま、その判断の記録を合意で複製したものが Paxos Commit で、2PC は acceptor が 1 台（F = 0）の場合に対応する特別な場合だと位置付けられています。