VLDB 2017 の論文メモ（編集中）

Mostly-Optimistic Concurrency Control for Highly Contended Dynamic Workloads on a Thousand Cores

MOCC (Mostly-Optimistic Concurrency Control) という方式の CC (Concurrency Control = 並行性制御) についての論文。

MOCC は OCC と PCC のいいとこ取りをしたような CC。通常は OCC のように振る舞うが、conflict 可能性が高いデータへの読み書きは PCC のように read/write ロックを獲得する。 conflict の可能性が高いというのは、これまでのトランザクションでアボート率が高い、またはリトライするトランザクション（最終的にアボートになったもの）で前に読み書きしていたデータのどちらかを指している。

PCC は global order でロックを獲得しないため本質的にデッドロックの可能性がある。 MOCC では conflict の可能性が高いデータに対しては PCC のように読み書きの前に read/write ロックを獲得するが、もし global order に違反した順番でロックを獲得しようとした場合、違反しているロックを解放（＝キャンセル）して、該当のロックを獲得する。これにより global order でロックを獲得するというポリシーが保たれるためデッドロックが発生しない。ただし、違反してキャンセルしなければならないロックが多すぎる場合は、キャンセル処理自体が高コストなためロックの獲得を一か八か試みて獲得成功したら続行、獲得失敗（デッドロックの可能性があるという判断）したらアボートする。獲得したロックを解放するというのは 2PL の原理に違反するため PCC では correctness が保証されない。しかし、MOCC では最終的にコミット可能かどうかを判断は最後の validation フェーズで行うため、途中でロックを解放しても correctness が保証される。

すなわち、MOCC は括りとしては OCC。トランザクションの途中でロックを獲得しているが、2PL と違ってロックの獲得によって correctness を保証しようとしているわけではなく、アボートを防ぐためにロックを獲得するのである。

MOCC を使った結果、read-only トランザクションにおいては OCC と同等の性能（MOCC によるオーバーヘッドがほぼない）。 write ありのトランザクションについては abort 率が改善されることにより、OCC よりも高い性能を示す。

（感想） MOCC は性能面においては最強の CC なように思う。マイナス面としては理論的な理解の難さと実装の複雑さである。

以下、CC ってなんぞやという人のための補足

代表的な CC としては PCC と OCC がある。

PCC は比較的 traditional なデータベースシステムなどで用いられる。 PCC はデータを読み書きする前に read/write ロックの取得を試みて、ロックの競合がある状態ではそれ以上処理を進めない（ロックが獲得できるまで待機 or アボート）。代表的な PCC は 2PL (2-Phase Locking) 。

OCC はひとまずデータを読み書きしてみて（ここでの書き込み先はローカル変数）、最後に conflict があるかどうかをチェックし、conflict があればアボート、なければコミット（グローバルなデータに実際に書き込む）する。 OCC ではトランザクションの最後に write ロックを global order で獲得し、 read ロックは取得はしない。 read ロックを取得しない代わりに validation フェーズで conflict がないかチェックすることで correctness を保証する。

マルチコア、マルチソケットの環境においては、並行性制御は PCC(Pesimistic CC = 悲観的並行性制御）ではなく OCC (Optimistic CC = 楽観的並行性制御) が良いとされる。 PCC は read でもロックを獲得するためキャッシュの invalidation が発生し、read-only transaction で性能がスケールしない。

BlueCache: A Scalable Distributed Flash-based Key-value Store

PaxosStore: High-availability Storage Made Practical in WeChat

State Management in Apache Flink

Samza: Stateful Scalable Stream Processing at LinkedIn

An Empirical Evaluation of In-Memory Multi-Version Concurrency Control

Write-Behind Logging

永続ストレージ上のテーブル領域を更新してから、どこまでコミットしたかという情報をログに書いて永続化するという Write-Behind Logging（WBL）というロギング方式の提案。 Write-Ahead Logging（WAL）では、永続ストレージ上のテーブル領域に書き込む前に、変更内容を記載したログを永続化する。論文で指摘されている WAL の欠点はログの書き込みとテーブル領域へのデータの書き込みが二重で発生する点。 WAL はシーケンシャルライトで一度に書き込めるので HDD の書き込み特性に適しているが NVM ではランダムライトがシーケンシャルライトと同等の性能を持つのでより効率的な方法が考えられる。

論文で前提とする DBMS は steal かつ MVCC である。その前のトランザクションの変更が全て永続ストレージに記録されている最新のコミット済みトランザクションのコミット timestamp (cp) と次のグループコミットの完了前はどのトランザクションにも割り当てられない commit timestamp cd (cp < cd) をログに記録する。 ∀ c < cp の commit timestamp c を持つトランザクションはコミット済みとみなすことができる。一方、∀ c > cp ∧ c < cd の commit timestamp c を持つトランザクションは永続ストレージ上のテーブル領域に追記（Multi-version なので上書きはされない）されているが、コミット扱いとはみなされない。System Failer 後の restart recovery 後にその更新はなかったものとみなされる。

（感想とか疑問点） MVCC で過去のバージョンが参照できるから、直接 durable なテーブル領域にデータを追記して、後からログを書いてコミット確定する方式は PCMLogging[どこか] などいくつか提案されているうちの一つ。ただ、いちばん大事な cp, cd の具体的な算出方法が書いていなくて非常にモヤモヤした。 cd は普通に（コミット直前で）計算されるコミットタイムスタンプのことかなと思ったけど、独特な言い回しがしっくりきていないので外れている気がする…。cp はまともに計算するのが大変だから、Silo というシステムでは epoch を使ってどこまでは少なくともコミットされているか（≒どこまでクライアントに結果を返してよいか）を管理していたりするんだけど、この論文では各ワーカー w の最小コミット済みトランザクションの timestamp を c_w とすると、cp = min(c_w) みたいな感じで計算しているのかなあ？これやるとワーカー数増えた時にしんどくなりそう。「ロングトランザクションのケースだと cp が increment できないから、コミットタイムスタンプをログに記録する」みたいなことが書いてあって、この「コミットタイムスタンプ」って cd とはまた違うんだよね、きっと。自分の知識不足はおいといて、肝となる部分が説明されていない、論文中の具体例がない（あっても説明がなくてよく分からない）、で本当に大丈夫か？という論文でした。