詳説 データベース

―ストレージエンジンと分散データシステムの仕組み

[cover photo]
TOPICS
Database
発行年月日
PRINT LENGTH
392
ISBN
978-4-87311-954-0
原書
Database Internals
FORMAT
Print PDF EPUB
Ebook
4,180円
Ebookを購入する
Print
4,180円

データベースを選択し、使用し、管理するには、その内部構造を理解することが不可欠です。しかし、今日ではたくさんの分散型データベースやツールが存在するため、それぞれが何を提供しているのか、どのように異なるのかを理解することは困難です。
本書はデータベースとストレージエンジンの内部で利用されている概念を解説します。ストレージエンジンでは、ストレージの分類、Bツリーベースのストレージエンジンとイミュータブルなログ構造化ストレージエンジンの違いと事例を紹介します。ストレージの構成要素については、ページキャッシュ、バッファプール、ログ先行書き込みなどの補助的なデータ構造を使って、効率的なストレージを構築するためのデータベースファイルの構成を説明します。分散型システムでは、ノードとプロセスがどのように接続され、複雑な通信パターンを構築するのかを段階的に学びます。
データベースそれぞれで大きな違いがあるストレージエンジンの内部構造や、データの分散方法を決定するサブシステムについて詳述する本書は、データべースシステムを使ってソフトウェアを構築するすべての人に必携の一冊です。

目次

監訳者まえがき
はじめに

第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 参考文献

索引