LSMツリーとは？ログ構造マージツリーを解説

LSMツリーとは？

ログ構造マージツリー（LSM）は、受信した書き込みをメモリ内でバッファリングし、ソート済みの不変なバッチとしてディスクにマージするデータ構造です。データをその場で変更することは決してありません。代わりに変更を蓄積し、整理を後回しにすることで、読み取り側の単純さと引き換えに書き込みスループットを高めます。

LSMツリーは、Patrick O’Neil、Edward Cheng、Dieter Gawlick、Elizabeth O’Neilが1996年に発表した論文「The log-structured merge-tree (LSM-tree)」で体系化されました。その後約10年間、比較的知られていない学術的なデータ構造でしたが、GoogleのBigtableがこの概念をストレージレイヤーに採用しました。Bigtableの設計からLevelDBが生まれ、LevelDBからRocksDBが生まれ、現在では大量取り込み向けに構築されたシステムの大半で、何らかのLSMツリーが基盤として使われています。  

この名前は単一のツリーを連想させますが、これは大きな誤解を招きます。 

LSMツリーは、次の3つのコンポーネントが連携する仕組みとして理解するのが適切です。

• メモリテーブル：直近の書き込みを保持するインメモリバッファ
• 先行書き込みログ（WAL）：書き込みの永続性を保証する、ディスク上の追記専用ファイル
• 増え続けるソート済み文字列テーブルファイル（SST）：それ以前のすべてのデータを保持する、ソート済みの不変ファイル

LSMの挙動に関する興味深い点のほぼすべては、これら3つのコンポーネント間でデータがどう移動するかに由来します。その移動はすべて、一般にputと呼ばれる、一見単純な1回の関数呼び出しから始まります。

putとは？ 

Putは、内部でレコードを1件だけ含むWriteBatchを作成し、変更を処理する**Write()**に渡す便利なラッパーです。 

説明は**Put(key, value)**から始めるのが自然ですが、厳密にはRocksDBにそのような単独の操作はありません。すべての書き込みはバッチであり、単独のputも1件のバッチにすぎません。これはネイティブな操作であるため、RocksDBでは複数キーへのアトミックな書き込みを追加コストなしで利用できます。

WriteBatchは、固定形式のコンパクトなバイト列です。具体的には、8バイトのシーケンス番号と4バイトのレコード数を保持する12バイトのヘッダーに、レコード本体が続きます。各レコードは、1バイトの型タグ、長さプレフィックス付きのキー、そして書き込みの場合は長さプレフィックス付きの値で構成されます。

このシリーズの最初の記事で述べた「キーと値は任意のバイト配列である」という点が、ここで文字どおりの意味を持ちます。バッチのエンコーディングは、そのバイト列が何を意味するかを認識せず、気にも留めません。適用される構造は長さプレフィックスだけです。 

各バッチには、単調増加するカウンターであるシーケンス番号が付けられます。これにより、データベースが受け付けたすべての書き込みに全順序が設定されます。スナップショット、一貫性のある読み取り、クラッシュ復旧を可能にするのがシーケンス番号です。WAL内の各レコードは自身の順序を把握しているため、再生できます。

Put、Delete、Merge

重要なのは、PutがkTypeValue、DeleteがkTypeDeletionである点です。つまり、deleteはデータの除去ではありません。削除されたという事実を記録する書き込み、すなわちトゥームストーンであり、実際の領域回収はコンパクションまで延期されます。

PutとDeleteは、Merge操作によって書き込まれるkTypeMergeと同じWriteBatch形式を使用します。Mergeが存在するのは、読み取り・変更・書き込みが、書き込み最適化ストアにとって致命的だからです。Putでカウンターを増やすには、現在の値を読み取り、1を加算し、結果を書き戻す必要があります。1つの数値を変更するためにデータベースを2回たどることになり、読み取りでは読み取りパスの全コストが発生します。 

Mergeでは読み取りを完全に省略します。 

