Open2022/02/17にコメント追加4

詳説データベース

プラハの社長 2022/02/10に更新

データファイルとインデックスファイルの話

データファイル

実際にデータレコードが保存されているファイルのこと

データファイルの種類

ヒープファイル:特に並べ替えなく順番に追加されていく
ハッシュファイル:キーに基づいて整理される
インデックス構成表:インデックスの中に直接データレコードも書いてある

全部インデックス構成表でよくね？

ヒープテーブルがいらないから容量節約できるし、PKで検索するときも効率的。全部これでよくね？と思ったらここでセカンダリインデックスを作成した時のデメリットが言及されていた（日本語版は真逆のことを書いてるのでちょっと混乱した）
- インデックス構成表に保存されたデータは物理的なアドレスが変化しうるため（インデックスの順序を保証するために）、セカンダリインデックスから論理的ポインタでしか参照できない。なのでセカンダリインデックス->PKのクラスタインデックス->じつデータ、といった経由テーブルが増える
- uuidをpkに使うとセカンダリインデックスの容量が増える〜という話は、プライマリインデックスのキーが間接的に参照として使われているから
- サービスの読み書き頻度に応じてどちらを採用するか決まってきそう

Bツリーに関する話

二部探索木(BST)が原型。BSTはツリーが高くなりがちなので1つのキーに含めるポインタを増やしてツリーの高さを抑えている
（概念的には）キーとポインターで構成されていて、キーの範囲で分割されたサブツリーに対するポインタを持っている
- リーフノードは隣接する兄弟ノードに対するポインタを持つこともある（範囲検索の効率化のため）
リーフノードには多少空き容量を持っておくことでデータ追加・更新時の過度な再構築を防げる
時系列的にランダムに追加されると再構築が走りやすく、かつノードの使用率も下がってしまう
ノードの使用率が一定を下回るとマージが、一定を上回ると分割が行われる

ファイル形式に関する話

メモリよりディスクに保存するときの方が考慮すべき項目は多い
- シリアライズ/デシリアライズ方法(バイト配列への変換)
- ファイル構造
  - ファイル内の構造は概ね「ヘッダ(1)」「ページ(N)」「トレーラ(1)」に分割される
  - 固定長フィールドをファイル前半に持ってきて可変長を後半に持ってくる
    - textを無闇に使わない方が良い理由になりうるんだろうか？そこはストレージエンジンが吸収する？
  - ルックアップテーブルが別のファイルに作成されることもある
  - ファイルはページに分割される。bツリーの場合ページ構造は概ね「pointer」「key」「value」
  - ノードとページは概ね対応しているが複数ページでノードを表現することもある
    - ページサイズはfsのブロックサイズに依存して大体16kbまで。可変長のレコードを管理しているときとか、複合インデックスのカラム指定を増やしすぎると1ノードが複数ページに及ぶこともありそう

プラハの社長 2022/02/14に更新

