# 詳説 データベース ## 概要 『詳説 データベース ― ストレージエンジンと分散データシステムの仕組み』は、[[Alex Petrov]] による *Database Internals: A Deep Dive into How Distributed Data Systems Work*(O'Reilly Media, 2019)の日本語版である。データベースを「ストレージエンジン」と「分散システム」の二層に分解し、単一ノードのディスク上データ構造から、複数ノードにまたがる合意形成までを一本の筋で扱う。 同種の書籍が API・データモデル・運用の側から論じるのに対し、本書は**実装者の視点**に立ち、B ツリーのノードレイアウトやスロット化ページのバイト配置、LSM ツリーのコンパクション戦略、Paxos の各変種の差分といった、通常は論文と実装ソースを往復しないと得られない水準の細部を体系化している点に特徴がある。 ## 書誌情報 - **原書**: *Database Internals: A Deep Dive into How Distributed Data Systems Work*(Alex Petrov, O'Reilly Media, 2019) - **著者**: [[Alex Petrov]](アレックス・ペトロフ) - **監訳**: 小林 隆浩 - **訳**: 成田 昇司 - **出版社**: オライリー・ジャパン(発売元: オーム社) - **発行日**: 2021 年 7 月 2 日(初版第 1 刷) - **ISBN**: 978-4-87311-954-0 - **構成**: 全 2 部・全 14 章(第 I 部 ストレージエンジン: 1〜7 章 / 第 II 部 分散システム: 8〜14 章)、および各部の序論とむすび、付録 A 参考文献 - **分量**: 392 ページ ## 構成と主要テーマ ### 第 I 部: ストレージエンジン(序論・第 1〜7 章) 単一ノードのデータベースが、ディスクという「ブロック単位でしか読み書きできず、ランダムアクセスが高くつく」媒体の上に、いかにして索引と永続性と同時実行性を成立させるかを扱う。中心に置かれるのは B ツリーと LSM ツリーという二大系統で、両者の対立軸(in-place 更新 対 追記のみ、読み取り増幅 対 書き込み増幅)が部全体を貫く。 → [[@2021__OReillyJapan__詳説 データベース - Part I 序論 ストレージエンジン]] — データベース選定はワークロードのシミュレーションと内部構造の理解に基づくべきで、ストレージエンジンの設計はあらゆるユースケースに最適な単一解が存在しないトレードオフの連続である。 → [[@2021__OReillyJapan__詳説 データベース - Chapter 1 基本事項の紹介と概要]] — DBMS アーキテクチャ、メモリベース対ディスクベース、列指向対行指向、データファイル対インデックスファイル、バッファリング・イミュータビリティ・オーダリングという本書全体の座標軸を定義する導入章。 → [[@2021__OReillyJapan__詳説 データベース - Chapter 2 Bツリーの基本]] — 二分探索木の局所性・ファンアウト・高さの限界からディスクベース構造の要件を導出し、B ツリーの階層構造・セパレータキー・検索アルゴリズム・分割とマージの手続きを体系的に示す。 → [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]] — バイナリエンコーディング、スロット化ページ、セルレイアウト、可変長データ管理、バージョン管理、チェックサムという、ディスク上のバイト配置という最も具体的な層を扱う。 → [[@2021__OReillyJapan__詳説 データベース - Chapter 4 Bツリーの実装]] — 2 章が示した B ツリーの理論を、ページヘッダ・兄弟リンク・ハイキー・パンくずリスト・オーバーフローページという補助構造によって実装可能にする。 → [[@2021__OReillyJapan__詳説 データベース - Chapter 5 トランザクション処理とリカバリ]] — バッファ管理(退避ポリシー)、リカバリ(WAL・steal/force・ARIES)、同時実行制御(OCC・MVCC・2PL・分離レベルとアノマリー)を扱う、第 I 部で最長かつ最も密度の高い章。 → [[@2021__OReillyJapan__詳説 データベース - Chapter 6 Bツリーの亜種]] — B ツリーという単一の構造に対し、ハードウェアと同時実行性の要請から派生した 5 系統(コピーオンライト・遅延・FD ツリー・Bw ツリー・キャッシュオブリビアス)の設計の系統樹を示す。 → [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]] — イミュータブルな LSM ツリーを、B ツリーとの読み書き増幅トレードオフ(RUM 予想)、Bitcask・WiscKey という順序なし LSM ストレージ、そして FTL・ファイルシステムログ・LLAMA というログ構造化スタック全体の観点から解説する。 ### 第 II 部: 分散システム(序論・第 8〜14 章) 複数ノードにまたがったとき、単一ノードでは自明だった「今の状態」「操作の順序」「生きているかどうか」がいずれも自明でなくなる。部の構成そのものが積み上げになっており、障害検出 → リーダー選出 → レプリケーションと一貫性 → 収束機構 → 分散トランザクション → 合意という順に、下の層が上の層の前提を供給する。 → [[@2021__OReillyJapan__詳説 データベース - Part II 序論 分散システム]] — 垂直スケーリングの限界から水平スケーリングへの移行を導入し、参加者・クロック・通信リンクという基本語彙と、通信チャネルとプロセスの不完全な信頼性という困難さの根源を定義する。 → [[@2021__OReillyJapan__詳説 データベース - Chapter 8 基本事項の紹介と概要]] — 並行実行から出発し、分散コンピューティングの誤謬、リンクの抽象化、2 人の将軍の問題、FLP の不可能性、システムの同期性、障害モデルという、第 II 部全体を貫く語彙と不可能性結果を導入する。 → [[@2021__OReillyJapan__詳説 データベース - Chapter 9 障害検出]] — 非同期分散系では「クラッシュ」と「単に遅い」を区別できないため障害検出は本質的に困難であり、完全性と正確性のトレードオフを軸に ping・ハートビート・Phi-Accrual・ゴシップ・FUSE という異なる設計思想を紹介する。 → [[@2021__OReillyJapan__詳説 データベース - Chapter 10 リーダー選出]] — 活性と安全性の両立が理想だが、ブリー・次候補フェイルオーバー・候補者/一般人・招待・リングの 5 系統はいずれも安全性を欠き、安定した選出には障害検出との組み合わせが不可欠である。 → [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] — CAP 定理、共有メモリレジスタ(セーフ/レギュラー/アトミック)、線形化可能性から因果一貫性までの階層、セッションモデル、R + W > N の調整可能な一貫性、ウィットネスレプリカ、CRDT を体系的に扱う、第 II 部の中核章。 → [[@2021__OReillyJapan__詳説 データベース - Chapter 12 アンチエントロピーと情報散布]] — アンチエントロピーを対話型(読み取り修復・ダイジェスト読み取り)、バックグラウンド型(Merkle ツリー・ビットマップバージョンベクトル)、ゴシップ型(情報散布)の 3 系統に分類し、それぞれがスコープ削減・最新性・完全性のどれに最適化されているかを示す。 → [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] — 分散トランザクションを、アトミックコミット(2PC・3PC)、決定論的順序(Calvin)、TrueTime による外部一貫性(Spanner)、分散スナップショット分離(Percolator)、調整の回避(RAMP)という 5 つのアプローチから対比的に解説する。 → [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] — ブロードキャスト、ZAB、Paxos(基本と 5 つの亜種)、Raft、PBFT を通じ、リーダー選出と障害検出の積み重ねの先にある分散合意の到達点を提示する、本書の最終章。 ## 影響と位置づけ 本書の独自性は、**同一の対立軸を単一ノードと分散環境の両方に一貫して適用した**点にある。第 I 部の「in-place 更新か追記か」「読み取り増幅か書き込み増幅か」というストレージ層のトレードオフは、第 II 部では「同期的な調整か結果整合性か」「強い一貫性か可用性か」という形で反復される。どちらの部でも著者は「万能の設計はなく、何を諦めたかを言えることが設計である」という立場を崩さない。 読み方としては、第 I 部が実装者向けの詳細(バイト配置・ページ構造)に踏み込むのに対し、第 II 部はアルゴリズムとその不可能性結果を扱うため抽象度が上がる。第 II 部は 8 章の不可能性結果(FLP・2 人の将軍の問題)を起点に、9 章から 14 章までが「その制約下で何ができるか」の段階的な回答になっており、章順どおりに読むことに意味がある構成になっている。 ## 関連 - 実体: [[Alex Petrov]] - ストレージエンジン: [[B-Tree]] / [[LSMツリー]] / [[スロット化ページ]] / [[Write-Ahead Logging (WAL)]] / [[ARIES]] / [[ACIDと分離レベル]] / [[スナップショット分離とMVCC]] - 分散システム: [[FLPの不可能性]] / [[2人の将軍の問題]] / [[分散コンピューティングの誤謬]] / [[障害検出器]] / [[リーダー選出]] / [[CAP定理]] / [[線形化可能性]] / [[結果整合性]] / [[CRDT]] / [[アンチエントロピー]] / [[分散トランザクション]] / [[分散コンセンサス]] ## 出典 - Alex Petrov 著, 小林隆浩 監訳, 成田昇司 訳, *詳説 データベース ― ストレージエンジンと分散データシステムの仕組み*, オライリー・ジャパン, 2021.