【技術本】詳説データベース
【技術本】詳説データベース
https://amzn.to/4nRvdV6
【技術本】詳説データベース
へポスト
データベースの内部実装の詳細を解説してくれている一冊。
前半は、従来のHDDを利用したデータベースにおける、ストレージのファイルフォーマットを考慮したCRUDの管理方法から、データベーステーブルにおけるBツリーなどのによる検索最適化の実装例や、ページキャッシュ（バッファ）の仕組み、トランザクション同時実行制御などが基本設計書レベルの粒度で記され、実装をイメージすることができる。さらに、従来のHDDに加えSSDに最適化を想定したデータベース、インメモリDBなども紹介され、SSDのストレージ特性と調和のあるイミュータブル（追記型）のLSMツリーにおけるデータ書き込み、検索効率化のための実装内容にも言及してくれており、データベースアーキテクチャの進歩を俯瞰することができる。
後半は、データベースの分散処理に言及してくれている。いくつかの分散処理のアーキテクチャを例に挙げ、調停方法のアルゴリズムや、ノード障害やネットワーク障害時の対処や問題点、CAP定理に基づくレプリケーションノードにおけるデータレスポンスのトレードオフなどを解説してくれている。
システム開発などで、ほぼ実装はブラックボックスに近くザックリした仕様特性で何気なしに選定して利用してたデータベースであるが、本書を読むことでかなり踏み込んだ実装内部の仕組みが見えてくる。これにより、今後のデータベース選定においても、利用するハードウェアや環境（分散環境）、アプリケーション特性を考慮して、データベースの実装特性と調和した選定をするために考慮すべき知見や観点を多く学べる著作だと感じた。
ーーーーーーー
以下内容メモ
第一部：ストレージエンジン
１章：基本事項の紹介と概要
メモリベースDBMS
ディスクより高速アクセスが可能
システムクラッシュ、電源断でデータが失われる
> バックアップをディスク上に格納して永続性の実現：全てのDBが永続性の保障をしているわけでない
バックアップはI/O回数削減のため、バッチ処理
OSによってメモリ管理が抽象化
ディスクベースDBMS
データ参照、シリアライズ、フォーマット、解放領域管理、フラグメンテーションを手動で管理が必要
***インメモリDBMSと大量量のページキャッシュを持つディスクベースDBMSと同等と言うのは公平な意見ではない。
ページがメモリ内にキャッシュされていたいとしても、シリアライズのフォーマットとデータレイアウトによって追加のオーバヘッドが発生する。
よってインメモリのデータストアで達成可能な最適化と同じレベルには達しない
チェックポイント処理
ログレコード（データ更新内容をシーケンシャルで書き込まれたもの）はバッチ処理でバックアップに適用される。これが終了すると、特定の時点のデータベースのスナップショットがバックアップによって保持され、これまでの時点のログ内容は破棄できるようになる。これをチェックポイント処理という
1.3 列指向DBMSと行指向DBMS
行指向：
行単位でデータにアクセスする場合に有用：行全体を格納。
行ごとに隣接して格納
しかし、特定列アクセス（たとえば電話番号列のみアクセス）の場合は、すべての列が含まれているのでコストが高くなる。
列指向：
垂直指向＞列単位で複数行をまとめている。
同じ列の値が、ディスク上で隣接して格納される。
列ごとの効率なクエリが有効になる。クエリの対象にならなかった列の破棄が不要
集計処理などの分析的なワークロードに適す。
DBMSでは、データファイルと、インデックスファイルは分けられている
データファイル：データレコードを格納
インデックスファイル：レコードメタデータを格納
最新のストレージシステムでは、レコード削除時に、データをページから明示的に削除はしない。削除マーカーで印だけつけて、ガーベージコレクションの際に回収される
データレコードの順序が検索キー順に従っている場合、このインデックスはクラスタ化されているという。
データの参照方法：
ファイルオフセットとして直接扱う
＞ディスクシーク回数を削減できる
＞メンテナンスプロセスの間にレコードが更新されたり再配置されるとポインタを更新する必要がある。
プライマリキーインデックスを介して行う
ストレージエンジンの共通した変動要素
・バッファリング
ディスクに書き込む前に、一定量のデータをメモリ内に収集する
・ミュータビリティ（可変）、イミュータブル（不変）
ストレージ構造がファイルの一部を読み取り、それらを更新し、更新の結果をファイル内の同じ場所に書き込むかどうかの定義
＞イミュータブルは変更不可なので、追記のみ
コピーオンライト：変更済みのページは、レコードの更新された
バージョンを保持したたままで、ファイル内の元の場所でなく、新しい場所に書き込まれます
・オーダリング
ディスク上のページ、データレコードをキーの順序で格納するかどうかを定義
ソートされた結果で、近くのキーたちがディスク上の隣接したセグメントに格納
一定範囲のレコードを効率的にスキャンできるかも定義される。
２章：Bツリーの基本
・二分探索木
ツリーのバランシング：一部だけ長すぎるツリーは、線形探索に近くなってしまう
バランス：高さがlog2Nであるツリー
１６個のノード 16＝long2 4 (2^4)
バランスのとりかた：回転ピボット
5 3
3 ->(３を中心に右回転) 2 5
2
ディスク向けの実装に適したツリー
・大きなファンアウト（ノードに許容される子の制限数）で隣接するキーの局所性を改善
・ツリーの高さを低くたもち、ノードをたどる時のシークの回数を削減
ディスクベースの構造
・データ量が多すぎてデータセット全体をメモリ全体に保持できない時などにディスク上のデータ構造は利用される。任意の時点でメモリにキャッシュできるデータは一部
従来は、ディスクが回転するHDDに最適化したアルゴリズム
ランダムアクセスは、ディスクシークでコストが増大する
そのかわり、シーケンシャルアクセスは効率的
近年は、フラッシュドライブなどが登場して、新たなアルゴリズムも出る
SSDには、HDDのヘッドなど可動部分がない。
変更が加えられるのは、空白のメモリセルのみ。
空白ブロッックの含まれる複数のページには、シーケンシャルな書き込みがされる
SSDの場合、ランダム、シーケンシャルI/Oの違いがあまり強調されない
ディスク上の構造
ディスクの最小単位がブロック
＞レコード業が含まれていても、ブロック全体を取り出す必要がある。
Bツリー
データはソートされている＞二分探索などのアルゴリズムが利用可能
約４０億のなかから検索対象キーを検出するのに約３２回の比較が必要
Bツリーのノードには数十〜数百の項目が格納＞この１レベル移動ごとにディスクシークのオーバヘッドがかかる。
ノードのファンアウトを大きくすることで、ツリーのバランスを保つための必要な変更コストを削減。
子ノードへのキーやポインタを単一ブロック、または連続した複数ブロックに格納して、シーク回数を減らす。
バランシング（スプリット、マージ）は、ノードが満杯、または空の時に行われる
計算量 logkM k個のノードファンアウト数、M：項目の総数
*二分木はlog2N
分割とマージ
分割：ノードに登録できる項目数がオーバフローした場合
マージ：隣接したノードに保持されている値がわずかな場合
つまり、それらの利用率が閾値を下回った場合アンダーフローと呼ばれる
３章：ファイルフォーマット
データをディスク上に効率的に格納するには、コンパクトで容易に
シリアライズ、デシリアライズできるフォーマットを使用してエンコードが必要
キー値：integer, data, stringなどの型をもち、バイナリ形式のまま表現可能
多くのデータは固定長の値として表現
マルチバイトの数値を扱うときは、エンコードとてコードの両方に、同じバイトオーダー（エンディアンネス）を使用することが重要
エンディアンネスのバイト並び順
・ビッグエンディアン：最上位バイトから始まり、上位から下位へバイトが続く
・リトルエンディアン：最下位バイトから始まり、下位から上位へバイトが続く
レコードは数値、文字型、ブール値のプリミティブ型とそれらの組み合わせ
ただし、ネットワーク上でデータを転送するときや、ディスク上に格納するときは、シリアライズ（解釈可能なバイトの列に変換）の必要がある。
シリアライズとは：構造を持ったオブジェクトには、メモリのアドレスのポインタが含まれるものがある。
これらは、PC固有で有効のアドレスだったりするので、全てのマシンで普遍的に利用できるように明示的なデータ値に変換する。これをシリアライズという。読み取り後に、レコードで使用できるようにするには、デシリアライズが必要
スロット化ページ
可変長レコードの格納時には、空き領域の管理（削除された領域の回収）が主な問題になる。
次のことを可能にする必要がある
・オーバヘッドを最小に抑えながら可変長レコードを格納できる
・削除されたレコードが使用していた領域を回収できる
・実際の配置にかかわらず、ページ内のレコードを参照できる
文字列、バイナリラージオブジェクト(BLOB)などの可変長レコードを効率的に格納にするには、スロット化ページ、またはスロットディレクトリの技術を使う
ページをスロット、またはセルのコレクションに編成し、ページの両端にある独立したメモリ領域にポインタとセルをそれぞれ配置する。
＞順序を維持するために必要なのは、セルをアドレスしているポインタの再編成のみで済む。レコードの削除はポインタを無効、または削除のみで済む
＞領域の回収は、ページのデフラグと書き直しで回収できる。
＞空いた領域は、利用可能領域リストで管理もする
ファーストフィット、ベストフィット方式などで格納
４章：Bツリーの実装
ページヘッダ
・マジックナンバー：ブロックがページを表すことを知らせたりするためのもの
・兄弟リンク：ノード内の同レベルの前後の兄弟ノードへのリンク。ルートから辿らなくても済む
・ノードハイキー：ノード内の扱う値を右ポインタの値を超えないようにする。＞ファンアウト数の制限
・オーバーフローページ：空き領域がなかったデータの残りを格納
Bツリー
・パンくずリスト：どのノードを辿ったかの痕跡リスト
・リバランシング：スプリットやマージなどはコストが多いので、要素を移動させる
・ページのデフラグ：コンパクション、バキューム＞ガベージコレクション
５章：トランザクション処理とリカバリ
ACID特性の実現
ページキャッシュ：永続ストレージとストレージエンジンとの仲介
永続ストレージと同期されていないページのキャッシュとして機能
バッファ管理
低速な永続ストレージ（ディスク）
高速なメインメモリ（RAM）
永続ストレージにアクセスする回数削減のためにキャッシュで利用
ストレージレイヤから再度同じページ要求があった場合は、キャッシュされたコピーを返すようにする。
メモリ内にキャッシュされたページは、他のプロセスがディスク上のデータを変更していないという前提のもと再利用できる＞仮想ディスク
仮想ディスク：ページのコピーがメモリにない場合ディスクにアクセス
同じ概念を表す別名：ページキャッシュ、バッファプール
キャッシュされてないページを読み込む＞ページイン
キャッシュされたページに変更が加えられた場合、これらの変更がディスクにフラッシュして描き戻されるまで、そのページはダーティである
キャッシュされたページの保持されるメモリ領域は、データセット全体より小さい＞ページキャッシュがいっぱいになる＞退避が必要
ページキャッシュの主要機能
・キャッシュされたページ内容をメモリ内に保持
・ディスク上のページに対する変更をまとめてバッファリング
そのキャッシュされたバージョンに対して変更を適用できる
・要求されたページがメモリにない場合は、ページインして返す
・キャッシュされているページ要求は、キャッシュされているバージョンを返す
・領域が足りなくなったら、いずれかのページをディスクにフラッシュして退避させる
バッファに加えられた変更は、最終的にディスクに描き戻されるまで、メモリ内に保持
他プロセスは元のファイルの変更権限がないので、同期はメモリからディスクの一方通行＞カーネルのページキャッシュをアプリケーション特有にしたイメージ
永続性：
データベースがクラッシュした場合、フラッシュされなかったデータは失われる。
フラッシュはチェックポイントプロセスと強調して動作する。
チェックポイント：
ログ先行書き込み(WAL)とページキャッシュを制御し、連携する。
WALから廃棄できるのは、フラッシュされたキャッシュ済みのページに適用された操作に関連するログレコードのみです。ダーティページは、このプロセスが完了するまで退避できない。
トレードオフ：
・ディスクアクセスの回数を減らすために、フラッシュを先延ばし
・迅速な退避を可能にするため、先取りしてページフラッシュする
・退避させるページを最適な順序でフラッシュ
・キャッシュサイズをメモリの制限内に維持
・プライマリストレージに永続されていない時にデータを失うことを防止
キャッシュのロック＞ピン留め
ピン留めされたページは、通常より長い時間メモリに保持することができる。＞ディスクアクセス回数削減
例：Bツリーの上部をメモリに常駐において、下部はノード数が多いのでメモリから除外
ページ置換戦略
FIFO, LRU、CLOCK,LFU,
WAL
コミットされていないデータをログから再現し、クラッシュ前のDB状態に復元
リカバリ
ログファイル：
追記型：変更不可、書き込みはシーケンシャル
WALはログレコードで構成：シーケンス番号を持つ
同期チェックポイント：
全てのダーティページを強制的にディスクにフラッシュするプロセス
＞プライマリのストレージ構造を完全に同期する
フラッシュ処理のポリシ：
steal:トランザクションのコミット前でもフラッシュを許容
no-steal:コミット前はフラッシュを許容しない
force:コミット前に、トランザクションによって変更された全てのページをフラッシュ
no-force:全てディスクにフラッシュされていなくてもコミットを許容
同時実行制御：
トランザクション間の相互作用を処理する
・楽観同時実況制御
・マルチバージョン同時実行制御
・悲観または保守的同時実行制御
直列化可能性
・分離レベル
READ UNCOMMITTED:dirty read, non repeatable read, phantom read
READ COMMITTED: non repeatalbe read, phantom read
REPEATABLE READ: phantom read
SERIALIZABLE:
６章：Bツリーの亜種
各種Bツリーの実装紹介
７章：ログ構造化ストレージ
イミュータブル構造：一度書き込まれたら２度と書き換えられない。その代わりに新しいレコードが新しいファイルに追加されます。>安全性の高さから人気が高まってきている。
整合性はストレージ構造を修正できないという事実によって保証
ストレージ構造の内部：
イミュータブル：複数のコピーを保持でき、相対的に新しいコピーが古いコピーを上書き>ログ構造化マージツリー（LSMツリー）>追記型のストレージとマージによる調停
Bツリー＞ディスク上のデータレコードを探し、ファイル内のオフセット位置からページを更新
書き込み性能に最適化されている
ミュータブル：一般的に最新の値のみ保持
書き込み性能を犠牲にして実現
LSMツリー
イミュータル構造では断片化を避けるためにシーケンシャルにデータレコードを配置できる
>更新されたレコードが最初に書き込まれたレコードより大きな領域を必要とする場合に備えるために、予備領域を確保していくことはない。
ファイルはイミュータブルなので、挿入、更新、削除の操作で、当該レコードを探す必要はない。
>書き込みスループット向上
>読み込みより書き込みが多く行われるケースで役立つ
データファイルとインデックスファイルの線形可能なメモリ内ビューを保持
LSMツリー構造
ソートされたデータレコードがファイルの保持
イミュータブルのファイル内容をディスクに書き出すには、最初にそれらをバッファリングして、内容をソートする必要がある
・メモリ上のコンポーネント＞ミュータブル、データレコードをバッファリング
内容は、そのサイズが設定可能な閾値まで増大した時にディスクで永続化
ここのデータを更新しても、ディスクアクセスは発生しない。I/Oコストも軽微
・ディスク上のコンポーネント＞メモリにバッファリングされている内容をディスクにフラッシュすることで構築される。ディスク上のコンポーネントは読み取りのみ使用される
バッファリングされた内容はディスクに永続化され、決して変更されないそのため、操作を単純化して考えることができる。
＞メモリ上のテーブルに対する書き込み
＞ディスク、メモリベースのテーブルに対する読み込み
＞マージとファイルの削除
２コンポーネントLSMツリーの実装：
・ディスクコンポーネントが一つ：イミュータブルセグメントで構成
Bツリーで構成されている。ノードの使用率１００％で読み取り専用のページを持つ
メモリ上のツリーの内容は部分的にディスクにフラッシュされる
インメモリのサブツリーごとに対応するサブツリーがディスク上に検出され、メモリ上のセグメントとディスク上のサブツリーがマージされた内容が、ディスクの新しいセグメントに書き出される。
サブツリーのフラッシュが終了すると、用済みになったメモリ上のサブツリーと、ディスク上のサブツリーは破棄される。新しくマージしたツリーのみ新たに既存のツリーから検索可能になる。
フラッシュの実装時に重要なこと：
・フラッシュプロセスが開始されたら、即座に新規書き込みが、新規のメモリ上のツリーに向かうようにする。
・サブツリーのフラッシュ中は、ディスク上のサブツリーとフラッシュ中のメモリ上のサブツリー両方読み取りアクセスが可能でなくてはならない。
・フラッシュ後は、マージされた内容の公開、マージされなかったディスク上とメモリ上の内容の内容の破棄がアトミックに実行される必要がある。
マルチコンポーネントLSMツリーの実装
ディスク上のテーブルを一つだけでなく、複数使用する＞フラッシュによってディスクにできた複数テーブルは、コンパクションによって、マージされる。
インメモリテーブル
フラッシュ＞定期的起動、サイズ閾値トリガなどで起動可能
・memtableの切り替えが必要＞新規memtableが割り当てられると、そこが新規書き込み先となる
・古いmemtableはフラッシュ中状態に
この2つのステップをアトミックに行う必要あり。
フラッシュ中のmemtalbeは完了まで引き続き読み込み可能
フラッシュ完了後、古いmemtableは破棄される
更新と削除：
挿入、更新、削除の際に、ディスク上のデータレコードの検索は不要
データ削除は述語削除を使用する。
＊会計伝票の赤伝、黒伝みたいなもの。
マージイテレーション：
memtableとディクス上のテーブルのマージ
最小ヒープなどの優先度付きキューを使用してマージ
調停：
更新、削除などで、同じキーに対するデータレコードが異なるテーブルに保持されている
場合がある。＞調停および競合の解決
タイムスタンプなどの比較で実現
RUM予想：
Read, Update, Memoryの各オーバヘッドを考慮に入れる予想
これらのオーバヘッドのうち２つを削減すると、必然的に３つめのオーバーヘッドが悪化すると言われている。
最適化では、3つの項目のうち、一つを犠牲にした場合のみ可能である
理想：メモリと書き込みのオーバヘッドを抑える一方で、最小の読み込みコストを実現する。＞現実には達成不可能でトレードオフが必要。
Bツリー：読み取りに最適化されている
Bツリーに書き込みするには、ディスク上でレコードを検索する必要があり、同じページに対する後続の書き込みでは、ディスク上のページを複数更新しなければならないことがある。
LSMツリー：書き込み時ディスク検索不要
そのかわり、冗長レコードを格納することで生じるオーバヘッドがある。
デフォルトでは、読み込みにコストがかかる＞完全な結果を戻すには、複数テーブルのアクセスが必要なため
Sorted String Table：
LSMツリーにおける、ディスク上のテーブルの実装
Sorted String Table>SSTable : データレコードはソートされている。
・通常インデクスファイル
・データファイル:レコードキーが順に保持される
からなる。
ブルームフィルタ：
LSMツリーにおける読み込みコストは、ディスク上の複数のテーブルを検索するため
テーブル検索を避ける方法として、そのキーの範囲をメタdー穢多に保持して、検索対象>のキーがテーブルに含まれているかどうかチェックする際に、ブルームフィルタを使用する
>大きなビット配列と複数のハッシュ関数が使用される。
スキップリスト：
ソート済みのデータをメモリ内に保持する手段として、その単純さで注目されている
LSMツリーとSSDは相性の良い組み合わせ：
SSDのシーケンシャルなワークロードと、LSMツリーの追記型の書き込みが、
同じ場所を上書きすることで発生する書き込み増幅を削減するのに有効。
同じ場所上書きは、SSDパフォーマンスに悪影響を及ぼす
--------
第２部：分散システム
８章：基本事項の紹介と概要
9章：障害検出
heart beat：
ping:定期的なpingにおいて、応答が遅延し次のping送信以降に応答がずれ込む＞障害と認知される場合がある。>タイムアウトの慎重な選択に依存
１０章：リーダー選出
ブリーアルゴリズム：プロセスのランクを使用して新しいリーダーを識別
リーダーが変わる時、もっともランクが高いのが次のリーダー
１１章：レプリケーションと一貫性
フォールトトレランス：コンポーネントの障害があっても正しく動作し続けられるシステム＞単一障害点をなくし、冗長を持たせる。通常、冗長性はユーザに透過的
CAP定理：一貫性(Consistency)、可用性(Availability)、分断耐性(Partition tolerance)のトレードオフについて議論したもの
一貫性と分断耐性を備えたシステム：
CPシステムは、一貫性が失われた可能性のあるデータを提供する場合には、リクエストを失敗させる
可用性と分断耐性を備えたシステム：
APシステムは、一貫性の条件を緩和し、リクエストに対し、一貫性が失われた可能性があるデータを提供する。
一貫性モデル：
線形化可能性
逐次一貫性
結果整合性モデル：
今日の多くのデータベース
１２章：アンチエントロピーと情報散布
ブロードキャスト：一つのプロセスから他の全てのプロセスに通知
アンチエントロピー：定期的なpeer-to-peerの情婦交換、ピア同士は互いに接続しメッセージ交換
ゴシップ：連携ブロードキャスト：メッセージを受信したプロセスが、ブロードキャストする立場になる
ブロードキャスト：もっとも単純なアプローチ
ノードが少ない時は十分機能するが、大規模クラスタではコストが高くなる。
一つのプロセスに過度に依存するので、信頼性が低くなる可能性あり。
一部の更新が伝播に失敗することを前提とする。
エントロピー：
システム内の無秩序さの度合いを表す性質。分散システムの場合＞ノードの状態が異なる程度を表す
アンチエントロピー：
初期の配信で障害が発生した場合に、ノードを最新の状態に戻すために使用される。
読み取り修復：
更新が欠落しているレプリカに、欠落している更新を送信＞ブロッキング、非同期操作として実装できる。
ダイジェスト読み取り：
レプリカ同士でハッシュ値を交換して一致していれば同期していると判断
１３章：分散トランザクション
２相コミット
注意すべき障害点
・コミット可否の投票してノードから応答後に、コーディネータがコミッチ送信途中で障害
＞代替ノードがサイド投票してコミットする仕組みが必要
・コミット可否の投票をしてノードから応答後に、コーディネータが障害
＞バックアップ用コーディネータを用意
３相コミット
双方のタイムアウトが追加
提案、準備、コミットor中断の３ステップ
コーディネータ、ノードの障害があっても先に進むことができる。
コーディネータが障害が起きても、ノードが処理を続行
しかし、ネットワーク分断によって、ノードがタイムアウト後にコミットするものや、コーディネータと通信できずに、タイムアウト後動作中断するものが別れ、スプリットブレインに陥る場合がある＞3相コミットが広く使用されない理由
Spanner
Calvin
データベースパーティショニング
ルーティングキーから、ターゲットノードを見つける＞キーのハッシュを計算し、ハッシュ値からノードIDへのマッピングを使用
１４章：合意
ブロードキャスト
アトミックブロードキャスト
Virtual Synchrony
Zookeeper Atomic Broadcast
Paxos
Raft
ビザンチン合意
以上。
へポスト