変更をどこへ反映するかが違う
B木はキー順を保つ多分岐の木を使い、検索や範囲走査を行います。DBではページに対応する形で実装されることが多く、更新先のページを見つけて変更し、必要なら分割などを行います。LSM木では、変更をメモリ上へため、ソート済みのファイルへ書き出し、後で複数のファイルを併合する構成が代表的です。どちらも一つの固定された実装ではありません。メモリ、ログ、キャッシュ、圧縮の設計も製品によって異なります。比較の中心は、変更を反映するタイミングと、その費用をどの処理へ配分するかです。
一つのキーの更新を追う
キーkの値を1から2へ変える例を考えます。B木では、対応するページ上のエントリーを更新する仕組みを想像できます。LSMでは、新しい版がメモリや新しいファイルに入り、古い版が別のファイルに残る場合があります。読取りは必要な場所を調べ、新しい有効な版を選びます。古い版を消すには、併合の時点で、その版が読者にまだ必要かなどを判断します。同じキーに版が複数あることを、直ちにアプリへ重複した行を返すという意味にしてはいけません。内部の保持方法と、APIが返す論理的な結果を区別します。
読取り・書込み・空間の増幅を比べる
一回のアプリ更新に対し、実際の記憶装置へ何倍の量を書くかが書込み増幅です。LSMの併合では同じデータを複数回書き直す場合があります。読取りでは候補ファイルを複数調べる費用があり、Bloom filterや索引がその一部を減らします。古い版や併合中の入出力ファイルを保持すれば、一時的な空間も必要です。B木でもページ分割、ログ、空き領域、キャッシュの状態が費用へ影響します。最初のメモリへの書込みが速いことだけで、長時間の総書込み量や遅い要求まで有利と結論するのは早計です。
削除マーカーの寿命を考える
LSMの削除では、削除されたというマーカーを残して、古いファイルの値が再び見えないようにする構成があります。これを見たからといって、直後にすべての媒体から元の値が消去されたとは限りません。併合、古い読者、バックアップなどの条件で保持が続く場合があります。削除の論理的な見え方と、空間の回収、媒体上の情報の消去は別の要件です。B木側でも、削除した一行のサイズだけ即座にファイルが小さくなるとは限りません。容量問題や機密情報の削除を扱うなら、製品の具体的な回収・保持手順まで確認します。
併合が追い付かないと何が起こるか
書込みを受け続けても併合が追い付かなければ、ファイル数や待ち仕事が増え、読取りの費用や書込みの停止に影響する場合があります。背景処理だから利用者の応答へ関係しない、とは言えません。併合が使うCPU、I/O、空間を、手前の要求と共有するためです。短い空のDBへの試験だけでは、長期間の更新や削除の後の状態を再現できません。測定では取り込みから定常状態までの経過と、併合量、停止時間、遅い側の応答も残します。設定変更で背景負荷を減らした結果、後でまとめて負荷が表面化しないかを確認します。
ワークロードと実装をそろえて選ぶ
小さいランダム読取り、大きな範囲走査、追記中心の入力、同じキーへの更新では、望ましい費用の配分が違います。データの大きさと分布、メモリ量、耐久性、圧縮、読書きの割合をそろえて測ります。PostgreSQLのB木索引とRocksDBのLSMを、そのまま同じ機能のDB製品全体の優劣として比べることも適切ではありません。索引とストレージエンジンでは、受け持つ責務が異なるためです。ここでは仕組みの費用を比較しており、実測の性能差は示していません。要件を満たす具体的な構成で結果を確かめることが最後の判断になります。