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