PostgreSQL中空閑數據塊管理機制的原理是什么

本篇文章給大家分享的是有關PostgreSQL中空閑數據塊管理機制的原理是什么，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

數據塊空閑空間的產生

根據PostgreSQL的MVCC機制，所有UPDATE和DELETE操作都會產生過期數據，需要通過vacuum命令來清理過期數據。vacuum命令基本上有兩種：

• VACUUM

將過期tuple對應的磁盤空間標記為可用，但不會真正釋放空間給操作系統，其他程序無法再利用。該操作執行時不會要求排它鎖(EXCLUSIVE  LOCK)，不影響表讀寫操作。

• VACUUM FULL

將正常的tuple數據拷貝到新磁盤文件中，重新組織，將原數據文件刪除，未使用的磁盤空間退還給操作系統，該操作執行時需要獲取排它鎖，會影響正常的讀寫操作。因此執行該操作時需要慎重，特別是表數據量較大時，執行時間會比較長。

我們知道PostgreSQL的表(Relation)實際上是由多個物理數據塊(頁)組成，當執行vacuum操作后，這些數據塊中的保存有過期記錄(tuple)的磁盤空間就會被標記為可用，就會產生空閑空間。

當新增記錄(tuple)時，會優先重新利用表中數據塊的空閑空間，而不是分配一個新的數據塊。然而當多個數據塊都有空閑空間時，該選取哪個數據塊來保存新記錄呢?被選取的記錄必須要能夠有足夠的空間存放新記錄。

空閑數據塊的組織結構

為解決以上問題，PostgreSQL設計了FSM(Free Space  Map)結構來表示各個數據塊中空閑磁盤空間的大小。在pg8.4版本之后，每個表(Relation)都會獨立的FSM空間，具體表現為以_fsm為后綴的物理文件：

-bash-4.2$ cd $PGDATA/ins2/base -bash-4.2$ ll *fsm -rw------- 1 postgres postgres 24576 Jun 26 15:40 1247_fsm -rw------- 1 postgres postgres 24576 Jun 26 15:40 1249_fsm -rw------- 1 postgres postgres 24576 Jun 26 15:40 1255_fsm

FSM文件的存儲結構如下所示：

為了快速搜索到合適數據塊，減少因搜索帶來的IO開銷(即節省FSM文件大小)，FSM結構只使用一個字節來記錄一個數據塊中的空閑磁盤空閑大小，因1byte=8bits，那么就可以記錄2^8種空閑磁盤大小，假設一個數據塊大小(BLCKSZ)為8k(PostgreSQL默認為8k)，那么就可以劃分成256(2^8)等份，每份有BLCKSZ/256字節來表示范圍，示例如下：

Range      Category   0 - 31        0  32 - 63        1 ...    ...     ... 8096 - 8127    253 8128 - 8163    254 8164 - 8192    255

FSM數據塊內的數據結構

知道了數據塊中空閑空間大小的表示方法，那如何來組織這些表示記錄，保持高效查詢效率呢?答案是PostgreSQL使用了一種二叉樹結構(大根堆)來存儲這些表示空閑空間大小的記錄，葉子節點存儲實際的空間大小記錄，非葉子節點只是作為輔助查詢。當需要查詢是否有合適的數據塊大小時，只需要先比較樹的根節點即可知道，大大減少了查詢次數。大根堆數據結構示例如下：

 4  4     2 3 4   0 2    <- This level represents heap pages

上述例子中葉子節點的值3,4,0,2分別代表了空閑數據塊的map值，值3代表的就是空閑磁盤空間大小在[96,127]的數據塊。PostgreSQL源碼中FSM頁數據結構定義如下：

typedef struct {     int            fp_next_slot;      uint8        fp_nodes[FLEXIBLE_ARRAY_MEMBER]; } FSMPageData;

其中，fp_next_slot指向的是下一次查詢開始的slot位置，具體作用稍后闡述，fp_nodes數組存儲二叉樹的節點值。FSM數據塊內的數據存儲結構類似如下圖所示：

按照這種存儲結構，一個FSM數據塊(存儲FSM記錄的數據塊，和普通數據塊大小是一致的)可以存儲的實際記錄數(數據塊的空閑空間大小對應的map  value)為：

(BLCKSZ - headers) / 2        //除以2是因為二叉樹的葉子節點數約為總節點數的1/2

其中，BLCKSZ表示數據塊大小，headers表示數據塊固定大小的頭部信息。如果按照數據塊默認大小8k，那么單個FSM數據塊可存儲的記錄數大約為4000個，另外，PostgreSQL中一個表(Relation)最多可以有2^32個數據塊，那么最多就需要2^32條map記錄來表示這些數據塊中擁有的空閑空間大小，顯然，單個FSM數據塊是無法存儲下這些記錄，實際需要約2^32/4000個FSM數據塊來存儲。

