SE-Radio417_note.md

Software Engineering Radio Episode #417

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(子ノードの数)とローカリティを改善
• Q. インデックスについて
  • A. いくつかの実装方法がある
    1. インデックスがプライマリキーを持つ実装。インデックスのBツリーを検索してプライマリキーを見つけた後、Index-organized table(プライマリキーでソートされたBツリー)を検索して値を得る必要がある。2回検索が必要だがデータに重複がない。
    2. インデックスがデータの格納されているストレージへのポインタを持つ実装。Index-organized tableを検索する必要はないが、インデックスの更新時に処理が必要になる。
    3. インデックスにデータをまるごと重複して持たせる実装。
  • RUM Conjecture
    • Read, Update, Memory amplificationにはトレードオフがあるというconjecture。どれか２つを最適化しようとすると残りが犠牲になる。例えばBツリーはRead-optimized。書き込みにはデータの検索のあと、ディスクのページの更新が複数回必要になるかもしれない(Bツリーのスプリットが起こる場合)。また、将来の更新や削除のために余分にスペースを確保する。
• 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. データベースの将来