# Percolator Percolator は、分散データベースである [[Bigtable]] を基盤として、その上にトランザクション API を実装する Google のライブラリである。既存のシステムの上にトランザクション API を構築する例として知られる。データレコード、コミットされたデータポイントの場所(書き込みメタデータ)、異なる列のロックを Bigtable 上に格納する。競合状態を避けて1回の RPC 呼び出しでテーブルのロックを確実に行うために、1回のリモートコールで読み取り変更書き込み(read-modify-write)操作を実行できる、条件付き変更の Bigtable API を使用する。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] §13.7) ## トランザクションモデル Percolator は[[スナップショット分離とMVCC|スナップショット分離(SI)]]を採用する。トランザクション内のすべての読み取りは、開始タイムスタンプより前にコミットされた値の一貫したスナップショットに限定される。書き込みと書き込みが競合する場合(2つの並行トランザクションが同じセルへ書き込もうとする場合)は、最初にコミットしたほうのみが成功する(first committer wins)。 各トランザクションは、クラスタ全体で一貫性があり単調増加する**タイムスタンプオラクル**へ2回問い合わせる: 1回はトランザクション開始時のタイムスタンプ取得、もう1回はコミット時のタイムスタンプ取得である。書き込みはバッファリングされ、クライアント駆動のツーフェーズコミットでコミットされる。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] §13.7) ## prewrite/commit の2フェーズ 1. **初期状態**: 以前のトランザクション実行後の最新タイムスタンプが各セルに記録され、ロックは未取得。 2. **prewrite(第1フェーズ)**: トランザクション中に書き込まれるすべてのセルのロック取得を試みる。ロックの1つはプライマリとしてマークされ、クライアントのリカバリに使用される。より新しいタイムスタンプを持つデータの既存書き込みや未解放のロックがあれば競合とみなしトランザクションを中断する。 3. **commit(第2フェーズ)**: すべてのロックの取得に成功し競合の可能性がないと判断されると、プライマリから始めてクライアントがロックを解放し、ロックを書き込みレコードに置き換えて書き込みを公開する。書き込みメタデータを最新のデータポイントのタイムスタンプで更新する。 クライアントがコミットを試みたときに障害が発生する可能性があるため、より新しいトランザクションが不完全な状態を発見した場合はプライマリロックを解放してコミットを試みるか、プライマリロックがすでに解放されていればトランザクションの内容をコミットする。一度にロックを取得できるトランザクションは1つのみであり、すべての状態遷移はアトミックである。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] §13.7) ## 実装例 Percolator モデルに基づくデータベースの例として TiDB(Ti は Titanium を表す)がある。TiDB は強い一貫性・高可用性・水平スケール性を持つオープンソースデータベースで、MySQL と互換性がある。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] §13.7) ## 関連 - ソース: [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] - 概念: [[スナップショット分離とMVCC]] / [[分散トランザクション]] - 基盤: [[Bigtable]] ## 出典 - [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]](§13.7 Percolator のトランザクションモデルと prewrite/commit の実装)