In-Memory DBのアーキテクチャは数多く提案されてきたが、特にパフォーマンスに直結するトランザクション周りでのボトルネック改善は需要の高い研究領域である。
これから紹介するStephen TuらのSOSP'13は大きなメモリと多くのCPUコアを活用してより高い性能を発揮するために考案された新しいトランザクションアルゴリズム：Siloを提案している。
In-Memory DBの問題点
昨日書いたように、In-Memory DBではページ単位でのバッファプールの管理やWALやUndoログが不要となり、トランザクション内でページを書き換えるたびにLog Sequence Numberを生成する必要はなくなった。
コミット時にリカバリに足る分のRedoログが記録できればよいのだが、そのRedo処理を行うためにはログをどの順序で実行すべきかを決定する指標が必要となる。逆に言えば、どの順序でログをRedoするかさえ決定するならログそのものは複数のファイルやハードディスクにトランザクションごとに散り散りに保存されても負荷が増えるだけでリカバリは可能である。そうしてログファイルを複数用意できるのでディスク帯域はボトルネックではなくなった。
Redo時の順序関係を正しく復元できるようにするためには、単純には個々のトランザクションログに単調増加するユニークなトランザクションIDを振っていく事が考えられる。しかしその方法ではIDを発行するための単一の数字に対するインクリメント操作がボトルネックになる。
発行するIDを管理するためにロックでID管理を保護するか、FetchAndAdd命令でWait-Freeに並行制御を行う事になるが、そのどちらもマルチコア、特にはマルチソケット環境では致命的に速度ボトルネックになることが判明した。
Siloの概観
Siloはエポックというグローバルな数値を定期的に増やす専用のスレッドを用意する。
そのスレッドは40msに1度、グローバルな数値(32bit幅)をインクリメントする。
各トランザクションワーカーはそのエポックの数字を読み、そのトランザクションワーカーが実行するトランザクションに割り当てるTIDの上位32bitとして利用する。なお各トランザクションワーカーとエポックスレッドの間のエポック値は多くても1までしか乖離せず、トランザクションワーカ全員が最新のエポック値を読むまではエポックスレッドはエポックの値を増加させない。これは後に説明する永続性において重要である。
グローバルなTIDをみんなでインクリメントして回す場合とエポックを用いた場合のの速度比較を以下に引用する。
これは4ソケットの物理32コアのXeonマシン上のベンチマークだが、GlobalTIDの速度が24コアで頭打ちになっている一方で、MemSiloのエポックはほぼ線形なスケーラビリティを示している。
SiloはTIDでトランザクションのRedo時の順序関係を決定する。逆に言えばTIDの値さえ確定してしまえばログに物理的に書き込まれる順序が逆転してもリカバリ時に並び替えるだけで良い。
ログの物理的な書き込み順序の反転を厭わないので、Early Lock Releaseは「ロガーにエンキューが完了した後」にしかアンロックできなかったものを「ロガーにエンキューが完了する前」にアンロックできるようになり更に並列性が向上した。
SiloのトランザクションID発行プロトコル
Siloが扱うデータはすべて「その値を最後に更新したTID」をそれぞれ持っている。
Siloがコミットを行う際は、エポックとそのトランザクションが関わったすべてのデータ(Read/Write-Set)のTIDを集めて以下のID候補の中から最大のものでそのトランザクションのTIDを決定する。
- 今確認したエポックを32bit左にビットシフトしたもの
- Read/Write-SetのTIDすべてのうち最大のものに1足した物
- そのワーカースレッドが過去に発行したことのある最大のTIDに1足した物
早い話が、そのトランザクションが関わったデータとそのトランザクションワーカ内での順序を破壊しないように局所的な順序関係を定義している。
例えば
- エポックが
0xDEADBEEF - Read/Write-SetのTID群のうち最大の物が
0xCAFEBABE0000001 - そのワーカスレッドの過去最大のTIDが
0xDEADBEEF000003
だったら、最大のものは0xDEADBEEF000003なのでそこに1を足した0xDEADBEEF000004を、そのWrite-Setに新しい値と一緒に書き込んでアンロックする。
これによってログ同士の半順序関係が定義される。この半順序関係は同一のキーに対する操作に対しては全順序関係だが、同一のトランザクションで操作されなかったり同一のワーカスレッドによって操作されなかった2つのキーに対するTIDはたまたま完全一致する事はある。が、それはリカバリに対して何の問題もない。
(厳密にはTIDの下3bitは予約されているが、これは別用途のためなので詳細は論文で）
Siloのコミットプロトコル
Siloは基本的にOptimistic Concurrency Controlでトランザクションを実行する（厳密にはBackword-Oriented OCC）。
つまり、トランザクションとしての実行途中はReadはバージョン番号(TID)をセットで読み出し、Writeは直接は反映せず手元のWrite-Setに保存する。
コミットする際には以下のステップで実行する。
- Write-Setに含まれるデータをすべてLock
- エポックのスレッドから現在のエポックの値を読み出す
- Readした値のTIDが変動していないか確認する
- 新しいTIDを算出する
- Lockした値に新しいTIDとWrite-Set内の新データを書き戻しながらUnlock
- Write-SetとTIDのペアをログに書き出す
Unlockのタイミングが早いところがポイントである。
Siloのリカバリ
前述のようにSiloが生成するログは半順序関係はあるが全順序の関係はない。これはトランザクションAがコミットステップ5でUnlockしたRedoログを6で永続化する直前に、トランザクションBがUnlockされた値を読んで新たなトランザクションを実行しディスクに永続化してサーバの電源が落ちたとする。
するとトランザクションBはトランザクションAの実行結果に基づいて実行されたにも関わらず、トランザクションAの結果はディスク上のどこにも痕跡が残っていない。これではDurabilityに違反している。
さて、上位32bitに保存されるエポックの値は単調増加しているので、エポックを跨るログの間には全順序関係がある。
なので、リカバリをする際にはDurabilityを守る為に「同一エポック内のすべてのログが揃っている場合に限りそのエポックをRedoする」というプロトコルを取る。
また、当然Redo可能となったログしか永続化されたと見做されないので「同一エポック内のすべてのログが揃うまでユーザに完了を報告しない」というプロトコルを取ることでユーザとのインタフェースでの一貫性を守っている。
ベンチマーク
以下にTPC-Cのベンチマーク結果を引用する。
ロギングを行わないMemSiloと比べてログを行うSiloはややパフォーマンスが落ちているが、物理32コアのマシンで70万トランザクション/秒が出ているのは驚異的な速度である。
TPC-Cの世界トップがSPARCのモンスターマシンでカリカリにチューニングして30,249,688トランザクション/分なので、50万トランザクション/秒程度であり、そこらのちょっと豪華めなXeonサーバで20万トランザクション/秒の差をつけるのは大したものである。（なおちゃんとしたTPC-Cのスコアのためにはクライアントからネットワーク経由でクエリを叩き込んでそれをParseして云々という仕組みまで作りこむ必要があるが、Siloのベンチマークではそれをやっていないので正式なスコアではない）
misc
論文中にはまだこの他にもSnapshot Isolationを実現して大幅高速化を実現するSnapshot Epochなどのアイデアが含まれているが今日はもう長くなってしまったのでこのへんで。