1、pg空閑空間管理技術(shù)報(bào)告1.概述隨著表中不斷插入和刪除元組，文件塊中必然會(huì)產(chǎn)生空閑空間，在插入元組時(shí)優(yōu)先選擇將其存放在空閑空間內(nèi)是利用存儲(chǔ)的好方法。但是這需要在該表的眾多擁有空閑空間的文件塊之間進(jìn)行選擇，而遍歷所有文件塊進(jìn)行選擇的開銷將是非常龐大的。在postgresql8.4之前，方法是使用全局的FSM文件來記錄所有表文件的空閑空間狀況，其缺點(diǎn)是在全局FSM文件中只能記錄每個(gè)表文件一定數(shù)量的文件塊空閑空間，所以對(duì)于實(shí)際來說管理起來比較復(fù)雜，使用起來比較低效。在postgresql8.4之后，方法是為每個(gè)表（包括系統(tǒng)表在內(nèi)）創(chuàng)建一個(gè)用于管理空閑空間的文件，稱之為空閑空間映射表文件（FSM）。2

2、.存儲(chǔ)和組織方式2.1存儲(chǔ)方式在block.h中有這樣一個(gè)聲明，typedef uint32 BlockNumber;這個(gè)uint32就決定了一個(gè)relation最大只能有4G個(gè)block，每個(gè)block大小為8KB，也就是說一個(gè)relation的磁盤大小最大為32TB,比較大。我們需要注意relation的不斷的插入刪除記錄，會(huì)造成很多的block其實(shí)是有空閑空間的，Page的空閑空間管理的只是8KB空間內(nèi)有多少剩余空間，而FSM管理的則是relation對(duì)應(yīng)的所有的Block分別有多少剩余空間。所以為了更快的查找合適的空閑空間，fsm文件不應(yīng)該太大。所以FSM存儲(chǔ)的并不是真是的剩余空間，而

3、是近似值，用一個(gè)字節(jié)表示剩余空間的大小，也就是FSM將其剩余空間分成了256個(gè)檔次，每8K/256=32為一檔，那么，一個(gè)字節(jié)就足以表示一個(gè)block的剩余空間。所以產(chǎn)生了如下的對(duì)應(yīng)形式所以，對(duì)于任何一個(gè)表塊，只要找到它在fsm文件中對(duì)應(yīng)的字節(jié)，根據(jù)該字節(jié)的值就可以知道這個(gè)表中空閑空間的范圍是多少。同樣，對(duì)于任何一個(gè)表塊，可以根據(jù)其空閑空間的大小計(jì)算出它對(duì)應(yīng)的fsm文件的取值。比如，對(duì)于一個(gè)有N字節(jié)的表塊，其在fsm中記錄的值為（31+N）/32.2.2組織方式：我們最容易想到的管理relation所有block的的剩余空間的方式就是以數(shù)組的方法表示各個(gè)block的剩余空間，fsm0表示第0個(gè)

4、block的剩余空間，fsm1表示第一個(gè)block的剩余空間，然后把這個(gè)信息存入fsm文件即可。比如我想知道第800個(gè)block（0-based）還剩下多少空間，只需要將對(duì)應(yīng)的fsm文件的第800個(gè)字節(jié)（從0開始計(jì)數(shù)）讀出來即可。方便可以擴(kuò)展，比如relation新增一個(gè)block，只需要fsm文件新增一個(gè)字節(jié)即可。可是數(shù)組有致命的缺陷，我要查找剩余空間的值最小為40的，那數(shù)組就傻了眼，因?yàn)樗坏貌话€(gè)的比較，知道遇到值大于40的才能停下，如果block特別多，數(shù)組長度非常大，效率太低。所以不能采用這種方法。在postgresql中為了實(shí)現(xiàn)快速查找，F(xiàn)SM文件中并不是簡單的使用數(shù)組順序的存儲(chǔ)每

