分散トランザクション入門 - 2相コミットが詰まる理由と Saga パターンの使いどころ

在庫を1つ減らして、決済を3000円ぶん確定して、注文レコードを作る。1台のデータベースの中でなら、これはBEGINとCOMMITで囲むだけの話です。ところが在庫サービスと決済サービスと注文サービスが別々のデータベースを持った瞬間、この「囲む」という操作が驚くほど難しくなります。決済だけ成功して在庫が減らない、あるいは在庫だけ減って注文が残らない。そういう状態を防ぐ仕組みを、自分で選んで組み立てなければいけません。

この記事では、原子的コミット問題という出発点から、2相コミット（2PC）、3相コミット、X/Open XA、Sagaパターン、アウトボックスパターン、そして「exactly-once」という言葉の実際の意味までを順に追います。すべての主張は原典論文と公式ドキュメントで裏を取り、実演部分は手元のPostgreSQL 14とpython3で実際に動かして出力を確認しました。トランザクションとACID・分離レベルが1台のDBの中の話だとすれば、この記事はその境界をまたいだ先の話です。

なぜ単一DBのトランザクションは分散すると壊れるのか

1台のRDBMSの中でトランザクションが成立するのは、そこに単一の権威があるからです。ログ（WAL）は1つ、ロックマネージャは1つ、コミットの瞬間を決めるのも1つ。「コミットした」という事実が、システム内のどこから見ても同時に、同じ形で確定します。

これが複数のノードに分かれると、3つの前提が同時に崩れます。

• ログが複数になる: それぞれが自分のWALに書きます。片方だけ書き終わった状態が物理的に存在し得ます。
• 決定が伝わるのに時間がかかる: 「コミットせよ」という指示が届くまでにネットワークがあり、届かないこともあります。
• 相手の状態がわからない: 応答が返ってこないとき、それが「まだ処理中」なのか「落ちた」のか「応答だけ失われた」のかを区別できません。

3つ目が特に厄介です。分散システムでは、タイムアウトは障害の証拠にならない。応答が来ないという事実からは、相手が死んだのか生きているのかを原理的に判別できません。この曖昧さを抱えたまま「全員でひとつの決定に到達する」のが、これから見る問題です。分断が起きたときに一貫性と可用性のどちらを取るかという議論はCAP定理で扱いましたが、分散トランザクションはその選択が最も生々しく現れる領域です。

素朴な実装がなぜ壊れるかも押さえておきます。「サービスAをコミットしてから、サービスBをコミットする」を順に呼ぶだけのコードは、Aのコミット直後にプロセスが落ちた瞬間に破綻します。Aだけが確定し、Bは何も知らない。リトライすれば直る、という話でもありません。リトライする主体（そのプロセス）が消えているからです。

原子的コミット問題 — 全員一致を取り付ける

この問題は原子的コミット（atomic commit）問題として定式化されています。Jim GrayとLeslie Lamportの論文「Consensus on Transaction Commit」（ACM TODS, 2006年）は冒頭でこう述べます。分散トランザクションは複数サイトで実行される操作の集まりであり、コミットまたはアボートの要求で終端する。サイト群はトランザクションコミットプロトコルを使ってコミットするかアボートするかを決める。トランザクションがコミットできるのは、全サイトがコミットを望む場合に限られる。

つまり必要なのは多数決ではなく全員一致です。誰か1人でも「無理です」と言えば全体がアボートする。この非対称性が、後で見るブロッキングの根っこになります。

満たすべき性質を整理すると次のようになります。

この3つを、通信が遅延しノードが落ちる環境で同時に満たしたい、というのが要求です。ここでRaft合意アルゴリズムを思い出す人もいるでしょう。実は密接に関係していて、GrayとLamportの論文の主眼はまさに「トランザクションコミットは合意問題の一種である」と示すことにあります。後で戻ってきます。

2相コミット(2PC) — 手順とコーディネータ障害でのブロッキング

もっとも古典的な解が2相コミットです。コーディネータ（transaction manager, TM）が1人いて、参加者（resource manager, RM）たちに二段構えで問い合わせます。

要点はPhase 1で参加者が「約束」をしてしまうことです。yesと答えた参加者は、その後どんなことがあってもコミットできなければなりません。だからロックを握ったまま、ログにPREPAREDを書いて待機します。この待機状態をin-doubt（未決）と呼びます。

実際に手を動かして挙動を見ます。次はPythonで書いた最小の2PCシミュレータの中核です。

def run_2pc(rms, crash_after_prepare=False):
    trace = []
    # --- Phase 1: prepare ---
    votes = []
    for rm in rms:
        v = rm.prepare()
        votes.append(v)
        trace.append(f"  TM -> {rm.name}: Prepare / {rm.name} -> TM: {v}")
    decision = "commit" if all(v == "yes" for v in votes) else "abort"
    trace.append(f"  TM: 決定 = {decision} (安定ストレージへ書き込み)")
 
    # --- コーディネータ障害 ---
    if crash_after_prepare:
        trace.append("  !! TM がここでクラッシュ。決定は誰にも届かない !!")
        for rm in rms:
            if rm.state == "prepared":
                trace.append(f"  {rm.name}: state=prepared のまま。"
                             f"独断でcommitもabortもできない -> ブロッキング")
        return trace, decision, False
 
    # --- Phase 2: commit / abort ---
    for rm in rms:
        if rm.state == "prepared":
            rm.finish(decision)
            trace.append(f"  TM -> {rm.name}: {decision} / {rm.name}: state={rm.state}")
    return trace, decision, True

3つのシナリオで実行しました。(a)全員がyes、(b)1つがno、(c)全員preparedの直後にコーディネータがクラッシュ、の3つです。(a)は全員committed、(b)は全員abortedになり、どちらも「全員が決着したか: True」で終わります。問題は(c)の出力です。

