本記事について
DEIM2022 (DEIM2022 第14回データ工学と情報マネジメントに関するフォーラム)
T3：近代的トランザクション処理技法
講演者：川島 英之（慶應義塾大学）
の聴講メモです。
メモは口頭説明を中心にまとめています。資料を併せてご参照ください。
【公式サイト資料】
https://event.dbsj.org/deim2022/post/tutorial/deim2022_tutorial_T3_slides.pdf
※当日配布資料とは多少の差異がありました。本メモは当日配布資料をベースにしています。
Transaction
Transaction Processing System = Concurrency Control + Recovery
トランザクションは様々な場面で使われている。例えば、spotify で音楽を聴くときにも裏ではトランザクションが利用されている。
Why transaction?
ATM が以下の操作で構成されているとする。
- DB の値を Read でメモリ上に読み込む。
- メモリ上で値を操作する。
- メモリ上の値を Write で DB に書き戻す。
スライドの例では Company と You の操作が並行して行われている。3万円の口座から You が1万円を引き出し、Company が1万円を入金している。本来なら Company と You の操作完了後に口座は3万円となるべき。
だが、Company, You 共に初期値の3万円を Read したため、You 側の Write で2万円と書き込み、その後に Company 側の Write で4万円と書き込んでしまう。結果として口座が4万円になってしまった。
こういった事態を防ぐのがトランザクションである。
Lost Update
先ほどのような事象を Anomaly と呼ぶ。
Anomaly にもいろいろあるが、今回のは Lost Update と呼ばれる。
Isolation Levels & Anomalies
Serializable に実行できれば全ての Anomaly が発生しないとわかっている。
この Serializable な処理をいかに早く実行するかがポイントになる。
Serializability
Serializability は Serialize な実行と同等なもの。
Serialize な実行とは、トランザクション T1, T2 であれば T1 -> T2, T2 -> T1 のいずれかの順で実行されること。
Quiz How many serial orders?
トランザクションが N 個あったとすると、その組み合わせのパターンは N! となる。
Serializable
Serializable にはいくつかの種類がある。Conflict, Final State, View など。
今回は Conflict Serializable を取り上げる。
表記法の説明をする。
"r1(A)" は以下を意味する。
- オペレーションは read
- トランザクションIDは 1
- アクセスするデータIDは A
つまり、トランザクションID:1がデータID:Aをreadした、ということになる。
r1(A);w1(A);r2(A);w2(A);r1(B);w1(B);r2(B);w2(B);
このスケジュールはトランザクションID:1,2が混在しているので、Serial でないことは明らか。では、Serializable を満たせているのか？
Serial なスケジュールへ変換するために操作を交換していくが、スライドに "No!" と記載した操作は交換できない。
スライドに記載の青文字部分の操作は交換できる。そうすると、Serial なスケジュールに変換することができた。よって、Serializable といえる。
Quiz : Serializable?
Quiz-2 は "r2(y);w1(y);" と "w1(x);w2(x);" がある。
つまり、TX2 -> TX1, TX1 -> TX2 の関係があるため、これは Serializable でないといえる。
Concurrency Control Protocols
Pessimistic : 2PL
Optimistic : Silo
Strict 2 Phase Locking (S2PL)
2PL はシンプルだが、優れた設計といえる。Silo も 2PL の設計を参考にしている。Silo は 2PL の一部を楽観的にしたものといえる。
Kung-Robinson Model
Optimistic は commit コマンドを発行するタイミングで validate する。validate した結果、conflict がなければ良し！と判断する。
conflict は2つのケースで判断する。
- 時間がずれている (Validation Case 1)
- 異なるデータアイテムに対して read / write が行われる (Validation Case 2)
- write x と read y なら問題ない
先の Quiz-2 の例は同じデータアイテムに対して操作を行っているため、conflict と判定される。
An Example
Validation Phase では誰と conflict する可能性があったかを調べる。この例では TX 4-6 と conflict する可能性がある。Validation Phase で conflict に問題がないと判断できてから TX に番号（この例では 7）を与える。
この手法は validation で GiantLock が必要になる。この GiantLock をなくしたのが Silo である。
Silo CC
Speedy transactions in multicore in-memory databases.
commit を発行すると Lock -> Validate -> Write が実行される。
プロダクションレベルの DB 実装としては、中園さんの LineairDB がある。
https://lineairdb.github.io/LineairDB/html/index.html
Silo commit protocol の例
write はローカルな領域に書き込んでいる。DB にはまだ書き込んでいない。
スライドの緑文字は T1、青文字は T2 の操作を示している。
L : Lock
V : Validate
W : Write
B が W1(B') で書き換えられたことを V2{B} の Validate で検知し、T2 を abort している。
このスライドの例で示しているように、commit protocol は複数のトランザクション（緑文字と青文字）がパラレルに実行される可能性がある。それでも正しく処理できることを保証している。
Silo Concurrency Control Protocol
"Lock records(DB). Sorting is for deadlock avoidance." を見ていく。
"sorted(W)" で write set を sort しているのは deadlock avoidance のため。
Deadlock
alice は x, y の順にアクセスし、bob は y, x の順にアクセスしたとする。
wl : write lock
alice の wla(y); は bob の wlb(y); にブロックされる。
bob の wlb(x); は alice の wla(x); にブロックされる。
つまり、2人ともロック待ちで止まってしまう。
Deadlock Detection
Deadlock の検出には Wait graph が用いられるが、この処理は重い。
Deadlock avoidance
そもそも Deadlock が発生しなければよい。
ロックする順序が同じであれば Deadlock にならない。
なので、Silo は write set をソートしている。
Silo Concurrency Control Protocol
"Record-TID and RS-TID are different? abort." を見ていく。
Phase 1 では write lock を獲得した。
Phase 2 では read したものが書き換えられていないか？を調べる。
Silo commit protocol
V2{B} で W1(B') が先行していることを検知し、abort する。
T2 が read したのは T0（初期値）。read すべき値は T1 の write した値だったので、T2 は abort になる。
Silo Concurrency Control Protocol
"Record is locked, abort." を見ていく。
Silo commit protocol
V2{B} の時点で L1(B) が lock を獲得しているので、T2 は abort になる。
なぜこれがダメなのかは 2PL として考える。
T2 は B の read lock を獲得しているつもりだったが、獲得できていなかった。となると、abort するしかないかもしれない（あくまで可能性）。そして、T2 は abort する。
Silo の論文では anti dependency をトラップしていない、という記述が頻出する。それは 2PL の一部を楽観的にしたということを意味している。
Quiz (Can a CC prevent following?)
S2PL も Silo も Non-Serializable Schedule を正しく判定できるか？
⇒いずれも正しく判定できる。
Quiz (Can Silo pass the following?)
スライドに記載された Serializable Schedule を Silo は False negative に判定してしまう。これをスケジュール空間が狭いという。
Why is Silo speedy?
スケジュール空間が狭いということから性能が悪いといえるのか？
1. Shorter blocking time.
典型的なベンチマークとして YCSB や TPC-E が用いられる。これらはショートトランザクションで評価している。ショートトランザクションで評価する場合、スケジュール空間よりもエンジニアリングとしてワークしているかが重要になる。
2PL は操作する前に lock を獲得するが、Silo は validation で lock を獲得している。これにより、Silo は lock する時間が短くて済む。
2. Native latch
latch は write mode しかない lock と考えて良い。
多くで使われる Centralized lock manager はハッシュテーブルで実装される。
これには以下の弱点がある。
- ハッシュ構造全体に対してロックしなければいけないかもしれない。
- 値の書き換えに CAS 操作が多発するため、キャッシュミスの確率が上がる。
この問題を解決するために "Native latch" を使う。レコード毎にラッチを設定し、CAS を使ってデータを切り替える。そうすると、ハッシュ構造のように複雑なデータ構造を使わなくて済む。
Concurrent index
Concurrent index をいかに高速に処理するかがトランザクション研究では極めて重要となっている。
B-link-tree
B-link-tree については「DBSJ最強データベース講義」で石川先生が講義されていた。
B-link-tree は leaf でしかロックを獲得しない。
TX1: insert (27), TX2: search (25) の状況を考える。
- TX1 が左のリーフノードのロックを獲得した。
- TX2 は左のリーフノードのロック待ちする。
- TX1 は 27 を insert した。この時、リーフノードはスプリットする。
- TX2 は左のリーフノードのロックを獲得する。
- TX2 は左のリーフノードから 25 を search するが見つからない。既にスプリットされているため。
- TX2 は右隣のリーフノード（中央のリーフノード）で 25 を search する。
Why deadlock? Two directions.
search は必ず右方向に行く。逆方向（左方向）に行くと deadlock が起きてしまう。
Hard to implement…Why are you there?
Concurrent index を実装するのはとても難しい。
正しく実装できていないとデータ順が "1,2,3" ではなく "1,3,2" のようになってしまう。デバッギングも困難。
PostgreSQL Code
PostgreSQL は実装で read lock を獲得している。これは実装が難しかったからか…？
Silo recovery
Motivation
リカバリのコンセプトは「ログを出力して歴史を繰り返せばよい」。
Performance of Parallel Write
スループットは SSD (#thread:1) より SSD (#thread:8) のほうが高い。
マルチスレッドでランダムライトしたほうが速い。
P-WAL (2/3) Multiple WALfiles
従来のWALファイルは1つだけだった。
今後はWALファイルをN個用意して完全並列に出力する。
P-WAL (3/3) Early Lock Release
Early Lock Release (ELR) は Write log の前にデータを unlock する。単にこれを実装すると Dirty read するかもしれない。なので、Commit を遅らせるという手法を組み合わせる。
Coping with dirty read: notification controlThreads read data in secret to users…
T1 が Commit or Abort を発行した後に T2 が Commit を発行した。この時、T2 は競合するかもしれない T1 の結果が確定するまで、クライアントへの応答を待つ。
ログファイルが複数あるときの実現方法について。ワーカースレッド毎にカウンタ (F_LSN) を持たせる。スライド例では3つのワーカースレッドカウンタの最小値は 5 となっている。つまり、5 までの歴史は繰り返せる（戻せる）とわかる。これをもって、TX-5 までのクライアントには Commit の応答ができる。
Thinking about Locking
カウンタは処理が遅い。
Lock library の実装では遅すぎる。
Atomic Add だとまだましだが、50スレッド程度で性能が急激に落ちる。
Epoch based synchronization
Silo はシングルカウンタ (Epoch) を 40ms 毎に更新する。
Epoch は1スレッドだけが更新を行い、他のスレッドは読むだけ。
Epoch が切り替わるまで not durable な状態が続く。Epoch の更新が 40ms といっても、かなり多くのトランザクションがクライアントへの応答を待たされることになる。
Transaction Processing System = Concurrency Control + Recovery
Concurrency Control も Recovery もオーダー（順序）の概念がある。そして、Concurrency Control と Recovery は分離して動作している。
Place of the Epoch
Serialization point は安全な状態。
Silo は Phase 1 で lock を獲得した後に Epoch を読む。
Epoch は compiler-fence() に囲まれたタイミングで読まなければいけない。"Why not here?" と書かれたタイミングで読むと、Inverse Order が発生しうる。
これは single node なら問題にならない。HTAP で問題となる。
Modern CC and future directions
Really fast? (MOCC)
MOCC の速さ（スループットの高さ）には再現性があった。
Cache-Line-Conflicts
SI がとても遅い（スループットが低い）。SI はスケジュール空間が広いのに遅い理由は Centralized ordering が悪さをしているため。
Modern CC Research
Optimistic だと high contention で性能が出ないのでは？との指摘があり、調べてみた。Cicada は Silo に low contention のスループットで負けるが、high contention だと勝つ。
Future Directions
バッチは重要な分野だが、あまり研究されていない。今後の研究テーマとして面白いのではないか。