前面我們介紹了單個FSM數據塊內的存儲map值的數據結構，當有多個FSM數據塊時，但是我們又該按照什么順序去選擇FSM數據塊頁來搜索呢?順序查找FSM數據塊顯然效率太低。

FSM數據塊間的邏輯組織結構

為了提升查找FSM數據塊的效率，PostgreSQL采用Higher-level(類似多叉樹)的邏輯結構來組織FSM數據。為每個FSM數據塊指定一個額外的邏輯結構FSMAddress，數據結構定義如下：

#define FSM_TREE_DEPTH    ((SlotsPerFSMPage >= 1626) ? 3 : 4) #define FSM_ROOT_LEVEL    (FSM_TREE_DEPTH - 1) #define FSM_BOTTOM_LEVEL 0  typedef struct {     int            level;            /* level */     int            logpageno;        /* page number within the level */ } FSMAddress;

其中，level表示該FSM數據塊所處的層號，logpageno表示在該層中的序號，序號從0開始。類似于FSM單個數據塊內的存儲方式，只有在***層(level=0)的FSM數據塊才實際存儲記錄，其它層作為查詢的輔助層，上層的葉子節點值代表了下層的根節點值。

那需要多少層邏輯結構才能表示所有的數據塊記錄呢，答案是當一個FSM數據塊內存儲超過1626條記錄(map  value)時，采用三層即可，因為162616261626>=2^32。

下面用一個示意圖來表示整體的組織結構，為了讓示意圖簡化，只在圖中每個數據塊存放4個字節的數據，這和存放1626個字節原理是一致的。FSM文件各數據塊間邏輯組織結構示意圖如下：

如圖所示，第2層數據塊中葉子節點值123就代表了它下一層(第1層)第0號數據塊的根節點值，而第1層第0號數據塊的葉子節點值123則代表的是第0層第1號數據塊的根節點，第0層第1號數據塊的葉子節點值123代表的是空閑空間大小為[3936,3967]字節的數據塊。每個數據塊都有邏輯地址，如第1號數據塊的邏輯地址{1,0}表示第1層的第0號FSM數據塊，實際上是對應的FSM物理文件的第1號數據塊。第2層和第1層的FSM數據塊內存儲的數據都只是作為輔助層索引，實際上只有第0層FSM數據塊內的葉子節點才存儲著表中空閑數據塊的map值，其他節點均是索引值。

空閑數據塊的搜索算法

上面介紹了空閑數據塊的表示方法和FSM文件中各數據塊的組織形式，接下來將介紹空閑空間數據塊的搜索算法。

首先，先介紹FSM數據塊內的查找算法。對于大根堆二叉樹查找，簡單的方法就是每次從root節點開始比較查找，如果root節點小于待查找值，則表示該塊內沒有滿足條件的map  value，否則可以繼續向下找到一個滿足條件的葉子節點。但是PostgreSQL的設計并不是這樣的，而是通過之前介紹的FSMPageData結構體的fp_next_slot來保存下一次查詢的起點位置(slot)，搜索算法如下：

比較根節點值，如果待查詢值大于根節點，則直接返回，表示該FSM數據塊內沒有滿足條件的map值，否則進行下一步。

比較查詢的起點位置(slot)對應的map值，如果不滿足條件，則進行下一步，否則跳到第5步。

設置新查詢位置為下一個slot(slot序號+1，slot值代表了在葉子節點的順序號)的父節點，再比較，如果不滿足條件則重復該步驟，直到向上查找到根節點。如果找到滿足條件的中間節點，則進行下一步。

向下查找，找到滿足條件的葉子節點，然后進行下一步。

重新設置下一次查詢的fp_next_slot變量，然后返回該葉子節點的slot。

FSM數據塊內搜索算法的核心源碼如下：

