LSM 木

LSM 木は変更を永続ログに記録し、最新バージョンをメモリに置いて、ディスク上の整列とマージをバッチへ回す。書き込み時に最終配置を組み替える必要はない。その代わり、読み取りが重なる複数ファイルを調べたり、バックグラウンドのコンパクションが既存レコードを書き直したりする。

先に追記し、後から整理する。整理を待つ間も、シーケンス番号と新しい順の読み取りで正しいバージョンを選ぶ。

WAL、メムテーブル、フラッシュ

各 put と delete に単調増加するシーケンス番号を付ける。WAL へ追記してからメムテーブルを更新する。このレッスンでは WAL 追記が同期的に永続化されるため、WAL とメモリの更新後に書き込みを確認できる。SSTable の変更はまだ不要だ。

メムテーブルはキーごとに現在のレコードを一つ持つ。キー 20 を二度書いてもメモリのスロットを置き換えるだけで、異なるキーの枠を二つ使わない。WAL には両方の変更が残り、そのログ区間が不要になるまで保持する。削除も同じ経路でトゥームストーン、つまり削除マーカーを書き込む。古いファイルから値をその場で消すわけではない。

異なるキーの数が容量に達すると、世代全体を不変メムテーブルに切り替え、新しい活動中の表と WAL を開く。不変表は到着順に関係なくキー昇順で L0 にフラッシュする。新 SSTable のインストール後に、封印した WAL 区間を回収できる。

ステップ実行

既定値はメムテーブルが 3 キー、L0 が 2 ファイルでコンパクションを開始する。操作列は次のとおり。

put 20 A, put 10 B, put 30 C, put 20 A2, get 20, delete 10, get 10, put 40 D, get 20