--- (c) 全員 prepared の直後にコーディネータがクラッシュ ---
  TM -> orders: Prepare / orders -> TM: yes
  TM -> inventory: Prepare / inventory -> TM: yes
  TM -> payments: Prepare / payments -> TM: yes
  TM: 決定 = commit (安定ストレージへ書き込み)
  !! TM がここでクラッシュ。決定は誰にも届かない !!
  orders: state=prepared のまま。独断でcommitもabortもできない -> ブロッキング
  inventory: state=prepared のまま。独断でcommitもabortもできない -> ブロッキング
  payments: state=prepared のまま。独断でcommitもabortもできない -> ブロッキング
  最終状態: orders=prepared, inventory=prepared, payments=prepared
  全員が決着したか: False

参加者はもうyesと答えてしまったので、勝手にアボートできません（コーディネータはcommitを決めたかもしれない）。かといって勝手にコミットもできません（誰かがnoと言ってアボートになったかもしれない）。待つ以外に選択肢がないのです。

GrayとLamportの論文は3.3節「The Problem with Two-Phase Commit」でこれを明確に書いています。TMの障害はTMが修復されるまでプロトコルをブロックさせ得る。とりわけ全RMがPreparedメッセージを送った直後にTMが落ちると、他のRMにはTMがコミットしたのかアボートしたのかを知る術がない。ここで問題なのは、参加者がロックを握ったまま止まることです。1つのトランザクションが止まるだけでなく、同じ行に触ろうとする無関係なトランザクションまで巻き込まれます。

コストも見ておきます。同論文3.2節は、参加者数をNとしたとき通常系のメッセージ数を次のように数えています。開始RMがPreparedをTMへ送る（1通）、TMが他の全RMへPrepareを送る（N-1通）、各RMがPreparedを返す（N-1通）、TMが全RMへCommitを送る（N通）。合計3N-1通で、RMは4メッセージ遅延後にコミットを知ります。TMが開始RMと同じノードにあるのが典型で、その場合2通はノード内に落ちるので3N-3通、3メッセージ遅延になります。

--- 通常系のメッセージ数 (Gray & Lamport の数え方) ---
 N (RM数)   3N-1      TMがRM同居: 3N-3
        2      5                  3
        3      8                  6
        5     14                 12
       10     29                 27

さらに効いてくるのが可用性の掛け算です。参加者が独立に確率pで落ちるとすると、全員が揃って初めて成立する2PCの成功確率は(1-p)^Nになります。

--- 参加者が独立に確率 p で落ちるとき、2PC 全体が成功する確率 ---
  N    p=0.001     p=0.01     p=0.05
  1    0.9990    0.9900    0.9500
  2    0.9980    0.9801    0.9025
  3    0.9970    0.9703    0.8574
  5    0.9950    0.9510    0.7738
 10    0.9900    0.9044    0.5987

各サービスが99%の可用性でも、10サービスをまたぐ2PCは90.4%まで落ちます。2PCは参加者を増やすほど脆くなるという性質があり、これがマイクロサービス構成で敬遠される最大の理由です。

3PCがなぜ実用されないのか

「コーディネータが落ちるとブロックするなら、フェーズを増やして回避すればいい」という発想が3相コミット（3PC）です。Dale Skeenが1981年の論文「Nonblocking Commit Protocols」（SIGMOD '81）で示したもので、prepareとcommitの間にpre-commitという段階を挟みます。参加者は「全員が投票を終えた」ことを知ってからでないとcommitへ進まないので、コーディネータが落ちても残ったノードだけで決定を再構成できる、という理屈です。

理屈としては成立します。それでも実務でほぼ見かけないのは、前提が現実と合っていないからです。

• ネットワーク分断に耐えられない。3PCがノンブロッキングなのはノードの停止故障を前提とした場合であって、ネットワークが割れて両側が別々に「残ったメンバーで決定を再構成」し始めると、コミットとアボートに分裂し得ます。
• 同期モデルを仮定している。メッセージ遅延に上限がある、タイムアウトが故障を正しく検出する、という仮定が要ります。実際のネットワークにその保証はありません。
• メッセージ遅延が増える。フェーズが1つ増えるぶん、通常時のレイテンシが素直に悪化します。

GrayとLamportの論文の評価は辛辣です。ノンブロッキングコミットプロトコルは何度も提案され、いくつかは実装された。それらはたいてい、最初のTMが落ちたら別のTMを選ぶという方法で2PCを「直そう」としてきた。しかし明確に述べられた正しさの条件を満たすと証明された完全なアルゴリズムを、我々は1つも知らない。同論文はさらに、古典的教科書（Bernstein, Hadzilacos, Goodman）のノンブロッキングコミットの議論について、2つの異なるプロセスが両方とも「自分が現在のTMだ」と主張するメッセージを受け取ったときにどうすべきかを説明できていないと指摘しています。そしてその状況が起きないことを保証するのは、トランザクションコミットプロトコルを実装するのと同じくらい難しい、と。

言い換えると、3PCが素朴に避けようとした問題は、結局リーダー選出という合意問題そのものだったわけです。だったら最初から合意アルゴリズムを使えばよい、という結論になります。これが後半で見るPaxos CommitやSpannerの発想です。

X/Open XA — 標準化された2PCと、ヒューリスティック決定という抜け道

2PCを製品間で相互運用するための標準がXAです。一次資料を確認すると、正式名称は「X/Open CAE Specification — Distributed Transaction Processing: The XA Specification」、著作権表示は1991年12月、X/Open Document NumberはXO/CAE/91/300です。

