LSM-Tree と B-Tree 徹底解説 - 書き込み最適化ストレージエンジンの仕組み

INSERT を1行実行したとき、ストレージには何バイト書かれているでしょうか。行のサイズが128バイトなら128バイト、とはいきません。手元で書いたシミュレーションでは、400万行のテーブルにランダムな更新を20万回かけると、論理的には 24.4 MiB の更新なのに物理的には 2310.4 MiB が書かれました。書き込み増幅は約94.6倍です。

この差はバグではなく、B+Tree というデータ構造が「書く前に置き場所を決める」設計だから生じます。そして、この増幅を減らすために「置き場所を決めるのを後回しにする」という真逆の設計を選んだのが LSM-Tree です。

この記事では、データベースインデックス入門で扱った「インデックスがどう使われるか」の一段下、ストレージエンジンがディスクへどう書いているかを追いかけます。数値と仕様は RocksDB / LevelDB / PostgreSQL / MySQL / Cassandra の公式ドキュメントと、LSM-Tree の原論文・RUM 予想の論文から引いています。

二つの流派: in-place 更新と追記型

ストレージエンジンの設計は、突き詰めると次の一点で分かれます。既にある場所を上書きするか、後ろに書き足すかです。

どちらが優れているという話ではありません。後述の RUM 予想が示すとおり、これはどのコストを誰に払わせるかの配分の違いです。

B+Tree はなぜ RDB の標準になったのか

B+Tree の強さは「1回のディスクアクセスで大量の分岐を進める」ことにあります。ディスクの読み書きはページ（ブロック）単位でしか行えません。ならばページ1枚に数百のキーを詰め込み、1回の読み込みで数百分岐すればよい、という発想です。

InnoDB のインデックスページは既定で 16KB です（innodb_page_size で初期化時に決まります）。SQLite のページサイズは 512 から 32768 のべき乗に限られ、バージョン 3.12.0（2016-03-29）以降は既定が 4096 になりました。手元の SQLite 3.51.0 で新規データベースを作って PRAGMA page_size を見ると、たしかに 4096 が返ります。

1ページに200エントリ入るなら、木の深さ3で800万件、深さ4で16億件を収容できます。深さがほとんど増えないので、探索は実質的に定数回のI/Oで済みます。

ノード分割 - 満杯のページに挿入すると何が起きるか

問題は、ページが満杯のときに挿入が来た場合です。B+Tree はノード分割（page split）で対処します。

分割前: リーフページが満杯。ここにキー 35 を挿入したい
   親: [ ... | 60 | ... ]
                |
   リーフ: [ 10 | 23 | 41 | 58 ]   <- 空きなし
 
分割後: リーフを2枚に割り、区切りキーを親へ押し上げる
   親: [ ... | 35 | 60 | ... ]     <- 親にもエントリが1つ増える
              /      \
   リーフA: [ 10 | 23 ]   リーフB: [ 35 | 41 | 58 ]
              \___双方向リンクで連結___/

この分割は2ページの書き込みに加えて親ページの更新を伴い、親も満杯なら連鎖して根まで遡ります。さらに、分割直後の2枚は半分しか埋まっていないため、空間効率も落ちます。

InnoDB のマニュアルは、この挙動を具体的な数字で説明しています。通常の挿入では将来の挿入・更新に備えてページの 1/16 を空けようとするため、キーが昇順・降順に挿入される場合はページが約 15/16 まで埋まる一方、ランダムな順序で挿入されるとページの充填率は 1/2 から 15/16 の間に散らばるとされています。逆に削除でページの充填率が MERGE_THRESHOLD（既定 50%）を下回ると、InnoDB は木を縮めてページを解放しようとします。

MyRocks の Wiki が「B+Tree インデックスは順次挿入でなければ断片化する。断片化で 30〜50% の追加領域が必要になることも珍しくない」と書いているのは、まさにこの性質を指しています。

WAL がなければ B-Tree は壊れる

