# Calvin Calvin(Thomson ほか, 2012 [THOMSON12])は、ロック獲得前にレプリカ間で実行順序とトランザクション境界について合意を得ることで、ノード障害がトランザクション中断の原因にならないようにする分散トランザクションプロトコルである。従来のデータベースシステムは二相ロックまたは楽観的並行性制御を使い、決定論的なトランザクション順序を持たないため実行フェーズでの調整が必要になるのに対し、Calvin は決定論的な順序を事前に導入することでこの調整オーバーヘッドをなくし、すべてのレプリカが同じ入力から同等の出力を独立に生成できるようにする。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] §13.4) ## アーキテクチャ 典型的な Calvin の実装は、パーティションごとにシーケンサ・スケジューラ・ワーカー・ストレージシステムを同じ場所に配置する。 - **シーケンサ**: 全トランザクションのエントリポイント。トランザクションが実行される順序を決定し、グローバルなトランザクション入力シーケンスを確立する。競合とバッチでの決定を最小化するため、タイムラインはエポックに分割され、シーケンサはトランザクションを短時間のウィンドウ(原著論文では 10ms)にグループ化する。このウィンドウがレプリケーションの単位にもなる。 - **スケジューラ**: トランザクションのバッチがレプリケーションに成功すると、シーケンサから転送を受けてトランザクション実行を編成する。決定論的なスケジューリングプロトコルにより、トランザクションの一部を並行実行しつつ、シーケンサが指定したシリアル実行の順序を維持する。 - **ワーカー**: スケジューラの管理下で、(1) 読み取りセット・書き込みセットを分析してアクティブな参加ノードを特定、(2) ローカルなデータを収集、(3) 他ノードから転送されたデータレコードを受け取る、(4) トランザクションのバッチを実行し結果をローカルストレージに永続化する、という4ステップを実行する。実行結果を他ノードへ転送する必要はなく、他ノードも同じ入力を受け取り独立に実行・永続化する。 エポック内でどのトランザクションが含まれるかについてシーケンサが確実に合意に達するよう、Calvin は Paxos のコンセンサスアルゴリズムまたは専用リーダーによる非同期レプリケーションを使用する。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] §13.4) ## 制約 Calvin は、読み取りセット・書き込みセットを特定するための追加読み取りに依存するトランザクション(read set が動的に決まるトランザクション)をネイティブにサポートしない。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] §13.4) ## Spanner との対比 Calvin がシーケンサでの合意によりグローバルなトランザクション実行順序を確立するのに対し、[[Spanner]] はパーティション(シャード)ごとの合意グループに対してツーフェーズコミットを使用する。両者は分散トランザクションを管理する対照的な2つのアプローチとして並置される。Calvin を用いた実装例として FaunaDB が知られる。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] §13.5) ## 関連 - ソース: [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] - 概念: [[分散トランザクション]] / [[分散コンセンサス回避]] - 比較対象: [[Spanner]] ## 出典 - [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]](§13.4 Calvin のシーケンサ/スケジューラ/ワーカー設計、§13.5 Spanner との対比) - Thomson, Alexander, Thaddeus Diamond, Shu-Chun Weng, Kun Ren, Philip Shao, and Daniel J. Abadi. 2012. "Calvin: fast distributed transactions for partitioned database systems." In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (SIGMOD '12): 1-12.(原著論文、詳説 データベース経由の間接引用)