Percolatorスタイルの分散SI(MVCC+2PC)

なぜ Percolator が要るのか

スナップショット分離（SI）は、トランザクション開始時点の一貫したスナップショットを読み、書き込みは MVCC で別バージョンとして積む方式です。単一ノードなら開始時刻とコミット時刻を1つの時計から配れば成立します。ところがデータが多数のノードに分散すると、(1) 全ノードで一意かつ単調増加する時刻をどう配るか、(2) 複数ノードへの書き込みをどう原子的に確定するか、という2つの難題が出てきます。

Google の Percolator は、この2つを「タイムスタンプオラクル」と「行に埋め込んだ2相コミット」で解いた設計で、TiKV/TiDB をはじめ多くの分散DBが継承しています。中央のトランザクションマネージャを持たず、コミットの状態をデータ行そのものに載せるのが最大の特徴です。

タイムスタンプオラクル：時刻を一元配給する

Percolator は時刻を分散させず、**単一のタイムスタンプオラクル（TSO）**が単調増加の整数を払い出します。各トランザクションは開始時に start_ts を、コミット直前に commit_ts を TSO から受け取ります。この2つの時刻が、そのトランザクションが読むスナップショットと、書いたバージョンの可視性を決めます。

物理時計のずれを気にしなくてよいのが TSO 方式の利点です。対照的に Google Spanner は TrueTime という不確かさ付きの物理時計を使い、待ち（commit-wait）でずれを吸収します（→ ハイブリッド論理時計と TrueTime）。Percolator は論理時刻の一元配給を選び、設計を単純化しています。

データレイアウト：3つの列ファミリ

Percolator は各論理列を、下層の分散KVに対して3つの列で表現します。

Data  : (key, start_ts)   -> value         実データ。バージョンごとに残す
Lock  : (key)             -> {primary, start_ts, ...}  未コミットのロック
Write : (key, commit_ts)  -> start_ts       コミット済みバージョンへのポインタ

読み取りは Write 列を commit_ts <= start_ts の範囲で新しい順に引き、見つかった start_ts で Data 列を参照します。Lock 列が、まさに分散2PCの状態を行に埋め込む仕掛けです。あるキーにロックが載っていれば、そのキーは誰かのトランザクションがコミット中だと分かります。

コミット手順：Prewrite と Commit の2フェーズ

クライアント自身がコーディネータ役を兼ね、書き込み集合の中から1つのキーを**主キー（primary）**に選びます。残りは副キー（secondary）です。primary のロックを消す1回の操作が、トランザクション全体のコミット点になります。

肝は「全体の原子性が primary のロック削除という単一キー上の原子操作に帰着する」点です。下層KVは単一キーの読み書きさえ原子的なら良く、分散合意は各キーの複製（Raft 等）に任せられます。これは古典的 2相コミット と同型ですが、prepare に相当するのが Prewrite、commit に相当するのが primary のロック削除です。

障害回復：ブロッキングしない理由

古典的 2PC の弱点は、コーディネータが prepare 後に落ちると参加者がロックを抱えて固まるブロッキングでした。Percolator はコーディネータの状態を持たない代わり、state を primary 行のロック/Write に載せているため、後から来たトランザクションが状況を読んで自律的に決着できます。

副キーにロックを見つけて止まったトランザクションは、ロックが指す primary を調べます。

つまり「コミットしたか否か」の唯一の真実が primary の状態に集約され、誰が見ても同じ判断に到達します。クライアントが Commit フェーズの最中（primary はコミット済みだが副キーが未処理）で落ちても、後続が roll-forward で前へ進めるため、一度確定したコミットが失われることはありません。ロックには TTL を付け、生きているクライアントを誤って横取りしないようにします。

SI が防ぐ／防がない異常

Prewrite の衝突チェックにより、2つのトランザクションが同じキーを書こうとすれば後発がアボートし、ロストアップデートは防げます。一方で SI は本質的に書き込みスキューを許すため、素の Percolator は直列化可能ではありません。TiDB などは悲観ロックモード（Prewrite 前に行ロックを取る）や SELECT FOR UPDATE で、書き込みスキューが問題になる場面を補います。

まとめ

• Percolator は TSO が配る単調増加の start_ts/commit_ts と、行に埋め込んだ Lock/Write 列で、分散KV上に MVCC ベースのスナップショット分離を実装する。
• コミットは Prewrite（各キーにロック）→ Commit（primary のロック削除で原子的に確定） の2相で、専用コーディネータプロセスを持たず、クライアントが調整役を兼ねる。
• 原子性が primary 行の単一キー原子操作に帰着するため、下層は単一キーの原子性と複製合意さえあればよい。
• コミット状態が primary に集約されるので、障害時は後続が primary を見て roll-forward / roll-back で自律決着でき、古典的 2PC のブロッキングを避けられる。
• 素の SI は書き込みスキューを許し直列化可能ではない。GC と短いトランザクション維持が運用の要となる。