代わりに、オペランド、つまり「1を加算する」などの変更内容を追記して処理を終えます。書き込み時には何も計算しません。データベースは後から、アプリケーションが提供するマージ演算子を使ってオペランドを最終値に畳み込みます。これは、次にキーが読み取られたとき、またはコンパクションがそのチェーンを検出したときに行われます。

Deleteは領域回収を延期し、Mergeは計算を延期します。 

LSMツリーの性質は、これら3つの型タグにすべて表れています。既存の状態に論理的に依存するものも含め、あらゆる変更が単純な追記になります。LSMツリーでは、すべてが追記です。 

LSMツリーの書き込みパスを解説

LSMツリーを最も明確に理解する方法は、1回の**Put(key, value)**を関数呼び出しからディスクまで追跡することです。

ステップ1：先行書き込みログ

書き込みは、まずWALに追記されます。この追記はメモリテーブルに触れる前に行われ、この順序が永続性の契約を形成します。つまり、WALへの追記が完了した時点で、書き込みはまだ読み取り用に整理されていなくても、クラッシュ後も残る形式でディスク上に存在します。

ログへの追記は、実行可能なディスク操作の中で最も低コストです。それこそが重要です。永続性をシーケンシャル書き込みのコストで確保できます。

RocksDBは、同時書き込みをグループコミットにまとめてコストをさらに分散します。また、syncオプションは、呼び出しが戻る前に追記内容をOSのページキャッシュから安定したストレージへフラッシュするかどうかを制御します。

ステップ2：メモリテーブル

永続性を確保すると、書き込みはメモリテーブルに挿入されます。デフォルトでは、RocksDBのメモリテーブルはスキップリストです。スキップリストを使うのは、メモリテーブルが同時書き込みを取り込みつつ、読み取りと後続のフラッシュの両方に向けて、内容をキー順で返す必要があるためです。

スキップリストは、すべてを常にソートされた状態に保ちながら、ロックフリーの同時挿入をサポートします。これは、書類を積み上げておくのではなく、届いた時点で整理することに相当するデータ構造です。

ステップ3：メモリテーブルが満杯になる

メモリテーブルは、設定されたしきい値、つまりwrite_buffer_sizeに達するまで増加します。デフォルトは64 MBです。この時点で不変としてマークされ、新しい空のメモリテーブルに切り替わるため、受信する書き込みは中断せずに続行されます。満杯になって固定されたメモリテーブルは、バックグラウンドでフラッシュされる順番を待ちます。 

書き込みがフラッシュ自体を待ってブロックされることはありません。

ステップ4：フラッシュ

バックグラウンドスレッドが、不変のメモリテーブルをツリーのレベル0（L0）にSSTファイルとして書き出します。スキップリストはすでにソートされているため、フラッシュはエントリを順番にたどって書き出す、1回のシーケンシャルな処理になります。

これでメモリテーブルの役割は完了し、対応するWALエントリは最終的に破棄できます。データは永続的かつ読み取り可能な形式でディスク上に保持されます。

SSTファイルの中身は？

SSTファイルは、データが残りの期間を過ごす場所です。3種類のブロックとフッターで構成されます。

• データブロック：ソート済みのエントリ本体。各ブロックは数キロバイトで、個別に圧縮されます
• インデックスブロック：キーレンジをブロックオフセットにマッピングし、ルックアップが適切なブロックへ直接移動できるようにします
• オプションのブルームフィルターブロック：他のデータを読み取らずに「このキーはこのファイルに絶対に存在しない」と判定できる、コンパクトで確率的な要約です
• フッター：上記すべての位置を示します

このレイアウトの各要素は、今後の読み取りでアクセスするバイト数を可能な限り減らすために存在します。特に重要なのが、インデックスとブルームフィルターです。

書き込みパスの実践

ここまで説明したことは、すべて直接確認できます。このセクションでは、RocksDBに同梱されている検査ツールのldbとsst_dumpを使用し、データベース内で1回のPutを簡単に追跡します。この例ではRustとrocksdbクレートを使用しますが、どのバインディングでも構いません。

前提条件

手順を実行するには、RocksDBのコマンドラインツールとRustツールチェーンをインストールしてください。 