FSM數據塊內搜索算法的核心源碼如下：  int fsm_search_avail(Buffer buf, uint8 minvalue, bool advancenext,                  bool exclusive_lock_held) {     ...... restart:     if (fsmpage->fp_nodes[0] < minvalue) //每次查詢先檢查根節點是否滿足條件         return -1;     target = fsmpage->fp_next_slot;     if (target < 0 || target >= LeafNodesPerPage)         target = 0;     target += NonLeafNodesPerPage;     nodeno = target;                     //開始查詢時的slot位置     while (nodeno > 0)     {         if (fsmpage->fp_nodes[nodeno] >= minvalue)             break;         nodeno = parentof(rightneighbor(nodeno));  //返回下一個slot的父節點位置     }     while (nodeno < NonLeafNodesPerPage)      //向下查找到葉子節點     {         int    childnodeno = leftchild(nodeno);  //先查看左子節點         if (childnodeno < NodesPerPage &&             fsmpage->fp_nodes[childnodeno] >= minvalue)         {             nodeno = childnodeno;             continue;         }         childnodeno++;                //左子節點不滿足條件查找右子節點         if (childnodeno < NodesPerPage &&             fsmpage->fp_nodes[childnodeno] >= minvalue)         {             nodeno = childnodeno;         }         else         {             //都沒找到，說明當前可能存在"torn page"的情況（ IO寫磁盤數據時出現crash，只有部分數據寫入）             //重新更新頁數據后再查詢             .......             fsm_rebuild_page(page);             ......             goto restart;          }     }     slot = nodeno - NonLeafNodesPerPage;                   //找到slot序號     fsmpage->fp_next_slot = slot + (advancenext ? 1 : 0);  //保存下一次查詢開始的slot位置     return slot; }

至此，就找到了該FSM數據塊中滿足條件的葉子節點，如果該頁不是處在第0層，則該葉子節點并不是我們最終查詢目標，根據前述FSM數據塊間的組織結構可知，輔助層中葉子節點對應的是下一層FSM數據塊的根節點，因此，需要繼續向下查找到第0層的對應葉子節點。查找葉子節點對應下一層的數據塊則是通過返回的slot值來計算的，核心查找算法源碼如下：

for (;;){     ......     slot = fsm_search_avail(buf, min_cat, (addr.level == FSM_BOTTOM_LEVEL),    false);     ......     if (slot != -1)   //找到滿足條件的葉子節點，否則退出循環     {         if (addr.level == FSM_BOTTOM_LEVEL)    //查找到第0層，返回結果             return fsm_get_heap_blk(addr, slot);          addr = fsm_get_child(addr, slot);     //非第0層，繼續查找子樹     }     ...... }  static FSMAddress fsm_get_child(FSMAddress parent, uint16 slot) {     FSMAddress    child;     Assert(parent.level > FSM_BOTTOM_LEVEL);     child.level = parent.level - 1;     child.logpageno = parent.logpageno * SlotsPerFSMPage + slot; //根據上一層的slot查找下層對應數據頁的logpageno     return child; }

整個搜索算法就介紹完畢，至于為什么要把fp_next_slot來作為起始查詢位置而不是root節點呢?原因有幾點：

• 當有多個后端連接同時新增tuple時，可以盡量避免對同一數據塊的寫沖突，提高寫并行度。如果每次都從root節點開始查找，有可能多個查詢都同時查找到同一個數據塊。

• 獲取的是上一次返回查詢結果的臨近數據塊，更有利于提升磁盤IO效率。

更新空閑數據塊空間大小

查找到表中合適的空閑數據塊后，新記錄會寫入該數據塊，然后需要更新該數據塊的空閑空間大小。相較于搜索，更新相對簡單，核心思想就是先重新計算該空閑數據塊的map值，然后更新在FSM數據塊中對應葉子節點的值，再以“冒泡”的方式向上不斷更新，直到更新到父節點值不變化或者root節點。核心源碼如下：

fsmpage->fp_nodes[nodeno] = value;                 //更新當前節點 do {     ......     nodeno = parentof(nodeno);     lchild = leftchild(nodeno);     rchild = lchild + 1;     newvalue = fsmpage->fp_nodes[lchild];     if (rchild < NodesPerPage)                       //右子節點存在，則選取***值作為父節點的新值         newvalue = Max(newvalue,  fsmpage->fp_nodes[rchild]);     oldvalue = fsmpage->fp_nodes[nodeno];     if (oldvalue == newvalue)                        //檢查更新后父節點是否有變化         break;     fsmpage->fp_nodes[nodeno] = newvalue;            //有變化，更新父節點，繼續向上更新 } while (nodeno > 0);                                //更新到root節點退出

鎖

搜索空閑數據塊時只會對當前搜索的FSM數據塊加共享鎖(shared buffer locks)，更新FSM數據塊時才會加排它鎖(exclusive  buffer  lock)。這里值得注意的一點是在搜索時，使用了fp_next_slot變量來表示下一次搜索的起點位置，并沒有為之加一個排它鎖，因為維持一個排它鎖的代價遠比fp_next_slot變量出現異常后的代價大很多。

以上就是PostgreSQL中空閑數據塊管理機制的原理是什么，小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注億速云行業資訊頻道。