什么是 buffer pool

磁盤管理介紹完畢之后，在來看看內存的 buffer pool 管理的內容。

Buffer Pool 本質上就是一塊共享內存區域，其目的主要是對磁盤上的 page 進行緩存，盡量減少磁盤 IO，提升數據庫系統的性能。

前面講存儲模塊的時候提到過，內存的訪問速度更快，并且磁盤 page 的訪問讀取在時間和空間上具有局部性的特征，所以一次被訪問到的 page，加載到內存之后，有可能被再次訪問，這樣可以避免頻繁從磁盤中加載 page。

buffer pool 對內存區域劃分為了被稱為 frame 的小塊，每個 frame 就是緩存了磁盤的 page 內容。

此外，還需要維護一個 page table，它是一個哈希表，存儲的是 page id 對 buffer pool 中 frame 的一個映射，此外還需要存儲一些 page 的元數據信息，例如 page 是否為臟頁、page 的引用計數等等。

對于 page table 的訪問，一般要保證并發安全，因為在多線程環境下，對于同一個內存中 frame 的讀寫不能同時進行。

PostgreSQL 中對于 buffer pool 的描述及代碼可參考：https://github.com/postgres/postgres/blob/master/src/backend/storage/buffer/README

buffer pool 優化

前面簡要說明了 buffer pool 的基本概念，在實際使用的時候，會針對 buffer pool 進行各種各樣的優化，下面依次介紹常見的幾種。

Multiple Buffer Pool

buffer pool 并不是一塊內存進行劃分，不同的數據庫系統中，有不同的用法。

大多數系統都實現了可以開辟多個 buffer pool，避免多個線程對同一個 buffer pool 的鎖競爭，這樣能夠更大程度上提升數據讀寫的效率。具體的實現可以是多樣化的，例如：

• 創建多個 buffer pool 的實例
• 每個數據庫分配一個 buffer pool
• 同類型的磁盤 page 分配一個 buffer pool

一般有兩種方式來實現一條 tuple 到 buffer pool 的映射：object id 和 hashing。

Object ID 一般可以是一條 tuple 的隱藏列（例如在 PostgreSQL 中叫做 ctid），它主要記錄了 tuple 的磁盤存儲位置。根據這個 object id 就能夠知道我們需要訪問哪個 buffer pool，然后再獲取其中的 page 進行數據讀寫。

另一種 hash 的方式，可以將 tuple 的某些信息進行 hash 操作，然后再定位到某一個 buffer pool上。

Pre-Fetching

prefetch 一般叫做預讀取，例如當進行一個查詢時，如果一個 page 不在 buffer pool，我們需要將 page 加載上來，此時我們可以通過一些預讀取策略，預先將 page 記載到 buffer pool 中，這樣下次查詢的時候，不用讀磁盤，能夠提升整體的響應性能。

以一個簡單的順序掃描來說明，例如下圖中，加載所有的 page 對表進行順序掃描，如果沒有 prefetch 的話，加載一個 page 之后，上層執行引擎處理完畢， 然后再次加載另一個 page，這樣的話每次都會在加載的時候等待 page 加載完畢，效率較低。

如果是索引掃描，葉子節點指向的 page 有可能并不是連續的，但是作為數據庫系統內部，我們可以識別出來，加載想要的 page 到 buffer pool 中（這也是上一篇文章中提到的數據庫系統一般會自己管理內存，而不依賴于 mmap）。

例如下圖，葉子節點的 page 分別是 3 和 5，這樣的話加載的時候就跳過中間不需要的 page。

Scan Sharing

scan sharing 的思路總體來說就是如果一個 query 想要掃描一個表，此時已經有另一個查詢也正在掃描這個表了，那么可以將兩個查詢的操作合并起來，共享同一個 page 的內容。

這個優化在大多數數據庫中都有實現，例如 Sql Server、Oracle、PostgreSQL。

下面是一個簡單的例子，假設有一個查詢需要全表掃描，并且表內容分布在 page 0-5 中，那么它會依次讀取所有的 page 到 buffer pool 中。

此時 Buffer Pool 滿了，根據淘汰策略，在加載 page3 的時候，需要淘汰掉一個 page 出去，這里我們假設淘汰的是 page0。

淘汰掉 page0 后，然后將 page3 加載進來。

如果此時有另一個查詢，也需要對這個表進行全表掃描，在沒有任何優化的情況下，它也從頭開始讀寫該 table 的所有 page。首先它也會去加載 page0，但實際上 page0 剛剛從 Buffer Pool 中被替換出去。

