LSM木と書き込み最適化構造

なぜB木では書き込みが遅いのか

データベースのインデックスといえば平衡木、とりわけB+木が定番です。範囲検索に強く読み出しは速い一方、B+木には書き込みが本質的に分散する弱点があります。新しいキーは木のどこに入るか分からないため、挿入のたびにディスク（SSD）上のランダムな位置を更新する必要があり、しかも更新はページ単位です。1バイトのキーを足すために4KBや8KBのページ全体を読み書きする、いわゆるページ単位の書き込み増幅が避けられません。

LSM木（Log-Structured Merge-tree、1996年、O'Neilら）は発想を逆転させます。ランダムな更新をその場で反映するのをやめ、すべての書き込みをいったん追記（append）として受け、後でまとめてソート・整理する。ランダム書き込みをシーケンシャル書き込みに変換することが、設計の一点突破の核心です。RocksDB、LevelDB、Cassandra、ScyllaDB、HBase、そしてSSDの内部FTLまで、書き込み主体のストレージはほぼこの構造に基づいています。

三段構えの書き込み経路

LSM木の書き込みは、揮発メモリと不揮発ストレージにまたがる三つの部品で構成されます。

• WAL（Write-Ahead Log）: 書き込みはまずディスク上のログへ追記される。これは純粋なシーケンシャル書き込みで速く、クラッシュ時にメモリ表を再生するための保険。
• メモリ表（memtable）: 同じ書き込みをメモリ上のソート済み構造（スキップリストや平衡木）にも入れる。ソート済みなので後で順番に吐き出せる。
• SSTable（Sorted String Table）: メモリ表が一定サイズに達したら、その内容をキー順にソートされた不変（immutable）ファイルとして一括でディスクに書き出す（フラッシュ）。

書き込み(put)
   │
   ├─→ WAL に追記              （耐障害性のため・シーケンシャル）
   └─→ memtable に挿入          （メモリ上・ソート済み）
           │ 満杯になったら
           ▼
        SSTable としてフラッシュ  （不変ファイル・シーケンシャル書き出し）

ここで決定的に重要なのが**SSTableは一度書いたら変更しない（不変）点です。既存キーの更新や削除すら、新しいSSTableに「新しい値」や「削除を表す印」を追記するだけで行います。削除は値を消すのではなく墓石（tombstone）**という特殊なマーカーを書き、読み出し時に「このキーは消えている」と判断させます。こうしてディスクへの書き込みは常に追記のみとなり、ランダムな上書きが原理的に発生しません。

読み出しはなぜ重くなるのか

書き込みを軽くした代償は読み出しに回ります。あるキーを探すには、まず memtable を見て、無ければディスク上の複数のSSTableを新しい順に走査しなければなりません。最悪、すべてのSSTableを覗くことになります。1回の論理的な読み出しが複数のファイルアクセスに膨らむこの現象を**読み出し増幅（read amplification）**と呼びます。これはB+木が「木を1本下るだけ」で済むのと対照的な、LSM木の構造的な弱点です。

これを救う二段の仕掛けがあります。

第一に各SSTableは内部に**スパースインデックス（疎索引）**を持ちます。全キーではなく一定間隔のキーとそのファイル内オフセットだけを記録し、目的キーがブロックのどこにあるかを絞り込みます。ファイル内はソート済みなので、ブロックを特定すれば二分探索で到達できます。

第二がブルームフィルタです。これが読み出し増幅対策の主役です。

ブルームフィルタ — 存在しないキーを早く諦める

読み出しが重くなる典型は「存在しないキーを全SSTableに問い合わせてしまう」ケースです。ブルームフィルタ（Bloom filter）は、各SSTableに付随する小さなビット配列で、「このファイルにキーがあるか」を高速に確率判定します。

仕組みはこうです。キーを k 個の独立なハッシュ関数に通し、得られた k 個の位置のビットを1にして登録します。問い合わせ時は同じ k 個の位置を見て、1つでも0なら絶対に存在しないと断言できます（偽陰性ゼロ）。すべて1なら「たぶん存在する」とだけ言えます。ここに偽陽性、つまり本当は無いのに「あるかも」と答える誤りが一定確率で混じります。

登録: key を h1,h2,h3 に通し、対応3ビットを 1 にする
判定: 同じ3ビットを見る
      1つでも 0 → 確実に存在しない（このSSTableをスキップできる）
      全部 1   → たぶん存在する（実際に読みに行く）