ページの上書きには、もう一つ厄介な問題があります。ページの書き込み途中で電源が落ちるケースです。16KB のページの前半だけが新しく、後半が古いままという「ちぎれたページ（torn page）」ができると、そのページはもはやどんな木構造としても読めません。

そこで登場するのが WAL（Write-Ahead Log）です。PostgreSQL 公式ドキュメントは、その中心概念をこう述べています。「データファイルへの変更は、その変更がログに記録された後にのみ書き込まれなければならない」。変更を記述した WAL レコードを永続ストレージへフラッシュしてから、はじめてデータページを触ってよい、というルールです。

WAL には副次的な、しかし決定的な利点があります。同ドキュメントによれば、WAL ファイルは順次書き込まれるため、散らばったデータページをフラッシュするより同期コストがはるかに小さく、しかも小さなトランザクションが多数走っているときはWAL の1回の fsync で多数のトランザクションをコミットできるとされています。ランダム書き込みをシーケンシャル書き込みに変換する装置、と読み替えてもよいでしょう。

ちぎれたページ対策は WAL の上にさらに一段積まれています。PostgreSQL の full_page_writes（既定は on）は、チェックポイント後に各ページを最初に変更するとき、ページ全体の内容を WAL へ書きます。行レベルの差分だけでは、ちぎれたページを復元できないからです。MySQL InnoDB は同じ問題を doublewrite buffer で解決します。どちらも「安全のために同じデータを2回書く」ことを選んでおり、これが B-Tree 系の書き込み増幅の重要な源になっています。

ログ先行書き込みという発想自体はファイルシステムのジャーナリングと同根です。詳しくはファイルシステムの仕組みを参照してください。トランザクションの原子性・耐久性の側から見たい場合はトランザクションとACIDが対応します。

書き込み増幅を数えてみる

「ランダム更新はページ単位の書き込みを増やす」という話を、実際に走るコードで確かめます。1行128バイト、ページ16KB、400万行のテーブルに20万回の更新をかけ、チェックポイントごとにダーティページをまとめて書き戻す想定です。

import random
 
PAGE_SIZE = 16 * 1024   # InnoDB の既定ページサイズ
ROW_SIZE = 128          # 1行の論理サイズ
ROWS = 4_000_000        # テーブルの行数
UPDATES = 200_000       # 実行する更新回数
CHECKPOINT = 20_000     # この回数ごとにダーティページを書き戻す
 