仕様はアプリケーションプログラム（AP）、トランザクションマネージャ（TM）、リソースマネージャ（RM）という3者のモデルを定義し、XAインタフェースはTMとRMの間のインタフェースだと明記しています。RMの例としてDBMS、ISAMのようなファイルアクセス手法、さらにはプリントサーバまで挙げられているのが面白いところで、XAはDB専用の仕組みとして設計されたわけではありません。

2.3節「Transaction Completion and Recovery」は、TMとRMがpresumed rollback（推定ロールバック）付きの2相コミットを使うと述べています。ここで定義されているのが次の点です。Phase 1でRMがコミットできると判断したら、そのために必要な情報を安定的に記録してから肯定応答を返す。否定応答を返してロールバックした後は、RMはそのブランチに関する知識を破棄してよい。Phase 2でTMは実際のコミットまたはロールバックを要求する。コミット要求を出す前に、TMはコミットを決めた事実と関与する全RMのリストを安定的に記録する。一方でロールバックの決定と参加者は安定記録する必要がない、というのがpresumed rollbackの意味です。

実務上重要な最適化も2つ規定されています。

• Read-only最適化: RMがprepare要求に対して「このブランチでは共有リソースを更新していない」と応答すると、そのRMのPhase 2は省略されます。ただし仕様は注意も書いており、グローバルトランザクションがprepareされる前にread-only応答を返すと、RMが読み取りロックを早期解放し得るためグローバルな直列化可能性が保証できなくなるとしています。
• One-phase commit: 共有リソースを変更しているRMがDTPシステム内に1つしかないとTMが知っている場合、Phase 1を省いていきなりPhase 2のコミット要求を出せます。この場合TMはグローバルトランザクションを安定記録する必要がなく、障害ケースによってはTMが結果を知り得ないとも書かれています。

そして2PCの安全性に穴を開ける規定が2.3.3節Heuristic Branch Completion（ヒューリスティックなブランチ完了）です。仕様の記述はこうです。一部のRMはヒューリスティックな意思決定を行うことがある。すなわちコミット準備を済ませたRMが、TMとは独立に自分の作業をコミットまたはロールバックすると決めてしまうことがある。そうすればロックを解放できるが、これは共有リソースを不整合な状態に置き得る。後でTMがブランチの完了を指示したとき、RMは「すでに済ませた」と応答し得る。コミットしたのか、ロールバックしたのか、あるいは混在した結果（一部コミット・一部ロールバック）になったのかを報告する。

これは仕様が公式に認めた「詰まったら人間か製品の判断で解く」という抜け道です。XAの2PCで運用したことがある人が口を揃えて嫌がるのが、このヒューリスティック例外の後始末です。整合性が壊れた事実だけが通知され、どう直すかはアプリケーション側の責任になります。

主要RDBMSの対応も見ておきます。MySQLの公式マニュアルは、XAトランザクションサポートはInnoDBストレージエンジンに限られると明記し、実装はX/Open CAE文書「Distributed Transaction Processing: The XA Specification」に基づくと書いています。TMはクライアントプログラム側、RMはMySQLサーバという役割分担です。次節ではPostgreSQL側を実際に動かします。

PostgreSQL の PREPARE TRANSACTION を実際に動かす

PostgreSQLはPREPARE TRANSACTIONというコマンドでin-doubt状態を明示的に作れます。手元でPostgreSQL 14の検証用インスタンスを立てて動かしました。まず注意すべき設定から。

SELECT name, setting, boot_val FROM pg_settings WHERE name='max_prepared_transactions';

           name            | setting | boot_val 
---------------------------+---------+----------
 max_prepared_transactions | 10      | 0

settingが10なのはこの検証インスタンスで明示的に上書きしたためで、boot_val（組み込みの既定値）は0です。公式ドキュメントも「このパラメータをゼロ（これが既定値）に設定すると、prepared transaction機能が無効になります」と書いています。つまり素のPostgreSQLでは2相コミットは最初からオフで、意図して有効化しない限り使えません。公式ドキュメントは、prepared transactionを使う予定がないならゼロのままにしてprepared transactionの偶発的な作成を防ぐべきだ、と推奨しています。

実際の2相コミットの流れです。aliceから300円引いてbobへ足す送金を、2つのブランチに分けてprepareします。

BEGIN;
UPDATE accounts SET balance = balance - 300 WHERE id = 'alice';
PREPARE TRANSACTION 'txn-transfer-001';
 
-- prepared のまま。まだ確定していない
SELECT id, balance FROM accounts ORDER BY id;
SELECT gid, owner, database FROM pg_prepared_xacts;

--- 2. prepared のまま。セッションから見えるのはコミット前の値 ---
  id   | balance 
-------+---------
 alice |    1000
 bob   |     500
(2 rows)
 
--- 3. pg_prepared_xacts に残っている ---
       gid        | has_prepared_at | owner | database 
------------------+-----------------+-------+----------
 txn-transfer-001 | t               | demo  | postgres
(1 row)
 
--- 4. prepared なトランザクションは行ロックを握り続ける ---
   locktype    |     mode      | granted 
---------------+---------------+---------
 transactionid | ExclusiveLock | t
(1 row)
 
--- 6. 全参加者が prepared になったので COMMIT PREPARED ---
COMMIT PREPARED
COMMIT PREPARED
  id   | balance 
-------+---------
 alice |     700
 bob   |     800
(2 rows)
 
 remaining_prepared 
--------------------
                  0

PREPARE TRANSACTIONを実行するとセッションからトランザクションが切り離され、pg_prepared_xactsビューに残ります。値はまだ1000のまま、しかしロックは握られたままです。全参加者がprepared になったところでCOMMIT PREPAREDを投げてはじめて確定します。

ここまでは幸せなケースです。次に、prepareした直後にコーディネータが消えた状況を再現します。DBサーバを-m immediateで強制停止して再起動しました。

=== 1. prepare して放置（コーディネータからの最終指示が来ない状態）===
     gid      | owner 
