1. 介紹#
如何存儲：
- 我們的 pages 要存儲在 disk 上的什麼樣的地方
快速操作：
- 對於 DBMS 來說，在進行操作數據之前需要將所有的數據從 Disk 先轉移到 Memory 中才可以進行操作。
2. 鎖與閂#
3. 緩衝池#
Memory 中存儲的是一個個固定大小的 pages。
其中的每一個記錄稱之為 frame
當我們需要一個 page 的時候，我們會立刻複製一個 frame。
Dirty pages 不會立刻寫回。(Write-Back Cache)
緩衝池元數據#
page table 是用來跟蹤哪些 pages 在 memory 中。
通常還有一些信息也會被保存在 page table 中
- Dirty Flag
- Pin/Reference Counter
Dirty Flag 用來表示這個頁是否被寫過。
Pin/Reference Counter 是用來固定 frame 來確保該頁面不會被放回到 disk 中。
page directory 是一個將 page id 映射到 page location 的一個映射。所有信息必須存放在 disk 上，以便 DBMS 可以找到。
page table 是一個將 page id 映射到 buffer pool 中的幀上的映射。這是一個 in-memory 的數據結構不需要存儲在 disk 上。
記憶體分配策略#
全局策略
- 為所有的操作負責，確保全局最優
局部策略
- 僅僅考慮當前的查詢的效率而不考慮其對全局的影響
4. 緩衝池優化#
多個緩衝池#
通常 DBMS 不總是僅僅有一個 buffer pool
DBMS 維護多個 buffer pool 是為了多種目的 (i.e per-database buffer pool, per-page type buffer pool)。然後每個緩衝池可以針對每個存儲在其中的數量進行定制本地策略。
主要有兩種方式訪問不同的 buffer Pool
- Object id
通過 Object Id 來識別不同的 buffer pool
- Hashing
通過 hash page id 來識別不同的 buffer pool
預取#
DBMS 可以基於查詢提前交換頁面，特別適用於
- 順序查詢
- 索引查詢
查詢到 page1 的時候 buffer pool 就將接下來需要解析的加載到 buffer pool 中
同樣是可以提前加載
掃描共享（同步掃描）#
通常發生在多次查詢同一個東西的時候。
如果第一個查詢一張表，不久之後第二個也在查詢同一張表，那麼最終的情況會第二個查詢會和第一個查詢進行同步查詢。在第一個查詢結束後，第二個查詢會補查漏掉的數據。
在 Q1 查詢到了一半的時候 Q2 也執行了同樣的查詢
由於 Q1 已經查詢了一段距離，在 Buffer pool 中重新載入 page0 是非常浪費的。那么我們可以和 Q1 一起查詢。
在一起查詢結束之後我們再去查詢 Q2 剩下來的 page0-page2
如果啟用這種策略進行查詢到的話，那麼最終的結果可能是不同的。因為我們的查詢是無序的。對於一個順序十分重要且確定的結構中，一般不會採用這種方式進行查詢。
緩衝池旁路#
對於一些操作可能不會存儲在 buffer pool 中，這樣可以減少開銷。
5. OS 頁面緩存#
在 DBMS 中通常不會直接採用 OS 的的文件管理。
- 減少 pages 的多次拷貝
- 減少 page 的退出策略
- 加強對 I/O 的控制
6. 緩衝替換策略#
當 DBMS 需要將 buffer pool 裡的 frame 給清除了，需要決定就近是哪些頁退出。
所以 Buffer Replacement Policies 就是關於清除 frame 的算法。
它的主要目標是
- 正確
- 一致
- 速度
- 元數據的開銷
最少最近使用（LRU）#
維護一個時間表來記錄哪個 page 是最後被訪問的，在需要置換 frame 的時候，將最後被訪問的頁面給置換出去。
時鐘#
clock 算法是 LRU 的一種近似的產物。它的好處是不再需要一張時間表來記錄各個 pages 了，而採用 bit 的形式記錄。
Clock 是，將所有的頁面以某種順序進行記錄，並且該順序是首位相連的。初始時，將所有的頁都標記為 0 ，在某個頁訪問的時候，將該頁的 bit 標記為一。在尋找需要置換的頁面時，也將順序的找下去，如遇到 page 的 bit 為 1 那麼就將該 bit 置為 0 ， 如果該頁的的 bit 為 0 ，那麼則將該頁置換下去。
page_id clock_page() {
static page_id ref = 0;
for ( ; ; ref ++ ) {
if(ref >= BUFFER_POOL_SIZE) ref = 0;
if (bit[ref])
bit[ref] = 0;
else
return ref;
}
return -1;
}
替代方案#
不管是 LRU 還是 CLOCK 都對 sequential flooding 操作影響較深。
- 一種順序查詢所有頁的操作
- 這種操作僅僅執行一次，並且不會再次進行訪問
這就會導致一種結果，Buffer pool 裡面存儲的數據不會是接下來需要用到的數據。
為了減少這種情況的發生我們通常會採用 LRU-K 來進行置換。
追蹤每個頁面的最近 K 次訪問。DBMS 根據這個記錄來確定訪問優先級。
髒頁#
對於非 Dirty Page 而言，只需要將 page 丟掉即可，而 Dirty Page 則需要寫回到 disk 上以保持持久性。
為了避免這一現象，有一種策略是通過周期性掃描 buffer pool 中的 dirty pages 並將其寫回 disk 中，這樣就可以較為安全的移除 dirty pin flag 。