詳説 データベース
詳説 データベース ―ストレージエンジンと分散データシステムの仕組み
オライリー・ジャパン
著者：Alex Petrov
監訳：小林 隆浩
訳者：成田 昇司
監訳者まえがき
はじめに
第I部 ストレージエンジン
I.1 データベースの比較
I.2 トレードオフの理解
1章 基本事項の紹介と概要
1.1 DBMSアーキテクチャ
1.2 メモリベースのDBMSとディスクベースのDBMS
1.2.1 メモリベースのストアの永続性
1.3 列指向DBMSと行指向DBMS
1.3.1 行指向のデータレイアウト
1.3.2 列指向のデータレイアウト
1.3.3 相違点と最適化
1.3.4 ワイドカラムストア
1.4 データファイルとインデックスファイル
1.4.1 データファイル
1.4.2 インデックスファイル
1.4.3 間接参照としてのプライマリインデックス
1.5 バッファリングとイミュータビリティおよびオーダリング
1.6 まとめ
2章 Bツリーの基本
2.1 二分探索木
2.1.1 ツリーのバランシング
2.1.2 ディスクベースのストレージ用のツリー
2.2 ディスクベースの構造
2.2.1 ハードディスクドライブ
2.2.2 ソリッドステートドライブ
2.2.3 ディスク上の構造
2.3 ユビキタスBツリー
2.3.1 Bツリーの階層
2.3.2 セパレータキー
2.3.3 Bツリーの検索の計算量
2.3.4 Bツリーの検索アルゴリズム
2.3.5 キーのカウント
2.3.6 Bツリーノードの分割
2.3.7 Bツリーノードのマージ
2.4 まとめ
3章 ファイルフォーマット
3.1 モチベーション
3.2 バイナリエンコーディング
3.2.1 プリミティブな型
3.2.2 文字列と可変長のデータ
3.2.3 ビットパック化データ：ブール型と列挙型とフラグ
3.3 一般的な原則
3.4 ページ構造
3.5 スロット化ページ
3.6 セルのレイアウト
3.7 セルをスロット化ページに結合
3.8 可変長データの管理
3.9 バージョン管理
3.10 チェックサム
3.11 まとめ
4章 Bツリーの実装
4.1 ページヘッダ
4.1.1 マジックナンバー
4.1.2 兄弟（Sibling）リンク
4.1.3 右端のポインタ
4.1.4 ノードハイキー（NodeHighKey）
4.1.5 オーバーフローページ
4.2 二分探索
4.2.1 間接ポインタによる二分探索
4.3 スプリットとマージの伝播
4.3.1 パンくずリスト
4.4 リバランシング
4.5 右側限定の追加
4.5.1 バルクロード
4.6 圧縮
4.7 バキュームとメンテナンス
4.7.1 更新と削除による断片化
4.7.2 ページのデフラグ
4.8 まとめ
5章 トランザクション処理とリカバリ
5.1 バッファ管理
5.1.1 キャッシュの概要
5.1.2 キャッシュの退避
5.1.3 キャッシュにおけるページのロック
5.1.4 ページの置換
5.2 リカバリ
5.2.1 ログの概要
5.2.2 操作とデータログ
5.2.3 stealポリシーとforceポリシー
5.2.4 ARIES
5.3 同時実行制御
5.3.1 直列化可能性
5.3.2 トランザクションの分離
5.3.3 読み取りと書き込みのアノマリー
5.3.4 分離レベル
5.3.5 楽観的同時実行制御
5.3.6 マルチバージョン同時実行制御
5.3.7 悲観的同時実行制御
5.3.8 ロックベースの同時実行制御
5.4 まとめ
6章 Bツリーの亜種
6.1 コピーオンライト
6.1.1 コピーオンライトの実装：LMDB
6.2 ノード更新の抽象化
6.3 遅延Bツリー
6.3.1 WiredTiger
6.3.2 遅延適応ツリー
6.4 FDツリー
6.4.1 フラクショナルカスケーディング
6.4.2 対数的な配列
6.5 Bwツリー
6.5.1 アップデートチェーン
6.5.2 コンペアアンドスワップによる同時実行性の制御
6.5.3 構造を変更する操作
6.5.4 統合とガベージコレクション
6.6 キャッシュオブリビアスBツリー
6.6.1 vanEmdeBoasレイアウト
6.7 まとめ
7章 ログ構造化ストレージ
7.1 LSMツリー
7.1.1 LSMツリー構造
7.1.2 更新と削除
7.1.3 LSMツリーの検索
7.1.4 マージイテレーション
7.1.5 調停
7.1.6 LSMツリーにおけるメンテナンス
7.2 読み取りと書き込みおよび領域の増幅
7.2.1 RUM予想
7.3 実装の詳細
7.3.1 SortedStringTable
7.3.2 ブルームフィルタ
7.3.3 スキップリスト
7.3.4 ディスクアクセス
7.3.5 圧縮
7.4 順序付けされないLSMストレージ
7.4.1 Bitcask
7.4.2 WiscKey
7.5 LSMツリーにおける並行性
7.6 ログスタック
7.6.1 フラッシュトランスレーションレイヤ
7.6.2 ファイルシステムログ
7.7 LLAMAと注意深いスタック
7.7.1 Open-ChannelSSD
7.8 まとめ
第Ⅰ部 むすび
第II部分散システム
II.1 基本的な定義
8章 基本事項の紹介と概要
8.1 並行実行
8.1.1 分散システムでの共有された状態
8.2 分散コンピューティングの誤謬
8.2.1 プロセス
8.2.2 クロックと時間
8.2.3 状態の一貫性
8.2.4 ローカル実行とリモート実行
8.2.5 障害への対処の必要性
8.2.6 ネットワーク分断と部分障害
8.2.7 カスケード障害
8.3 分散システムの抽象化
8.3.1 リンク
8.4 2人の将軍の問題
8.5 FLPの不可能性
8.6 システムの同期性
8.7 障害モデル
8.7.1 クラッシュ障害
8.7.2 欠落障害
8.7.3 任意障害
8.7.4 障害の処理
8.8 まとめ
9章 障害検出
9.1 ハートビートとping
9.1.1 タイムアウトフリーな障害検出機能
9.1.2 ハートビートのアウトソーシング
9.2 Phi-AccuralFailureDetector
9.3 ゴシップと障害検出
9.4 障害検出の問題記述の反転
9.5 まとめ
10章 リーダー選出
10.1 ブリーアルゴリズム
10.2 次候補へのフェイルオーバー
10.3 候補者／一般人の最適化
10.4 招待アルゴリズム
10.5 リングアルゴリズム
10.6 まとめ
11章 レプリケーションと一貫性
11.1 可用性の実現
11.2 悪名高いCAP
11.2.1 注意が必要なCAPの使用
11.2.2 収穫と収量
11.3 共有メモリ
11.4 オーダリング
11.5 一貫性モデル
11.5.1 厳密な一貫性
11.5.2 線形化可能性
11.5.3 逐次一貫性
11.5.4 因果一貫性
11.6 セッションモデル
11.7 結果整合性
11.8 調整可能な一貫性
11.9 ウィットネスレプリカ
11.10 強力な結果整合性とCRDTs
11.11 まとめ
12章 アンチエントロピーと情報散布
12.1 読み取り修復
12.2 ダイジェスト読み取り
12.3 ヒンテッドハンドオフ
12.4 Merkleツリー
12.5 ビットマップバージョンベクトル
12.6 ゴシップの散布
12.6.1 ゴシップの仕組み
12.6.2 オーバーレイネットワーク
12.6.3 ハイブリッドゴシップ
12.6.4 部分的なビュー
12.7 まとめ
13章 分散トランザクション
13.1 アトミックに見せる操作
13.2 ツーフェーズコミット
13.2.1 2PCにおけるコホートの障害
13.2.2 2PCにおけるコーディネータの障害
13.3 スリーフェーズコミット
13.3.1 3PCにおけるコーディネータの障害
13.4 Calvinによる分散トランザクション
13.5 Spannerによる分散トランザクション
13.6 データベースパーティショニング
13.6.1 コンシステントハッシュ法
13.7 Percolatorによる分散トランザクション
13.8 調整の回避
13.9 まとめ
14章 合意
14.1 ブロードキャスト
14.2 アトミックブロードキャスト
14.2.1 VirtualSynchrony
14.2.2 ZookeeperAtomicBroadcast（ZAB）
14.3 Paxos
14.3.1 Paxosアルゴリズム
14.3.2 Paxosにおけるクォラム
14.3.3 障害シナリオ
14.3.4 Multi-Paxos
14.3.5 Fast Paxos
14.3.6 Egalitarian Paxos
14.3.7 Flexible Paxos
14.3.8 合意の汎用ソリューション
14.4 Raft
14.4.1 Raftにおけるリーダーの役割
14.4.2 障害シナリオ
14.5 ビザンチン合意
14.5.1 PBFTアルゴリズム
14.5.2 リカバリとチェックポイント
14.6 まとめ
第Ⅱ部 むすび
付録A 参考文献
索引