Concurrency Control Protocolをゼロから設計する
皆さん，初めまして．NTT SICの中園 (nikezono) です．
プロトコルの考案という作業は，既に提案されているものを追実装するのとはかなり趣が異なります．具体的には，数理的な証明にかける作業の割合がかなり大きくなります．この作業を怠って，雰囲気で実装をしたり改変をしたりすると，ほぼ間違いなく処理の正しさが担保されません．
しかし，得られるリターンは大きく，特定のワークロードを狙ったデータベースであれば，それに特化した性能を出すプロトコルを作ることが容易くできるようになります．特に，インメモリDBや地理分散DBにおいてはCCがボトルネックになってきていることから，アカデミアでもホットな研究領域となっています．
CC以外のインメモリDBの最適化については，明日のエントリにて執筆予定です．
Preliminaries
$ S: スケジュール．データベースに対して要求されたすべての命令の（半順序）集合．
$ CP(S): Commit Projection．$ Sからコミットしたトランザクションのみを取り出す．
$ c_j, a_j: それぞれトランザクション j のコミット/アボート．
$ x: data item x．
$ t_j: トランザクション j ．
$ w_j(x_j): トランザクション j が， data item xについてwriteをした．このとき生まれるversionを $ x_jと表記する．
$ r_j(x_k): トランザクション j が， data item xについてreadし， $ t_kによって書かれた $ x_kを読んだ．
1. Concurrency Control Protocolとは
データベース内部のワーカーの挙動を決定するアルゴリズムであり，トランザクションを並行実行した際の一貫性を保証するための部品です．ここでいう
「並行実行」は，CPUのプリエンプションであったり，マルチスレッドプログラミングの結果として，データベースが論理的に同時に複数のワーカーから操作されていることを指します．
「一貫性」は，いろいろな性質や条件を含んだ概念で，あいまいな言葉です．
CCの手法において主に使われる「一貫性」は以下です．
一応，このScrapboxに解説記事がありますので，よかったらどうぞ．
本記事では，Recoverability と Serializability に限定して議論をします．
2. "プロトコル"の定義
Concurrency Control Protocolは，一貫性（すなわち上記の３つの条件）を満たすように設計しなければなりません．
ここで，「プロトコル」の定義を考えてみます．
https://gyazo.com/95a485cd92881083fec5a5b4fec306c5
上図に示すように，Concurrency Control Protocolというものを，以下の手順で構成される関数だと考えます:
1. スケジュールからactive (not committed/aborted) なトランザクション $ t_jをひとつ取り出す
2. $ t_j をCommitしても一貫性が満たされる(correct) かどうか，バリデーションを行う
3. Correctであれば， $ t_jをコミット ($ c_j をスケジュールに追加)する．そうでなければ，abortする
4. 1に戻る．
Correctnessの定義とプロトコルの命題
ここで，ユーザに提供する一貫性 (Correctness) を Serializability (SR) と Recoverability (RC) からなる，とすると，
$ Correct(CP(S')) \Leftrightarrow SR(CP(S')) \land RC(CP(S'))
です．すべてを満たさないとCorrectnessは保証されません．
これで，雑にプロトコルを作っても，正しさの証明ができます．命題を２つに分割して，
code:Correct
S を，Correct(CP(S)) == true となるスケジュールとおく． # incorrectな入力からは，correctな結果は通常得られません
1. Sを入力とするプロトコル A の出力するスケジュール S' は，常に SR(CP(S')) == trueである．
2. Sを入力とするプロトコル A の出力するスケジュール S' は，常に RC(CP(S')) == trueである．
というふうに，欲しい一貫性の性質すべてについて，出力されたスケジュールが満たされているかどうかチェックすれば，Correctなプロトコルかどうかが判定できます．
3. プロトコルの自作と証明を試してみる：限りなく保守的なプロトコル
前置きがとても長くなりましたが，ここからプロトコルを作ってみましょう．
とりあえず，証明が通るところから始めたいので，最も単純なプロトコル DBLock を考えます．
DBLockでは，以下の仕様に従ってワーカーは動作するものとします:
code: DBLock
1. トランザクション開始時に，データベース全体の粗粒度ロックを取る．
2. 常に最も新しいcommitted versionsをread/writeする．
3. トランザクション終了時 (Commit後) に，ロックを解放する．
このプロトコルのSerializabilityの証明は簡単です．が，これからやっていくプロトコルの作り方すべてのベースラインです．
code: theorem
定理:
S を，Correct(CP(S)) == true となるスケジュールとおく.
S を入力として DBLock の出力するスケジュール S' は，常にCorrectである．
証明(sketch)
$ t_jを $ t_j \in CP(S') かつ $ t_j \notin CP(S)である(つまり，今回コミットした）トランザクションとする．
S' がCorrectではないと仮定する．すなわち， RC(CP(S')) か SR(CP(S')) がfalseである．
(Recoverability)
すなわち，$ t_jの読んだversion を書いたトランザクションのいずれかがまだコミットしていない．
しかし，DBLockのルール 3 より， これは成り立たない．
(Serializability)
この性質に違反していると仮定する．
S には循環がなく， S' に循環があることから，循環パスは $ t_jを必ず含む．
すなわち $ t_j \to ...となるような $ t_jからの outgoing edge が存在する．
https://gyazo.com/3b84b446a321f1997090dd8a10a8c844
$ t_j \to t_k となる $ t_kは，MVSGに存在することから，コミット済みである．
また，outgoing edgeであることから， $ t_kは$ t_jの読み書きしたversionsよりも大きいversionを読み書きしている．それぞれ，write/readの組み合わせで，上図に示すように3種類のエッジがありうる．
しかし，DBLockのルール1, 2, 3より，$ t_jがコミットする時点で$ t_jはすべて最新のversionを読み書きしており，他のトランザクションの並行実行は許されていない．よってこれは成り立たない
よって，RecoverabilityもSerializabilityのどちらも，違反すると仮定すると前提と矛盾するため，違反は起こり得ない．□
-------------------------------------------------------------------------------------------------
このように，CCプロトコルの正しさの証明にはほぼ必ず背理法が用いられます．
「このプロトコルは正しいか」という観点で見るとかなりクドいのですが，「プロトコルを作るぞ」という状況では，「最低限，何が起こり得ないようにすればよいのか」という考え方ができるので，なかなか役立ちます．
4. ゼロから設計する: 何もしないプロトコルからはじめる
DBLockは一貫性を満たしますが，明らかにオーバーキルだと思われます．少なくとも証明の方針はわかりましたが・・・．
そこで，性能を最大限出したいので，まずは「何もしないプロトコル」NoCC を考えてみましょう．
code: NoCC
1. トランザクションは，任意のversionを読み書きできる．
これは，当然ながら証明が通りません．
コミットしていないversionを読んでコミットしてしまう(RC違反)
グラフに循環が生じている状態でコミットしてしまう(SR違反)
どちらもありえます．
4.1 Read Committed
そこで，まずRCのほうの制約を満たすようにしましょう．
RCだけを満たすプロトコルを作ると，一般的に Read Committedと呼ばれているものと合致します（Read Committedにも形式的な定義がされており，以下とは厳密には異なりますが，ここでは扱いません）．
code: ReadCommitted
1. トランザクションは，コミット済みのいずれかのversionをreadする．
(読んだversionがuncommittedなら，committedになるまで待つ．)
2. トランザクションは，任意のversionとしてwriteできる．
先に結論を言うと，このプロトコルによって，RCの性質は満たされますが，SRは満たされません．
一応見てみましょう．だいたい DBLock のときと一緒です．
証明(sketch) (命題と，証明の前提となる仮定は DBLock の証明と同じ)
(Recoverability)
この性質に違反していると仮定する．
すなわち，$ t_jの読んだversion を書いたトランザクションのいずれかがまだコミットしていない．
しかし，ReadCommittedのルール 1 より， これは成り立たない．
一旦，ここまででRCは満たすことがわかりました．RCを満たすように作ったプロトコルなので，当たり前ですね．
では，SRの性質をどこまで満たせるか見てみましょう．
(Serializability)
この性質に違反していると仮定する．
このとき必ず，依存関係グラフが循環しており，循環パスは $ t_jを必ず含み，$ t_j \to t_kとなるような $ t_jからの outgoing edge が存在する．
$ t_j \to t_k のエッジは三種類ある($ \stackrel{w-r}{\to},\stackrel{\ll(ww)}{\to},\stackrel{\ll(rw)}{\to})．それぞれの場合を考えると:
1. $ t_j \stackrel{w-r}{\to} t_k: 🆗
このエッジは， $ t_jの書いたversionが $ t_kによって読まれているときに生まれる．
Read Committedのルール1より， $ t_kが$ t_jより先にコミットしている以上，これは起こり得ない．
2. $ t_j \stackrel{\ll(ww)}{\to} t_k:🆖
このエッジは， $ t_jの書いたversionが $ t_kの書いたものよりも小さいときに生まれる．
Read Committedのルール2より，committed versionより小さいversionを $ t_jは生成できる．
よって循環は発生しうる．
3. $ t_j \stackrel{\ll(rw)}{\to} t_k:🆖
（すでに証明失敗しているので省略）
-------------------------------------------------------------------------------------------------
https://gyazo.com/11e936c8334df58dfde16b18d1547f6a
Read Committedで起こりうる循環パス．
このように，Read Committedにするだけで，RCだけでなく SRの証明の1/3のパートがパスできます．
ここまでは既存のプロトコルのほぼ全てが同じ道を辿っています．
あとの２つをどう満たすか，というのがオリジナリティの出しどころです．
4.2 Write Exclusive
次に，Read Committedに場合分けの$ t_j \stackrel{\ll(ww)}{\to} t_kのパターンを潰しにいく条件を追加しましょう．
code: Write Exclusive
1. トランザクションは，コミット済みのversionをreadする．
(読んだversionがuncommittedなら，committedになるまで待つ．)
2. **トランザクションは，Write時に最新のversionのLockを取る．このLockは，Commit時まで解放しない．**
新しく追加されたルール2は「自分が書いたversionが，Commit時に必ず最新である」 ことを保証するものです．
これによって証明がまたワンステップ進みます．
証明(sketch) (前半はRead Committedと同じなので省略)
...
(Serializability)
1. $ t_j \stackrel{w-r}{\to} t_k: 🆗
前述のようにRead Committedのルール1より起こり得ない．
2. $ t_j \stackrel{\ll(ww)}{\to} t_k:🆗
このエッジは， $ t_jの書いたversionが $ t_kの書いたものよりも小さいときに生まれる．
Write Exclusiveのルール2より，$ t_kは$ t_jより先にcommitしているため，これは起こり得ない．
3. $ t_j \stackrel{\ll(rw)}{\to} t_k:🆖
このエッジは， $ t_jのreadしたversionが $ t_kの書いたよりも小さいときに生まれる．
これは起こりうる．
-------------------------------------------------------------------------------------------------
https://i.gyazo.com/ae1c0e6b089b7c472d07aae4a5c69e4e.png
Read Committed + Write Exclusive で起こりうる循環パス．
以上のように， Read Committed + Write Exclusive というプロトコルによって，SRの証明の2/3をパスすることができるようになりました．あと一息でRCとSRを満たし，Correctなプロトコルを作ることができます．
余談
SIはSerializabilityを満たさない，という話を聞いたことがある方も多いかもしれませんが，この残りの1/3の証明をパスできないのがその所以です．
4.3 Anti Dependency Validation (という魔境)
実は，既存のほとんどのプロトコルは，ここまでに説明したRead Committed + Write Exclusive までのやり方を使っています．
産業的に使われているDBMSの手法はもちろんのこと，研究レベルでもそうです．
近年のトップ国際会議では両手の指では収まらない数のCCプロトコルが提案されてきましたが，やはりそのほとんどがRead Committed + Write Exlusiveを前提としています．
つまり，ここまでのプロトコルの組み方はわりと異論が出ないもので，残る$ t_j \stackrel{\ll(rw)}{\to} t_k のエッジからはじまる循環パスを潰すためだけに，多くのプロトコルが提案されている，ということです．
このエッジは通称 Anti dependency と呼ばれています．
なぜこのエッジがこれほど議論されているのか
なぜこのエッジを潰すのが難しいのか，というと， このエッジは，$ t_jがreadしたときに生まれることと，DBMSはread-intensive な処理を行うものという暗黙の仮定があるからです．
例えば，100%このエッジが出ないようにするのは簡単です．例えば，Read Exclusiveというプロトコルを考えましょう．
code: Read Exclusive
1. トランザクションは，コミット済みの **最新の** versionをreadする．
(読んだversionがuncommittedなら，committedになるまで待つ．)
このとき， **最新のversionのLockを取り，Commit時まで解放しない**．
2. トランザクションは，Write時に最新のversionのLockを取る．このLockは，Commit時まで解放しない．
証明は省きますが，これによってSRは満たせます．具体的には， $ t_jのコミット時に，$ t_jからのoutgoing edgeは一切ない，というプロトコルになります．
ただし，このプロトコルは明らかに性能上厳しいものがあります．特にインメモリDBにおいては， Readするだけでロックを獲得する，というのは避けるべき重い条件です．というか，ほぼ最初に作った DBLockに逆戻りです．
既存手法のAnti Dependecy
参考までに，私の知る手法をいくつか羅列すると:
2PL (Two Phase Locking)
上記のRead Exclusive に，Read時は共有ロック(shared lock)を獲得する，という条件を追加したものです．
これによってreadは同時に実行できますが，writeすることは許されないので，$ t_jのcommit時には$ t_j \stackrel{\ll(rw)}{\to} t_kのエッジは存在しないことが保証できます．
OCC (Optimistic Concurrency Control)
上記のRead Exclusiveと等価な処理になるように，$ t_jのcommit時にvalidationをかけるものです．
なんらかの方法で $ t_jがreadしたversionすべてについてより新しいversionが存在しないことを検証します．
これによって，2PLと同様に$ t_jのcommit時には$ t_j \stackrel{\ll(rw)}{\to} t_kのエッジは存在しないことが保証できます．
SSI (Serializable Snapshot Isolation)
Snapshot Isolationに，$ t_j \stackrel{\ll(rw)}{\to} t_k のエッジのtracking機構をつけたものです．
このエッジが存在するとき，更にグラフ構造のチェックを行い，循環する可能性を検出した場合にabortします．
2PL/OCCと異なり，エッジが存在しないことを保証するのではなく，循環しないことを保証するvalidationです．
よってより細やかなプロトコルといえますが，tracking機構を作るためにread時に少し重い処理が乗るのが難点です．
5. まとめ
以上がプロトコルを設計するうえでの一般的な流れになります．
要約すると，
1. Read Committedにする
2. Write Exclusive かそれと等価なしくみを導入する
3. Anti dependencyからはじまる循環パスが起こり得ないことを保証する仕組みを実装する
が主な流れになります．MVSRの魅力に取り憑かれると2. のWrite Exclusiveの前提から疑っていくことになりますが，それはかなり上級編で，一般的には3. のAnti Dependency への取り組み方がオリジナリティを出す部分です． しかし，オリジナリティとはいっても，大別すると以下になるでしょう：
$ t_jのCommit時点でエッジがないことを保証する(e.g., 2PL/OCC)
エッジはあってもよいが，それが$ t_j まで到達しないようにValidationをする (e.g.,SSI)
どれが最適解なのかは，実際に動かすアプリケーションによって変わるでしょう．ロジック的に等価でも，どれだけ効率的な実装を組めるか，というエンジニアリングの部分も重要です．
また，そもそも一貫性をどこまで保証するか，という観点も重要です:
例えば，ロングトランザクションが多いのなら，2PLでロックを取ったほうが望む性能特性が得られるかも
そもそもwriteが少ないのなら，Read Committed + Write Exclusive とか SI くらいの強さで良いかも
同じデータを同時に読み書きすることは少なく，ほとんど循環しないことが事前にわかっているのなら，Read Committedでも問題ないかも
というふうに，そもそもSRの証明をどこまでパスできるプロトコルにするか，ということを自由に設計することで，アプリケーションの最適解を見出すことができます．型にとらわれず，自由なCCプロトコル自作ライフを送りましょう！！
実例と宣伝: LineairDB
NTT SICでは，トランザクショナルKVS である LineairDBをOSSとして公開しています． 他のデータベースでいわゆるストレージエンジンと呼ばれている InnoDB, TiKV, LevelDB などに近い思想で実装しており，
他のより大きいデータベースの一部として動作すること
モバイル開発や組み込みなどでの利用
を想定しています．他のデータベースと大きく異なるのは， 自作CCをすることで "Writeに強い" という特性をもたせていることです．以下は，YCSB-A と呼ばれるベンチマークの結果です． https://gyazo.com/76e21b22bd20c942446de1a20125fd4a
先行研究である Silo (OCCベースの手法です) に対して， "SiloNWR" がLineairDBの搭載しているCC手法です．このベンチマークでは，X軸(クライアント数) が伸びていくにつれ，Y軸(スループット) がどう変化しているかを見ています． Siloでは，低下していきます．先程述べた Write Exclusive のルール 2 と同じく， 常に最新のversionを書き込むという仕様を持っているため，Writeの多いワークロードでは最終的にはロックの取り合いになってしまいます．
LineairDBの自作CCでは，この「最新versionのロックの取り合い」を避けるため，ワーカーは積極的に「最新ではない，古いVersionを書き込む」ことにトライしています．このため，Writeの並列性が上がり，スケーラビリティを得ています．
細かい技術的詳細については arXiv をご参照ください．この記事で紹介した説明の仕方でいうと， Write Exclusive のルール2 が満たされないため，$ t_j \stackrel{\ll(ww)}{\to} t_kのエッジが$ t_jのコミット時に存在しえます．
となると，ここからはじまる循環パスがないことを保証しなければSRの証明が通りません．
提案手法では，validationによってこの循環パスがないことを保証しています．
一見簡単に思えますが，最新以外のversionでも，どこでも好きなだけ書ける，というスケジュールのSR証明は NP-Completeであることが証明されていますので，ナイーブに実装することはできない......というのがポイントです． LineairDBはまだversion 1.0 未満のソフトウェアで，コミッタも私一人 (2020/12/17時点) ですが，パッチ投稿やテスト，ベンチマーク，実験など，どのような形でも関わっていただけるcontributorを常に募集しています．ぜひお気軽にどうぞ！
以上です．
明日は，LineairDBを実装するうえで用いた「最近の論文で提案されている {Logging, Checkpointing, Indexing}」 の３つについて解説します．