Alex Petrov on Database Storage Engines
Database Internals: A Deep Dive into How Distributed Data Systems Workの著者がゲスト。書籍の内容をもとに、データベースの内部についてトーク。
- Q. ストレージエンジンとは？
- A. データの保存を助けるもの
- Q. ストレージエンジンは交換可能（プラガブル）？
- A. そうだとよいと思っている。実例としてはMongoDBで使われているWiredTiger、Cassandraで使われているRocksDBなど。
- Q. In-memoryデータベースとの比較
- A. ページのマネジメントをOSではなく、DBでやらないといけないのが大変(メモリを一定サイズ(4kBなど)の領域に区切ったものをページといい、OSがページの確保や割り当てなどを行ってくれる。In-memoryでないDBでは、ディスクに対する同等の処理をDBソフトウェアで行う必要がある）。
- Q. 直接ファイルシステムを使うのではなく、なぜDBを使うのか？
- A. 1. ストレージの効率。ストレージのオーバーヘッドを最適化できる 2. アクセス効率、3. 更新効率
- Q. Bツリーについて
- A. まず二分探索木について
- 2つの子ノードを持つ。ノードはキーの値と子へのポインタを持つ。左の子の値は親より小さく、右の子は親の値より大きい。
- 二分探索木で実装しようとすると木の再構成時のコストが高い
- ローカリティも問題。同時に検索する対象が同じページにあるとは限らない。
- BツリーではFanout(子ノードの数)とローカリティを改善
- A. まず二分探索木について
- Q. インデックスについて
- A. いくつかの実装方法がある
- インデックスがプライマリキーを持つ実装。インデックスのBツリーを検索してプライマリキーを見つけた後、Index-organized table(プライマリキーでソートされたBツリー)を検索して値を得る必要がある。2回検索が必要だがデータに重複がない。
- インデックスがデータの格納されているストレージへのポインタを持つ実装。Index-organized tableを検索する必要はないが、インデックスの更新時に処理が必要になる。
- インデックスにデータをまるごと重複して持たせる実装。
- RUM Conjecture
- Read, Update, Memory amplificationにはトレードオフがあるというconjecture。どれか２つを最適化しようとすると残りが犠牲になる。例えばBツリーはRead-optimized。書き込みにはデータの検索のあと、ディスクのページの更新が複数回必要になるかもしれない(Bツリーのスプリットが起こる場合)。また、将来の更新や削除のために余分にスペースを確保する。
- A. いくつかの実装方法がある
- Q. LSMツリーについて
- Bツリーはread-optimized。Bツリーをimmutableにし、更新時は別のBツリーを構築してまるごと置き換える実装が考えられる。Copy-on-write Bツリーという。LMDBで使われている。
- Copy-on-write Bツリー + バッファリング
- 2-Component LSMツリー: メモリにデータをBツリーとしてバッファリングし、しきい値を超えたらディスクにフラッシュする。その際にディスクの対応するデータとマージする（マージソートの要領）。
- Multi-Component LSMツリー: フラッシュされた複数のテーブルに対しマージ(コンパクション)を行う。
- 一般的には書き込み効率が良いと言われている。
- Q. HDDとSSD
- Q. データベースの将来