5、個(gè)表塊的空閑空間，而是使用了樹的結(jié)構(gòu)。在FSM塊之間使用了一個(gè)三層樹的結(jié)構(gòu)，第0層和第1層為輔助層，第2層FSM塊中用于實(shí)際存放各表塊的空閑空間值。第0層FSM塊只有一個(gè)，作為樹根；第1層FSM塊可以有多個(gè)，作為第0層FSM塊的子節(jié)點(diǎn)；第2層FSM塊也可以有多個(gè)，作為第1層FSM塊的子節(jié)點(diǎn)每一個(gè)FSM塊內(nèi)又構(gòu)成一個(gè)局部的最大堆二叉樹，但每一層的FSM塊內(nèi)的最大堆二叉樹又略有不同。第2層的FSM塊中的最大堆二叉樹的每一個(gè)葉子節(jié)點(diǎn)表示一個(gè)表塊的空閑空間值。按照從左至右的順序，所有的第2層FSM塊中葉子節(jié)點(diǎn)排列起來就一一對(duì)應(yīng)了表文件中的每一個(gè)表塊。所有的FSM塊中的節(jié)點(diǎn)從邏輯上構(gòu)成了一個(gè)全局的最大堆

6、二叉樹，其中的葉子結(jié)點(diǎn)從左至右順序?qū)?yīng)表文件中的文件塊。下面是FSM文件磁盤存儲(chǔ)與其邏輯結(jié)構(gòu)的映射關(guān)系實(shí)例圖。(1) 第0、1、4001+1、4001*2+1號(hào)FSM塊為FSM文件的輔助塊，用于快速的查找FSM文件，其中第0號(hào)塊就是根節(jié)點(diǎn)（第0層FSM塊），第1、1、4001+1、4001*2+1號(hào)FSM塊是第1層的FSM塊。(2) 其余的FSM塊術(shù)語第2層，用于存儲(chǔ)表塊的空閑空間值。即:l 第2個(gè)FSM塊存儲(chǔ)對(duì)應(yīng)表塊第0-4000-1表塊的空閑空間值。l 第3個(gè)FSM塊存儲(chǔ)對(duì)應(yīng)表塊第4000-4000*2-1表塊的空閑空間值。優(yōu)點(diǎn)，通過這樣的組織結(jié)構(gòu)，可以保證FSM文件的第一個(gè)文件塊中的二叉

7、樹根節(jié)點(diǎn)存儲(chǔ)的是所有表塊的空閑空間的最大值。這樣，當(dāng)需要從FSM文件中選擇一個(gè)表塊時(shí)就可以快速判定是否存在滿足要求的表塊。3.FSM原理及實(shí)現(xiàn)方式 FSM最主要的操作包括創(chuàng)建、查找和調(diào)整，下面注意介紹。3.1FSM創(chuàng)建FSM文件并不是在創(chuàng)建表文件的時(shí)候就被創(chuàng)建，而是推遲到需要使用FSM文件的時(shí)候，即執(zhí)行vacuum（清理操作）時(shí)或?yàn)榱瞬迦朐M第一次查找FSM文件時(shí)才創(chuàng)建。在創(chuàng)建FSM文件時(shí)，會(huì)預(yù)先創(chuàng)建三個(gè)FSM塊。在第2號(hào)FSM塊內(nèi)葉子節(jié)點(diǎn)中一次存儲(chǔ)從第0號(hào)開始的個(gè)表塊的空閑空間值，若沒有空閑空間或者空閑空間太小，則記錄為0。當(dāng)?shù)?號(hào)FSM塊滿之后，將會(huì)擴(kuò)展新的FSM塊。每個(gè)FSM塊的物理結(jié)構(gòu)

