什么是 buffer pool

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

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

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

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

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

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

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

buffer pool 優(yōu)化

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

Multiple Buffer Pool

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

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

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

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

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

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

Pre-Fetching

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

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

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

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

Scan Sharing

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

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

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

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

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

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

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

Buffer Pool Bypass

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

PostgreSQL demo

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

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

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

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

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

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

buffer pool 淘汰策略

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

LRU

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

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

Clock

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

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

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

LRU-K

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

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

Localiztion

這種淘汰策略也能夠緩解 LRU 可能產(chǎn)生的緩存污染問(wèn)題，它實(shí)際上比較類(lèi)似前面提到的 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ì)對(duì)全局的 buffer pool 產(chǎn)生影響。

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

Dirty Page

最后再來(lái)看一個(gè)簡(jiǎn)單的概念 dirty page。

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

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

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

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