B-TreeかLSM-Treeか――Alex Petrov『詳説 データベース』でストレージエンジンの内部を覗く

レプリケーションの遅延やフェイルオーバーの挙動を、「そういうものだから」で済ませていないか。

Alex Petrov著『詳説 データベース ―ストレージエンジンと分散データシステムの仕組み―』（オライリー・ジャパン、2021年）は、クエリ解析やSQL最適化といった上位レイヤの話を切り離し、データの物理的配置からネットワークを介した合意形成までの低レイヤメカニズムだけに焦点を絞った専門書だ。BツリーやLSMツリーのバイナリレイアウト、ARIESリカバリプロトコル、PaxosやRaftといった分散合意まで、100本以上の学術論文やOSS実装から抽出した知見が、特定製品に依存しない形で整理されている。

1. インプレース更新とアペンドオンリー――対極に位置するストレージエンジン

多くのリレーショナルデータベースが長らく採用してきたBツリーは、ディスク上の同じ場所を直接書き換える「インプレース更新」を特徴とする。読み込みや範囲検索の効率は高いが、ランダムアクセスが多発し書き込みのオーバーヘッドを生む。対極にあるのがLSMツリー（ログ構造化マージツリー）だ。メモリ上でデータをソートしてから不変のディスクファイル（SSTable）として書き出し、バックグラウンドの「コンパクション」で整理していく。

flowchart LR
    subgraph BTree["B-Tree（インプレース更新型）"]
        A["ディスク上の同じ位置を直接書き換え"] --> B["読み込み・範囲スキャンに強い"]
        A --> C["ランダムI/Oの書き込みオーバーヘッド"]
    end
    subgraph LSM["LSM-Tree（アペンドオンリー型）"]
        D["メモリでソート後、不変のSSTableへフラッシュ"] --> E["書き込みをシーケンシャルI/Oに集約"]
        D --> F["バックグラウンドのコンパクションが必要"]
    end
    style A fill:#e8f4fd,stroke:#4a9eda
    style D fill:#e8f8e8,stroke:#4caf50

すべてのワークロードに最適な単一のデータ構造は存在しない。アクセスパターンに応じた使い分けが必要になる。

2. ACIDを支えるバッファ管理とリカバリプロトコル

データベースがクラッシュしてもデータを失わない「耐久性」は、SQLの文法ではなくその裏側で動くページキャッシュやバッファプールのメカニズムに支えられている。本書は、ディスクへのフラッシュ前に変更を不揮発なログへ記録する「WAL（先行書き込みログ）」の設計や、再起動時に一貫した状態へ高速に巻き戻す「ARIESリカバリプロトコル」の内部構造を詳述する。チェックポイント処理やWALのフラッシュ間隔がなぜ重要なのか、その物理的な動作機序を追える構成だ。

3. 不確実なネットワークの上で一貫性を作る――分散合意とクラスタ協調

システムが複数ノードにスケールアウトすると、ネットワークの遅延や消失、ノードの突然死が避けられなくなる。本書後半では、各ノードの生死を推測する「Failure Detector」、データを伝播させる「Gossipプロトコル」、そして「Paxos」や「Raft」といった分散合意アルゴリズムが順を追って解説される。CAP定理の限界を理解しつつ、現実のシステムが何を犠牲にして可用性や一貫性を成立させているのかという、アーキテクトに不可欠なトレードオフ感覚を養える。

この本が解決できる具体的な状況

RDBMSのチューニングオプションや分散レプリケーションの挙動を論理的に評価できず、直感に頼った技術選定を行っている――この状況に、本書はストレージエンジンと分散合意の物理的なメカニズムから根拠を与える。分散クラスタの運用でスプリットブレインやリーダー再選定に伴うダウンタイムの原因が特定できずにいるSREにも、故障検知や合意プロトコルの理論的背景が助けになる。

こんな人に向いている

• データベースエンジンや分散ミドルウェアの自作・コントリビュートを目指すシステム開発者
• 大規模分散ミドルウェアを運用するSRE・プラットフォームエンジニア
• RDBMSのチューニングや分散レプリケーションの挙動を、勘ではなく物理的な根拠から判断したいシニアバックエンド開発者

