Silo
トランザクションアルゴリズム
Serializable
serialに実行したときと同じ結果が得られること = 正しい
Finite State Equivalent
- エルブランセマンティクス(Herbrand Semantics)が全て同じ = FSR
- 終わりだけ一致していたらなんでも良くなってしまう
- 総当りで一致を確認するため実用的でない
- Serializablitiyとは？ １. Final State Serializabilityについて - Qiita
View Equivalency
- Txの全てのステップでHSが一致すればよい
- 判定は NP Complete
- FSRより強いが実用性足りない
Conflict Equivalence
- CSR
Serializablitiyとは？ 3. Conflict Serializabilityについて - Qiita - 非常に高速に判定できる
Two Phase Lock
- CSRを動的に生成できる
- Strict - = S2PL もあるらしい
- Dead Lock が起きる
- 策: Wait-Die or Wound-Wait or No-Wait (即abort)
Optimistic Concurrenct Control
- commitまでlockを獲得せずに実行する平行制御方式
todo - WebアクセスとかはReadがかなり多い, CPU coreにscaleする
- ので最近提案のアルゴリズムはこれベースが多い
ログ
HDDは毎秒120箇所を書き換えれないのに1つのトランザクションが120箇所を更新する内容をすべてそのままディスク上のデータに反映させていたら毎秒1トランザクションしか走らない。それではパフォーマンスが致命的に落ちるので、データベースは可能な限りHDDのヘッドシークを減らす方向に進化してきた。それがログである。
ログの形にまとめる事で1秒あたりにコミットできるトランザクションの数はトランザクションの大きさにおよそ関わらず秒間100トランザクション程が見えてくる。
知らなかった.
ディスクの遅延とトランザクション
HDDの遅延10ms, CPUから見ると 30M clock (1s ~ 347days)
lockを10msも保持するのは正気の沙汰じゃないので短くしたい
- Postgresは 8KB/page
- ログにはundo情報, redo情報があり, 冪等になるように書かれている
- 昔のPostgresでは LRU を使っていたが, Clock-Sweep に変えた todo
In-Memory DB
- Redoログだけで十分
HekatonのBw-TreeやMass-Treeといったマルチコア環境向けに特化した高速B+ツリーの亜種を紹介し、更にはボトルネックがCPUに移るため従来のいわゆるボルケーノスタイルの操作抽象化がボトルネックになるのでJITコンパイルすることの必要性を論じている。
他にはカーネギーメロン大学の2016年のDatabase Systemsの講義資料も素晴らしい。最近のインメモリDBによく出てくる論文をまとめて英語の講義映像も含めて載っている。学生の演習課題がBw-Treeの実装だったりPelotonへの独自改造だったりと非常に激しい。
最近はIn-Memory DBの研究が多い
Silo
これから紹介するStephen TuらのSOSP’13は大きなメモリと多くのCPUコアを活用してより高い性能を発揮するために考案された新しいトランザクションアルゴリズム：Siloを提案している。
- ログは分散して用意できるのでディスクはボトルネックではない
- ログの順序関係を管理する
- incrementがボトルネックに
Siloはエポックというグローバルな数値を定期的に増やす専用のスレッドを用意する。
そのスレッドは40msに1度、グローバルな数値(32bit幅)をインクリメントする。
各トランザクションワーカーはそのエポックの数字を読み、そのトランザクションワーカーが実行するトランザクションに割り当てるTIDの上位32bitとして利用する。なお各トランザクションワーカーとエポックスレッドの間のエポック値は多くても1までしか乖離せず、トランザクションワーカ全員が最新のエポック値を読むまではエポックスレッドはエポックの値を増加させない。これは後に説明する永続性において重要である。
- 700k tx/s/32CPU core
Spanner
- Googleの分散データベース
- KVSだがSQL-like
- OSS実装がCockroachDB
複数のデータセンターに跨ってデータベースの内容を複製し続ける事で高い可用性を実現するという構想は数多くあった。
しかしそれらの分散データベースは実用的な速度を実現しようとすると、データモデルがただのRDBより単純化して使いにくかったりトランザクションをサポートしなかったりと、アプリケーションの一貫性を実現するのが難しい。
現にGoogleの社内でもBigtableなどを用いたアプリケーションは複数あるものの、それぞれでそのデータモデルの上で無理やりトランザクションを再実装するためにあれこれ頑張った事例が多くそこでエンバグする事態が多発していたとSpannerの論文には書いてある。
そこで、一貫性とデータセンター間複製と性能とを鼎立する為に新たに設計されたのがSpannerである。
- 時間のズレを無くすためにTrueTimeAPIを使う
- 時間がずれ過ぎたら故障
- NTPで良いらしい