pg技术报告重点讲义

1、pg空闲空间管理技术报告1.概述随着表中不断插入和删除元组，文件块中必然会产生空闲空间，在插入元组时优先选择将其存放在空闲空间内是利用存储的好方法。但是这需要在该表的众多拥有空闲空间的文件块之间进行选择，而遍历所有文件块进行选择的开销将是非常庞大的。在postgresql8.4之前，方法是使用全局的FSM文件来记录所有表文件的空闲空间状况，其缺点是在全局FSM文件中只能记录每个表文件一定数量的文件块空闲空间，所以对于实际来说管理起来比较复杂，使用起来比较低效。在postgresql8.4之后，方法是为每个表（包括系统表在内）创建一个用于管理空闲空间的文件，称之为空闲空间映射表文件（FSM）。2

2、.存储和组织方式2.1存储方式在block.h中有这样一个声明，typedef uint32 BlockNumber;这个uint32就决定了一个relation最大只能有4G个block，每个block大小为8KB，也就是说一个relation的磁盘大小最大为32TB,比较大。我们需要注意relation的不断的插入删除记录，会造成很多的block其实是有空闲空间的，Page的空闲空间管理的只是8KB空间内有多少剩余空间，而FSM管理的则是relation对应的所有的Block分别有多少剩余空间。所以为了更快的查找合适的空闲空间，fsm文件不应该太大。所以FSM存储的并不是真是的剩余空间，而

3、是近似值，用一个字节表示剩余空间的大小，也就是FSM将其剩余空间分成了256个档次，每8K/256=32为一档，那么，一个字节就足以表示一个block的剩余空间。所以产生了如下的对应形式所以，对于任何一个表块，只要找到它在fsm文件中对应的字节，根据该字节的值就可以知道这个表中空闲空间的范围是多少。同样，对于任何一个表块，可以根据其空闲空间的大小计算出它对应的fsm文件的取值。比如，对于一个有N字节的表块，其在fsm中记录的值为（31+N）/32.2.2组织方式：我们最容易想到的管理relation所有block的的剩余空间的方式就是以数组的方法表示各个block的剩余空间，fsm0表示第0个

4、block的剩余空间，fsm1表示第一个block的剩余空间，然后把这个信息存入fsm文件即可。比如我想知道第800个block（0-based）还剩下多少空间，只需要将对应的fsm文件的第800个字节（从0开始计数）读出来即可。方便可以扩展，比如relation新增一个block，只需要fsm文件新增一个字节即可。可是数组有致命的缺陷，我要查找剩余空间的值最小为40的，那数组就傻了眼，因为他不得不挨个的比较，知道遇到值大于40的才能停下，如果block特别多，数组长度非常大，效率太低。所以不能采用这种方法。在postgresql中为了实现快速查找，FSM文件中并不是简单的使用数组顺序的存储每

5、个表块的空闲空间，而是使用了树的结构。在FSM块之间使用了一个三层树的结构，第0层和第1层为辅助层，第2层FSM块中用于实际存放各表块的空闲空间值。第0层FSM块只有一个，作为树根；第1层FSM块可以有多个，作为第0层FSM块的子节点；第2层FSM块也可以有多个，作为第1层FSM块的子节点每一个FSM块内又构成一个局部的最大堆二叉树，但每一层的FSM块内的最大堆二叉树又略有不同。第2层的FSM块中的最大堆二叉树的每一个叶子节点表示一个表块的空闲空间值。按照从左至右的顺序，所有的第2层FSM块中叶子节点排列起来就一一对应了表文件中的每一个表块。所有的FSM块中的节点从逻辑上构成了一个全局的最大堆

6、二叉树，其中的叶子结点从左至右顺序对应表文件中的文件块。下面是FSM文件磁盘存储与其逻辑结构的映射关系实例图。(1) 第0、1、4001+1、4001*2+1号FSM块为FSM文件的辅助块，用于快速的查找FSM文件，其中第0号块就是根节点（第0层FSM块），第1、1、4001+1、4001*2+1号FSM块是第1层的FSM块。(2) 其余的FSM块术语第2层，用于存储表块的空闲空间值。即:l 第2个FSM块存储对应表块第0-4000-1表块的空闲空间值。l 第3个FSM块存储对应表块第4000-4000*2-1表块的空闲空间值。优点，通过这样的组织结构，可以保证FSM文件的第一个文件块中的二叉

7、树根节点存储的是所有表块的空闲空间的最大值。这样，当需要从FSM文件中选择一个表块时就可以快速判定是否存在满足要求的表块。3.FSM原理及实现方式 FSM最主要的操作包括创建、查找和调整，下面注意介绍。3.1FSM创建FSM文件并不是在创建表文件的时候就被创建，而是推迟到需要使用FSM文件的时候，即执行vacuum（清理操作）时或为了插入元组第一次查找FSM文件时才创建。在创建FSM文件时，会预先创建三个FSM块。在第2号FSM块内叶子节点中一次存储从第0号开始的个表块的空闲空间值，若没有空闲空间或者空闲空间太小，则记录为0。当第2号FSM块满之后，将会扩展新的FSM块。每个FSM块的物理结构

