什么是 buffer pool

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

Buffer Pool 本質(zhì)上就是一塊共享內(nèi)存區(qū)域，其目的主要是對磁盤上的 page 進(jìn)行緩存，盡量減少磁盤 IO，提升數(shù)據(jù)庫系統(tǒng)的性能。

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

buffer pool 對內(nèi)存區(qū)域劃分為了被稱為 frame 的小塊，每個(gè) frame 就是緩存了磁盤的 page 內(nèi)容。

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

對于 page table 的訪問，一般要保證并發(fā)安全，因?yàn)樵诙嗑€程環(huán)境下，對于同一個(gè)內(nèi)存中 frame 的讀寫不能同時(shí)進(jìn)行。

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

buffer pool 優(yōu)化

前面簡要說明了 buffer pool 的基本概念，在實(shí)際使用的時(shí)候，會(huì)針對 buffer pool 進(jìn)行各種各樣的優(yōu)化，下面依次介紹常見的幾種。

Multiple Buffer Pool

buffer pool 并不是一塊內(nèi)存進(jìn)行劃分，不同的數(shù)據(jù)庫系統(tǒng)中，有不同的用法。

大多數(shù)系統(tǒng)都實(shí)現(xiàn)了可以開辟多個(gè) buffer pool，避免多個(gè)線程對同一個(gè) buffer pool 的鎖競爭，這樣能夠更大程度上提升數(shù)據(jù)讀寫的效率。具體的實(shí)現(xiàn)可以是多樣化的，例如：

• 創(chuàng)建多個(gè) buffer pool 的實(shí)例
• 每個(gè)數(shù)據(jù)庫分配一個(gè) buffer pool
• 同類型的磁盤 page 分配一個(gè) buffer pool

一般有兩種方式來實(shí)現(xiàn)一條 tuple 到 buffer pool 的映射：object id 和 hashing。

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

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

Pre-Fetching

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

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

如果是索引掃描，葉子節(jié)點(diǎn)指向的 page 有可能并不是連續(xù)的，但是作為數(shù)據(jù)庫系統(tǒng)內(nèi)部，我們可以識(shí)別出來，加載想要的 page 到 buffer pool 中（這也是上一篇文章中提到的數(shù)據(jù)庫系統(tǒng)一般會(huì)自己管理內(nèi)存，而不依賴于 mmap）。

例如下圖，葉子節(jié)點(diǎn)的 page 分別是 3 和 5，這樣的話加載的時(shí)候就跳過中間不需要的 page。

Scan Sharing

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

這個(gè)優(yōu)化在大多數(shù)數(shù)據(jù)庫中都有實(shí)現(xiàn)，例如 Sql Server、Oracle、PostgreSQL。

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

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

淘汰掉 page0 后，然后將 page3 加載進(jìn)來。

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

于是一個(gè)優(yōu)化策略是將兩個(gè)查詢的掃描指針會(huì)合起來，共享同一個(gè) Buffer Pool 中的內(nèi)容，等到前面的結(jié)束之后，第二個(gè)查詢再把前面沒掃描到的 page 繼續(xù)掃描完。

Buffer Pool Bypass

在一些特殊的情況下，我們可能并不需要 Buffer Pool，例如順序掃描磁盤 page，如果我們需要加載的磁盤 page 的分布是連續(xù)的，我們可以直接加載磁盤數(shù)據(jù)，因?yàn)槭琼樞?IO，性能仍然能夠不錯(cuò)，并且省去了 Buffer Pool 換入換出的開銷。

PostgreSQL demo

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

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

當(dāng)首次啟動(dòng)系統(tǒng)時(shí)，沒有任何數(shù)據(jù)在 buffer pool 中，因此一次查詢需要從磁盤中獲取所有的表數(shù)據(jù)，可以看下面的這個(gè)例子：

read 55140 表示從磁盤中獲取的 page 數(shù)量。

當(dāng)我們再次運(yùn)行這個(gè)查詢時(shí)，由于在前一次查詢中已經(jīng)將部分?jǐn)?shù)據(jù)緩存在 buffer pool 中，因此相應(yīng)的執(zhí)行計(jì)劃就會(huì)發(fā)生一些改變：

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

buffer pool 淘汰策略

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

LRU

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

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

Clock

clock 時(shí)鐘淘汰算法跟 LRU 的思路比較類似，但是實(shí)現(xiàn)上不太一樣。這種算法將 page 區(qū)域看做一個(gè)環(huán)，每個(gè)  page 都有一個(gè)標(biāo)記為叫做 reference bit，初始情況下都為 0。

如果 page 被訪問到了的話，則會(huì)將 reference bit 設(shè)置為 1。

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

LRU-K

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

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

Localiztion

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

例如 PostgreSQL 在對表順序掃描時(shí)會(huì)維護(hù)一個(gè)本地的 ring buffer 緩存。

Dirty Page

最后再來看一個(gè)簡單的概念 dirty page。

dirty page，即臟頁，指的是緩存在 buffer pool 中的數(shù)據(jù)被修改了，但是還沒有來得及寫到磁盤中。每個(gè) page 都有一個(gè)相應(yīng)的標(biāo)志位，來表示自己是否是臟頁。

如果一個(gè) page 不是臟頁，那么在替換該 page 時(shí)，系統(tǒng)可以直接將它從 buffer pool 中移除，反之，則需要將 page 中的數(shù)據(jù)持久化。

一般我們可以啟動(dòng)一個(gè)后臺(tái)進(jìn)程，定期對臟頁進(jìn)行處理，當(dāng)將臟頁數(shù)據(jù)寫到磁盤后，可以將臟頁從 buffer pool移除，也可以直接重置 page 的臟頁標(biāo)志位。

這一節(jié)講述了內(nèi)存緩沖區(qū)的管理，淘汰策略，以及它是怎么和磁盤 page 進(jìn)行交互的，下一節(jié)會(huì)開始講關(guān)于索引的部分。