# 詳説 データベース ―ストレージエンジンと分散データシステムの仕組み
# Info
- 書名: 詳説 データベース ―ストレージエンジンと分散データシステムの仕組み
- 著者: Alex Petrov
- 読んだ日付: 2021/12-
# Motivation
データベースの内部構造、分散システムについての理論を理解するため。 学科同期とゼミ形式で取り組んだ。
# Contents
# 第1部イントロ ストレージエンジン
- ストレージエンジンとは
- DBMSのソフトウェアコンポーネントの1つであり、基盤。この上にスキーマ・クエリ言語・インデックス・トランザクション、などの多くの機能や概念が成り立つ
- エンジンとそれ以上のレイヤを分離することで、異なるエンジンを使い分けることができる。
- データベースの比較
- 定義しておくべき変動要素
- スキーマとレコードサイズ
- クライアント数
- クエリのタイプとアクセスパターン
- 読み取りクエリと書き込みクエリの比率
- これらの要素の予期される変更
- これによって、
- そのDBでは必要なクエリはサポートされている？
- 想定したデータ量を扱える？
- 読み取り・書き込み操作を単一ノードでどれくらい処理できるか？
- 複数ノードにする場合、いくつ必要？
- サービスなどの成長率から、クラスタをどう拡張していくか？
- メンテナンスは？
- などを明らかにする。
- テスト(負荷試験)
- スループット
- 定義しておくべき変動要素
- トレードオフ
# 1. 基本事項の紹介と概要
- DBMSのアーキテクチャ
- クライアント・サーバモデル
- query processor
- query parser
- query optimizer
- execution engine
- remote execution
- local execution
- storage engine
- transaction manager
- lock manager
- access method
- buffer manager
- recovery manager
- メモリベース・ディスクベース
- メモリベース: データの殆どをRAMに保持
- ディスクベース: データの殆どをディスクに保持
- RAMのほうが圧倒的に早い
- RAMはOSのメモリ管理の抽象化の上で考えられるので単純
- RAMは揮発性->永続性の欠如とコスト
- RAMはディスクより高価
- 列指向・行指向
- 行指向: レコード単位でアクセスするのに有利
- 列指向: 列ごとに効率的なクエリを可能にする(e.g., ある属性の平均値)
- ワイドカラムストア: 行キーに対して複数の列ファミリを持つ。
- ファイル構成
- ストレージの効率性
- アクセスの効率性
- 更新の効率性
- の実現のためにわざわざ特殊な構造を取っている。
- DBMSでは通常、データファイルにデータレコードを格納し、インデックスファイルにレコードメタデータを格納。metaなデータを使って検索。
- 通常、削除は明示的にはせず、マーカー(tombstone)を付けるだけ。ガベージコレクションの際に回収される
- データファイルの実装
- ヒープファイル
- インデックス構成表(IOT)
- ハッシュファイル
- インデックスファイルの実装
- データファイル無いの場所にキーをマッピングする
- Primary Key Index: ユニークで明示的なキー(recordに対して一意) vs ファイルオフセットを使用して直接行う
- buffering, immutability, ordering
- buffering
- データをディスクに書き込む前に一定量のデータをメモリ内に収集するかどうか
- immutability
- ストレージがデータファイルを変更できるかどうか。
- ordering
- ディスク上のページにデータレコードをkeyの順序で格納するかどうか。スキャンの効率性に関する定義。
- buffering
# 第2部イントロ 分散システム
- 水平スケーリング
- 多数のコンピュータを論理的には1つの実体であるかのように見せる
- 用語
- 参加者(Process, Node, Replica)
- 状態(State)
- Link
- Messageを交換
- Clock
- 論理的/物理的
- 参加者(Process, Node, Replica)
- 動作
- 調整
- 複数ノードの行動及び振る舞いを管理
- 協調
- 複数ノードが相互依存しながらタスクを行う
- 散布
- 関係する参加者に情報を広める
- 合意
- 複数プロセス(ノード)の間で合意(Consensus)を取る
- 調整
# 8. 基本事項の紹介と概要
分散システムと並行コンピューティングの相違点
- 分散システムではそれぞれのノードはローカルな場合を保ち、通信によりメッセージを交換。
障害モデル
- 分散システムでは障害の定義は非自明。まずは障害とはどのように起こるかを定義。
- 冗長性とバックアップDBの追加
- 複数のコピーをどう同期させるか？
何を信頼するか、どのように仮定を置くか
- https://ably.com/blog/8-fallacies-of-distributed-computing
- latency is not zero
- connection can be disconnected
- bandwidth is limited
process
- process内処理は待ち時間がかかる
- 各プロセスの処理性能は異なる
- キューの容量は有限
クロック
- Remoteのクロック同期は困難
- プロセス同士の時差、処理にかかる時間を考慮
- 連続値と離散値の限界
stateのconsistency
- プロセス間で状態が一貫しているとは限らない。
分散システムの抽象化
- Fair-lossリンク
- 送信側と受信側が両方とも正常で、送信側が際限なく何度もメッセージを再送信続ける->いつかは配信される。
- 有限重複
- 送信されたメッセージはいつかは配信される。無限回送ることはない。
- リンクはメッセージを生成しない。(途中でメッセージが生まれることはない)
- UDPのような。
- 確認応答(ACK)
- 送信側が、相手が受信したことを知る手段
- M(n)が受信サれると、送信側にACK(n)というメッセージを送る
- メッセージの再送
- ACK以外の手段として、送信側がひたすら再送信すれば確実にメッセージを届けられる。
- が、重複排除が必要
- メッセージの順序と重複
- シーケンス番号の順にメッセージが届くかどうかは保証されない
- n_consecutive := 届いたメッセージの最大のシーケンス番号 -> 順序ソートに使う
- n_processed := 処理済みとなったメッセージの最大のシーケンス番号 -> 重複排除
- これらにより、perfect linkを実現。
- 信頼できる配信
- 重複なし
- 生成なし
- TCPのような。
- exactly-once: 厳密に一回の配信
- at-least-once: 少なくとも一回(~TCP) vs at-most-once: 多くとも一回(~UDP)
- at-least-onceはexactly-onceではないが、重複排除をすることで擬似的にはexactly-onceになってる！
- Fair-lossリンク
2人の将軍の問題
- リンクの障害が存在していて、通信が非同期の場合には、2つの集団の間で同意をとることは不可能
- ACKのACKが届いたかわからない。いつまでたっても次のACKが必要になり、ストールする。
FLPの不可能性
- FLP
- 同意性: 全てのプロセスで同じ値を決定する
- 妥当性: 決定される値はいくつかのプロセスから提案される
- 終了性: 障害がない全てのプロセスが値を決定すると終了する
- FLP
システムの同期性
- 分散システムは同期的だとみなしてよく、タイミングの概念を導入して議論する。
障害モデル
- Failureの定義をする必要がある
- クラッシュ障害(crash faults)
- プロセスがクラッシュする。
- 実行されるべきアルゴリズムが途中で停止
- !本書はこのクラッシュ障害を仮定して冗長性を導入することで障害を回避しようとするアルゴリズムを考える。
- 欠落障害(omission faults)
- 他の参加プロセスとの間でメッセージが欠落、ネットワークの切断・スイッチの障害など
- プロセス同士の関係がfailure
- 欠落障害(omission faults)
- 任意障害(byzantine faults)
- ソフトウェア自体のバグ、バージョンの違い、など。