--------------+-------
 txn-in-doubt | demo
(1 row)
 
=== 2. DBサーバを immediate 停止 -> 再起動 ===
     gid      | owner 
--------------+-------
 txn-in-doubt | demo
(1 row)
 
=== 3. 他セッションは同じ行に触れない（3秒でタイムアウト）===
ERROR:  canceling statement due to statement timeout
CONTEXT:  while updating tuple (0,3) in relation "accounts"
 
=== 4. ROLLBACK PREPARED で人手決着 ===
ROLLBACK PREPARED
  id   | balance 
-------+---------
 alice |     700
 bob   |     800

見どころは3つです。第一に、prepared トランザクションはサーバの強制停止と再起動をまたいでも消えません。これは仕様どおりで、PREPARE TRANSACTIONはトランザクション状態をディスクに完全に保存します。第二に、他のセッションは同じ行を更新できません。3秒のステートメントタイムアウトを設定していなければ、無期限に待ち続けます。第三に、決着させるには誰かがCOMMIT PREPAREDかROLLBACK PREPAREDを明示的に実行するしかありません。これがまさに2PCのブロッキングです。

公式ドキュメントの警告も具体的です。prepared トランザクションはトランザクションが保持していた全ロックを保持し続けるため、長期間prepared状態のまま放置するとVACUUMをブロックし、極端な場合はトランザクションID周回を防ぐためのデータベース停止を招く。またこのコマンドは「アプリケーションや対話的セッションで使うことは意図されていない」とも明記されており、複数データベースにまたがるグローバルトランザクションを行う外部トランザクションマネージャのためのものだと位置づけられています。

Saga パターン — 補償トランザクションで意味的に取り消す

2PCがロックを握って待つのが問題なら、ロックを持たない方向へ発想を変える手があります。それがSagaです。

原典はHector Garcia-MolinaとKenneth Salemによる論文「Sagas」で、Princeton大学在籍時の研究、1987年のACM SIGMOD国際会議（SIGMOD '87）の議事録249〜259ページに収録されています。動機は分散システムではなく長寿命トランザクション（long lived transaction, LLT）でした。論文の書き出しはこうです。LLTは比較的長期間データベースリソースを保持し、より短くありふれたトランザクションの終了を大きく遅らせる。この問題を緩和するために、我々はsagaという概念を提案する。

論文の定義は次のとおりです。LLTは、他のトランザクションと交錯（interleave）できるトランザクションの列として書けるならsagaである。データベース管理システムは、sagaの中の全トランザクションが成功裏に完了するか、あるいは部分実行を修正するために補償トランザクションが実行されるか、のどちらかを保証する。

補償トランザクションの定義も明確です。各sagaトランザクションTiには補償トランザクションCiが与えられるべきである。補償トランザクションはTiが行った動作を意味的な観点から取り消すが、Tiの実行が始まった時点の状態に必ずしもデータベースを戻すわけではない。論文は航空券予約の例を挙げます。Tiが座席を予約するならCiはその予約をキャンセルできる。しかしCiはTi実行時点の座席数をそのまま書き戻すことはできない。なぜならTiとCiの間に他のトランザクションが走り、予約数を変えているかもしれないからです。

そして保証されるのは次のどちらかの実行列です（論文の記法）。

T1, T2, ..., Tn                              （こちらが望ましい）
T1, T2, ..., Tj, Cj, ..., C2, C1             （0 <= j < n なる j について）

実装して動かしてみます。オーケストレーション型のsagaで、失敗したら実行済みステップの補償を逆順に流します。

def run_saga(ledger, steps, fail_at=None):
    done = []
    print(f"  開始時: {ledger.snapshot()}")
    for i, s in enumerate(steps):
        if fail_at == s["name"]:
            print(f"  [{i+1}] {s['name']:<16} -> 失敗")
            print(f"  --- 補償を逆順で実行 ---")
            for c in reversed(done):
                c["undo"](ledger)
                print(f"      compensate {c['name']:<16} {ledger.snapshot()}")
            return False
        s["do"](ledger)
        done.append(s)
        ledger.observed.append((s["name"], ledger.snapshot()))
        print(f"  [{i+1}] {s['name']:<16} OK  {ledger.snapshot()}")
    return True

注文作成・在庫引当・課金・出荷の4ステップを並べ、最後の出荷で失敗させた実行結果です。

=== (b) ship で失敗 -> 補償を逆順に実行 ===
  開始時: {'order': None, 'stock': 10, 'ledger': [], 'shipped': False}
  [1] create_order     OK  {'order': 'PLACED', 'stock': 10, 'ledger': [], 'shipped': False}
  [2] reserve_stock    OK  {'order': 'PLACED', 'stock': 9, 'ledger': [], 'shipped': False}
  [3] charge_payment   OK  {'order': 'PLACED', 'stock': 9, 'ledger': [('charge', 3000)], 'shipped': False}
  [4] ship             -> 失敗
  --- 補償を逆順で実行 ---
      compensate charge_payment   {'order': 'PLACED', 'stock': 9, 'ledger': [('charge', 3000), ('refund', -3000)], 'shipped': False}
      compensate reserve_stock    {'order': 'PLACED', 'stock': 10, 'ledger': [('charge', 3000), ('refund', -3000)], 'shipped': False}
      compensate create_order     {'order': 'CANCELLED', 'stock': 10, 'ledger': [('charge', 3000), ('refund', -3000)], 'shipped': False}
  結果: compensated  最終: {'order': 'CANCELLED', 'stock': 10, 'ledger': [('charge', 3000), ('refund', -3000)], 'shipped': False}
  開始時と同一か: False