8、和內(nèi)存中FSM塊的結(jié)構(gòu)如下 物理結(jié)構(gòu) 內(nèi)存結(jié)構(gòu)從FSM塊的物理結(jié)構(gòu)和內(nèi)存結(jié)構(gòu)可以看,FSM塊的物理結(jié)構(gòu)和內(nèi)存結(jié)構(gòu)是一一對(duì)應(yīng)的。其中Fp_next_slot值是一個(gè)整數(shù)，用于提示下一次開始查詢二叉樹的葉子節(jié)點(diǎn)的位置。當(dāng)從FSM塊中找到一個(gè)合適的葉子節(jié)點(diǎn)位置時(shí)，若該FSM塊為葉子節(jié)點(diǎn)塊，則將fp_next_slot+1，否則設(shè)置為slot。這樣做的有兩點(diǎn)好處：第一，多個(gè)進(jìn)程同時(shí)向一個(gè)表中插入數(shù)據(jù)時(shí)，可以請(qǐng)求的進(jìn)程返回不同的表塊，從而避免了對(duì)同一個(gè)表塊的爭用。第二,符合操作系統(tǒng)預(yù)讀取和批量寫技術(shù)，按照表塊的順序進(jìn)行插入將獲益于操作系統(tǒng)的這一特性。fp_nodes數(shù)組存儲(chǔ)了一個(gè)最大堆二叉樹，從根節(jié)點(diǎn)開

9、始每層順序排列直到葉子節(jié)點(diǎn)，每個(gè)數(shù)組元素值都是一個(gè)整數(shù)值。3.2FSM查找函數(shù)fsm_search利用FSM文件查找一個(gè)具有指定空閑空間的表塊。在fsm_search中為了方便查找FSM文件，使用了如下數(shù)據(jù)結(jié)構(gòu)來表示FSM塊在樹中的位置。fsm_search函數(shù)的工作過程如下：（1） 首先初始化指針指向第0號(hào)FSM塊。然后循環(huán)地執(zhí)行步驟2-4。（2） 由塊指針表示的邏輯地址計(jì)算得到物理地址，并將這個(gè)FSM塊裝入緩沖區(qū)。（3） 如果對(duì)應(yīng)的FSM塊不存在，則直接返回一個(gè)無效表塊。（4） 調(diào)用函數(shù)fsm_search_avail在步驟2中裝入的FSM塊中查找一個(gè)符合條件的葉子節(jié)點(diǎn)。如果能找到這樣的葉

10、子結(jié)點(diǎn)，fsm_search_avail將返回該葉子結(jié)點(diǎn)在塊內(nèi)fp_nodes數(shù)組中的編號(hào)，否則將返回-1。根據(jù)這個(gè)返回值進(jìn)行如下判斷l(xiāng) 如果找到這樣的葉子節(jié)點(diǎn)編號(hào)不等于-1且當(dāng)前的塊指針已經(jīng)到達(dá)第二層，說明當(dāng)前的FSM塊中包含一個(gè)具有合適空閑空間的表塊信息，則調(diào)用函數(shù)fsm_get_heap_blk計(jì)算出表塊返回。l 如果找到的葉子節(jié)點(diǎn)的編號(hào)不等于-1且當(dāng)前的指針還沒有到達(dá)第2，說明當(dāng)前的FSM塊是第0層或者是第1岑的輔助塊，還需要繼續(xù)向下搜索，則調(diào)用函數(shù)fsm_get_child根據(jù)返回的葉子結(jié)點(diǎn)的編號(hào)取得下一個(gè)要搜索的FSM塊，然后回到步驟2繼續(xù)循環(huán)。l 如果找到的葉子節(jié)點(diǎn)的編號(hào)等于-1

11、，且當(dāng)前的塊指針指向第0層，說明整個(gè)FSM文件中都沒有可以滿足的空閑空間信息，因此直接返回?zé)o效塊好。l 如果找到的葉子節(jié)點(diǎn)的編號(hào)等于-1且當(dāng)前塊的指針沒有指向第0層，這種情況可能是因?yàn)楦讓拥腇SM的最大空閑空間值沒有得到更新。跟新后將直接重新指向第0號(hào)的FSM塊，再次從文件的根塊盡心剛搜索。具體的實(shí)現(xiàn)如下：static BlockNumberfsm_search(Relation rel, uint8 min_cat)intrestarts = 0;FSMAddressaddr = FSM_ROOT_ADDRESS;for (;)intslot;Bufferbuf;uint8max_avai