偽陽性率はビット配列のサイズ m、登録要素数 n、ハッシュ関数の本数 k で決まり、k = (m/n)·ln2 で最適化したとき最小になります。1要素あたり約10ビット割けば偽陽性率はおよそ1%に収まり、99%の「存在しないキー」問い合わせをディスクアクセス前に弾けます。偽陽性が起きても「無駄に1ファイル読むだけ」で正しさは壊れないため、誤りを許容して空間と速度を買う典型的なトレードオフです。ハッシュ品質が効く点はハッシュテーブルの内部と共通の発想です。

コンパクション — 散らばったファイルを整理する

放っておくとSSTableは増え続け、読み出し増幅も古いデータ（墓石や上書き前の値）による無駄な容量も膨らみます。これを定期的に併合・整理する背景処理がコンパクション（compaction）です。複数のSSTableをマージソートの要領で1つにまとめ、その過程で重複キーは最新だけ残し、墓石が消した古い値は物理的に捨てます。すべてのファイルがキー順にソート済みなので、併合は線形時間のマージで済みます。

ただしコンパクションはタダではありません。1バイトのデータが、その生涯で何度もコンパクションに巻き込まれて読み書きされます。「ユーザーが書いた量」に対して「ディスクに実際に書かれた総量」の比を**書き込み増幅（write amplification）**と呼び、これがLSM木で最も注意すべき指標です。コンパクションをサボれば読み出し増幅と空間増幅が悪化し、頑張れば書き込み増幅が悪化する。三者は同時に最小化できません。

レベル戦略 — トレードオフの配分を決める

コンパクションをどう組むかが、増幅三兄弟（書き込み・読み出し・空間）の配分を決めます。代表的な二戦略を対比します。

**サイズ階層型（size-tiered）**は、同じくらいのサイズのSSTableが規定数たまるまで併合を待ち、まとめて1つの大きなファイルにします。併合の頻度が低いので書き込み増幅は小さい一方、同じキー範囲を持つファイルが各階層に複数同居し得るため、読み出しは多くのファイルを覗くことになります。Cassandraの既定や、書き込みが圧倒的なログ系で好まれます。

レベル型（leveled）は、L1以降の各レベルをキー範囲が互いに重ならないSSTable群で構成し、レベルが1つ深くなるごとに容量上限を約10倍に増やします。あるレベルが溢れると、はみ出した分を次レベルの重なる範囲のファイルだけと併合し直します。この制約のおかげで、L1以降は1つのキーが各レベルに高々1ファイルしか存在せず、読み出しで覗くファイル数が「レベル数（＝おおむね対数）」に抑えられます。代償として併合が頻繁に起き、書き込み増幅は大きくなります。LevelDB／RocksDBの既定路線で、読み出しや更新の多いワークロードに向きます。

性能特性とハードウェアとの相性

LSM木が現代ストレージの主役になった背景にはSSDの特性があります。SSDはブロックを上書きできず、消去してから書く必要があるため、内部でガベージコレクション（FTL）が走ります。ランダム上書きを多発させるB+木はこのGCを誘発しSSD自身の書き込み増幅を増やしますが、LSM木のシーケンシャルな大きな書き込みはSSDのフラッシュ消去単位と相性が良く、デバイス寿命の面でも有利です。連続したアクセスがハードウェアに優しいという原則はメモリレイアウトとデータ局所性と通底します。

計算量で整理すると、書き込みは memtable への挿入がO(log n)、フラッシュとコンパクションはならしで安価なシーケンシャル書き込み。点読み出しはブルームフィルタが効けば実質O(1)に近づき、効かない最悪でもレベル数ぶんのファイル走査に収まります（計算量とBig-Oの感覚で言えば対数オーダー）。範囲検索だけはB+木に分があり、ここがエンジン選定の分かれ目になります。

まとめ

LSM木の核心は「ランダム書き込みを追記に変え、整理を後回しにする」という一点です。memtableで受けてSSTableへシーケンシャルに吐き、不変ファイルへの追記と墓石で上書き・削除すら追記化することで、書き込みスループットを最大化します。その代償である読み出し増幅をブルームフィルタとスパースインデックスで抑え、散らかったファイルをコンパクションで整理する。そしてサイズ階層型かレベル型かの選択が、書き込み増幅・読み出し増幅・空間増幅という同時には満たせない三者の配分を決めます。B+木が「読み出しと範囲検索のための構造」なら、LSM木は「書き込みのための構造」であり、どちらを選ぶかはワークロードが書き込み主体か読み出し主体かという問いに帰着します。