Percolator

• Googleが作った、大規模データに対するインクリメンタル処理のためのシステム

• Googleの検索インデックス構築で使われている

• TiKVの分散トランザクションでもアイデアが使われている

• Percolatorでは、Snapshot isolationを保証

仕組み

• カラムCは、以下のカラム群に細分化され、BigTableに載る
  • c:lock, c:write, c:data, c:notify, c:ack_0
• こんな感じで書かれる
  • example, ,,, ,,,, ,,,, ,,,
  • タイムスタンプ値はTimestamp Oracleから取る
  • c:notifyは変更されたセルがdirtyであることを示す
  • ユーザーはPercolatorにオブザーバを追加することができ、オブザーバが処理をしたらその時のタイムスタンプをc:ack_0に書く
    • オブザーバのread onceを保証するためという感じかな(kekeho)

write

• 2PCで書く
  1. prewrite
     • TSOから取得したstart_tsでc:lockにロックを掛ける
       • ロックのうち、どれか1つがPrimary lockとなり、ほかはSecondary lockとなる?
     • start_tsでc:dataに値を書き込む
     • 既にロックされている or start_tsより新しいバージョンの値がある場合、書き込み競合なので、現在のトランザクションはrollbackされる
       • 単にロックと、データ列の対応する値を削除するだけ
  2. commit
     • TSOからcommit_tsを取得
     • commit_ts、c:writeに書き込む。Primary lockを取る。すべてのSecondary lockに対してもこれを繰り返す
       • PrimaryのCommitが完了すればトランザクションはおしまい。セカンダリロックのコミットが失敗しても問題ない
         • なんで? というか、いまいちprimary lock, secondary lockがわかっていない(kekeho)
• read
  • TSOからタイムスタンプtsを取得
  • 読み込もうとしているrowが、$[0,ts]$の範囲でロックされていないかチェック
    • ロックがないか、tsより大きなタイムスタンプでロックされていればOK
  • c:writeのcommit_tsが$[0,ts]$の範囲の中で最新のレコードを取得する
    • そこで指しているstart_tsのc:dataを読む
  • lock-free readとhistorical readを提供

参考

• https://tikv.org/deep-dive/distributed-transaction/percolator/