12、l = 0;buf = fsm_readbuf(rel, addr, false);if (BufferIsValid(buf)LockBuffer(buf, BUFFER_LOCK_SHARE);slot = fsm_search_avail(buf, min_cat,(addr.level = FSM_BOTTOM_LEVEL),false);if (slot = -1)max_avail = fsm_get_max_avail(BufferGetPage(buf);UnlockReleaseBuffer(buf);elseslot = -1;if (slot != -1)if (addr

13、.level = FSM_BOTTOM_LEVEL)return fsm_get_heap_blk(addr, slot);addr = fsm_get_child(addr, slot);else if (addr.level = FSM_ROOT_LEVEL)return InvalidBlockNumber;elseuint16parentslot;FSMAddressparent;parent = fsm_get_parent(addr, &parentslot);fsm_set_and_search(rel, parent, parentslot, max_avail, 0)

14、;if (restarts+ > 10000)return InvalidBlockNumber;addr = FSM_ROOT_ADDRESS;在開始的地方定義了一個(gè)整型變量restart，它的作用是在出現(xiàn)第4種情況的時(shí)候來一個(gè)判斷，當(dāng)程序從根塊循環(huán)執(zhí)行10000次還沒有找合適的空閑塊，則返回沒有找到，防止程序一直循環(huán)下去。fsm_search只是反映了在FSM塊層面上的查找過程，而每一個(gè)FSM塊內(nèi)的最大堆二叉樹的搜索過程則有函數(shù)fsm_search_avail實(shí)現(xiàn)，該函數(shù)從指定的FSM塊中獲取一個(gè)大于或等于min_cat的葉子節(jié)點(diǎn)。其流程如下：l 首先檢查FSM塊中的根節(jié)點(diǎn)，若根節(jié)點(diǎn)

15、無法滿足min_cat,則表明該塊中沒有滿足該請(qǐng)求的節(jié)點(diǎn)，返回-1.l 否則，根據(jù)fp_next_slot的值（fp_next_slot在初始化時(shí)為0，每一次找到合適的葉子節(jié)點(diǎn)會(huì)設(shè)置fp_next_slot的值，見步驟5），設(shè)置當(dāng)前結(jié)點(diǎn)指針nodeno=每個(gè)FSM塊中非葉子結(jié)點(diǎn)個(gè)數(shù)+fp_next_slot.進(jìn)入以下循環(huán)：（1） 若當(dāng)前的節(jié)點(diǎn)滿足需求，則跳出循環(huán)。（2） 否則，設(shè)置當(dāng)前結(jié)點(diǎn)指針為當(dāng)前結(jié)點(diǎn)的右節(jié)點(diǎn)的父節(jié)點(diǎn)，并返回步驟1。l 從步驟2找到的節(jié)點(diǎn)開始向下尋找一條通往葉子節(jié)點(diǎn)的路徑，該路徑上的每個(gè)節(jié)點(diǎn)的值都需要滿足要求。注意在尋找的過程那個(gè)中，可能會(huì)碰到左右子節(jié)點(diǎn)都滿足要求的情況，這時(shí)

16、候優(yōu)先選擇左節(jié)點(diǎn)。從該路徑到達(dá)的葉子節(jié)點(diǎn)即為最終的結(jié)果，將其序號(hào)記錄為slot。l 若當(dāng)前結(jié)點(diǎn)的塊為葉子結(jié)點(diǎn)塊，則設(shè)置fp_next_slot=slot+1，否則不變。l 返回solt，即找到的葉子節(jié)點(diǎn)的序號(hào)。具體的程序如下fsm_search_avail(Buffer buf, uint8 minvalue, bool advancenext, bool exclusive_lock_held)Pagepage = BufferGetPage(buf);FSMPagefsmpage = (FSMPage) PageGetContents(page);intnodeno;inttarget;u

17、int16slot;restart:if (fsmpage->fp_nodes0 < minvalue)return -1;= fsmpage->fp_next_slot;if (target < 0 | target >= LeafNodesPerPage)target = 0;target += NonLeafNodesPerPage;nodeno = target;while (nodeno > 0)if (fsmpage->fp_nodesnodeno >= minvalue)break;nodeno = parentof(rightne

18、ighbor(nodeno);while (nodeno < NonLeafNodesPerPage)intchildnodeno = leftchild(nodeno);if (childnodeno < NodesPerPage &&fsmpage->fp_nodeschildnodeno >= minvalue)nodeno = childnodeno;continue;childnodeno+;/* point to right child */if (childnodeno < NodesPerPage &&fsmpage

19、->fp_nodeschildnodeno >= minvalue)nodeno = childnodeno;elseRelFileNode rnode;ForkNumberforknum;BlockNumber blknum;BufferGetTag(buf, &rnode, &forknum, &blknum);elog(DEBUG1, "fixing corrupt FSM block %u, relation %u/%u/%u", blknum, rnode.spcNode, rnode.dbNode, rnode.relNode

20、);/* make sure we hold an exclusive lock */if (!exclusive_lock_held)LockBuffer(buf, BUFFER_LOCK_UNLOCK);LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);exclusive_lock_held = true;fsm_rebuild_page(page);MarkBufferDirtyHint(buf, false);goto restart;slot = nodeno - NonLeafNodesPerPage;fsmpage->fp_next_slot =

21、 slot + (advancenext ? 1 : 0);return slot;在其中我們需要注意的是關(guān)于葉節(jié)點(diǎn)的過程中并不是一味的從根節(jié)點(diǎn)開始往下尋找，而是先根據(jù)根節(jié)點(diǎn)判斷，再根據(jù)slot來指向一個(gè)葉子結(jié)點(diǎn)來進(jìn)行判斷的，這樣做的好處我們在上面也已經(jīng)提過了，不再累述。3.3FSM調(diào)整當(dāng)從FSM文件中找到一個(gè)具有合適空閑空間的表塊并使用它進(jìn)行數(shù)據(jù)插入之后，需要對(duì)FSM文件中的相關(guān)信息進(jìn)行修改，需要調(diào)整該表塊的空閑空間值，同時(shí)對(duì)其所附屬的FSM塊內(nèi)的最大堆二叉樹進(jìn)行相應(yīng)的調(diào)整。這個(gè)調(diào)整過程由函數(shù)fsm_set_avail完成，其參數(shù)包括表塊號(hào)，表的信息以及當(dāng)前的空閑空間值，主要的流程如下（1）

22、 如果新的空閑空閑空間值與舊值相等，則不做調(diào)整。（2） 如果空閑空間值發(fā)生了變化，則將新值賦給相應(yīng)的葉子結(jié)點(diǎn)。（3） 調(diào)整除二叉樹根節(jié)點(diǎn)以外的其他節(jié)點(diǎn)，是父節(jié)點(diǎn)的值總是為連個(gè)子節(jié)點(diǎn)的最大值。（4） 若新值大于樹的根節(jié)點(diǎn)的值是，調(diào)用fsm_rebuild_page重建快內(nèi)結(jié)構(gòu)，使其符合最大堆結(jié)構(gòu)。具體函數(shù)如下:bool fsm_set_avail(Page page, int slot, uint8 value)intnodeno = NonLeafNodesPerPage + slot;FSMPagefsmpage = (FSMPage) PageGetContents(page); uint

23、8oldvalue;Assert(slot < LeafNodesPerPage);oldvalue = fsmpage->fp_nodesnodeno;if (oldvalue = value && value <= fsmpage->fp_nodes0)return false;fsmpage->fp_nodesnodeno = value; douint8newvalue = 0;intlchild;intrchild;nodeno = parentof(nodeno);lchild = leftchild(nodeno);rchild = lchild + 1;newvalue = fsmpage->fp_nodeslchild;if (rchild < NodesPerPa