最後の行に注目してください。開始時と同一ではありません。注文は消えずにCANCELLEDとして残り、元帳には課金と返金の2行が残っています。これがまさに論文の言う「意味的な取り消しであって、状態の巻き戻しではない」ということです。会計の世界では正しい姿でもあります。取引を消すのではなく、打ち消す取引を追加するのが原則だからです。

補償を設計するときに効いてくる制約を整理します。

3つ目と4つ目が実務上いちばん重要です。「送ってしまったメール」は補償できません。だからsagaを設計するときは、取り消せる操作を前に、取り消せない操作を後ろに並べ替えるところから始めます。

コレオグラフィとオーケストレーション

sagaの進行を誰が管理するかで2つの流儀があります。Chris Richardsonのmicroservices.ioは次のように区別しています。コレオグラフィではサービスがドメインイベントを発行し、それが他サービスのトランザクションを起動する。オーケストレーションでは専任のオーケストレータが、各サービスがどのローカルトランザクションを実行すべきかを指示する。

AWS Prescriptive Guidanceの「Saga orchestration pattern」は、オーケストレーション型の考慮事項として次を挙げています。補償トランザクションとリトライがアプリケーションコードを複雑にする。ローカルトランザクションを逐次処理するため結果整合になる。saga参加者は冪等でなければならない。予期しないクラッシュやオーケストレータ障害による一時的失敗で再実行され得るためです。sagaにはトランザクション分離がないため、並行実行で古いデータが見え得る。この対策としてセマンティックロックの使用を推奨する。そしてオーケストレータは全体を調整するため単一障害点になり得る。場合によってはコレオグラフィが好まれるのはこの問題のためだ、とも書かれています。

同ドキュメントは、AWS Step Functionsの標準ワークフローを使うことで単一障害点の問題を緩和できるとしています。Step Functionsは組み込みの耐障害性を持ち、各AWSリージョンの複数のアベイラビリティーゾーンにわたってサービス容量を維持するため、というのがその理由です。Temporalの公式ドキュメントも同様に「Sagaパターンは、トランザクションを一連のより小さく扱いやすいサブトランザクションに分解することで、複雑なワークフローにおける障害を管理・処理するために使われるデザインパターンです」と定義し、ワークフロー中のステップが失敗したら以前のステップを取り消す特定のアクションを実行して補償する、と説明しています。

いずれの製品も本質的にやっていることは同じで、「どこまで進んだか」を耐久性のあるストレージに記録し、プロセスが落ちても続きから再開することです。sagaの実装で本当に難しいのはビジネスロジックではなく、この状態管理のほうです。自作するくらいならワークフローエンジンに任せたほうが安全な場面は多いでしょう。

Saga には I がない

Sagaを採用するときにもっとも見落とされるのが分離（isolation）の欠如です。1987年の論文は、sagaと入れ子トランザクションの違いをこう述べています。sagaは2段階のネスト（トップレベルのsagaと単純なトランザクション）しか許さないこと。そして外側のレベルでは完全な原子性は提供されない。すなわちsagaは他のsagaの部分的な結果を見ることがある。

さらに補償の際の扱いも明記されています。補償トランザクションCiが実行されるとき、Ciによって補償される前にTiの結果を見てしまったかもしれないトランザクションに通知したりアボートしたりする努力は一切なされない。

先ほどのシミュレータでも観測できました。

=== (c) 他トランザクションから見えた中間状態（Iがない）===
  create_order     の直後に外部が読める値: order=PLACED, stock=10, ledger=[]
  reserve_stock    の直後に外部が読める値: order=PLACED, stock=9, ledger=[]
  charge_payment   の直後に外部が読める値: order=PLACED, stock=9, ledger=[('charge', 3000)]
  -> 補償で取り消される前の状態が、外部にはいったん見えている

後にこの性質を指して「sagaはACIDのうちIを持たない、つまりACDである」と表現されることがあります。ただしこの「ACD」という呼び方そのものは原論文には登場しません（後年の通称であり、初出は未確認です）。中身として押さえるべきなのは次の2点です。

• ダーティリード: 他のsagaやクエリが、後で補償される中間状態を読んでしまう。
• ロストアップデート: 中間状態を読んだ別のsagaがそれをもとに更新し、補償と競合する。

対策としてAWSが推奨するセマンティックロックは、レコードにPENDINGのような業務上の状態フラグを立て、その状態のレコードを他の処理が扱わないようにする手法です。要するにロックを業務モデルの一部として明示的に設計するということで、DBのロックが自動でやってくれていた仕事を、自分でドメインに書き下す作業になります。設計コストはかかりますが、少なくとも「何がロックされているか」がコードから読めるようになる利点はあります。

二重書き込み問題とアウトボックスパターン

sagaでもコレオグラフィでも、実装は必ず「DBを更新して、イベントを発行する」という形になります。ここに二重書き込み（dual write）問題が潜んでいます。DBのコミットとメッセージブローカへのpublishは、別々のシステムへの2つの書き込みです。どちらか片方だけ成功する状態が存在します。

実験してみます。DB書き込みの直後にプロセスが落ちるケースと、ブローカが停止しているケースを比較しました。

def outbox(order_id, crash_point):
    db, broker = DB(), Broker()
    # (1) 業務データとイベントを「同じローカルトランザクション」で書く
    db.stage("orders", order_id)
    db.stage("outbox", order_id)
    db.commit()
    if crash_point == "after_db":
        return db.orders, broker.topic, db.outbox     # リレーは後で再開する
    # (2) 別プロセス（CDC / ポーリングリレー）が outbox を読んで publish
    pending = list(db.outbox)
    for m in pending:
        try:
            broker.publish(m, fail=(crash_point == "broker_down"))
            db.outbox.remove(m)
        except RuntimeError:
            break                                      # 送れなければ outbox に残る = 再送される
    return db.orders, broker.topic, db.outbox

実行結果です。