macOSでは、brew install rocksdbによってldbとsst_dumpの両方がインストールされます。 Debian/Ubuntuでは、パッケージ名はrocksdb-toolsです。

インストールしたら、新しいプロジェクトを作成します。

$ cargo new lsm-trace
$ cd lsm-trace
$ cargo add rocksdb

rocksdbクレートは初回ビルド時にRocksDBのC++ライブラリをソースからコンパイルするため、最初のcargo runには数分かかります。

ステップ1：書き込んで停止する

src/main.rsの内容を次のコードに置き換えます。

use rocksdb::{Options, DB};

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    let db = DB::open(&opts, "/tmp/lsm-trace").unwrap();

    db.put(b"slot:0001", b"hello").unwrap();
// Deliberately no flush. Let the process exit.
}

cargo runで一度実行し、作成されたデータベースディレクトリの内容を一覧表示します。

$ ls /tmp/lsm-trace
000004.log CURRENT IDENTITY LOCK LOG MANIFEST-000005 OPTIONS-000007

CURRENTとMANIFESTファイルはデータベースのファイル一覧を追跡し、OPTIONSはデータベースを開いた際の設定を記録します。番号の付いていないLOGはデバッグ用の人間が読めるテキストログです。先行書き込みログそのものである000004.logと混同しないでください。

正確なファイル番号は実行ごとに異なりますが、構成は変わりません。

ディレクトリには**.sst**ファイルが1つもない点に注目してください。プロセス終了後も残っているため書き込みは永続化されていますが、WALレコードとしてしか存在していません。これが、永続化と整理を分離する仕組みです。

ステップ2：WALをダンプする

ディレクトリ内にある**.logファイルをldb**に指定します。

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s) 1,1,29,0,PUT(0) : 0x736C6F743A30303031

バッチは1つです。シーケンス番号は1で、1件のレコード（29バイト）が含まれています。これはPUTで、キーはslot:0001を16進数でエンコードしたものです。 

サイズは先ほどのエンコーディングと一致します。12バイトのヘッダーと17バイトのレコードで、レコードには1つの型タグ、2つの長さプレフィックス、9バイトのキー、5バイトの値が含まれます。

ステップ3：フラッシュしてSSTをダンプする

まず、データベースディレクトリを削除して（rm -rf /tmp/lsm-trace）、今回の実行をクリーンな状態から開始します。

putの後に、main.rsへ次の1行を追加します。

db.put(b"slot:0001", b"hello").unwrap();
db.flush().unwrap();

**db.flush().unwrap();**を呼び出すと、メモリテーブルが満杯になるのを待たず、SSTファイルとして強制的に書き出されます。

ファイルをもう一度実行し、ディレクトリの内容を一覧表示します。 

出力に新しい**.sst**ファイルがあることを確認できます。実際のファイル名に置き換え、sst_dumpの2つの便利なモードで調べられます。

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

sst_dumpはスキャン出力の前に、ファイル形式に関する数行の前置きを出力します。ここ、および以下の出力では省略しています。

これが新しい永続的な保存先に格納されたキーと値のペアで、シーケンス番号も引き続き保持されています。 

続いて、次のコマンドでプロパティを確認できます。

$ sst_dump --file=/tmp/lsm-trace/000010.sst --show_properties

プロパティ出力には、この記事で先ほど説明したSSTの構造が項目別に表示されます。具体的には、データブロックの数とサイズ、インデックスブロックのサイズ、フィルターの有無、圧縮アルゴリズム、エントリ数です。 

キーが1つしかなくても、構造要素はすべて項目として表示されます。ただし、参考になる例外が1つあります。RocksDBではブルームフィルターがオプトインであり、filter_policyで設定します。デフォルトのオプションでは指定されていないため、フィルターブロックのサイズはゼロで、フィルターポリシーはN/Aです。 

このシリーズの次の記事では、本番環境でほぼ必ずブルームフィルターを有効にする理由を解説します。 

ステップ4：再度開いてログを確認する