逆に向いていないケース

• SQLやPythonの初学者、日々のクエリチューニングにすぐ使える実用知識を求める人: 難度が高く、Webサービス開発やクエリチューニングに直接応用できる知識は少ない
• 特定製品（Oracle Databaseなど）のマニュアル的な知識を求める人: 普遍的な学術用語で書かれているため、特定プロダクトの用語体系に慣れたエンジニアには概念の変換コストがかかる
• ストレージや合意形成そのものに関心がない人: アプリケーション設計寄りの技術（キャッシング、データモデル、メッセージングなど）はほぼ扱われず、関心領域が別にある場合は学習曲線が急峻になる

知っておきたい限界

批判として押さえておきたい点が二つある。

一つは著者の経歴に由来する偏りだ。著者はApache Cassandraのコミッターであり、LSMツリーや一部の分散トピックの説明に、ややCassandra寄りのユースケースが重きを置かれている傾向がある。

もう一つは、扱う範囲の狭さだ。多くの読者が指摘するように、本書は『データ指向アプリケーションデザイン』に比べてキャッシング・データモデル・メッセージングといったアプリケーション設計寄りの技術をほぼ扱わず、ストレージと合意形成という二つの物理レイヤに極端にフォーカスしている。自身の関心がデータベースエンジンの実装やトラブルシューティングそのものにない場合、学習曲線は急峻になる。

同じテーマの本との比較

『SQLパフォーマンス詳解』でB-Treeインデックスの内部構造を理解してから本書を読むと、LSM-Treeとの対比がより鮮明になる。読み書き特性の異なるデータ構造を比較できるようになり、DBエンジン選定の眼が養われる。

具体的な一実装として『PostgreSQL徹底入門』でMVCCやVACUUMなどの物理的な挙動を掴んでおくと、本書が扱う抽象的な議論を相対化する地図として使いやすい。

単一ノードのストレージエンジン内部を理解して初めて、複数ノードに分散したときの整合性・レプリケーション・パーティショニングの議論が地に足のついたものになる。『データ指向アプリケーションデザイン』は本書を必須の前提として、分散データシステム設計の原理を体系化する到達点だ。ストレージエンジンの理解を運用の視点に橋渡ししたいなら、『データベースリライアビリティエンジニアリング』が次のステップになる。

まとめ

データベースを製品名やベンダー用語ではなく、ストレージエンジンと分散合意という物理的な仕組みから理解する。ブラックボックスのままでは説明できなかった挙動に、根拠を持った説明を与えてくれる一冊だ。

筆者の体験から

テックリードとしてマネージドデータベースサービスへの移行を検討していたとき、レプリケーション方式やフェイルオーバーの挙動がサービスごとに違う理由を、ベンダーのドキュメントの文言だけでは説明しきれずにいた時期がある。SLAの数字は分かっても、「なぜこの構成だとフェイルオーバーに数秒かかるのか」を自分の言葉で説明できなかった。

本書のBツリーとLSMツリーの対比や、PaxosやRaftといった分散合意の説明を読んでから、少なくとも「何がトレードオフになっているか」を自分の言葉で説明できるようになった。故障検知や分散合意の理論は、社内でマネージドDBの構成を検討する際の判断材料として役に立った。

一方で、著者がCassandraのコミッターであるためか、分散システムの説明にCassandra寄りの前提が感じられる箇所があり、自分たちが使っているRDBMS系のマネージドサービスにそのまま当てはめられない部分もあった。また、自作データベースの実装経験がないため、後半の分散合意プロトコルの実装レベルの詳細は、理解はできても実務にすぐ活かせる知識には至らなかったというのが正直なところだ。

DevBookPath のマップで確認する

この本の学習パス上の位置づけ・前後の読書順は、DevBookPath のグラフで辿れます。

👉 データベースの地図を見る

📖 Amazon で購入する

---

本記事のリンクには Amazon アソシエイト等の広告が含まれる場合があります。リンク経由の購入で運営者に紹介料が支払われることがあります。