シナリオ                        orders   topic  判定
二重書き込み / 正常                      1       1  一致
二重書き込み / DB後にクラッシュ               1       0  不一致(イベント消失)
二重書き込み / ブローカ停止                  1       0  不一致(イベント消失)
 
シナリオ                        orders   topic  outbox残  判定
アウトボックス / 正常                     1       1        0  整合(未送信は再送可)
アウトボックス / DB後にクラッシュ              1       0        1  整合(未送信は再送可)
アウトボックス / ブローカ停止                  1       0        1  整合(未送信は再送可)

二重書き込みでは、DBには注文が残っているのにイベントは永久に失われます。誰も再送してくれません。アウトボックスでは、イベントはoutboxテーブルに残っているので後から再送できる状態が保たれます。この差が本質です。

原理は単純で、業務データとイベントを同じローカルトランザクションで同じデータベースに書くだけです。分散トランザクションが要らなくなります。イベントを実際にブローカへ流すのは、CDC（変更データキャプチャ）やポーリングを行う別プロセスの仕事になります。

Debeziumの公式ドキュメントは、Outbox Event Router SMTが期待するアウトボックステーブルの構造を次のように示しています。

既定設定ではroute.by.fieldがaggregatetype、route.topic.replacementがoutbox.event.${routedByValue}になっており、aggregatetypeがcustomersのレコードはoutbox.event.customersトピックへ、ordersのレコードはoutbox.event.ordersトピックへ送出されます。ドキュメントはアウトボックスパターンの目的を「サービスの内部状態と、同じデータを必要とする他サービスが消費するイベント内の状態との不整合を避けること」と説明しています。

なおaggregateidをメッセージキーにするのは、Kafkaが同一キーを同一パーティションへ振り、パーティション内では順序が保たれるからです。同じ集約に対するイベントの順序が入れ替わらないようにするための設計です。

冪等性と exactly-once の現実

アウトボックスにしても、イベントはat-least-once（少なくとも1回）で届きます。リレーがpublishした直後にクラッシュすれば、outboxから削除する前なので再送されます。では「exactly-once」を謳うシステムは何をしているのか。

Apache Kafkaの公式ドキュメント「Message Delivery Semantics」の記述が率直で参考になります。多くのシステムが「exactly-once」配送セマンティクスを提供すると主張しているが、細かい注記を読むことが重要である。それらの主張はときに誤解を招くからだ（コンシューマやプロデューサが落ちるケース、複数のコンシューマプロセスがあるケース、ディスクに書いたデータが失われ得るケースに当てはまらないことがある、と続きます）。

Kafkaが実際に提供しているものを整理します。

• 冪等プロデューサ: 0.11.0.0以降、ブローカが各プロデューサにIDを割り当て、プロデューサが全メッセージに付けて送るシーケンス番号でメッセージを重複除去します。設定はenable.idempotenceで、公式の設定リファレンス上の既定値はtrueです。
• トランザクション: 同じく0.11.0.0以降、複数のトピックパーティションへ原子的に送れます。transactional.idを設定するとenable.idempotenceが暗黙に有効になります。設定リファレンスによればtransactional.idの既定値はnullで、既定ではトランザクションは使えません。同ページはさらに、既定ではトランザクションに最低3ブローカのクラスタが必要だと注記しています。transaction.timeout.msの既定値は60000（1分）です。
• コンシューマ側の分離レベル: isolation.levelをread_committedにすると、コミット済みのトランザクショナルメッセージのみを返します。ここが要注意で、既定値はread_uncommittedです。この既定のままだと、アボートされたトランザクションのメッセージまでコンシューマに届きます。

そしてKafkaのドキュメントが正直に書いている限界がここです。外部システムへ書き込む場合、コンシューマの位置（オフセット）と実際に保存される出力とを協調させる必要があるという制約がある。これを達成する古典的な方法は、コンシューマ位置の保存と出力の保存の間に2相コミットを導入することだろう。これはコンシューマにオフセットを出力と同じ場所に保存させることで、より単純かつ一般的に扱える。

つまりKafkaのexactly-onceは、Kafkaの内部で閉じた「読んで加工して書く」ループについての保証です。外部のDBやAPIへ書きに行った瞬間、その保証は切れます。そこから先で必要になるのがat-least-once配送 + 冪等な処理という組み合わせです。実験で確かめました。

class Consumer:
    def __init__(self, dedup):
        self.dedup, self.seen, self.balance = dedup, set(), 0
    def handle(self, msg):
        key, amount = msg
        if self.dedup:
            if key in self.seen:            # 同じ処理と同じトランザクションで記録する前提
                return "skipped"
            self.seen.add(key)
        self.balance += amount
        return "applied"

1000件のイベントを、30%の確率で再送が起きるブローカから受け取った結果です。

dedup=False 配送回数= 1490 残高= 149000 期待値=100000 差分= +49000
dedup=True  配送回数= 1455 残高= 100000 期待値=100000 差分=     +0

重複除去なしでは1490回配送されて残高が49%も水増しされました。重複除去ありでは、1455回配送されても残高は期待値ちょうどです。配送回数は変えられないが、処理の結果は変えられるというのが冪等性の意味です。

ここでのポイントは、self.seen.add(key)とself.balance += amountを同じトランザクションで確定させることです。片方だけ確定する実装だと重複除去が効きません。実務では処理済みキーのテーブルと業務更新を同一DBの同一トランザクションに入れます。

冪等キーの選び方も重要です。

--- 冪等キーの選び方で結果が変わる ---
  user+操作 (弱すぎる)               合計= 300 (正しくは600)
  user+操作+金額 (まだ弱い)            合計= 300 (正しくは600)
  クライアント発行の一意ID            合計= 600 (正しくは600)