putとflushの行をコメントアウトし、DB::openの行だけを残して、もう一度実行します。ディレクトリを一覧表示すると、古い000004.logは消え、より大きい番号が付いた新しい、ほぼ空のログに置き換わっています。ステップ3で内容がSSTにフラッシュされたため、レコードは不要になり、RocksDBが再オープン時にファイルを破棄しました。

これがWALとメモリテーブルのライフサイクル全体の連動です。 

さらに一層深く確認するには、Linuxでステップ1のバイナリをstrace -e trace=write,fdatasync下で実行し、syscall境界における永続性の契約を表示できます。シーケンシャルなwrite呼び出しが**.logファイルへ追記し、fdatasyncはWriteOptions.sync**が設定されている場合にのみ現れます。

ステップ5：キーを削除して残ったものを確認する

先ほど述べた「deleteは書き込みである」という点を直接確認できます。 

main.rsを変更してキーを削除し、もう一度フラッシュを強制します。

db.delete(b"slot:0001").unwrap();
db.flush().unwrap();

実行してから、ディレクトリの内容を一覧表示します。 

今度は**.sst**ファイルが2つあります。古いファイルは不変なので変更されず、キーとその値がまだ含まれています。これはスキャンで確認できます。

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

次に、新しいファイルをスキャンします。

$ sst_dump --file=/tmp/lsm-trace/000014.sst --command=scan
'slot:0001' seq:2, type:0 =>

同じキーですが、シーケンス番号がより大きく、type:1ではなくtype:0で、値はありません。これがトゥームストーンです。WriteBatchのセクションで説明したkTypeDeletionレコードが、独自のSSTへフラッシュされています。データベースには現在、値とその削除記録の両方が、別々のファイルに並んで存在します。

キーを読み取ると、この矛盾はトゥームストーンを優先して解決されます。 

プログラムにルックアップを追加して確認できます。

match db.get(b"slot:0001").unwrap() {
    Some(v) => println!("found: {:?}", v),
    None => println!("not found"),
}

読み取りパスは新しいデータを先に確認し、シーケンス番号2がシーケンス番号1より優先されるため、not foundと出力されます。データベースから見ると値は消えていますが、古いSSTファイル内のディスク上にはまだ存在します。 

領域は何も回収されていません。つまり、削除は記録されただけであり、コンパクションによって最終的に2つのファイルがマージされ、トゥームストーンと隠された値の両方が削除されるまで、その値を隠し続けます。

ステップ6：キーを削除して残ったものを確認する

Mergeレコード型も確認できます。RocksDBはオペランドの意味を単独では解釈できないため、マージ演算子を設定する必要があります。

データベースディレクトリをもう一度削除し、main.rsを次のコードに置き換えます。

use rocksdb::{Options, DB, MergeOperands};

fn add(_key: &[u8], existing: Option<&[u8]>, operands: &MergeOperands) -> Option<Vec<u8>> {
    let mut total: i64 = existing
        .and_then(|v| std::str::from_utf8(v).ok())
        .and_then(|s| s.parse().ok())
        .unwrap_or(0);
    for op in operands {
        total += std::str::from_utf8(op).ok().and_then(|s| s.parse().ok()).unwrap_or(0);
    }
    Some(total.to_string().into_bytes())
}

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    opts.set_merge_operator_associative("add", add);
    let db = DB::open(&opts, "/tmp/lsm-merge").unwrap();

    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    println!("{:?}", db.get(b"counter").unwrap());
}

WALをダンプすると、3つの独立したMERGEレコードが表示されます。つまり、1回の読み取りではなく、3回の追記です。

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s)
1,1,23,0,MERGE(0) : 0x636F756E746572
2,1,23,30,MERGE(0) : 0x636F756E746572
3,1,23,60,MERGE(0) : 0x636F756E746572

マージ演算子は、読み取り時に結果を生のバイト列としてチェーンを畳み込みました。51は文字3のASCIIコードなので、プログラムは**Some([51])**と出力します。これも、キーと値が任意のバイト配列だからです。

