目錄

1、介紹

2、緩沖池

3、處理頁面請求

4、LRU替換和時鐘策略

1）順序掃描性能 - LRU

5、最近最常使用替換策略（MRU Replacement）

1）Sequential Scanning Performance - MRU

6、練習題

1）判斷真假

2）LRU、MRU、Clock相關問題

---

1、介紹

我們前面簡略討論了 DBMS 的最低級別如何管理磁盤空間，以及基于頁面的數據庫系統中如何管理文件和索引。現在，我們將探討 DBMS 中這兩個級別之間的接口 - 緩沖區管理器（the buffer manager）。

緩沖區管理器負責管理內存中的頁面，并處理文件和索引管理器的頁面請求。請記住，內存空間是有限的，因此我們無法負擔得起將所有頁面存儲在緩沖池中。緩沖區管理器負責淘汰策略，即在空間填滿時選擇淘汰哪些頁面。當頁面從內存中淘汰或新頁面讀入內存時，緩沖區管理器會與磁盤空間管理器通信，執行所需的磁盤操作。

2、緩沖池

內存通過將空間劃分為頁面可以放置的幀而轉化為緩沖池。一個緩沖幀可以容納與一個頁面相同量的數據（因此一個頁面完美地適應一個幀）。為了有效跟蹤幀，緩沖區管理器在內存中為元數據表分配了額外的空間。

該表追蹤了4個信息：

1. 與內存地址唯一關聯的 “框架ID”
2. 用于確定框架當前包含哪個頁面的 “頁面ID”
3. 用于驗證頁面是否已被修改的 “臟位”
4. 用于跟蹤當前使用頁面的請求者數量的“Pin計數”

3、處理頁面請求

當從緩沖管理器請求頁面并且頁面已經存在于內存中時，頁面的引用計數會遞增，并返回頁面的內存地址。

如果頁面不在緩沖池中且仍有空間，將找到下一個空框架，并將頁面讀入該框架。頁面的引用計數設置為1，并返回頁面的內存地址。在頁面不存在且沒有空框架的情況下，必須使用替換策略確定要驅逐的頁面。

替換策略的選擇在很大程度上取決于頁面訪問模式，并通過計算頁面命中次數選擇最優策略。頁面命中是指可以在內存中找到請求的頁面而無需訪問磁盤。每個頁面未命中會產生額外的IO成本，因此良好的淘汰策略對性能至關重要。訪問模式的命中率定義為#頁面命中次數 / (#頁面命中次數 + #頁面未命中次數)，或更簡單地說，#頁面命中次數 / #頁面訪問次數。

此外，如果被驅逐的頁面的臟位被設置，則將頁面寫入磁盤以確保更新被持久化。如果在內存中對頁面進行更新，則將臟位設置為1。一旦頁面被寫回磁盤，臟位就被設置為0。

一旦請求者完成其工作負載，它負責通知緩沖管理器減少其先前使用的頁面的引用計數。

4、LRU替換和時鐘策略

一個常用的替換策略是 LRU（最近最少使用）。當需要將新頁面讀入已滿的緩沖池時，將淘汰最近最少使用、引用計數為 0 且 "Last Used" 列具有最低值的未固定頁面。為了追蹤頁面的使用情況，在元數據表中添加了一個 "Last Used" 列，用于記錄頁面引用計數減少的最新時間。LRU 是一個有效的策略選擇，因為它會保留常被訪問的頁面在內存中，由于它們經常被訪問，因此很可能是最近使用的。

實現 LRU 通常可能成本較高。時鐘策略提供了一種替代實現，它使用元數據表中的一個 ref bit（最近被引用）列和一個時鐘手變量來高效地近似 LRU。使用 ref bit 可以降低空間和時間成本。只需每個框架一個比特，而不是多個比特來存儲 Last Used 值。在時間方面，緩沖管理器只需跟隨clock hand。在 LRU 中，緩沖管理器必須花費時間搜索 Last Used 列中的最小值。

