Log-Structured Merge Tree (LSMT)
概要
LSM ツリー (log-structured merge tree) またはログ構造マージツリーはデータベースのようなストレージエンジンにおいて検索性能を維持しながら高い書き込み性能を達成することを主な目的として使用されるデータ構造の一種である。従来の B-Tree や B+Tree とは異なり、データの書き込みがディスクへのシーケンシャルな書き込みとなるように最適化されていることで、ランダムな書き込みの発生する構造より書き込み性能を向上させている。
Table of Contents
シーケンシャル書き込み
ハードディスクドライブ (HDD) のような機械的構造を伴うデバイスでは、データを書き込むときにシーク (磁気ヘッドを書き込み先のトラックやセクターに移動するための位置合わせ) や回転待ち時間 (ディスクが回転して目的のセクターがヘッド下に来るまでの待機時間) が必要となる。ランダムな書き込み処理ではこのような物理的な移動と待機が繰り返されて大きな遅延が発生する。一方で、シーケンシャルな書き込みであればヘッドをほとんど移動せずデータを連続して書き込めるため物理的なオーバーヘッドが最小化される。
ソリッドステートドライブ (SSD) では機械的なヘッドの移動を伴わないため HDD と比較すればシーケンシャル書き込みの優位性は少ない。しかし、シーケンシャル書き込みのように大きく連続する範囲へ書き込むケースでは、ブロック内のページを効率的に埋めることができることから、FTL (flush translation layer; 論理アドレス空間と実際のフラッシュメモリ上の物理アドレスを結びつける抽象化層) の内部マッピングが単純化されやすく、ウェアレベリング
やガーベッジコレクションといったハウスキーピングが効率され [3]、結果的に SSD でのシーケンシャル書き込みも性能面で有利になることがある。このため、HDD ほど明確な速度差はないものの、SSD でも制御ロジックの簡略化やバッチ処理的な効率化が依然として機能することから一定の速度向上を期待できる。
アルゴリズム
LSM ツリーはまず \(C_0\) と呼ばれるメモリ上の可変長構造コンポーネントにデータを蓄積し、\(C_0\) が一定のしきい値に達すると不変コンポーネントとしてストレージデバイスへシーケンシャルに書き出してゆく。\(C_0\) に蓄積されたデータは連続したログ書き込みに近い形となっていることから、ランダムアクセスを伴う書き込みが多発する従来の B+Tree などの木構造と比較してディスクへの書き込みを効率的に行うことができる。LSTM ツリーはディスク上の不変構造へバッチ化された書き込みデータを段階的に反映することで単位時間当たりの書き込み性能を高めている。
ディスク上に複数世代の不変コンポーネントが併存することになり、このままでは検索や範囲クエリーの探索は冗長になる。このため、定期的に複数の不変コンポーネントをマージし、不要なデータの整理やインデックスの再構築を行うコンパクションを行うことで、ディスクの断片化を抑えながら読み取り効率を維持または向上させることができる。
検索操作
挿入操作
削除操作
参照
- Dzejla Medjedovic, Emin Tahirovic, Ines Dedovic. 大規模データセットのためのアルゴリズムとデータ構造. マイナビ出版 (2024)
- Alex Petrov. 詳説データベース ―ストレージエンジンと分散データシステムの仕組み. O'REILLY Japan (2021)
- Jack Vanlightly. Is sequential IO dead in the era of the NVMe drive? (2023)