ルックアップの前に**db.flush().unwrap();**を追加し、ディレクトリを削除して、プログラムを再実行することもできます。SSTをスキャンすると、レコードは1件だけです。

'counter' seq:3, type:2 => 3

フラッシュによって演算子が適用され、単一のオペランドにまとめられました。

レベル0が特別なのはなぜですか？

新しいSSTファイルはレベル0に配置されます。各ファイルはメモリテーブルの直接的なスナップショットであり、そのメモリテーブルが取り込んだキーレンジ全体を含みます。そのため、L0ファイル同士は重複する可能性があり、実際によく重複します。これは、ファイルが重複しない下位の各レベルとは異なります。下位レベルでは各ファイルが固有のキーレンジを所有するため、特定のキーを含められるファイルは各レベルで最大1つです。

その結果、各L0ファイルがキーの隠れている可能性のある別々の場所となり、L0ファイル数が読み取り性能に直接負担をかけます。このため、RocksDBはL0ファイル数を綿密に監視し、数が増えすぎると書き込みのスロットリングを開始し、場合によっては停止させます。

L0を小さく保つことは、コンパクションの主要な役割の1つです。

書き込みでは、なぜLSMツリーがBツリーより優れているのですか？

Bツリーは読み取り時にすべてが正確な場所で見つかるよう、書き込み時に整理のコストを支払います。一方、LSMツリーは整理をバックグラウンドのコンパクションに先送りし、後から一括でコストを支払います。

Bツリーは、従来型データベースの大半を支えるデータ構造です。データをその場で更新するため、書き込みのたびにキーを所有するページを探し、読み取り、変更し、書き戻します。関係するページはディスク全体に分散しているため、論理的にランダムな書き込みの連続が、物理的にランダムなI/Oの連続になります。

LSMツリーは、書き込み時にそのコストを支払いません。追記（WAL）、バッファリング（メモリテーブル）、バッチ処理（フラッシュ）を行います。ディスクへの書き込みはすべてシーケンシャルで、整理に伴う負債はコンパクションまで延期されます。処理が消えるわけではありません。後から一括で支払い、ディスクが非常に効率よく扱える形式へ統合します。

SSDはデータをその場で上書きできないため、これは非常に重要です。 

フラッシュストレージでは、数百キロバイトから数メガバイトに及ぶ大きなブロック単位で消去し、より小さなページ単位で書き込みます。そのため、小さなランダム上書きが発生するたびに、ドライブのフラッシュ変換レイヤー（FTL）は裏側で有効なデータを移動し、ブロックを消去する必要があります。 

Bツリーのランダムなページ書き込みは、FTLにこの処理を繰り返し実行させます。データ構造自体で生じるコストに加えて、デバイスによる書き込み増幅も発生し、スループットとドライブ寿命の両方で代償を支払います。LSMツリーの大きなシーケンシャル書き込みは、フラッシュハードウェアにとってほぼ理想的なケースです。

これはローンとして考えると分かりやすくなります。先送りした整理のコストはコンパクションI/Oとして後から発生し、読み取り時にはBツリーより多くの場所を確認する必要があります。つまりLSMツリーは、現在の書き込みスループットを手に入れ、その代償を後から読み取り増幅と空間増幅として支払います。 

読み取り増幅、書き込み増幅、空間増幅の観点からLSMツリーとBツリーをさらに詳しく比較するには、B-Tree vs LSM-Treeをご覧ください。 

RocksDBがクラッシュするとどうなりますか？

メモリテーブルは揮発性メモリなので、クラッシュすると消去されます。これこそがWALの存在理由です。

再起動時、RocksDBは応答済みでありながら、まだSSTにフラッシュされていないすべての書き込みを再生します。それらを新しいメモリテーブルに挿入し、クラッシュ前の状態を再構築します。復旧コストは未フラッシュのデータ量に比例します。そのため、WALとメモリテーブルのライフサイクルは連動しています。メモリテーブルの内容がSSTへ安全にフラッシュされると、対応するログエントリは不要になり、WALを切り詰められます。

