Carpe Diem

備忘録

LSM treeを図解する

LSM tree Bigtable Cassandra アルゴリズム

概要

LSMツリーを理解しやすくするためにアーキテクチャ、Write/Readフロー、コンパクションなどを図解します。

LSMツリーとは

LSMツリー（Log-Structured Merge Tree）は、データベースやストレージで大量の書き込みを高速に処理するための仕組みです。

アーキテクチャ図

全体のアーキテクチャはこのようになっています。

新しいデータはまずメモリにある一時領域（MemTable）に書き込み、同時にログ（WAL）に追記して安全に保存します。 メモリが一杯になると、まとめてディスク上のソート済みファイル（SSTable）に書き出し、古いファイルと統合（コンパクション）して整理します。

特徴

アーキテクチャから分かるように次のような特徴があります。

  • メモリ＋ディスクの階層構造
  • WALによるデータ耐久性
  • 読み込みは複数層を探索
  • 事前ソートされたデータ構造

内部処理・フロー

Writeフロー

書き込み時の流れは次のようになっています。

  • 書き込みはまずメモリ上の MemTable に格納し、満杯になると不変化して（Immutable MemTable）、ディスク上の SSTable にフラッシュ。
  • データがロストしないよう、WALに同時に書き込みデータ耐久性を持たせる。
  • ディスク上の SSTable はレベルごとに分かれ、バックグラウンドで コンパクション（マージとソート）を行い階層を整理する。

Readフロー

読み込み時の流れは次のようになっています。

  • MemTable → Immutable MemTable → L0 → L1 → … の順で検索。
  • Bloom filter やインデックスで無駄な SSTable 読み込みを回避。

コンパクションフロー

コンパクションはこちらのようになっています。

ref: LSM-Tree Compaction Visualization

SSTable はLevel 毎にまとまりを持っており、階層化されています。
先ほどのアーキテクチャ図だと、Level 0では大体10MB保存でき、Level 1だと100MB、Level 2だと1GBという感じに段々と増えていきます。
上限に達するとコンパクションが発生し、次の階層に移されます。

コンパクション時に重複キーや古いデータを削除されるので、無駄なストレージやデータ不整合が起きなくなります。

ソート

ソートされるタイミングは大きく3つあります。
これらの処理によって常にソートされたデータとしてアクセスできます。

  • MemTable
    • MemTable は通常、平衡木や skip list などの「常にソートを維持するデータ構造」で実装されている。
    • そのため、書き込み時にソート順が保たれる。
  • Flush
    • MemTable内のソート済みデータをそのまま SSTable に書き出す。
    • したがって、各 SSTable ファイルは 内部的にキー順でソート済み。
    • 製品によってはMinor Compactionが発生し、そのタイミングでもソート。
  • Compaction
    • 複数の SSTable をマージし直し、新しいソート済みファイルを作り直す。
    • ここで古い値や削除フラグを整理し、ディスク上の SSTable を「より大きな範囲でソート済み」に維持する。

メリット・デメリット

LSMツリーのメリット・デメリットは以下です。
これまでの説明からその特徴が分かったので、なぜこういったメリット・デメリットになるかも分かると思います。

メリット

  • 書き込みが早い
    • 追記型（append-only）でランダム I/O を回避。
    • 書き込みは主にメモリと順次ディスク書き込みなので速い。
  • 順序ありデータをO(logN)で効率的に探索できる
  • 圧縮率とストレージ効率が高い
    • コンパクション時に重複キーや古いデータを削除。
  • クラッシュリカバリが容易
    • WAL があるため、MemTable の内容を再構築可能。

デメリット

  • メモリもファイルも複数スキャンしないといけない
    • なのでBloom filterを組み合わせることが多い
  • ランダムリードはB-Treeの方がパフォーマンスが良い

採用している製品

LSMツリーを採用しているライブラリとしては以下があります。

  • LevelDB (Google製)
    • 軽量な組み込み向けKVストア。多くのプロジェクトの基盤に採用されています。
  • RocksDB (Facebook製、LevelDBベース拡張)
    • 高性能・高機能なKVストア。MySQLエンジンや分散DBで広く使われています。
  • WiredTiger (MongoDBのデフォルトストレージエンジン)
    • 内部でLSMツリーを利用可能（B+Treeとの切り替え対応）。

データベースだと次のような製品で採用されています。どれも書き込みに強いと言われるデータベースですね。

  • Cassandra (Apache)
  • HBase (Apache, Hadoop上)
  • Amazon DynamoDB
  • Google Bigtable

まとめ

LSMツリーを理解しやすくするためにアーキテクチャやフローを図解しました。