試しにdockerで立ち上げたテーブルの実ファイルをcatしたがバイナリにシリアライズされていたので文字化けしてた(*.ibdファイル）。stringsで表示したけど見てピンとくるものではなかった。ただ実態がこういうファイルだと意識できるのは良い
myisamみたいに.mydとか.myiファイルに分割されていない。これだけをみてinnodbはインデックス構成表を採用しているとは言い切れなさそうだけど、ストレージエンジンによって実ファイルの形式に違いがあることはわかった
- 公式を見る限りpkでクラスタインデックスを自動的に作成する、とのことだったからインデックス構成表で合ってそう

ファイル形式の話（続き）

固定長レコードの格納は比較的楽。k,v,p（ポインタ）を追加していくだけ。右端に追加するのが一番楽だけど
可変長レコードは大変。要素を削除した時に空いたスペースが使われないまま残ってしまうことを避けたい。ページをスロット化することで無駄な領域が生まれないようにすることが多い。postgresのドキュメント
スロットは「ヘッダ」「実データへのポインタ」「実データ」「特殊領域」に分かれていて、特殊領域はbツリーなら兄弟ノードへのポインタなどを持つ
ポインタとデータを分けておくことで、データは常に右端に追加していくだけで、ポインタさえ並び替えればソートを維持できるようにしている。

チェックサム

書き込み時に（ファイル単位ではなく）ページ単位でチェックサムを計算しておいて、読み込み時に比較することが多い。不一致したら読み込みは行われない
- ファイル単位だと単位が大きすぎるので1ビットの誤差しか検知できないチェックサムには不向き

プラハの社長 2022/02/15に更新

bツリーの実装

ページヘッダに何が含まれているのか

兄弟ノード（実装次第）。これがないとルートまでたどらないと兄弟にたどり着けない場合もあるため。ただしスプリット/マージ時にポインタを更新しなければいけないノードも増えるのが短所
ノード毎のポインタの数はセパレーターキー+1になる（1,5,10みたいなセパレーターキーがあれば、１より小さい、10より大きいポインタが存在するため）
- 一番右端のポインタが時々ヘッダに格納されることもある。sqliteが一例らしい
オーバーフローページに対するポインタ
- ペイロードがページに格納できる上限を超えた場合は複数ページに分割される。新規追加されたページはオーバーフローページと呼ばれ、これに対するポインタがヘッダに格納される
- ファンアウトの値、つまり各ノードがいくつの値を保持できるかは固定値になっていることが多い
- 日頃から気軽に使っているdbもアプリケーションロジックの塊なんやなぁ・・・と再認識
参考資料

スプリット/マージの伝播

子をスプリットした際に親にキーを追加したり、それにより親をスプリットする必要が生まれたりする
そういう伝播を効率的に実施するため、親に対するポインタを持つ、パンくずリストを持っておく方法がある
bツリーの変更は常にボトムアップで行われる（リーフに挿入してからスプリット/マージが上位に伝わっていく）

リバランシング

利用率が高いノードから低いノードへデータを渡すことがある
利用率が高ければ木の高さが低くなって検索時間が短縮されるため

最右端は少し特別

キャッシュしておくらしいので、autoincrementな性質を持つキーなら経路探索をすっ飛ばせる
利用率も高くなる
一斉にデータを追加するバルクロード時にも最右端に追加するだけなら楽ちん

デフラグ対応

データを削除したとき、厳密にはポインタを削除しているだけでセルが即座に解放されるわけではない
- 他のトランザクションから参照できてしまうのはおそらくポインタの番地、指定されたセルの値をトランザクションの中でキャッシュしているから？
連続したセル領域を確保する必要があるため、定期的にガベージコレクションしている（プログラミング言語と似てる）

プラハの社長 2022/02/21に更新

トランザクション

定義：システム動作の分割不可能な論理単位
コミットの説明が「トランザクション中に実行された書き込み操作による変更を全て可視化します」って書いてあるのが面白いなと思った。反映はされている、可視化されていないだけ、っていう
- 情報としては存在するけどポインタが登録されていない、みたいなイメージなんだろうか
トランザクションマネージャ
ロックマネージャ
ページキャッシュ
- 大事なポイント：読み書きのたびにdisk I/Oが起きているわけではない
- 全ての変更はまずここに適用される。まだストレージには書き込まれていない
- ディスクに対する変更をページキャッシュでバッファリングする役割も
- ディスクに書き込む　→ フラッシュ、ディスクから読み込む　→ ページイン
- OSレベルでも似たような仕組みがあるが、カーネルページキャッシュを飛ばして直接ディスクにアクセスすることも可能。多くのdbはそうしているらしい(O_DIRECTフラグ)
- 更新されたページはダーティページとしてフラッシュする必要があるが、都度フラッシュしているとパフォーマンスが劣化するためまとめてバックグラウンドプロセスに任せる仕組みもある
ログマネージャ
- ページキャッシュにはストレージには存在しない操作の履歴を保持しておく
- クラッシュ時には操作を再適用してページキャッシュをクラッシュ前の状態に戻す（あるいはロールバックの時にundoする）
- クエリキャッシュとは別物なので注意
- mysqlだと物理メモリの8割程度が割り当てられているらしい。でかい！
ページのロック
- ページキャッシュをロックすることを「ピン留め」と呼ぶ
- bツリーは上位ノードほど頻繁に参照される（キャッシュしておく価値がありそう）
- 上位レベルは情報量も少ないためメモリに常駐させておいて差し支えない
- postgresの挙動
ページの置換
- ページキャッシュがサイズ上限を超えたらページを入れ替える必要があるが、適切なアルゴリズムを選ばなければいけない
  - FIFOはどうか？→ツリー上部から先に読み込まれるのでツリー上部が先に退避させられることが多く、あまり適切とはいえない
  - LRUはどうか？ →アクセスされるたびにキューの末尾に戻されるのでマシだが、参照のたびに更新が行われるため最適とまではいえない

分離レベル

スナップショット分離を使用するデータベースがある
- 複数のトランザクションが同じ値を更新しようとしたら片方をロールバックする
- しかしこれでは防げないアノマリーとしてライトスキューが挙げられる
  - ライトスキューでは複数のトランザクションがそれぞれ異なる値を更新する時におき得る。例えばV1とV2をそれぞれのトランザクションが個別に更新してV1とV2の合計値によってロジックが変化する場合、片方の値の更新は反映されていないため
  - serializableならこういうエラーは起きない（片方のトランザクションによって更新された値がもう片方のトランザクションに可視化されるため）

楽観的同時実行制御

「楽観的同時実行にはクリティカルセクションが存在します。このセクションには1つのトランザクションしか入れません」とはどういう意味か
- 並行処理を行う際に複数の処理から同時にアクセスされるべきではない領域をクリティカルセクションと定義する。楽観的同時実行は読み取りと書き込みが同時に行われると破綻する（書き込みが先か後かで挙動が変わる）ためクリティカルセクションが存在する
- なのでこの部分だけは並行処理できないことがある
- あるいは排他的な所有権をいくつかの操作に許容する、とある通り、readers-writer-lock（読み取りなら複数の処理から共有ロックだけで可能だけど書き込みの際は排他ロックが必要）を使う必要がある

MVCC

mysqlのinnodbとかはこれだったはず
更新が発生した際にオリジナルデータを直接更新するのではなく、同じデータの複数バージョンを保持しておく。トランザクションの分離レベルによってどのバージョンを参照できるかが異なる
現在のトランザクションidやtsを見ながら、どのバージョンまで見て良いか判断する
postgresもmvccで、定期的に古いバージョンを自動的に削除してくれる。あるいはvacuumで削除できる
新しい値がコミットされるまでは古いバージョンの値を読み続けるので同時実行制御が可能
「トランザクションマネージャーの目的は、その時点において最大でも1つの未コミットの値を持つことです」とはどういう意味か
- イメージ的には、トランザクションをコミットすると今のトランザクションidのバージョンが保存される
- それより小さいトランザクションidを持つトランザクションの場合はそれを読めないイメージ
- まだコミットされていない値を（ロールバックするかもしれないので）各データにつき1つは保持しておかなければいけないよね...ってことを言っている？
MVCCの主要なユースケースの1つはスナップショット分離とのこと。前述のスナップショット分離には複数バージョンの管理が欠かせないため

悲観的同時実行制御

2種類紹介されている。tsベースとロックベース

タイムスタンプを使った排他制御

T1がある値の読み取りを実施したら、その値のmax_read_timestampが更新されるイメージ（max_writeもある）
T2が読み取りを試みた時のtsがmax_write_timestampより古い場合は処理が中断される。すでに新しい値が存在するため
T2が書き込みを試みた時のtsよりmax_read_timestampの方が新しい場合も処理が中断される。すでに他のトランザクションが読み込んでいるため

ロックベースの排他制御

二相ロックがよく使われる
- なぜ二相と呼ばれるの？
  - ロックの獲得と解放が2つのフェーズで行われるから
  - 必要なロックを段階的に獲得してコミットと同時にリリース→厳密な2相ロック
  - 必要なロックを最初に獲得する→保守的な２相ロック
    - こちらは同時実効性が著しく制限されるのであまり採用されないらしい
    - 保守的ロックよりはデッドロックを検知するアプローチの方が好まれる
デッドロックの検知は待ちグラフを使うことで検出することが多い
- どのトランザクションがどのトランザクションのロック解放を待っているかを管理しているグラフで、循環参照が見られたらデッドロックが起きているとみなせる
- ちなみに循環参照の検知は、こんなふうに「すでに見た値」を配列に保存して再起処理することで検知できるらしい

ロック

ロックは「それが存在しているかどうかにかかわらず」特定のキー又は一定範囲のキーを保護できます、とはどういうことか
- ネクストキーロックのようなものを指しているのかな・・・？
ロックはツリーの外部で保持及び管理される上位レベルの概念であり、ロックマネージャによって管理される
- ロックとトランザクションマネージャは別物、ちょいちょい混合されがちなので注意が必要

ラッチ

ストレージレベルの物理的な保護に関する機能。リーフページの再編成（スプリットとかマージとか）と他のトランザクションによるCRUDが並列に処理できるように
ドキュメントでも見たことないから存在を今まで意識したことがなかった