8、和内存中FSM块的结构如下 物理结构 内存结构从FSM块的物理结构和内存结构可以看,FSM块的物理结构和内存结构是一一对应的。其中Fp_next_slot值是一个整数，用于提示下一次开始查询二叉树的叶子节点的位置。当从FSM块中找到一个合适的叶子节点位置时，若该FSM块为叶子节点块，则将fp_next_slot+1，否则设置为slot。这样做的有两点好处：第一，多个进程同时向一个表中插入数据时，可以请求的进程返回不同的表块，从而避免了对同一个表块的争用。第二,符合操作系统预读取和批量写技术，按照表块的顺序进行插入将获益于操作系统的这一特性。fp_nodes数组存储了一个最大堆二叉树，从根节点开

9、始每层顺序排列直到叶子节点，每个数组元素值都是一个整数值。3.2FSM查找函数fsm_search利用FSM文件查找一个具有指定空闲空间的表块。在fsm_search中为了方便查找FSM文件，使用了如下数据结构来表示FSM块在树中的位置。fsm_search函数的工作过程如下：（1） 首先初始化指针指向第0号FSM块。然后循环地执行步骤2-4。（2） 由块指针表示的逻辑地址计算得到物理地址，并将这个FSM块装入缓冲区。（3） 如果对应的FSM块不存在，则直接返回一个无效表块。（4） 调用函数fsm_search_avail在步骤2中装入的FSM块中查找一个符合条件的叶子节点。如果能找到这样的叶

10、子结点，fsm_search_avail将返回该叶子结点在块内fp_nodes数组中的编号，否则将返回-1。根据这个返回值进行如下判断l 如果找到这样的叶子节点编号不等于-1且当前的块指针已经到达第二层，说明当前的FSM块中包含一个具有合适空闲空间的表块信息，则调用函数fsm_get_heap_blk计算出表块返回。l 如果找到的叶子节点的编号不等于-1且当前的指针还没有到达第2，说明当前的FSM块是第0层或者是第1岑的辅助块，还需要继续向下搜索，则调用函数fsm_get_child根据返回的叶子结点的编号取得下一个要搜索的FSM块，然后回到步骤2继续循环。l 如果找到的叶子节点的编号等于-1

11、，且当前的块指针指向第0层，说明整个FSM文件中都没有可以满足的空闲空间信息，因此直接返回无效块好。l 如果找到的叶子节点的编号等于-1且当前块的指针没有指向第0层，这种情况可能是因为更底层的FSM的最大空闲空间值没有得到更新。跟新后将直接重新指向第0号的FSM块，再次从文件的根块尽心刚搜索。具体的实现如下：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;在开始的地方定义了一个整型变量restart，它的作用是在出现第4种情况的时候来一个判断，当程序从根块循环执行10000次还没有找合适的空闲块，则返回没有找到，防止程序一直循环下去。fsm_search只是反映了在FSM块层面上的查找过程，而每一个FSM块内的最大堆二叉树的搜索过程则有函数fsm_search_avail实现，该函数从指定的FSM块中获取一个大于或等于min_cat的叶子节点。其流程如下：l 首先检查FSM块中的根节点，若根节点

15、无法满足min_cat,则表明该块中没有满足该请求的节点，返回-1.l 否则，根据fp_next_slot的值（fp_next_slot在初始化时为0，每一次找到合适的叶子节点会设置fp_next_slot的值，见步骤5），设置当前结点指针nodeno=每个FSM块中非叶子结点个数+fp_next_slot.进入以下循环：（1） 若当前的节点满足需求，则跳出循环。（2） 否则，设置当前结点指针为当前结点的右节点的父节点，并返回步骤1。l 从步骤2找到的节点开始向下寻找一条通往叶子节点的路径，该路径上的每个节点的值都需要满足要求。注意在寻找的过程那个中，可能会碰到左右子节点都满足要求的情况，这时

16、候优先选择左节点。从该路径到达的叶子节点即为最终的结果，将其序号记录为slot。l 若当前结点的块为叶子结点块，则设置fp_next_slot=slot+1，否则不变。l 返回solt，即找到的叶子节点的序号。具体的程序如下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;在其中我们需要注意的是关于叶节点的过程中并不是一味的从根节点开始往下寻找，而是先根据根节点判断，再根据slot来指向一个叶子结点来进行判断的，这样做的好处我们在上面也已经提过了，不再累述。3.3FSM调整当从FSM文件中找到一个具有合适空闲空间的表块并使用它进行数据插入之后，需要对FSM文件中的相关信息进行修改，需要调整该表块的空闲空间值，同时对其所附属的FSM块内的最大堆二叉树进行相应的调整。这个调整过程由函数fsm_set_avail完成，其参数包括表块号，表的信息以及当前的空闲空间值，主要的流程如下（1）

22、 如果新的空闲空闲空间值与旧值相等，则不做调整。（2） 如果空闲空间值发生了变化，则将新值赋给相应的叶子结点。（3） 调整除二叉树根节点以外的其他节点，是父节点的值总是为连个子节点的最大值。（4） 若新值大于树的根节点的值是，调用fsm_rebuild_page重建快内结构，使其符合最大堆结构。具体函数如下: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