# CMU DB 5. Buffer Pools
tags: CMU DB
授業
復習としてOLTPとOLAPの話
ETL(extract transform load)
今回はDBMSがメモリをどう扱い，ディスクからデータを行き来するように動かすかという問題について扱う
- 空間制御
- 一緒に使われるページをディスク上で出来るだけ物理的に近づけることが目的
- 時間制御
- ディスクからデータを読み込む必要から発生するストールの数を最小化することが目的
Buffer Pool Manager
固定長のページの配列として管理されているメモリ領域を"buffer pool"と呼び，そのような要素の1つを"frame"と呼ぶ．
DBMSはディスクからframeに全く同じコピーを要求する．
ページテーブルは現在メモリ上にあるページを追いかける．また，ページごとの追加のメタデータを補完する．それを"dirty flag"や"pin/reference counter"と呼ぶ．前者は書き込み，後者は現在いくつのスレッドがそのページを読み書きしているかを管理し，使われている場合はメモリから追い出せないようにする．
- Locks
Latches
- Mutex(mutual exclusion)的なもの
- 他のスレッドから守る
- ロールバックが出来る必要はない
page table
- データベースファイルにあるページIDのページの場所への写像
- page directory
- buffer pool frameにあるページIDのページのコピーへの写像
buffer poolは複数持っている．latchの競争を助け，局所性を改善する．
アプローチとしてはobject idとhashingがある
事前に読み込むことでI/Oを減らすことも可能
scan sharingでクエリにデータの再利用が出来る．
buffer pool bypassはオーバーヘッドを避けるためにbuffer poolに取ってきたページを納めない．
大半のディスク操作はOS APIを経験し，OSがファイルシステムのキャッシュを管理してしまう．大半のDBMSは使わないためには直接I/Oを使っている．
Replacement Policies
DBMSがframeを解放して新しいページのための空間を作るときの方針
- 正しさ
- 正確さ
- 早さ
- メタデータのオーバーヘッド
LRU(least recently used)というアルゴリズムを使う．DBMSは最も古いタイムスタンプのページを選んで追い出す．
CLOCKはALUの近似．ページごとにタイムスタンプを必要としない．参照bitを各ページが持ち，ページがアクセスされるとそのbitが1となる．時計回りに一掃し，それが1なら0にして，0ならそれを追い出す．
LRUとCLOCKはsequential floodingという問題がある．全てのページを連続で読み込むクエリではbuffer poolが一度しか読まれず，二度と読まれない．
最近使われたページは実は最も必要のないページ
LRU-Kは最新のK個の参照のタイムスタンプを追い，連続アクセスの間隔を計算する．
localizationはどのページを置き換えるかクエリごとに決める．各クエリのbuffer poolの汚染を最小化する．
priority hintsではDBMSはクエリ実行の間の各ページの文脈を知っていて，buffer poolはページが重要かどうかヒントを出す．
dirty pages
- fast
- buffer poolのページがdirtyでなければ，DBMSは単純にそれを捨てられる．
- slow
- dirtyならディスクに書き戻し，その変化が続くのを保証する．
ページテーブルを定期的に読み，dirtyページをディスクに書く．
Other Memory Pools
実装によるが，DBMSはtuplesやindexes以外のもののメモリ必要とする．
結論
DBMSはOSよりもメモリを上手く管理する．
より良い決定をするためのクエリプランについての意味論を使え．
- evictionis
- allocations
- pre-fetching
感想
後はプロジェクトについて．
プロジェクトどうしようかな...
- clock replacemnt policy
- buffer pool manager
について実装をする必要があるっぽい．
DBMSって今までやってきたことの総復習的な感じがしますね．
txnってtransactionってことか…