ログへの追記がディスクに到達した瞬間、書き込みは永続化されます。その後、フラッシュによって整理されると、低コストで読み取れるようになります。Bツリーでは両者が結合されていますが、LSMツリーでは分離されており、その分離からLSMツリーの特性の大部分が生まれます。 

Solanaは書き込みパスにどのような負荷をかけますか？

このシリーズの最初の記事では、AgaveがSolanaの台帳をRocksDBに保存する方法を説明しました。書き込みパスの観点では、このワークロードは専用に設計されたストレステストに近いものです。つまり、shred（台帳データの生の単位）がネットワーク経由で回線速度いっぱいに継続して届き、validatorのストレージレイヤーが処理を完了するまでに、そのすべてがWALへの追記とメモリテーブルへの挿入パスを通過する必要があります。

関係する仕組みは、本記事で追跡したものを本番規模にしただけで、まったく同じです。shredが到着すると、AgaveのBlockstoreの挿入パスは受信したshredのバッチ全体を検証し、欠落したshredに対してReed-Solomon復元を試み、すべてのデータ、つまりshredのペイロード、slotメタデータ、消失訂正メタデータ、インデックス更新を単一のRocksDB WriteBatchに準備してから、1回のアトミックな書き込みでコミットします。

insert_data_shredを簡略化したものです。

// We don't want only a subset of these changes going through.
write_batch.put_bytes::<cf::ShredData>((slot, index), &shred.payload)?;
update_slot_meta(/* ...metadata updates */);
data_index.set_present(index, true);

このコメントは、本記事の要点をAgaveのエンジニアが9語で表現したものです。バッチがアトミック性の単位であり、挿入中にvalidatorがクラッシュしても、台帳が中途半端に更新された状態に決してなってはなりません。 

実践で追跡した1件のバッチは、validator内では数千件のバッチになります。複数のカラムファミリーにまたがるshredとそのメタデータ、1つのシーケンス番号レンジ、1回のWAL追記、1回のグループコミットです。

ただし、ここには好都合な点があります。shredはslot番号から始まり、簡略化したコードスニペットの**(slot, index)タプルがShredData**キーです。そしてslotはほぼ単調に増加します。そのため、各メモリテーブルはキースペースの狭く、ほぼ連続した範囲を取り込み、フラッシュによって生成されるL0ファイルはほとんど重複しません。

私たちはこの書き込みパスの影響を直接受けています。 

Heliusで運用しているアーカイブシステムは、Solanaの全トランザクション履歴をRocksDBに取り込んでいます。これは数百テラバイト規模で、追記が多く、永続的に増え続けるワークロードです。このアーキテクチャを生み出した移行については、ClickHouseからRocksDBへの移行に関する記事で解説しています。

まとめ

LSMツリーは、ハードウェアとの取引です。データ整理を先送りする代わりに、すべての書き込みをシーケンシャルにします。そのため、たとえば読み取りパスでは、Bツリーより多くの場所からデータを探す必要があります。メモリテーブルが取り込み、WALが保証し、SSTが蓄積します。ランダム上書きに二重のペナルティがあるフラッシュストレージでは、これは非常に有利な取引です。

ただし、書き込みは簡単な側です。この設計の代償は読み取り時に支払います。キーの現在値が、メモリテーブル、L0ファイル、またはそれより下のどのレベルにも存在する可能性があるためです。このコストを一定範囲に抑える仕組みにこそ、LSMエンジニアリングの面白さがあります。 

このシリーズの次の記事では、メモリテーブル、ブルームフィルター、ブロックキャッシュ、そして実際の増幅トライアングルを取り上げながら、読み取りパスを詳しく解説します。

1つのキーと値のペアを4つの異なるデータ構造にわたって追跡することに魅力を感じるなら、私たちと一緒に開発しませんか。このシリーズで説明したシステムは、インターネット資本市場の規模で私たちがデプロイ、運用、チューニングしているものです。エンジニアリングチームでは幅広い職種を募集しています。募集中のポジションはhelius.dev/careersでご覧ください。