[[200392]]

導(dǎo)語

在上一篇文章《PostgreSQL的MVCC機(jī)制解析》結(jié)尾處講到PostgreSQL是通過vacuum命令來處理過期數(shù)據(jù)，本文將繼續(xù)對vacuum命令做介紹，并以此引出PostgreSQL空閑數(shù)據(jù)塊的產(chǎn)生，然后對空閑數(shù)據(jù)塊管理機(jī)制的原理做解析。

數(shù)據(jù)塊空閑空間的產(chǎn)生

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

• VACUUM

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

• VACUUM FULL

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

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

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

空閑數(shù)據(jù)塊的組織結(jié)構(gòu)

為解決以上問題，PostgreSQL設(shè)計(jì)了FSM(Free Space Map)結(jié)構(gòu)來表示各個數(shù)據(jù)塊中空閑磁盤空間的大小。在pg8.4版本之后，每個表(Relation)都會獨(dú)立的FSM空間，具體表現(xiàn)為以_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文件的存儲結(jié)構(gòu)如下所示：

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

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

FSM數(shù)據(jù)塊內(nèi)的數(shù)據(jù)結(jié)構(gòu)

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

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

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

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

其中，fp_next_slot指向的是下一次查詢開始的slot位置，具體作用稍后闡述，fp_nodes數(shù)組存儲二叉樹的節(jié)點(diǎn)值。FSM數(shù)據(jù)塊內(nèi)的數(shù)據(jù)存儲結(jié)構(gòu)類似如下圖所示：

按照這種存儲結(jié)構(gòu)，一個FSM數(shù)據(jù)塊(存儲FSM記錄的數(shù)據(jù)塊，和普通數(shù)據(jù)塊大小是一致的)可以存儲的實(shí)際記錄數(shù)(數(shù)據(jù)塊的空閑空間大小對應(yīng)的map value)為：

(BLCKSZ - headers) / 2        //除以2是因?yàn)槎鏄涞娜~子節(jié)點(diǎn)數(shù)約為總節(jié)點(diǎn)數(shù)的1/2 

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

前面我們介紹了單個FSM數(shù)據(jù)塊內(nèi)的存儲map值的數(shù)據(jù)結(jié)構(gòu)，當(dāng)有多個FSM數(shù)據(jù)塊時，但是我們又該按照什么順序去選擇FSM數(shù)據(jù)塊頁來搜索呢?順序查找FSM數(shù)據(jù)塊顯然效率太低。

FSM數(shù)據(jù)塊間的邏輯組織結(jié)構(gòu)

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

#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數(shù)據(jù)塊所處的層號，logpageno表示在該層中的序號，序號從0開始。類似于FSM單個數(shù)據(jù)塊內(nèi)的存儲方式，只有在***層(level=0)的FSM數(shù)據(jù)塊才實(shí)際存儲記錄，其它層作為查詢的輔助層，上層的葉子節(jié)點(diǎn)值代表了下層的根節(jié)點(diǎn)值。

那需要多少層邏輯結(jié)構(gòu)才能表示所有的數(shù)據(jù)塊記錄呢，答案是當(dāng)一個FSM數(shù)據(jù)塊內(nèi)存儲超過1626條記錄(map value)時，采用三層即可，因?yàn)?62616261626>=2^32。

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

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

空閑數(shù)據(jù)塊的搜索算法

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

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

比較根節(jié)點(diǎn)值，如果待查詢值大于根節(jié)點(diǎn)，則直接返回，表示該FSM數(shù)據(jù)塊內(nèi)沒有滿足條件的map值，否則進(jìn)行下一步。

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

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

向下查找，找到滿足條件的葉子節(jié)點(diǎn)，然后進(jìn)行下一步。

重新設(shè)置下一次查詢的fp_next_slot變量，然后返回該葉子節(jié)點(diǎn)的slot。

FSM數(shù)據(jù)塊內(nèi)搜索算法的核心源碼如下：

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

至此，就找到了該FSM數(shù)據(jù)塊中滿足條件的葉子節(jié)點(diǎn)，如果該頁不是處在第0層，則該葉子節(jié)點(diǎn)并不是我們最終查詢目標(biāo)，根據(jù)前述FSM數(shù)據(jù)塊間的組織結(jié)構(gòu)可知，輔助層中葉子節(jié)點(diǎn)對應(yīng)的是下一層FSM數(shù)據(jù)塊的根節(jié)點(diǎn)，因此，需要繼續(xù)向下查找到第0層的對應(yīng)葉子節(jié)點(diǎn)。查找葉子節(jié)點(diǎn)對應(yīng)下一層的數(shù)據(jù)塊則是通過返回的slot值來計(jì)算的，核心查找算法源碼如下：

for (;;){ 
    ...... 
    slot = fsm_search_avail(buf, min_cat, (addr.level == FSM_BOTTOM_LEVEL),    false); 
    ...... 
    if (slot != -1)   //找到滿足條件的葉子節(jié)點(diǎn)，否則退出循環(huán) 
    { 
        if (addr.level == FSM_BOTTOM_LEVEL)    //查找到第0層，返回結(jié)果 
            return fsm_get_heap_blk(addr, slot);  
        addr = fsm_get_child(addr, slot);     //非第0層，繼續(xù)查找子樹 
    } 
    ...... 
} 
 
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; //根據(jù)上一層的slot查找下層對應(yīng)數(shù)據(jù)頁的logpageno 
    return child; 
} 

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

• 當(dāng)有多個后端連接同時新增tuple時，可以盡量避免對同一數(shù)據(jù)塊的寫沖突，提高寫并行度。如果每次都從root節(jié)點(diǎn)開始查找，有可能多個查詢都同時查找到同一個數(shù)據(jù)塊。
• 獲取的是上一次返回查詢結(jié)果的臨近數(shù)據(jù)塊，更有利于提升磁盤IO效率。

更新空閑數(shù)據(jù)塊空間大小

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

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

鎖

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

原文鏈接：https://www.qcloud.com/community/article/941271

【本文是51CTO專欄作者“騰訊云技術(shù)社區(qū)”的原創(chuàng)稿件，轉(zhuǎn)載請通過51CTO聯(lián)系原作者獲取授權(quán)】

戳這里，看該作者更多好文