PostgreSQL 的空閑數(shù)據(jù)塊管理機(jī)制解析
導(dǎo)語
在上一篇文章《PostgreSQL的MVCC機(jī)制解析》結(jié)尾處講到PostgreSQL是通過vacuum命令來處理過期數(shù)據(jù)，本文將繼續(xù)對(duì)vacuum命令做介紹，并以此引出PostgreSQL空閑數(shù)據(jù)塊的產(chǎn)生，然后對(duì)空閑數(shù)據(jù)塊管理機(jī)制的原理做解析。
數(shù)據(jù)塊空閑空間的產(chǎn)生
根據(jù)PostgreSQL的MVCC機(jī)制，所有UPDATE和DELETE操作都會(huì)產(chǎn)生過期數(shù)據(jù)，需要通過vacuum命令來清理過期數(shù)據(jù)。vacuum命令基本上有兩種：
- VACUUM
將過期tuple對(duì)應(yīng)的磁盤空間標(biāo)記為可用，但不會(huì)真正釋放空間給操作系統(tǒng)，其他程序無法再利用。該操作執(zhí)行時(shí)不會(huì)要求排它鎖(EXCLUSIVE LOCK)，不影響表讀寫操作。
- VACUUM FULL
將正常的tuple數(shù)據(jù)拷貝到新磁盤文件中，重新組織，將原數(shù)據(jù)文件刪除，未使用的磁盤空間退還給操作系統(tǒng)，該操作執(zhí)行時(shí)需要獲取排它鎖，會(huì)影響正常的讀寫操作。因此執(zhí)行該操作時(shí)需要慎重，特別是表數(shù)據(jù)量較大時(shí)，執(zhí)行時(shí)間會(huì)比較長(zhǎng)。
我們知道PostgreSQL的表(Relation)實(shí)際上是由多個(gè)物理數(shù)據(jù)塊(頁)組成，當(dāng)執(zhí)行vacuum操作后，這些數(shù)據(jù)塊中的保存有過期記錄(tuple)的磁盤空間就會(huì)被標(biāo)記為可用，就會(huì)產(chǎn)生空閑空間。
當(dāng)新增記錄(tuple)時(shí)，會(huì)優(yōu)先重新利用表中數(shù)據(jù)塊的空閑空間，而不是分配一個(gè)新的數(shù)據(jù)塊。然而當(dāng)多個(gè)數(shù)據(jù)塊都有空閑空間時(shí)，該選取哪個(gè)數(shù)據(jù)塊來保存新記錄呢?被選取的記錄必須要能夠有足夠的空間存放新記錄。
空閑數(shù)據(jù)塊的組織結(jié)構(gòu)
為解決以上問題，PostgreSQL設(shè)計(jì)了FSM(Free Space Map)結(jié)構(gòu)來表示各個(gè)數(shù)據(jù)塊中空閑磁盤空間的大小。在pg8.4版本之后，每個(gè)表(Relation)都會(huì)獨(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文件的存儲(chǔ)結(jié)構(gòu)如下所示：
為了快速搜索到合適數(shù)據(jù)塊，減少因搜索帶來的IO開銷(即節(jié)省FSM文件大小)，F(xiàn)SM結(jié)構(gòu)只使用一個(gè)字節(jié)來記錄一個(gè)數(shù)據(jù)塊中的空閑磁盤空閑大小，因1byte=8bits，那么就可以記錄2^8種空閑磁盤大小，假設(shè)一個(gè)數(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)(大根堆)來存儲(chǔ)這些表示空閑空間大小的記錄，葉子節(jié)點(diǎn)存儲(chǔ)實(shí)際的空間大小記錄，非葉子節(jié)點(diǎn)只是作為輔助查詢。當(dāng)需要查詢是否有合適的數(shù)據(jù)塊大小時(shí)，只需要先比較樹的根節(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ù)組存儲(chǔ)二叉樹的節(jié)點(diǎn)值。FSM數(shù)據(jù)塊內(nèi)的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)類似如下圖所示：
按照這種存儲(chǔ)結(jié)構(gòu)，一個(gè)FSM數(shù)據(jù)塊(存儲(chǔ)FSM記錄的數(shù)據(jù)塊，和普通數(shù)據(jù)塊大小是一致的)可以存儲(chǔ)的實(shí)際記錄數(shù)(數(shù)據(jù)塊的空閑空間大小對(duì)應(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，那么單個(gè)FSM數(shù)據(jù)塊可存儲(chǔ)的記錄數(shù)大約為4000個(gè)，另外，PostgreSQL中一個(gè)表(Relation)最多可以有2^32個(gè)數(shù)據(jù)塊，那么最多就需要2^32條map記錄來表示這些數(shù)據(jù)塊中擁有的空閑空間大小，顯然，單個(gè)FSM數(shù)據(jù)塊是無法存儲(chǔ)下這些記錄，實(shí)際需要約2^32/4000個(gè)FSM數(shù)據(jù)塊來存儲(chǔ)。
前面我們介紹了單個(gè)FSM數(shù)據(jù)塊內(nèi)的存儲(chǔ)map值的數(shù)據(jù)結(jié)構(gòu)，當(dāng)有多個(gè)FSM數(shù)據(jù)塊時(shí)，但是我們又該按照什么順序去選擇FSM數(shù)據(jù)塊頁來搜索呢?順序查找FSM數(shù)據(jù)塊顯然效率太低。
FSM數(shù)據(jù)塊間的邏輯組織結(jié)構(gòu)
為了提升查找FSM數(shù)據(jù)塊的效率，PostgreSQL采用Higher-level(類似多叉樹)的邏輯結(jié)構(gòu)來組織FSM數(shù)據(jù)。為每個(gè)FSM數(shù)據(jù)塊指定一個(gè)額外的邏輯結(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ù)塊所處的層號(hào)，logpageno表示在該層中的序號(hào)，序號(hào)從0開始。類似于FSM單個(gè)數(shù)據(jù)塊內(nèi)的存儲(chǔ)方式，只有在***層(level=0)的FSM數(shù)據(jù)塊才實(shí)際存儲(chǔ)記錄，其它層作為查詢的輔助層，上層的葉子節(jié)點(diǎn)值代表了下層的根節(jié)點(diǎn)值。
那需要多少層邏輯結(jié)構(gòu)才能表示所有的數(shù)據(jù)塊記錄呢，答案是當(dāng)一個(gè)FSM數(shù)據(jù)塊內(nèi)存儲(chǔ)超過1626條記錄(map value)時(shí)，采用三層即可，因?yàn)?62616261626>=2^32。
下面用一個(gè)示意圖來表示整體的組織結(jié)構(gòu)，為了讓示意圖簡(jiǎn)化，只在圖中每個(gè)數(shù)據(jù)塊存放4個(gè)字節(jié)的數(shù)據(jù)，這和存放1626個(gè)字節(jié)原理是一致的。FSM文件各數(shù)據(jù)塊間邏輯組織結(jié)構(gòu)示意圖如下：
如圖所示，第2層數(shù)據(jù)塊中葉子節(jié)點(diǎn)值123就代表了它下一層(第1層)第0號(hào)數(shù)據(jù)塊的根節(jié)點(diǎn)值，而第1層第0號(hào)數(shù)據(jù)塊的葉子節(jié)點(diǎn)值123則代表的是第0層第1號(hào)數(shù)據(jù)塊的根節(jié)點(diǎn)，第0層第1號(hào)數(shù)據(jù)塊的葉子節(jié)點(diǎn)值123代表的是空閑空間大小為[3936,3967]字節(jié)的數(shù)據(jù)塊。每個(gè)數(shù)據(jù)塊都有邏輯地址，如第1號(hào)數(shù)據(jù)塊的邏輯地址{1,0}表示第1層的第0號(hào)FSM數(shù)據(jù)塊，實(shí)際上是對(duì)應(yīng)的FSM物理文件的第1號(hào)數(shù)據(jù)塊。第2層和第1層的FSM數(shù)據(jù)塊內(nèi)存儲(chǔ)的數(shù)據(jù)都只是作為輔助層索引，實(shí)際上只有第0層FSM數(shù)據(jù)塊內(nèi)的葉子節(jié)點(diǎn)才存儲(chǔ)著表中空閑數(shù)據(jù)塊的map值，其他節(jié)點(diǎn)均是索引值。
空閑數(shù)據(jù)塊的搜索算法
上面介紹了空閑數(shù)據(jù)塊的表示方法和FSM文件中各數(shù)據(jù)塊的組織形式，接下來將介紹空閑空間數(shù)據(jù)塊的搜索算法。
首先，先介紹FSM數(shù)據(jù)塊內(nèi)的查找算法。對(duì)于大根堆二叉樹查找，簡(jiǎn)單的方法就是每次從root節(jié)點(diǎn)開始比較查找，如果root節(jié)點(diǎn)小于待查找值，則表示該塊內(nèi)沒有滿足條件的map value，否則可以繼續(xù)向下找到一個(gè)滿足條件的葉子節(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)對(duì)應(yīng)的map值，如果不滿足條件，則進(jìn)行下一步，否則跳到第5步。
設(shè)置新查詢位置為下一個(gè)slot(slot序號(hào)+1，slot值代表了在葉子節(jié)點(diǎn)的順序號(hào))的父節(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; //開始查詢時(shí)的slot位置
- while (nodeno > 0)
- {
- if (fsmpage->fp_nodes[nodeno] >= minvalue)
- break;
- nodeno = parentof(rightneighbor(nodeno)); //返回下一個(gè)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ù)時(shí)出現(xiàn)crash，只有部分?jǐn)?shù)據(jù)寫入）
- //重新更新頁數(shù)據(jù)后再查詢
- .......
- fsm_rebuild_page(page);
- ......
- goto restart;
- }
- }
- slot = nodeno - NonLeafNodesPerPage; //找到slot序號(hào)
- 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)對(duì)應(yīng)的是下一層FSM數(shù)據(jù)塊的根節(jié)點(diǎn)，因此，需要繼續(xù)向下查找到第0層的對(duì)應(yīng)葉子節(jié)點(diǎn)。查找葉子節(jié)點(diǎn)對(duì)應(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查找下層對(duì)應(yīng)數(shù)據(jù)頁的logpageno
- return child;
- }
整個(gè)搜索算法就介紹完畢，至于為什么要把fp_next_slot來作為起始查詢位置而不是root節(jié)點(diǎn)呢?原因有幾點(diǎn)：
- 當(dāng)有多個(gè)后端連接同時(shí)新增tuple時(shí)，可以盡量避免對(duì)同一數(shù)據(jù)塊的寫沖突，提高寫并行度。如果每次都從root節(jié)點(diǎn)開始查找，有可能多個(gè)查詢都同時(shí)查找到同一個(gè)數(shù)據(jù)塊。
- 獲取的是上一次返回查詢結(jié)果的臨近數(shù)據(jù)塊，更有利于提升磁盤IO效率。
更新空閑數(shù)據(jù)塊空間大小
查找到表中合適的空閑數(shù)據(jù)塊后，新記錄會(huì)寫入該數(shù)據(jù)塊，然后需要更新該數(shù)據(jù)塊的空閑空間大小。相較于搜索，更新相對(duì)簡(jiǎn)單，核心思想就是先重新計(jì)算該空閑數(shù)據(jù)塊的map值，然后更新在FSM數(shù)據(jù)塊中對(duì)應(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ù)塊時(shí)只會(huì)對(duì)當(dāng)前搜索的FSM數(shù)據(jù)塊加共享鎖(shared buffer locks)，更新FSM數(shù)據(jù)塊時(shí)才會(huì)加排它鎖(exclusive buffer lock)。這里值得注意的一點(diǎn)是在搜索時(shí)，使用了fp_next_slot變量來表示下一次搜索的起點(diǎn)位置，并沒有為之加一個(gè)排它鎖，因?yàn)榫S持一個(gè)排它鎖的代價(jià)遠(yuǎn)比fp_next_slot變量出現(xiàn)異常后的代價(jià)大很多。
原文鏈接：https://www.qcloud.com/community/article/941271
【本文是51CTO專欄作者“騰訊云技術(shù)社區(qū)”的原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)通過51CTO聯(lián)系原作者獲取授權(quán)】