MIB = 1024 * 1024
rows_per_page = PAGE_SIZE // ROW_SIZE
 
 
def simulate(name, pick_row):
    dirty = set()
    pages_written = 0
    for i in range(1, UPDATES + 1):
        dirty.add(pick_row(i) // rows_per_page)   # 行が属するページを汚す
        if i % CHECKPOINT == 0:
            pages_written += len(dirty)           # まとめて書き戻す
            dirty.clear()
    pages_written += len(dirty)
    logical = UPDATES * ROW_SIZE
    physical = pages_written * PAGE_SIZE
    print("%s | ページ書き込み %7d 回 | 論理 %.1f MiB | 物理 %.1f MiB | 書き込み増幅 %.1f 倍"
          % (name, pages_written, logical / MIB, physical / MIB, physical / logical))
 
 
random.seed(42)
simulate("ランダム更新", lambda i: random.randrange(ROWS))
simulate("連番更新　　", lambda i: i % ROWS)
simulate("ホット10%内", lambda i: random.randrange(ROWS // 10))

ランダム更新 | ページ書き込み  147863 回 | 論理 24.4 MiB | 物理 2310.4 MiB | 書き込み増幅 94.6 倍
連番更新　　 | ページ書き込み    1572 回 | 論理 24.4 MiB | 物理 24.6 MiB | 書き込み増幅 1.0 倍
ホット10%内 | ページ書き込み   31206 回 | 論理 24.4 MiB | 物理 487.6 MiB | 書き込み増幅 20.0 倍

同じ更新回数でも、アクセスの局所性だけで増幅が1.0倍から94.6倍まで動きます。これは in-place 更新に内在する性質であり、実装の巧拙とは別の話です。MyRocks の Wiki も同じ論点を「1レコードを更新するだけでも、その行が属するページ全体がダーティになり、そのページを書き戻さなければならない。OLTP では変更単位（行）が I/O 単位（ページ）よりずっと小さいため、書き込み増幅が非常に高くなる」と説明しています。

LSM-Tree: 並べ替えを後回しにする

LSM-Tree（Log-Structured Merge-Tree）は、Patrick O'Neil, Edward Cheng, Dieter Gawlick, Elizabeth O'Neil による1996年の論文「The Log-Structured Merge-Tree (LSM-Tree)」（Acta Informatica 33巻 351-385ページ）で提案されました。論文の要旨は「レコードの挿入（および削除）が高頻度で長期間続くファイルに対して、低コストなインデックスを提供する」ことで、そのためにインデックスの変更を遅延させ、まとめて（batch）、マージソートに似た形でメモリ上のコンポーネントからディスク上のコンポーネントへ段階的に流すと書かれています。

現代の実装における全体像は次のようになります。

                        書き込み (put / delete)
                                |
              +-----------------+-----------------+
              v                                   v
      WAL (追記オンリーのログ)            MemTable (メモリ上のソート済み構造)
      クラッシュ復旧のためだけに存在        満杯になったら凍結
                                                  |
                                          Immutable MemTable
                                                  |
                                          バックグラウンドでフラッシュ
                                                  v
   L0: [SST][SST][SST][SST]     <- キー範囲が互いに重なりうる
        |
        |  コンパクション (マージして下へ)
        v
   L1: [SST][SST][SST]          合計サイズの上限あり / 範囲は重ならない
        |
        v
   L2: [SST] ... [SST]          L1 の約10倍
        |
        v
   L3: [SST] ............ [SST] L2 の約10倍

各パーツの役割を押さえます。

MemTable は書き込みを受け止めるメモリ上のソート済み構造です。RocksDB の既定実装はスキップリストで、「読み書き・ランダムアクセス・順次スキャンのいずれにもバランスよく効く」と説明されています。既定の write_buffer_size は 64MB、max_write_buffer_number は 2 です。

WAL はここでも必須です。MemTable はメモリ上にあるため、プロセスが落ちれば消えます。RocksDB のドキュメントは「新しい書き込みは MemTable に挿入され、オプションでログファイル（WAL）にも書かれる」としています。B-Tree の WAL が「ページのちぎれ」を防ぐためのものだったのに対し、LSM の WAL はメモリ上の未フラッシュ分を守るためにあります。

Immutable MemTable は、満杯になって凍結された MemTable です。RocksDB では書き込みが write_buffer_size を超えたとき、全カラムファミリの合計が db_write_buffer_size を超えたとき、WAL 合計が max_total_wal_size を超えたときに、この遷移が起きます。凍結後はバックグラウンドスレッドが SST ファイルへ書き出し、書き出し終わったら破棄されます。凍結してから書き出すので、フラッシュ中も新しい書き込みは別の MemTable で受け続けられます。

SSTable（Sorted String Table）は、キー順に並んだ不変（immutable）のディスクファイルです。一度書いたら二度と書き換えません。Cassandra のドキュメントはこの帰結を端的に述べています。「SSTable は不変であるため、データが更新または削除されても、古いデータが上書きされたり SSTable から取り除かれたりすることはない」。

上書きも削除も、すべて新しいエントリの追記として表現されます。ランダムな更新であってもディスクへは順次書き込みしか発生しません。先ほどのシミュレーションでいえば、LSM はどんなアクセスパターンでも「連番更新」の列に近い書き方をする、ということです。

コンパクション: leveled / tiered / universal

追記しかしないと、当然ながら同じキーの古い版が溜まり、読み取りで見なければならないファイルが増え続けます。これを回収するのがコンパクションです。Cassandra のドキュメントは、コンパクションの目的を「重複や古いデータを取り除いて読み取り性能を上げること」と「SSTable のサイズを減らしてディスク領域を取り戻すこと」の二つだと説明しています。

leveled（レベル型）

LevelDB のインプリメンテーションドキュメントが、この方式の原型を最も簡潔に説明しています。「若いレベル（level-0）のファイルはキーが重なりうるが、それ以外のレベルのファイルは互いに重ならないキー範囲を持つ」。そして、level-L のファイル合計サイズが 10^L MB を超えたとき（level-1 なら 10MB、level-2 なら 100MB）にコンパクションが起きます。出力ファイルはおおむね 2MB ごとに切り替えられます。

LevelDB のドキュメントは、その I/O 量も具体的に見積もっています。level-0 のコンパクションは最悪で「1MB の level-0 ファイルを最大4個と、level-1 の全ファイル（10MB）」を読みます。それ以外のコンパクションは、おおよそ 26MB を読んで 26MB を書きます。

RocksDB はどのレベルを次に圧縮するかをスコアで決めます。level-0 はファイル数を level0_file_num_compaction_trigger で割った値、それ以外のレベルは「そのレベルの合計サイズを目標サイズで割った値」がスコアで、最もスコアの高いレベルが優先されます。

tiered（サイズ階層型）と universal

tiered は、同じレベル内に似たサイズの複数のソート済みランを溜め、一定数集まったらまとめてマージして次のレベルへ落とす方式です。RocksDB のコンパクション解説では、両者の性質がこう対比されています。classic leveled は空間増幅を最小化する代わりに読み取り・書き込み増幅が高く、tiered は書き込み増幅を1レベルあたり約1に抑える代わりに読み取り増幅と空間増幅が増える。RocksDB が既定で使う level compaction は実際には両者の折衷（tiered+leveled）で、小さいレベルは tiered、大きいレベルは leveled として振る舞います。

RocksDB の Universal Compaction は tiered 寄りの戦略で、公式には「より低い書き込み増幅を必要とするユースケースを狙い、読み取り増幅と空間増幅を犠牲にするコンパクションスタイル」と定義されています。ただし制約も明記されています。フルコンパクション時に入力と出力が同時に存在するため一時的にディスク容量が倍必要になること、そして「コンパクションスケジューリングが遅延的であるため、ソート済みランの数が変動し、コンパクショントラフィックがスパイクして性能が不安定になる」ことです。

Cassandra は現在 UCS（Unified Compaction Strategy）、STCS、LCS、TWCS を提供しています。時系列データのように「古いデータはまとめて期限切れで捨てる」ワークロードには TWCS が向く、というように、戦略はワークロードの形に合わせて選ぶものです。

読み取り増幅とブルームフィルタ

LSM の読み取りは、原理上複数のソート済みランを新しい順に見る必要があります。これが読み取り増幅です。素直にやると、レベルの数だけディスクI/Oが増えてしまいます。

そこで、SSTable ごとにブルームフィルタを持たせます。

get(key)
  1. MemTable を見る               -> あれば返して終了
  2. Immutable MemTable を見る     -> あれば返して終了
  3. L0 の SST を新しい順に:
       3-1. Bloom filter に問い合わせ
              「確実に無い」  -> このファイルは一切読まない
              「たぶん有る」  -> インデックスブロックを読み、データブロックを読む
  4. L1, L2, ... と下へ。各レベルは範囲が重ならないので
     二分探索で候補を1ファイルに絞れる
  5. どこにも無ければ、あるいはトゥームストーンに当たれば「無い」

ブルームフィルタは「確実に含まない」を高速に返せるので、存在しないキーの探索でディスク読み込みを丸ごと省略できます。偽陽性はあり得ますが、そのときは実際にファイルを読んで確かめればよく、正しさは損なわれません。詳しい仕組みはブルームフィルタとはを参照してください。

もう一つ効くのが圧縮です。SSTable は不変でキー順に並んでいるため、隣接するキーは似ていることが多く、prefix encoding とブロック圧縮がよく効きます。RocksDB は圧縮済みブロックをセクタ境界に揃えないため、MyRocks の Wiki が指摘するように、16KB を 5KB に圧縮できたなら 5KB しか使いません。一方 InnoDB の圧縮はページ単位でセクタサイズに整列されるので、同じ 5KB でも実際には 8KB を消費します。圧縮アルゴリズムの選び方はデータ圧縮の基礎が参考になります。

ミニ LSM を書いて動かす

言葉だけでは掴みにくいので、MemTable、SSTable へのフラッシュ、tiered コンパクション、トゥームストーンを最小構成で書いてみます。

import itertools
 
TOMBSTONE = object()  # 削除マーカー
 
 
class MiniLSM:
    def __init__(self, memtable_limit=4, tier_trigger=3):
        self.memtable = {}              # キー -> 値（実装ではスキップリスト等）
        self.sstables = []              # 新しい順に並べた SSTable のリスト
        self.memtable_limit = memtable_limit
        self.tier_trigger = tier_trigger
        self.bytes_written = 0          # ディスクへ書いた累計エントリ数
        self.log = []
        self._seq = itertools.count(1)
 
    def put(self, key, value):
        self.memtable[key] = value
        self._maybe_flush()
 
    def delete(self, key):
        self.memtable[key] = TOMBSTONE   # 上書きせず、消したという事実を追記する
        self._maybe_flush()
 
    def get(self, key):
        # 新しい順に探す。最初に見つかったものが最新の値
        if key in self.memtable:
            return self._unwrap(self.memtable[key])
        for sst in self.sstables:
            if key in sst["data"]:
                return self._unwrap(sst["data"][key])
        return None
 
    def _unwrap(self, v):
        return None if v is TOMBSTONE else v
 
    def _maybe_flush(self):
        if len(self.memtable) < self.memtable_limit:
            return
        # MemTable を凍結し、ソート済みの SSTable としてフラッシュする
        data = dict(sorted(self.memtable.items()))
        self.sstables.insert(0, {"id": next(self._seq), "data": data})
        self.bytes_written += len(data)
        self.log.append("flush sst#%d entries=%d" % (self.sstables[0]["id"], len(data)))
        self.memtable = {}
        self._maybe_compact()
 
    def _maybe_compact(self):
        if len(self.sstables) < self.tier_trigger:
            return
        # tiered: 溜まった SSTable をまとめて1本にマージする
        merged = {}
        for sst in reversed(self.sstables):   # 古い順に上書きしていく
            merged.update(sst["data"])
        before = sum(len(s["data"]) for s in self.sstables)
        ids = [s["id"] for s in self.sstables]
        # 最下層に落ちたトゥームストーンはここで初めて捨てられる
        merged = {k: v for k, v in merged.items() if v is not TOMBSTONE}
        merged = dict(sorted(merged.items()))
        self.sstables = [{"id": next(self._seq), "data": merged}]
        self.bytes_written += len(merged)
        self.log.append(
            "compact %s -> sst#%d  %d entries -> %d entries"
            % (ids, self.sstables[0]["id"], before, len(merged))
        )
 
 
db = MiniLSM(memtable_limit=4, tier_trigger=3)
for i in range(1, 13):
    db.put("key%02d" % i, "v%d" % i)
db.put("key03", "updated")     # 上書きも「追記」
db.delete("key05")             # 削除も「追記」
db.put("key99", "last")
db.put("key98", "last")
for i in range(20, 24):
    db.put("key%02d" % i, "v%d" % i)
 
for line in db.log:
    print(line)
print("---")
print("get key03 ->", db.get("key03"))
print("get key05 ->", db.get("key05"))
print("get key12 ->", db.get("key12"))
print("sstables  ->", [(s["id"], len(s["data"])) for s in db.sstables])
print("memtable  ->", sorted(db.memtable))
print("書き込み操作 20 回に対し、ディスクへ書いた延べエントリ数 =", db.bytes_written)

flush sst#1 entries=4
flush sst#2 entries=4
flush sst#3 entries=4
compact [3, 2, 1] -> sst#4  12 entries -> 12 entries
flush sst#5 entries=4
flush sst#6 entries=4
compact [6, 5, 4] -> sst#7  20 entries -> 17 entries
---
get key03 -> updated
get key05 -> None
get key12 -> v12
sstables  -> [(7, 17)]
memtable  -> []
書き込み操作 20 回に対し、ディスクへ書いた延べエントリ数 = 49

読み取るべき点は3つあります。

1. key03 の更新も key05 の削除も、既存の SSTable には一切触れていません。すべて新しい MemTable への追記です
2. 2回目のコンパクションで、入力20エントリが出力17エントリに減りました。重複した key03 の古い版が消え、key05 のトゥームストーンもこのタイミングで初めて捨てられました
3. 書き込み操作は20回なのに、ディスクへ書いた延べエントリ数は49です。書き込み増幅は2.45倍。LSM も無償ではなく、コンパクションという形で増幅を払っています

3点目が重要です。LSM は書き込み増幅をゼロにするわけではなく、ランダムなページ書き込みを、順次のマージ書き込みに置き換えているのです。

RUM 予想: 3つのうち2つしか取れない

ここまで出てきた「読み取り増幅」「書き込み増幅」「空間増幅」の関係を、原理として定式化したのが RUM 予想です。Manos Athanassoulis, Michael S. Kester, Lukas M. Maas, Radu Stoica, Stratos Idreos, Anastasia Ailamaki, Mark Callaghan による EDBT 2016（Bordeaux, 2016年3月15-18日）の論文「Designing Access Methods: The RUM Conjecture」で提示されました。

論文が挙げる3つの量は、読み取りオーバーヘッド（R）、更新オーバーヘッド（U）、メモリ（またはストレージ）オーバーヘッド（M）です。予想の主張はこう書かれています。

The RUM Conjecture: Read, Update, Memory - Optimize Two at the Expense of the Third.

もう少し厳密な言い方として、論文は「RUM オーバーヘッドのうち2つに上限を設ける設計をすると、3つ目にはそれ以上下げられない厳しい下限が生じる」と述べています。極端なケースも命題として書かれており、たとえば更新オーバーヘッドだけを最小化する（すべての更新をひたすら追記する）場合は次のようになります。

• min(UO) = 1.0 のとき、RO と MO はともに無限に増大する（論文の Prop. 2）
• min(MO) = 1.0 のとき、RO = N（全走査が必要）で UO = 1.0（論文の Prop. 3）

                 Read (読み取り最適)
                       /\
     ハッシュ索引     /  \    B+Tree, Trie, Skiplist
                    /    \
                   /      \
                  /        \
   Update -------------------- Memory (空間最適)
   (更新最適)                   密な配列, Bitmap
   LSM, 差分構造                Bloom filter, 疎インデックス

論文の図でも LSM は Update 側の頂点近くに、B-Tree は Read 側の頂点近くに置かれています。ブルームフィルタや疎インデックスが Memory 側に置かれているのも示唆的で、LSM が読み取り増幅を補うためにブルームフィルタを併用するのは、Update 頂点に寄せた構成を Memory 側の道具で引き戻していると読めます。

そして論文は「万能の最良アクセスメソッドを作ることは不可能であり、あらゆるユースケースごとに最良のものを作ることも不可能だ」と結んでいます。ストレージエンジン選定で「どちらが速いか」を単体で問うのが不毛なのは、このためです。

実装の地図

主要な実装がどちら側に立っているかを整理します。

MyRocksは、B-Tree と LSM の差が同一の SQL 層の上で比較できる稀な例です。公式 Wiki が公開している Linkbench の結果（1.5B ID、32クエリスレッド、48時間、フラッシュストレージ）では、容量が InnoDB 1172GB に対し MyRocks 574GB（49%）、書き込み量が 152,422 KB/s に対し 66,932 KB/s（44%）、QPS が 22,227 に対し 33,094 と報告されています。ただしこれは開発元自身が特定ワークロードで測った値であり、時期もハードウェアも限定されます。自分のワークロードに一般化できる数字ではありません。

SQLite4は SQLite3 の置き換えではなく別の選択肢として設計され、キー・バリュー層に LSM を採用しました。公式サイトに LSM Design Overview のドキュメントが残っています。ただし src4 リポジトリのタイムラインを見ると最新のチェックインは2019年で、活発な開発は続いていません。一方、LSM の実装自体は SQLite3 のソースツリーに ext/lsm1 として現存しており、拡張として利用できます。

PostgreSQL は「B-Tree だが追記型」という別軸

ここで混同しやすい点を切り分けます。「B-Tree か LSM か」と「上書きするか追記するか」は、完全には一致しません。PostgreSQL がその例です。

PostgreSQL のインデックスは B-Tree ですが、テーブル本体（ヒープ）は MVCC のために追記型に振る舞います。公式ドキュメントは次のように述べています。

In PostgreSQL, an UPDATE or DELETE of a row does not immediately remove the old version of the row.

古い版は、他のトランザクションからまだ見えている可能性があるため即座には消せません。誰からも見えなくなった時点で領域を回収する必要があり、そのための仕組みが VACUUM です。公式ドキュメントは VACUUM が必要な理由として、更新・削除された行の領域回収、プランナ用統計の更新、visibility map の更新、そしてトランザクションID周回による古いデータの喪失防止の4つを挙げています。

この設計の困りどころは、1行の更新がインデックス側にも新しいエントリを生むことでした。そこで導入されたのが HOT（Heap-Only Tuple）です。公式ドキュメントによれば、次の2条件がともに満たされるとき HOT 更新が可能になります。

1. 更新が、そのテーブルのインデックスから参照される列を変更しないこと（summarizing index は除く）
2. 古い行が置かれているページに、更新後の行を入れるだけの空き領域があること

このとき「更新された行を表現するための新しいインデックスエントリは不要」になります。さらに HOT には副次的な利点があり、「ある行が複数回更新されたとき、最古と最新以外の版は、定期的な vacuum を要さず、SELECT を含む通常の操作の中で完全に取り除ける」とされています。インデックスは常に元の行版のアイテム識別子を指し続け、その識別子が redirect に変わることで、中間の版だけが回収されます。

つまり PostgreSQL は、木構造は B-Tree、更新モデルは追記型、回収は VACUUM と HOTという組み合わせです。「B-Tree だから上書き型」と決めつけると、VACUUM がなぜ必要なのか、なぜ fillfactor を下げると HOT が効きやすくなるのかが説明できません。実行計画から挙動を確かめる方法は実行計画とJOINアルゴリズムを参照してください。

削除とトゥームストーン

追記型の宿命として、削除は「消す」のではなく「消したという記録を追記する」操作になります。Cassandra のドキュメントはこう書いています。「Cassandra は削除を挿入として扱い、トゥームストーンと呼ばれるタイムスタンプ付きの削除マーカーを挿入する」。

トゥームストーンをすぐ捨てられない理由は分散システム固有です。ダウンしていたノードが復帰したとき、削除マーカーが既に消えていると削除済みのデータが復活してしまいます。そのため猶予期間が設けられており、Cassandra の gc_grace_seconds は既定 864,000 秒（10日）です。この期間を過ぎたトゥームストーンは、コンパクションの際に削除されます。

実務上の落とし穴もここにあります。大量削除の直後にレンジスキャンをかけると、読み飛ばすためだけに大量のトゥームストーンを読むことになり、レイテンシが悪化します。「削除したのに遅くなった」という現象は、追記型では珍しくありません。

どちらを選ぶか

判断軸を整理します。断定的な優劣ではなく、どのコストなら払えるかで選ぶのが実際的です。

補足がいくつかあります。

レンジスキャンは「LSM が苦手」と単純化できません。SSTable もキー順に並んでいるため走査自体は素直です。ただし複数のソート済みランをマージしながら読む必要があり、ブルームフィルタは点検索にしか効きません。一方で B+Tree はリーフが双方向リンクで繋がっていますが、断片化が進むと物理的にはランダムアクセスになります。どちらも「ワークロードと断片化の状態次第」というのが正直なところです。

SSD の特性は LSM に有利に働きやすいと言われます。SSD は内部で消去ブロック単位の書き換えを行うため、小さなランダム書き込みはデバイス内部でも書き込み増幅を生みます。大きな順次書き込みはそれを避けやすい、という理屈です。ただしこれはデバイスの FTL 実装に強く依存し、一般化した数値を出すのは困難です。

レイテンシは平均ではなく分布で見てください。LSM のレイテンシスパイクはコンパクションのスケジューリングに起因します。RocksDB が Universal Compaction について「コンパクショントラフィックがスパイクし、性能が変動する」と明記しているとおり、これは設定次第で緩和はできても消滅はしません。

まとめ

ストレージエンジンの二つの流派を、書き込み経路という一本の軸で振り返ります。

• B+Tree は書く前に置き場所を決めます。1ページに数百分岐を詰め込むことで浅い木を保ちますが、満杯ページへの挿入はノード分割を招き、ランダム更新はページ単位の書き込み増幅を生みます。手元のシミュレーションでは、同じ更新回数でもアクセスの局所性だけで増幅が1.0倍から94.6倍まで動きました
• WAL はどちらの流派にも必要ですが、役割が違います。B-Tree ではちぎれたページを防ぐため（PostgreSQL の full_page_writes、InnoDB の doublewrite buffer）、LSM ではメモリ上の MemTable を守るためです
• LSM-Tree は1996年の O'Neil らの論文が原点で、インデックス変更を遅延・バッチ化して段階的に下へ流します。MemTable、Immutable MemTable、SSTable、コンパクションの4つが基本部品です
• コンパクションは leveled が空間増幅を、tiered が書き込み増幅を最小化します。RocksDB の既定はその折衷です。追記型は増幅を消すのではなく形を変えて払っています
• RUM 予想は「Read, Update, Memory のうち2つを最適化すると3つ目が犠牲になる」と述べます。万能の最良アクセスメソッドは存在しません
• PostgreSQL は B-Tree だが追記型という第3の立ち位置で、VACUUM と HOT がその帰結です。「B-Tree = 上書き型」という短絡は避けてください
• 削除は追記です。トゥームストーンは gc_grace_seconds などの猶予を経てコンパクションで回収されるため、大量削除の直後は逆に遅くなりえます

「書き込みが多いなら LSM」という要約は、間違いではないものの粗すぎます。本当に問うべきは、読み取り増幅・書き込み増幅・空間増幅のどれを自分のシステムが払えるのかです。それが決まれば、選ぶべきエンジンはおのずと絞られます。

参考リンク

• The Log-Structured Merge-Tree (LSM-Tree) - O'Neil, Cheng, Gawlick, O'Neil (Acta Informatica 33, 1996)
• Designing Access Methods: The RUM Conjecture - Athanassoulis et al. (EDBT 2016, PDF)
• RocksDB Overview（公式Wiki）
• RocksDB MemTable（公式Wiki）
• RocksDB Compaction（公式Wiki）
• RocksDB Leveled Compaction（公式Wiki）
• RocksDB Universal Compaction（公式Wiki）
• RocksDB Bloom Filter（公式Wiki）
• LevelDB Implementation Notes（公式ドキュメント）
• PostgreSQL: Write-Ahead Logging (WAL)
• PostgreSQL: Write Ahead Log 設定パラメータ（full_page_writes）
• PostgreSQL: Heap-Only Tuples (HOT)
• PostgreSQL: Routine Vacuuming
• PostgreSQL: B-Tree Indexes
• MySQL 8.4 Reference Manual: Physical Structure of an InnoDB Index
• MySQL 8.4 Reference Manual: Doublewrite Buffer
• MyRocks advantages over InnoDB（公式Wiki）
• Apache Cassandra: What is compaction
• SQLite: PRAGMA Statements（page_size）
• SQLite4: LSM Design Overview