同じユーザが同じ金額を意図的に2回課金するケースで、キーを内容から導出すると正当な2回目まで潰してしまいます。キーは内容から作るのではなく、クライアントが操作ごとに発行する一意なIDにする。この考え方はAPI側の設計と共通なので、REST APIの冪等性設計とあわせて読むと理解が固まります。リトライの方針そのものはタイムアウト・リトライ・サーキットブレーカーの領域です。

TCC — 予約を明示的にモデル化する

sagaの補償が難しいのは、「いったん確定させてから打ち消す」からです。だったら最初から仮押さえにしておけばいいというのがTCC（Try-Confirm-Cancel）です。

Apache Seataの公式ドキュメントは、TCCを分散トランザクションにおける2相コミットプロトコルの一種と位置づけ、3つの操作をこう説明しています。Tryフェーズでは各ブランチトランザクションのリソースを予約する。Confirmフェーズは第2フェーズのコミット操作で、実際のビジネスロジックを実行する。Cancelフェーズは第2フェーズのロールバック操作で、予約したリソースをキャンセルして初期状態に戻す。全ブランチがリソース予約に成功すればグローバルにコミット、1つでも失敗すればグローバルにキャンセルへ進みます。

XAとの違いも同ドキュメントが述べています。TCCは侵入的な分散トランザクション解決策であり、ビジネスシステム側がTry・Confirm・Cancelの各操作を実装する必要がある。その代わりTCCは基盤のデータベースから完全に独立しており、データベースやアプリケーションをまたいだリソース管理ができ、業務エンティティに対してより細かい制御を提供する、と。

XA・Saga・TCCを並べると位置づけが見えます。

TCCで実装するとよく踏む落とし穴も知られています。Seataのブログは、TCCモードで扱う必要のある3つの問題として冪等性、ダングリング（Tryが来る前にCancelが来る）、空ロールバック（Tryが実行されていないのにCancelが呼ばれる）を挙げています。ネットワークの再送とタイムアウトを考えれば当然起きる状況で、Try/Confirm/Cancelを自前で書くとこれらを全部自分で面倒を見ることになります。

合意ベースのアプローチ — Percolator と Spanner

ここまで見た2PCの弱点は、突き詰めるとコーディネータが単一障害点だからでした。ならばコーディネータの状態を複製すればよい、というのが現代的な解です。

GrayとLamportの論文の主張はまさにこれです。要旨にはこうあります。古典的な2相コミットプロトコルはコーディネータが故障するとブロックする。耐障害合意アルゴリズムも同様に合意に到達するが、いずれかの過半数が動作している限りブロックしない。Paxos Commitアルゴリズムは、各参加者のcommit/abort決定に対してPaxos合意アルゴリズムを走らせることで、2F+1個のコーディネータを使い、そのうち少なくともF+1個が正常に動作していれば進行するトランザクションコミットプロトコルを得る。Paxos Commitは2相コミットと同じ安定ストレージ書き込み遅延を持ち、無障害ケースでは同じメッセージ遅延で実装できるが、より多くのメッセージを使う。古典的な2相コミットアルゴリズムは、Paxos CommitアルゴリズムのF = 0という特殊ケースとして得られる。

2PCはコーディネータ多重度ゼロのPaxos Commitという整理は、この分野で最も見通しのよい説明のひとつだと思います。合意アルゴリズムそのものについてはRaft合意アルゴリズム入門で詳しく扱いました。

実システムでの実例を2つ挙げます。

PercolatorはGoogleのDaniel PengとFrank Dabekによる論文「Large-scale Incremental Processing Using Distributed Transactions and Notifications」（OSDI '10）で発表されたシステムです。Bigtableの上に構築され、行をまたぎテーブルをまたぐスナップショット分離セマンティクスのACIDトランザクションを提供します。論文の記述によれば、バッファされた書き込みをコミットする基本的なアプローチはクライアントが調整する2相コミットで、異なるマシン上のトランザクションはBigtableのタブレットサーバ上の行トランザクションを介して相互作用します。

Percolatorの巧妙な点はロックをc:lockという専用列としてBigtable自身に書くところです。コミットの第1フェーズ（論文の呼び方では「prewrite」）で書き込む全セルをロックしようとし、そのうち1つを任意にprimaryに指定します。他のセカンダリのロックにはプライマリロックへの参照が入ります。クラッシュでロックが取り残されても、クリーンアップしたいトランザクションはプライマリの場所を辿って同期できる、という設計です。ロックの永続化をストレージ層に任せることで、コーディネータの状態を別管理しなくてよくなっています。論文は正直に代償も書いていて、故障マシン上のトランザクションが残したロックの掃除は遅延評価的な方式を採っており、この遅延はトランザクションのコミットを数十秒遅らせ得る。OLTPを走らせるDBMSでは受け入れられないが、ウェブの索引を作る増分処理システムでは許容できる、としています。

Spanner（OSDI 2012）はもう一段進んでいます。論文はSpannerを、データセンタに散らばるPaxos状態機械の多数の集合にわたってデータをシャードするデータベースだと説明します。そして2.1節に核心があります。トランザクションが複数のPaxosグループにまたがる場合、それらのグループのリーダーが協調して2相コミットを実行する。参加者グループの1つがコーディネータに選ばれる。そして各トランザクションマネージャの状態は、その下層のPaxosグループに保存される（したがって複製される）。

つまりSpannerは2PCを捨てていません。2PCのコーディネータをPaxosで複製することで、コーディネータの単一障害点という2PC最大の弱点だけを取り除いているのです。加えてSpannerはTrueTime APIで外部一貫性を達成しており、その部分は論理クロック入門で扱いました。

まとめると、現代の分散データベースが選んでいるのは「2PCをやめる」ではなく「2PCの各参加者とコーディネータを、それぞれ合意プロトコルで複製する」という道です。ただしこれはデータベース製品の中の話で、アプリケーションが自前の異種サービス群に対して同じことをやるのは現実的ではありません。だからアプリケーション層ではSagaが選ばれます。

