PostgreSQL Buffer Manager與hash演算法

作者：吳聰

1、概述

為了加速資料庫對資料的訪問，我們需要透過buffer cache來將磁碟的資料塊快取，那麼在PostgreSQL中是如何對buffer進行管理的呢？

說的直接點，我要在buffer中訪問某個page，資料庫怎麼去判斷buffer中是否存在呢，如果存在又是怎麼定位到這個page呢？很簡單，透過hash演算法。在資料庫中似乎hash演算法隨處可見，hash索引、hash連線等等。之所以使用hash演算法，自然是因為其速度快、效率高了。在PostgreSQL幾乎記憶體管理中所用的都是hash演算法。

在介紹PostgreSQL如何使用hash演算法進行 buffer管理前，我們先來了解下hash演算法。

2、hash演算法

2.1、什麼是hash演算法

我們在資料庫中可能經常會聽到hash這個詞，那什麼是hash呢？打個比方，給1個數字，然後對這個數字取餘，得到該餘數，這個就是hash。

可以發現hash函式主要的兩個特點：

給一個定值（hash key），得到另一個定值（hash value）；

過程可重複，對於同樣的傳入值，輸出值總是一樣的。

當然真正的hash函式不只是取餘這麼簡單，取餘這個操作是很佔用CPU的，況且只能對數字進行操作。我們以下面的例子來看看簡單的hash函式：

long hash（char *key， int len）{ int i； long ret = 0； if （key == 0） return 0； for （i=0； i<1 ； i++） ret ^=（key［i］ << （i&0x0f））； return ret；}

上面這個函式大致作用就是，對傳入值char *key（hash key）的每個字元進行位運算，返回值ret就是我們要求的hash值。

相較於前面的取餘運算，位運算就快很多了，佔用CPU週期也少很多，但是hash運算仍然是CPU密集型的操作。因此在資料庫中hash運算較多的情況下，CPU使用率自然是會比較高。

例如我們前面說的在buffer中搜索某個page，就是對buffer_tag進行hash操作得到hash值，然後使用hash值進行搜尋。這樣做的好處很顯然，就是可以更快速的搜尋。

2.2、連結串列與hash

既然我們前面說了是在buffer中搜索page，假設我們現在buffer中有這樣3個page：

我們看到有這樣存放在不同記憶體地址的3個page，一般它們在記憶體中會被存放成連結串列的形式，如下：

在記憶體地址2000的塊中記錄下下一個記憶體地址2400，在記憶體塊2400中記錄下下一個內粗地址2200，依次類推，這樣就構成了連結串列結構。

通常還會加上一個連結串列頭，如下所示：

那如果我們需要查詢page2的資訊，步驟大致如下：

取出頭中記錄的下一個地址2400；

對比記憶體地址2400中的內容是不是所需的；

判斷結果不是，繼續取出下一個記憶體地址2200；

對比記憶體地址2200中的內容是不是所需的，發現正是所需的。

可以看到這就是連結串列中搜索某個記憶體塊的步驟，方式很簡單，但是如果連結串列很長，搜尋時間必然要很久。因此hash演算法應運而生。

hash演算法需要對記憶體塊的分佈進行重新組織。在前面的連結串列中，我們的3個page的記憶體地址是隨機的，但是hash演算法需要他們的記憶體地址是連續的。而且還有一些其它特殊的要求，例如這3個page的hash值除以3取餘分別為1、2、3，假設每個page大小為8個位元組，那麼需要在記憶體中分配24個位元組，並且根據其hash值的餘數的順序，在記憶體中這三個page的順序依次是page1->page2->page3。

假設這三個page在記憶體中地址開始為10000，那麼page1的記憶體塊為10000~10008，page2為10008~10016，page3為10016~10024，其結構大致為：

可以看到不需要在儲存下一個記憶體塊的地址了，因為根據自己的記憶體地址加上8就是下一個。那麼這樣有什麼好處呢？例如我們的某個page的hash值是10000，除以3取餘為1，那麼它的地址就是10000+8*1=10008，這便是hash演算法，避免了遍歷連結串列的過程，我們將整個hash連結串列統稱為hash表。

下面簡單小結下連結串列和hash表的區別：

連結串列中，如果需要找的物件在第N個節點，那麼必須從連結串列頭開始逐個搜尋直至第N個節點，如果N很大，那麼搜尋時間便會很長；

在hash表中，只需要計算搜尋物件的hash值，根據hash表的hash值，加上N*每個hash節點的大小就可以得到第N個節點的地址。

總的來說，連結串列搜尋的演算法複雜度是O（n），hash搜尋的演算法複雜度是O（1）。

2.3、hash演算法的缺點與hash衝突

當然hash演算法也並不是沒有缺點，不然連結串列也沒有存在的意義了。

其缺點在於，我們在構建hash表時需要先確定節點個數，這裡我們稱為hash bulket。根據hash bulker的數量和大小我們才能去預先分配記憶體。

而且一般來說hash演算法需要的記憶體是不可變的，需要提前一次性分配，這便是hash演算法的不足之處。

除此之外，我們再來說說hash衝突。因為無論我們預先分配的hash bulket數量有多少，仍然會出現不同的資料塊計算出來的hash值是同樣的，我們把這種情況稱之為hash衝突。

我們前面也說了，hash bulket的數量和大小是需要提前確定的，所有碰到這種情況我們是沒辦法把這些hash值相同的資料塊放到同一個hash bulket中，那麼該如何處理呢？

首先，將這些hash值相同的bulket組織成一個連結串列，然後將這個連結串列的頭部地址放入前面的hash表中，這樣就不會出現hash bulket放不下多個數據塊的問題了，因為我只需要存放連結串列頭的地址即可。

所以可以看到，要解決hash衝突並不僅僅靠hash表，需要hash表加上鍊表才可以，將hash衝突的bulket放到同一個連結串列中。

3、PostgreSQL中的hash演算法

首先我們先來看下在PG中如何在buffer中定位資料塊的。

我們先來介紹下buffer_tag結構：

typedef struct buftag{ RelFileNode rnode； /* physical relation identifier */ ForkNumber forkNum； BlockNumber blockNum； /* blknum relative to begin of reln */} BufferTag；

我們透過buffer_tag（檔案ID，block number，fork number）來定位buffer中具體的某個page，對buffer_tag計算hash值，但是因為hash衝突的存在，我們同樣需要使用連結串列，將hash值相同的page存放到連結串列中。

當查詢指定的key時，首先計算出它的雜湊值，然後根據後面的幾位數，計算出對應的bucket位置。之後遍歷bucket的元素連結串列，檢視是否有key元素。