1. 20:A #1、10:B #2、30:C #3 を、それぞれ WAL、メムテーブルの順に書く。三つ目の異なるキーで第一世代を凍結し、S1 = [10:B #2, 20:A #1, 30:C #3] をキー順で出力する。
2. キー 20 を A2 #4 で上書きする。新値は活動中のメムテーブルにあり、S1 には 20:A #1 が残る。
3. 20 を読むとメモリの A2 #4 を返して終了する。L0 の古い値は調べない。
4. 10 を削除し、マーカー #5 を書く。S1 の 10:B #2 は変わらず、新しい可視バージョンがマーカーになる。
5. 10 の読み取りはメモリのマーカーで終了する。未検出として S1 へ進めば B が復活してしまう。
6. 40:D #6 で第二世代が満杯になり、S2 = [10:DEL #5, 20:A2 #4, 40:D #6] を出力する。L0 の重なる 2 ファイルをコンパクションする。
7. S1 と S2 をマージし、各キーの最大シーケンス番号を選ぶ。20 は A2 #4 を残し A #1 を捨てる。10 はマーカー #5 が勝つ。今回は下位の古い重複バージョンをすべて含み、最下層へ出力し、スナップショットもないので、マーカーと B #2 の両方を除去できる。30 と 40 は有効なまま残る。
8. 新 L1 [20:A2 #4, 30:C #3, 40:D #6] を一度にインストールする。提供する状態を切り替えた後で旧 L0 入力を回収する。
9. 20 を再読する。メモリと L0 は空なので、L1 が A2 #4 を返す。

論理的な変更 6 回から、整列済みフラッシュが 2 回生じる。コンパクションは保存バージョン 6 個を読み、有効な L1 レコード 3 個を書く。

読み取り・書き込み・容量の増幅

前景処理は WAL 追記とメモリ更新を行い、フラッシュとコンパクションを後へ回す。仕事そのものが消えるわけではない。

• 読み取り増幅：モデルには Bloom フィルター、キャッシュ、ファイル内インデックスがなく、L0 で見つからなければ重なる全ファイルを確認してから L1 へ進む。
• 書き込み増幅：コンパクションは既存レコードを読み直して書き直す。既定例では 6 入力バージョンから 3 レコードを出力する。
• 容量増幅：古い値、削除マーカー、置換後の値が、安全な破棄を証明できるまで共存する。

大きいメムテーブルは一般にフラッシュ回数を減らし、一回の出力を大きくする。L0 の閾値を上げるとコンパクションを遅らせるが、フィルターのない未検出検索が調べるファイルも増える。閾値を下げるとバックグラウンド I/O を早く使い、読み取り経路を短く保つ。画面はレコード数と参照元数を数え、バイト数や時間は測らないため、運用の調整式にはならない。

適する用途

書き込み中心で、ストレージが順次バッチ出力を処理でき、バックグラウンド用の CPU と I/O 予算がある場合に向く。点検索には補助構造が役立つ。Bloom フィルターはキーを含まないファイルを除外し、疎インデックスは候補ブロックを特定し、ブロックキャッシュはデバイスの再読み取りを減らす。読み取り増幅の物理コストを抑える仕組みだ。

読み取りを重視するなら、L0 ファイルが少ない段階でコンパクションを始める選択がある。逆に遅らせると未検出検索が調べる参照元が増える。実エンジンでは L0 の蓄積がコンパクション負荷や書き込み停止を招くこともあるが、この二層モデルは扱わない。

点検索、範囲検索、順序付きページの局所性を重視し、ページの更新維持が適するなら B+ 木を検討する。継続的な書き込みを追記とバッチ処理で吸収することを重視するなら LSM を検討する。

新しい順の読み取り

活動中のメムテーブル、L0 SSTable の新しい順、唯一の最下層 L1 の順に調べる。最初に見つかった値または削除マーカーで終了する。

参照元の順序は、古いファイルが新しい更新を隠すのを防ぐ。シーケンス番号は、コンパクションで同じキーの複数バージョンから勝者を選ぶ。この二つは役割が異なる。

Read amplification プリセットでは、L0 が 3 ファイルで閾値 4 に届かない。get(99) はメモリと 3 ファイルを調べ、論理的な参照元プローブは 4 回となる。ディスク I/O が 4 回という意味ではない。実際のデバイス処理はフィルター、インデックス、キャッシュ、ブロック配置で変わる。

コンパクションと削除マーカー

コンパクションは整列済み入力の多方向マージだ。各入力の先頭は未消費の最小キーを示す。最小ユーザーキーを選び、そのキーの全候補を集め、最大シーケンス番号を選ぶ。有効な勝者を新出力へ追加し、古い候補を捨てる。

削除マーカーには追加条件がある。選ばれていない下位ファイルに古い値が残る間にマーカーを捨てると、その値が再び見える。このレッスンで除去できるのは、全 L0 と重なる L1 全体を含め、最下層へ出力し、スナップショットがないためだ。条件を満たさなければ、隠れた旧値が復活しないと保証できるまで残す。

Tombstone safety プリセットは L1 に 10:B #1、新 L0 に 10:DEL #5 を置く。読み取りはマーカーで止まる。L1 の旧値を一緒に消費する前にマーカーを消せば B が復活する。

構築中の L1 は部分結果を提供しない。完成した出力を一度にインストールしてから、旧入力を無効化して回収する。

計算量

M は活動中メムテーブルのサイズ、F0 は重なる L0 ファイル数、S は各 L0 のレコード数、L1 は最下層のレコード数、N はコンパクション入力総数、k は入力列数とする。

アクセスの増加を示す式であり、遅延の保証ではない。WAL は同期を要する場合があり、SSTable 検索はメモリで済む場合もある。実製品にはブロック、フィルター、キャッシュ、圧縮、並列バックグラウンド処理がある。

境界ケース

• 最初のフラッシュ前はメモリだけが来源で、未検出は 1 プローブで終わる。全キーを落とすコンパクションも空の L1 ランを設置するので、以後の未検出はそれも調べる。
• 同一世代の上書きは値と番号を更新し、異なるキーの枠を増やさない。
• 容量を超えてからではなく、達した時点で世代を凍結する。
• 存在しないキーの削除も番号付きマーカーを書く。旧ファイルに値があれば隠し、旧値がなければ条件を満たす最下層コンパクションで除去できる。
• 新 L0 の一致で終了し、古い重複コピーは調べない。
• 削除マーカーは最終結果であり、下へ進む許可ではない。
• 複数ファイルでの未検出は、参照した全入力を読み取り台帳に示す。
• 画面は現在のユーザーキー最大 12 個、操作最大 20 回。描画上限であり、LSM の容量や書き込み停止の閾値ではない。

よくある間違い

• L0 を古い順に読み、新値を旧値で隠す。
• 削除マーカーを未検出として扱い、削除値を復活させる。
• 最大番号ではなく最初のコンパクション候補を選ぶ。
• 未選択の古い重複やスナップショットを無視し、毎回すべてのマーカーを消す。
• 出力のインストール前に入力を回収し、欠落や部分結果を見せる。
• SSTable の書き直しを前景書き込みの確認条件と見なす。既定例は WAL とメモリの状態を先に確認する。
• 参照元プローブを物理 I/O と同一視する。

モデルの範囲

直列の二層モデルで、同期永続 WAL、活動中の表一つと不変表最大一つ、重なる L0、完全な L1 一つ、最下層への全範囲コンパクションを扱う。スナップショット、Bloom フィルター、疎・ブロックインデックス、ブロックキャッシュ、圧縮、チェックサム、マニフェストとバージョン集合、復旧リプレイ、並行書き込み、複数の背景ジョブ、部分重複の選択、出力サイズ、書き込み停止は省略する。LevelDB や RocksDB 系の実装は方針を細分化する。マーカー除去の安全性は、全重複を含む最下層マージでスナップショットがない場合に限る。