時鐘策略算法將元數據表視為幀的循環列表。它在開始時將時鐘手設置為第一個未固定的幀，并在將每個頁面最初讀入幀時將其相應行的ref bit設置為1。該策略在嘗試淘汰時的工作方式如下：

1. 遍歷表中的幀，跳過固定的頁面，并在到達末尾時繞回到幀0，直到找到第一個未固定且ref bit = 0的幀。

2. 在每次迭代期間，如果當前幀的ref bit = 1，則將ref bit設置為0并將時鐘手移動到下一個幀。

3. 在到達ref bit = 0的幀時，淘汰現有頁面（如果dirty bit被設置，則將其寫入磁盤；然后將dirty bit設置為0），讀取新頁面，將幀的ref bit設置為1，并將時鐘手移動到下一個幀。

如果訪問當前在緩沖池中的頁面，則時鐘策略將頁面的ref bit設置為1而不移動時鐘手。

1）順序掃描性能 - LRU

LRU 總體上表現良好，但在一組頁面 S（其中 $|S| >$ 緩沖池大小）被多次重復訪問時，性能會受到影響。這種訪問模式稱為順序淹沒，經常在數據庫工作負載中出現，比如在表中掃描每個記錄。

為了突顯這一點，請考慮一個使用 LRU 的 3 幀緩沖池，具有以下訪問模式：

A B C D A B C D A B C D A B C D

5、最近最常使用替換策略（MRU Replacement）

另一個常用的替換策略是 MRU（最近最常使用）。與淘汰最近最少使用的未固定頁不同，MRU 策略淘汰最近最常使用的未固定頁，根據頁面的固定計數最后一次減少的時間來衡量。

1）Sequential Scanning Performance - MRU

起初使用這種策略可能會顯得違反直覺，但考慮一個使用 MRU 的 3 幀緩沖池的訪問模式：

A B C D A B C D A B C D A B C D

顯然，在發生順序淹沒訪問模式時，MRU 在頁面命中率方面遠遠優于 LRU。

6、練習題

1）判斷真假

a. 緩沖池中的每個幀都是一個磁盤頁面的大小。

真。幀的大小被定義為磁盤頁面的大小。

b. 緩沖管理器代碼（而不是文件/索引管理代碼）負責設置頁面的臟位。

假。頁面的請求者（文件/索引管理代碼）設置臟頁。

c. 臟位用于跟蹤頁面的受歡迎程度。

假。臟位用于跟蹤頁面在寫回磁盤之前是否已被修改。引用計數用于跟蹤受歡迎程度。

d. 使用LRU策略時，引用位用于在替換頁面之前為頁面提供“第二次機會”留在內存中。

假。引用位不用于LRU策略。它們用于時鐘策略。

e. 對文件進行順序掃描時，當文件小于緩沖池時，使用MRU或LRU將具有相同的命中率（從空緩沖池開始）。

真。由于我們可以將所有頁面放入內存，因此在順序掃描期間我們不需要驅逐頁面。

f. 頁面的引用計數只能由緩沖管理器遞減。

假。引用計數由請求頁面的人遞減，表示他們已經使用完畢。

2）LRU、MRU、Clock相關問題

對于以下問題，我們有一個初始為空的緩沖池，其中有4個緩沖幀。對于訪問模式：

A B D D E A E C A B C A E

a. LRU的命中率是多少？

b. 當LRU完成時，緩沖池中有哪些頁面？

c. MRU的命中率是多少？

d. 當MRU完成時，緩沖池中有哪些頁面？

e. Clock的命中率是多少？

f. 當Clock完成時，緩沖池中有哪些頁面？

詳細的訪問模式如下圖所示。在 LRU 和 MRU 中，行數對應于緩沖幀的數量，每列對應于一個單獨的訪問，其中字符表示缺失，星號表示命中。

a. 7/13

b. A, C, B, E

c. 7/13

d. E, B, D, C

e. 6/13

f. C, A, B, E

以上，DBS note4：Buffer Management

祝好。