于是一個優化策略是將兩個查詢的掃描指針會合起來，共享同一個 Buffer Pool 中的內容，等到前面的結束之后，第二個查詢再把前面沒掃描到的 page 繼續掃描完。

Buffer Pool Bypass

在一些特殊的情況下，我們可能并不需要 Buffer Pool，例如順序掃描磁盤 page，如果我們需要加載的磁盤 page 的分布是連續的，我們可以直接加載磁盤數據，因為是順序 IO，性能仍然能夠不錯，并且省去了 Buffer Pool 換入換出的開銷。

PostgreSQL demo

下面以 postgres 為例，說明一下數據庫 buffer pool 的具體行為。

postgres 的默認 buffer pool 大小是 128MB，當進行查詢時，我們可以加上explain (analyze, buffers)前綴，打印 sql 執行的時間和詳細計劃，以及 buffer pool 的使用情況。

當首次啟動系統時，沒有任何數據在 buffer pool 中，因此一次查詢需要從磁盤中獲取所有的表數據，可以看下面的這個例子：

read 55140 表示從磁盤中獲取的 page 數量。

當我們再次運行這個查詢時，由于在前一次查詢中已經將部分數據緩存在 buffer pool 中，因此相應的執行計劃就會發生一些改變：

shared hit 表示命中了 buffer pool 中的數據，比前一次查詢從磁盤中獲取的 page 就會更少了。

buffer pool 淘汰策略

由于 buffer pool 是一塊容量有限的內存區域，并且大小通常比存儲在磁盤上的數據容量小得多，因此當 buffer pool 已滿時，如果有新的數據需要加載，則需要合適的淘汰替換策略，來保證將舊的數據剔除掉，插入新的數據。

LRU

lru 即 Least Recently Used，最近最少使用原則，這是應用較為廣泛的一種緩存淘汰算法了，思路也比較簡單直觀。

可以為每個 page 分配一個訪問的時間戳，當訪問了一個 page，則更新該時間戳。當需要淘汰舊的 page 時，直接選擇最久未被訪問的 page 即可。

Clock

clock 時鐘淘汰算法跟 LRU 的思路比較類似，但是實現上不太一樣。這種算法將 page 區域看做一個環，每個  page 都有一個標記為叫做 reference bit，初始情況下都為 0。

如果 page 被訪問到了的話，則會將 reference bit 設置為 1。

一般會設定一個定時任務，然后我們可以順序掃描每一個 page，如果 bit 值為 1，則說明該 page 被訪問過，就將 bit 重置為 0。如果 bit 為 0，則說明該 page 沒有被訪問過，則直接清除這個 page。

LRU-K

前面提到的 LRU 算法雖然思路簡單，但是也存在一些問題，如果一個頻繁訪問的熱點 page，在短時間內被僅訪問一次的頁面所替換，那么會使緩存命中率下降，這種情況通常叫做緩存污染。

所以我們可以提升頁面訪問的次數上限，當達到 k 次時才能夠替換其他的頁面，所以不難理解傳統的 LRU 算法可以看做是 LRU-1。

Localiztion

這種淘汰策略也能夠緩解 LRU 可能產生的緩存污染問題，它實際上比較類似前面提到的 multi buffer pool，當多個 query 進行時，它可以從全局的 buffer pool 中獲取 page 數據，但是當淘汰數據時，它可以自己再維護一個 buffer pool，在這個 buffer pool 中淘汰數據，不會對全局的 buffer pool 產生影響。

例如 PostgreSQL 在對表順序掃描時會維護一個本地的 ring buffer 緩存。

Dirty Page

最后再來看一個簡單的概念 dirty page。

dirty page，即臟頁，指的是緩存在 buffer pool 中的數據被修改了，但是還沒有來得及寫到磁盤中。每個 page 都有一個相應的標志位，來表示自己是否是臟頁。

如果一個 page 不是臟頁，那么在替換該 page 時，系統可以直接將它從 buffer pool 中移除，反之，則需要將 page 中的數據持久化。

一般我們可以啟動一個后臺進程，定期對臟頁進行處理，當將臟頁數據寫到磁盤后，可以將臟頁從 buffer pool移除，也可以直接重置 page 的臟頁標志位。

這一節講述了內存緩沖區的管理，淘汰策略，以及它是怎么和磁盤 page 進行交互的，下一節會開始講關于索引的部分。