どれを選ぶか

判断の材料を整理します。まず、そもそも分散トランザクションが必要かを疑うのが最初のステップです。同一DB内のトランザクションで済むように境界を引き直せるなら、それがいちばん安上がりです。

2PCを選ぶかどうかの目安は次の4つです。参加者が2、3個までで全員が同一運用チームの管理下にあるか。prepared状態が残ったときに検知して人手で決着させる運用が組めるか。参加者のうち1つでも落ちたら全体が止まることを業務として受け入れられるか。ヒューリスティック決定が発生したときの整合性回復手順を書けるか。4つとも「はい」なら選択肢になります。1つでも怪しければSagaに寄せたほうが結果的に運用は楽です。

逆にSagaを選ぶときのチェックリストです。

• 各ステップに補償を書けるか。書けないステップはsagaの最後に寄せられるか。
• 中間状態が外部に見えることを業務として許容できるか。できないならセマンティックロックを設計できるか。
• 各ステップと各補償を冪等にできるか。冪等キーは何にするか。
• 進行状態を耐久性のあるストレージに記録し、プロセス障害から再開できるか。自作するか、ワークフローエンジンを使うか。

まとめ

分散トランザクションは、単一DBのトランザクションを「そのまま分散させる」ことができないという事実から始まります。要点を振り返ります。

• 分散するとログが複数になり、決定の伝達に時間がかかり、相手の状態が観測できなくなる。タイムアウトは障害の証拠にならない。原子的コミット問題は多数決ではなく全員一致を要求する。
• 2PCはprepareフェーズで参加者に「約束」させ、ロックを握ったまま待つ状態を作る。GrayとLamportの論文は、全RMがPreparedを送った直後にTMが落ちると他のRMは結果を知る術がないと明記している。
• 2PCの通常系メッセージ数は3N-1（TMが開始RMと同居なら3N-3）。参加者を増やすほど成功確率は(1-p)^Nで落ちる。
• 3PCはノード停止故障ならブロックしないが、ネットワーク分断に耐えられず同期モデルを仮定する。GrayとLamportは「明確な正しさの条件を満たすと証明された完全なアルゴリズムを知らない」と述べている。
• XA仕様（1991年12月、XO/CAE/91/300）はpresumed rollback付き2PC、read-only最適化、one-phase commit、そしてヒューリスティック分岐完了を規定する。ヒューリスティック決定は共有リソースを不整合な状態に置き得る、と仕様自身が認めている。
• PostgreSQLのmax_prepared_transactionsの既定値は0で、2相コミットは最初から無効。prepared トランザクションはサーバ再起動をまたいで残り、ロックを握り続け、VACUUMをブロックする。
• Sagaは1987年のGarcia-MolinaとSalemの論文が原典。補償トランザクションは意味的な取り消しであり、開始時点の状態に戻すわけではない。分離もなく、論文自身が「sagaは他のsagaの部分的な結果を見ることがある」と書いている。対策はセマンティックロック。
• 二重書き込み問題はアウトボックスパターンで解ける。業務データとイベントを同一ローカルトランザクションで書き、別プロセスがリレーする。
• exactly-onceは配送の保証ではない。Kafka公式ドキュメント自身が「主張の細かい注記を読め」と警告している。実務解はat-least-once配送と冪等な処理の組み合わせで、冪等キーはクライアント発行の一意IDにする。コンシューマのisolation.levelの既定はread_uncommitted、プロデューサのtransactional.idの既定はnullで、既定のままでは何も保証されない。
• PercolatorはロックをBigtableの列として書き、Spannerは2PCのトランザクションマネージャの状態をPaxosグループに複製する。2PCを捨てるのではなく、単一障害点だけを取り除くのが現代的な解。

最初に立ち返ると、いちばん強い一手は分散トランザクションを必要としない設計に変えることです。サービス境界の引き方を変えれば済む話は少なくありません。それでも境界をまたぐ整合性が要るなら、この記事で見た選択肢の中から、業務が許容できる不整合の形を選ぶことになります。どれを選んでも「完全に整合する」状態は買えません。買えるのは、どこにどんな不整合が現れるかを自分で決める権利のほうです。

参考リンク

• Sagas - Garcia-Molina & Salem, SIGMOD '87（原典PDF）
• Sagas - SIGMOD Record の書誌情報
• Consensus on Transaction Commit - Jim Gray & Leslie Lamport（ACM TODS 2006）
• Distributed Transaction Processing: The XA Specification - X/Open CAE Specification, 1991
• PostgreSQL Documentation: PREPARE TRANSACTION
• PostgreSQL Documentation: max_prepared_transactions（既定値0）
• PostgreSQL Documentation: pg_prepared_xacts
• Apache Kafka Documentation: Message Delivery Semantics
• Apache Kafka: Producer Configs（transactional.id と enable.idempotence）
• Apache Kafka: Consumer Configs（isolation.level の既定値）
• KIP-98 - Exactly Once Delivery and Transactional Messaging
• Debezium Documentation: Outbox Event Router
• Debezium Blog: Reliable Microservices Data Exchange With the Outbox Pattern
• microservices.io: Pattern - Saga
• AWS Prescriptive Guidance: Saga orchestration pattern
• AWS Prescriptive Guidance: Saga choreography pattern
• AWS Prescriptive Guidance: Transactional outbox pattern
• Temporal Documentation: Use cases and design patterns（Saga パターン）
• Apache Seata: TCC Mode
• Large-scale Incremental Processing Using Distributed Transactions and Notifications - Percolator, OSDI '10
• Spanner: Google's Globally-Distributed Database - OSDI 2012