決定論的トランザクション実行(Calvin)
分散トランザクションのコミット調停を丸ごと無くせます。Calvin が事前に実行順を決めて全レプリカで同じ順に流すことで、2PC のブロッキングをどう回避するかを原理から押さえます。
- 1.Calvin は全トランザクションの直列順をシーケンサ層で先に決め、全レプリカが同じ順序で決定論的に実行するため、コミット可否がレプリカ間で食い違わず2PCが不要になる。
- 2.各ノードはロックを順序どおりに取り、実行は完全に決定論的にするため、同じ入力からは必ず同じ結果になる。レプリケーションは状態ではなく入力ログのコピーで済む。
- 3.代償として、トランザクションが読み書きする対象（read/write set）を実行前に把握できる必要があり、対話的トランザクションや動的なアクセスは前処理（reconnaissance）が要る。
なぜ「順序を先に決める」のか
分散DBで複数ノードにまたがる更新を原子的に確定するとき、伝統的には 2相コミット（2PC） でコミット可否を投票し合います。しかし 2PC は、prepare で YES を返した参加者がコーディネータの決定を待つ間ロックを握って固まるブロッキング問題を抱えます。
Calvin は発想を逆転させます。「実行してみてからコミットできるか合議する」のではなく、実行を始める前に全トランザクションの直列順（serial order）を確定してしまう。順序さえ全レプリカで一致していれば、各レプリカは独立にその順で実行するだけで必ず同じ結果に至ります。結末がレプリカ間で食い違う余地が無いのだから、コミット可否を問い合わせる 2PC そのものが要らなくなる――これが核心です。
同じ初期状態に、同じトランザクション列を、同じ順序で適用すれば、必ず同じ最終状態になる。これを保証するのが決定論的実行です。実行結果が入力だけで一意に決まるため、レプリカは互いの状態を突き合わせる必要がなく、「どの順で何を流したか」という入力ログだけ一致させればよくなります。
3層アーキテクチャ
Calvin はトランザクション処理を3つの層に分けます。
シーケンサ（sequencer）層：入ってくるトランザクションを受け取り、グローバルな直列順に並べる。一定間隔（エポック, 例 10ms）ごとに入力をバッチ化し、その順序を全レプリカへ複製する。順序の合意自体には Paxos / Raft を使う。 スケジューラ（scheduler）層：確定した順序に従い、各ノードでロックを取得して実行を割り当てる。決定論的ロックプロトコルでデッドロックを原理的に避ける。 ストレージ層：実際の read/write を担う。Calvin は特定のストレージ実装に依存せず、key-value でも何でもよい。
ポイントは、複製されるのが「順序づけられた入力ログ」だけだという点です。各レプリカは同じ入力列を受け取り、独立に決定論的実行するので、最終状態は自動的に一致します。状態のページや WAL をコピーする一般的な レプリケーション と違い、Calvin の複製は「何を実行するか」のリストで足ります。これはレプリカ間の帯域を大きく節約します。
入力Tx
│
┌──────▼───────┐ エポック毎に順序確定 → Paxos/Raftで複製
│ Sequencer │───────────────┬───────────────┐
└──────┬───────┘ │ │
┌──────▼───────┐ ┌──────▼──────┐ ┌──────▼──────┐
│ Scheduler │ 同じ │ Replica B │ │ Replica C │
│ (決定論ロック)│ 順序 │ 同順で独立 │ │ 同順で独立 │
└──────┬───────┘ で実行 │ 実行 │ │ 実行 │
┌──────▼───────┐ └─────────────┘ └─────────────┘
│ Storage │
└──────────────┘
決定論的ロックプロトコル
順序を決めただけでは不十分です。各ノードがその順序を実行時に正しく守る必要があります。Calvin は次の規則でロックを取ります。
- スケジューラは確定した順序で各トランザクションを見て、そのトランザクションが必要とする全ロックを、順序の早い側から優先して付与する。
- あるトランザクション
Tiがロックを要求したとき、それより順序が前のTjが同じロックを待っている／保持している間は、Tiは割り込めない。
この規則は 2相ロック（2PL） に似ますが、決定的な違いがあります。通常の 2PL ではロック取得競合がデッドロックを生み、検出してどちらかをアボートする必要があります。アボートする相手の選択は実行時の状況に依存するため非決定論的で、レプリカごとに異なる結果を生みかねません。
全ノードが「グローバル順序の早い方を必ず先にロックさせる」という同一基準で待たせ合うため、待ちグラフは順序に沿って一方向にしか伸びません。循環待ち（A は B を、B は A を待つ）が原理的に作れないので、デッドロックは発生しません。検出もアボートも不要で、これが決定論を保つ鍵です。
read/write set 事前把握という制約
決定論的にロックを取るには、トランザクション開始前に「どのキーを読み書きするか（read set / write set）」が分かっていなければなりません。これが Calvin の最大の制約です。
SELECT の結果を見てから次に触る行を決める、といった実行してみないとアクセス対象が分からないトランザクションでは、事前にロック集合を確定できません。Calvin はこれを OLLP（Optimistic Lock Location Prediction） で扱います。まずロックを取らずに偵察実行（reconnaissance）――読み取りだけ先に走らせてアクセス対象を予測し、その予測したロック集合に基づいて本実行する。本実行の開始時にDBの状態が偵察時から変わってロック集合の予測が外れていたら、その回はアボートして偵察からやり直します。予測が外れやすいワークロードでは、この再試行が純粋なオーバーヘッドになります。
つまり Calvin は、アクセスパターンが事前に読める一括処理・ストアド的なトランザクションに強く、結果を見ながら枝分かれする対話的処理には弱い、という非対称を持ちます。
他方式との立ち位置
| 観点 | 2PC + 2PL（伝統的分散Tx） | Calvin（決定論的実行） |
|---|---|---|
| コミット調停 | prepare/commit の投票が必要 | 順序が事前一致するため不要 |
| 障害時ブロッキング | コーディネータ障害で in-doubt 化しうる | 起きない。順序ログから誰でも再実行できる |
| レプリケーション対象 | 状態（ページ/WAL）を複製 | 順序づけられた入力ログのみを複製 |
| デッドロック | 発生し検出・アボートが必要 | 決定論ロックで原理的に発生しない |
| read/write set | 実行時に動的でよい | 実行前に把握が必要（対話的処理は偵察が要る） |
| 非決定的アボート | 許される | 禁止（レプリカ間で結果が割れるため） |
Calvin が「非決定的なアボートを許さない」点は重要です。制約違反やユーザ要求による論理的なアボートは、入力から一意に決まるので全レプリカで同じく起きてよい。しかしデッドロックやノード障害といった実行時の偶発要因によるアボートは、レプリカごとに発生有無が変わって状態を分岐させるため、設計から排除されています。だからこそ決定論ロックでデッドロックを根絶し、ノードが落ちても順序ログから再実行する形を取ります。
楽観的制御・SSI との対比
OCC やタイムスタンプ順序、あるいは SSI は「まず走らせ、危なければ後で1つアボートする」という事後検証の思想でした。Calvin はその真逆で、走らせる前に順序を固定し、実行は決定論で必ず通すという事前確定の思想です。前者は競合がまれなほど速く、後者は順序づけのバッチ遅延（エポック1つ分のレイテンシ）を払う代わりに、調停も検出も無い一定コストでスループットを稼ぎます。
「Calvin が 2PC を不要にできるのは、全レプリカが事前に一致した順序で決定論的に実行するため、コミット可否がレプリカ間で食い違わないから」――この因果を一息で言えるかが肝です。代償は read/write set の事前把握が要ること、利点はデッドロック・非決定的アボートの排除と入力ログだけで済むレプリケーション、という対をセットで押さえましょう。
まとめ
- Calvin はシーケンサ層でグローバルな直列順を先に確定し、全レプリカが同じ順序で決定論的に実行する。結末が一意に決まるため 2PC のコミット調停とブロッキングが不要になる。
- 決定論ロックプロトコルによりデッドロックは原理的に発生しない。非決定的アボートを禁じることで、レプリカ間の状態分岐を防ぐ。
- 複製するのは状態ではなく順序づけられた入力ログだけで済み、レプリカ帯域を節約できる。
- 制約は read/write set を実行前に把握する必要があること。対話的トランザクションは偵察（OLLP）で予測し、外れたら再試行するためオーバーヘッドが乗る。
データベース Article
決定論的トランザクション実行(Calvin)を実務で読む
TL;DRは入口です。実際に選ぶ・使う段階では、何を解決するか、何と比較するか、導入後にどこで詰まるかまで見る必要があります。
解決すること
データベース
比較で見る軸
難易度: advanced / カテゴリ: データベース / タグ数: 5
導入後に効く点
各ノードはロックを順序どおりに取り、実行は完全に決定論的にするため、同じ入力からは必ず同じ結果になる。レプリケーションは状態ではなく入力ログのコピーで済む。
先に潰すリスク
用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。
- 難易度
- advanced
- カテゴリ
- データベース
- タグ数
- 5
判断チェックリスト
- 自社の用途が「データベース / 分散トランザクション」に近いか確認する。
- 強みである「Calvin は全トランザクションの直列順をシーケンサ層で先に決め、全レプリカが同じ順序で決定論的に実行するため、コミット可否がレプリカ間で食い違わず2PCが不要になる。」が本当に評価軸になるか確認する。
- 注意点の「用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。」を運用で吸収できるか確認する。
- 公開値や仕様値は、対象プラン・対象機種・対象リージョンまで確認する。
- 既存システム、ID、ネットワーク、監視、バックアップとの接続方法を先に洗い出す。
- 小さく試してから、本番移行、権限設計、障害時手順、コスト監視を決める。