暂无图片
暂无图片
暂无图片
暂无图片
暂无图片
首页 / 海山数据库(He3DB)源码详解：海山PG 空闲空间映射表FSM

海山数据库(He3DB)源码详解：海山PG 空闲空间映射表FSM

wukong 2024-09-23
462

一、FSM的基本原理

FSM文件是Free Space Map（空闲空间映射）的缩写，用于跟踪和记录数据块（Page）中的空闲空间。随着数据表不断进行插入、更新和删除元组等操作，数据页内必然会存在空页空间。在插入新的元组时，有两种方式可以选择：直接选择新的页来存放、存放到已有页的空闲空间中。

如果采用第一种存放方式，会明显造成空间利用率的浪费；而采用第二种存放方式，可以明显地节约存储成本，但是这种方式会存在一个问题：如何快速知道哪个页有足够的空闲空间可以存放元组数据，如果每次插入都要遍历所有数据页、直到找到有满足条件的数据页，但是这种方式的查询效率非常低。因此，海山PG采用FSM来记录每个页的空闲空间信息。

通过FSM，在插入新的元组时可以快速地定位到足够空间的空闲页面进行存放，或者发现没有满足条件的页面，需要扩展出一个新页。
FSM机制采用一个字节表示空闲空间的大小范围，并将这个字节叫做FSM级别（category）。通过这种方式，可以减少FSM的存储空间，加快搜索查询效率。FSM级别和真实的FSM范围之间的映射关系如下表所示。

字节 空闲空间范围（字节）
0 0～31
1 32～63
… …
255 8164~8191

为了实现快速查找，FSM文件并不是简单使用数组顺序存储每个表块的空闲空间，而是使用了树结构。在FSM块之间使用了一种三层树结构，其中第0层和第1层是辅助层，第二层FSM块实际存储各表块的FSM级别。第0层FSM块只有一个，作为树根；第1层FSM块可以有多个，作为第0层FSM块的子节点；第2层FSM块同理。每个FSM块内又构成一棵局部的最大堆二叉树，但每一层FSM块内的最大堆二叉树又略有不同。

（1）第2层FSM块内大根堆二叉树的每一个叶子节点对应一个表块的空闲空间级别。按照从左到右的顺序，最左边FSM块的最左边叶子节点代表表文件的第一块，左边第二个叶子节点代表表文件的第二块。

（2）第1层FSM块内大根堆二叉树的叶子节点从左到右对应第2层FSM块的根节点。

（3）第0层FSM块内大根堆二叉树的叶子节点从左到右对应第1层FSM块的根节点。

从上面的介绍可知，三层树结构形成了一个逻辑上的大根堆结构，其叶子节点从左到右依次对应表文件中的文件块。

在单个FSM块内，使用大根堆能保证所有叶子节点的最大值被上升到根节点处。因此只要看单个FSM块内的根节点值就可指导此FSM块内空闲空间的上限值。

每个FSM块大小为8KB，除去必要的页头信息，FSM块剩下的空间都用来存储块内的二叉树结构，每个叶子节点都用一个字节表示，因此FSM块内大约可以保存4000个叶子节点（这样，一个FSM文件如果采用三层树结构，大约可以记录4000^3 个叶子节点，对应于4000^3 个表块，远大于2^32 (单个表的最大块数，PG块号数据结构BlockIdData中定义块号长度为32，故单个表最多只能有（2^32-1）个表块)。因此，这样的三层树结构足以记录表文件所有文件块的空闲空间值。

一个FSM文件内所包含的FSM块和表块的映射关系如下图所示。

图片1.png

二、FSM文件的管理

1、FSM结构体

typedef struct
{
	/*
	 * fsm_search_avail() 函数尝试通过以循环方式返回不同页面给不同的后端来分散多个后端的负载
	 */
	int			fp_next_slot;  // 用于提示下一次开始查询二叉树时的叶子节点位置

	/*
	 * fp_nodes 包含以数组形式存储的二叉树。前NonLeafNodesPerPage个元素是上层节点
   * 后LeafNodesPerPage个元素是叶节点，未使用的节点为零
	 */
	uint8		fp_nodes[FLEXIBLE_ARRAY_MEMBER];
} FSMPageData;


/* 一个FSM块中可以保存的节点总数目（8192 - 24 - 4 = 8164 ） */
#define NodesPerPage (BLCKSZ - MAXALIGN(SizeOfPageHeaderData) - \
					  offsetof(FSMPageData, fp_nodes))

/* FSM块中保存的非叶子节点数目（8192/2 - 1 = 4095） */
#define NonLeafNodesPerPage (BLCKSZ / 2 - 1)

/* FSM块中保存的叶子节点数目 （8164 - 4095 = 4069） */
#define LeafNodesPerPage (NodesPerPage - NonLeafNodesPerPage)

2、FSM文件的创建

FSM文件并不是在创建表文件时立即创建的，而是在需要时才会创建，比如执行VACUUM操作时，或者为了插入行而第一次查询FSM文件时。在创建FSM文件时，会预先创建三个FSM块：第0号为根节点即第0层的FSM块，第1号为第1层的第一个节点，第2号为第2层的第一个结点。在第二号FSM块内叶子节点中一次存储从第0号开始的各表块的空闲空间值，若没有空闲空间或空闲空间太小，则记录为0。当第2号FSM块满了之后，将会扩展新的FSM块。该工作主要调用fsm_extend进行实现。

static void
fsm_extend(Relation rel, BlockNumber fsm_nblocks)
{
	BlockNumber fsm_nblocks_now;  // 当前FSM文件块数
	PGAlignedBlock pg;  // 结构体，用于存储页面数据
	SMgrRelation reln;  // 获取的存储管理器关系

	PageInit((Page) pg.data, BLCKSZ, 0);  // 初始化一个页面

	
	LockRelationForExtension(rel, ExclusiveLock);  // 加锁，防止其他后端同时扩展FSM文件或主文件

	/* 如果发生了缓存刷新，可能需要重新获取关系 */
	reln = RelationGetSmgr(rel);

	
	if ((reln->smgr_cached_nblocks[FSM_FORKNUM] == 0 ||
		 reln->smgr_cached_nblocks[FSM_FORKNUM] == InvalidBlockNumber) &&
		!smgrexists(reln, FSM_FORKNUM))   // 检查FSM文件是否存在；如果
		smgrcreate(reln, FSM_FORKNUM, false);  // 不存在，则创建；smgr_cached_nblocks是正数，则必定存在

	/* Invalidate cache so that smgrnblocks() asks the kernel. */
	reln->smgr_cached_nblocks[FSM_FORKNUM] = InvalidBlockNumber;
	fsm_nblocks_now = smgrnblocks(reln, FSM_FORKNUM);  // 获取当前FSM分支最新的块数

	/* Extend as needed. */
	while (fsm_nblocks_now < fsm_nblocks)  // 扩展条件
	{
		PageSetChecksumInplace((Page) pg.data, fsm_nblocks_now);  // 在新块上设置页面的校验和

		smgrextend(reln, FSM_FORKNUM, fsm_nblocks_now,
				   pg.data, false);  // 将新页面添加到FSM文件中

		fsm_nblocks_now++;
	}

	UnlockRelationForExtension(rel, ExclusiveLock);  // 释放锁
}

实现流程如下：

  1. 初始化一个空的页：首先，使用PageInit函数初始化一个PGAlignedBlock结构体pg的data字段，这个页被设置为一个空页，即所有位都填充为0，表示该页没有空闲空间。
  2. 加锁：通过LockRelationForExtension函数对关系加上扩展锁，以防止其他后端同时扩展FSM或主分叉。
  3. 获取SMgrRelation指针：通过RelationGetSmgr函数获取当前关系的存储管理器指针，以便后续进行存储层面的操作。
  4. 检查并创建FSM文件：如果FSM分叉不存在，则通过smgrcreate函数创建它。
  5. 更新缓存并获取当前FSM块数：将FSM分叉的缓存块数设置为InvalidBlockNumber，以强制smgrnblocks函数从内核获取最新的块数。然后，通过smgrnblocks函数获取当前FSM的块数。
  6. 扩展FSM：如果当前FSM的块数小于指定的fsm_nblocks，则进入一个循环，每次循环中都会创建一个新的空页，并使用PageSetChecksumInplace函数为该页设置校验和。然后，通过smgrextend函数将新页添加到FSM分叉中，并递增fsm_nblocks_now以跟踪当前FSM的块数。
  7. 解锁：扩展完成后，通过UnlockRelationForExtension函数释放之前获取的扩展锁。

3、FSM文件的查找

函数fsm_search利用FSM文件查找一个具有指定空闲空间的表块。该函数有两个参数：表的基本信息rel和最小空闲空间值min_cat，该函数将在rel中找到一个至少具有min_cat*32字节空闲空间的表块。

整体的逻辑如下：

  • 首先从FSM文件中获取根节点（root）的FSM块，在FSM块中开始寻找叶子节点：

  • 如果找到具有足够空间的叶子节点，判断当前是否是第2层：

  • 如果是第2层，直接返回结果

  • 如果不是，则继续向下遍历

  • 如果找不到有足够空间的叶子节点，判断当前是否是根节点：

    • 如果是根节点，说明当前FSM映射的所有表块都不够存储新元组，需要分配新的表块

    • 如果不是根节点，说明当搜索根节点的时候，是有足够空间，但是遍历到底层树的时候，空间被其它线程给分配了，这个时候，就需要更新上层节点的信息，重新从root FSM块开始重新搜索。

static BlockNumber
fsm_search(Relation rel, uint8 min_cat)
{
	int			restarts = 0;  // 初始化计数器跟踪搜索过程中的重启次数
	FSMAddress	addr = FSM_ROOT_ADDRESS;   // 从根地址开始搜索

	for (;;)  // 循环，直到找到符合条件的堆页面或确定没有符合条件的页面
	{
		int			slot;
		Buffer		buf;
		uint8		max_avail = 0;

		/* Read the FSM page. */
		buf = fsm_readbuf(rel, addr, false);  // 获取当前FSM页面的内容

		/* 在页面内部进行搜索 */
		if (BufferIsValid(buf))  // 页面有效
		{
			LockBuffer(buf, BUFFER_LOCK_SHARE);  // 加锁
			slot = fsm_search_avail(buf, min_cat, (addr.level == false);  // 尝试在该页面上找到具有至少min_cat类别空闲空间的槽位
			/* 如果当前块内无法找到满足条件的叶子节点，记录当前块内最大的FSM级别的max_avail */
			if (slot == -1)
				max_avail = fsm_get_max_avail(BufferGetPage(buf));
			UnlockReleaseBuffer(buf);  // 解锁
		}
		else
			slot = -1;

		/* 如果能找到满足条件的叶子节点 */
		if (slot != -1)
		{
			/* 如果在树的底层找到了合适的页面，则返回该页面 */
			if (addr.level == FSM_BOTTOM_LEVEL)
				return fsm_get_heap_blk(addr, slot);

			/* 如果未达到底层，则调用fsm_get_child获取下一个要搜索的FSM块，重新开始循环 */
			addr = fsm_get_child(addr, slot);
		}
		else if (addr.level == FSM_ROOT_LEVEL)
		{
			/* 如果在根级别没有找到，意味着整个FSM中没有足够的空闲空间。放弃搜索 */
			return InvalidBlockNumber;
		}
		else
		{
			uint16		parentslot;  // 父节点的块号
			FSMAddress	parent;  // 父节点的地址

			/*
			 * 在较低级别上搜索失败可能是因为上层节点的值没有反映下层页面的实际情况。
			 * 更新上层节点，避免再次陷入相同的陷阱，然后从头开始搜索
			 */
			parent = fsm_get_parent(addr, &parentslot);
			fsm_set_and_search(rel, parent, parentslot, max_avail, 0);  // 查找并更新父节点的最大空闲空间值

			/* 如果上层页面严重过时，可能需要多次循环更新 */
			if (restarts++ > 10000)
				return InvalidBlockNumber;

			/* 从根上开始重新搜索 */
			addr = FSM_ROOT_ADDRESS;
		}
	}
}

依赖的函数

上述代码中，查找具有足够空间的叶子节点这一关键功能是通过fsm_search_avail函数实现的。对于每个FSM块内部的二叉堆，并非从堆顶开始搜索，而是从fp_next_slot+NonLeafNodesPerPage的位置开始搜索。如果当前fp_next_slot不符合条件，则找到其右兄弟的父亲节点，继续判断，如果还不符合条件，则重复之前的操作继续向上搜索。

int
fsm_search_avail(Buffer buf, uint8 minvalue, bool advancenext, bool exclusive_lock_held)
{	
	Page		page = BufferGetPage(buf);
	FSMPage		fsmpage = (FSMPage) PageGetContents(page);
	int			nodeno;
	int			target;
	uint16		slot;

restart:

	/* 检查根节点，如果根节点的空闲空间小于minvalue，则直接返回-1 */
	if (fsmpage->fp_nodes[0] < minvalue)
		return -1;

	/* 从fp_next_slot开始搜索 */
	target = fsmpage->fp_next_slot;
	if (target < 0 || target >= LeafNodesPerPage)  // 目标节点错误
		target = 0;  // 将目标节点清零
	target += NonLeafNodesPerPage;  //目标节点加上非叶子节点的数量，指向第一个叶子节点

	/* 从目标节点开始搜索，在每一步中，向右移动一个节点，然后上升到父节点 */
	nodeno = target;
	while (nodeno > 0)
	{
		// 如果当前节点的FSM级别满足要求，直接跳出循环
		if (fsmpage->fp_nodes[nodeno] >= minvalue)
			break;

		/* 向右移动，必要时在同一层级内循环，即最右节点的右节点是最左节点 */
		nodeno = parentof(rightneighbor(nodeno));
	}

	/*
	 * 当在树的中间位置找到了有足够空间的节点，向下到底层
	 * 在向下寻径过程中，如果左右叶子节点都符合条件，优先选取左子节点
	 */
	while (nodeno < NonLeafNodesPerPage)
	{
		int			childnodeno = leftchild(nodeno);  // 优先寻找左节点

		if (childnodeno < NodesPerPage &&
			fsmpage->fp_nodes[childnodeno] >= minvalue)  // 左节点满足要求
		{
			nodeno = childnodeno;  // 设置当前节点为左节点
			continue;
		}
		childnodeno++;			/* 指向右子节点 */
		if (childnodeno < NodesPerPage &&
			fsmpage->fp_nodes[childnodeno] >= minvalue)  // 如果右节点满足要求
		{
			nodeno = childnodeno;  // 当前节点指向右节点
		}
		else
		{
			/* 如果出现了父节点承诺的空间不足的情况，修复损坏并重新开始 */
			RelFileNode rnode;
			ForkNumber	forknum;
			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);

			/* 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);  // 修复当前FSM块
			MarkBufferDirtyHint(buf, false);  // //将当前块变为脏块，写入磁盘
			goto restart;
		}
	}

	//跳出循环说明我们已经找到了符合条件的第2层的叶子节点
	slot = nodeno - NonLeafNodesPerPage;  //减去非叶子节点个数(直接获取在叶子层中的序号)

	/* 更新下一个目标指针 */
	fsmpage->fp_next_slot = slot + (advancenext ? 1 : 0);

	return slot;
}

4、FSM文件的调整

当从FSM文件中找到了一个具有合适空闲空间的表块并使用它进行了数据插入之后，需要对FSM文件中相关信息进行修改，需要调整该表块的空闲空间值，同时对其所属的FSM块内的最大堆二叉树进行相应的调整，整个调整的过程由函数RecordPageWithFreeSpace完成，其参数包括表块号，表的信息以及表块当前的空闲空间值。

void
RecordPageWithFreeSpace(Relation rel, BlockNumber heapBlk, Size spaceAvail)
{
	int			new_cat = fsm_space_avail_to_cat(spaceAvail);  // 获取新的空闲空间值
	FSMAddress	addr;  // FSM地址
	uint16		slot;  // 要修改的节点号

	/* 获取表示该页面在FSM中的地址和槽位 */
	addr = fsm_get_location(heapBlk, &slot);  

	fsm_set_and_search(rel, addr, slot, new_cat, 0);  // 设置并搜索相关信息，更新FSM中该页面的空闲空间值
}

依赖的函数

（1）fsm_set_and_search函数为RecordPageWithFreeSpace函数的核心部分，其作用是在给定的FSM页面和槽位中设置值。

过程大致如下：

  • 根据表块号读取块内容到缓冲区中并且上锁。

  • 调用fsm_set_avail函数对FSM块的内容进行修改

    • 如果新的空闲空间值和旧的空闲空间值相等，则无需修改。

    • 如果不相等，则赋新值给对应的叶子节点。

    • 调整根节点外的其他节点，维持大根堆的特性。

    • 如果新的空闲空间值比根节点的空闲空间值还大，则需要重新建树。

  • 如果发生了修改，则设置当前块为脏，写入到磁盘中。

static int
fsm_set_and_search(Relation rel, FSMAddress addr, uint16 slot,
				   uint8 newValue, uint8 minValue)
{
  Buffer		buf;  
	Page		page;
	int			newslot = -1;

	buf = fsm_readbuf(rel, addr, true);  // 读取指定的FSM页面到缓冲区中
	LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);   // 缓冲区加排他锁

	page = BufferGetPage(buf);  // 将缓冲区的内容转为块结构

	if (fsm_set_avail(page, slot, newValue))  // 在FSM页面的指定槽位上设置新值，判断是否成功
		MarkBufferDirtyHint(buf, false);  // 设置成功，则标记缓冲区为脏，以便后续将更改写回磁盘

	if (minValue != 0)
	{
		/* 在当前锁定的FSM页面中搜索具有至少 minValue 空闲空间的页面 */
		newslot = fsm_search_avail(buf, minValue, addr.level == true); 
	}

	UnlockReleaseBuffer(buf);  // 解锁

	return newslot;
}

（2）fsm_set_avail函数的作用是在页面上设置槽位的值，如果页面被修改，返回true。

bool
fsm_set_avail(Page page, int slot, uint8 value)
{
	int			nodeno = NonLeafNodesPerPage + slot;  // 计算槽位对应的节点编号
	FSMPage		fsmpage = (FSMPage) PageGetContents(page);   // 获取FSM页面内容
	uint8		oldvalue;

	Assert(slot < LeafNodesPerPage);  // 如果slot不是叶子节点，则报错

	oldvalue = fsmpage->fp_nodes[nodeno];  // 获取当前节点的旧值

	/* 若新值与旧值相同，不进行任何操作 */
	if (oldvalue == value && value <= fsmpage->fp_nodes[0]) 
		return false;

	fsmpage->fp_nodes[nodeno] = value;  // 设置新值

	/*
	 * 维护大根堆
	 * 向上传播更新，直到达到根节点或找到不需要更新的节点
	 */
	do
	{
		uint8		newvalue = 0;  // 新的空闲空间值，用于比较大小和修改
		int			lchild;  // 左节点
		int			rchild;  // 右节点
         
        /* 此时nodeno为目标节点的父节点 */
		nodeno = parentof(nodeno);  // 当前节点变为当前节点的父节点
		lchild = leftchild(nodeno); // 获取当前节点的左孩子
		rchild = lchild + 1;  // 获取当前节点的右孩子

		newvalue = fsmpage->fp_nodes[lchild];  // 将newvalue设置为左孩子的空闲空间值
		if (rchild < NodesPerPage)  // 如果右孩子不是叶子节点
			newvalue = Max(newvalue,
						   fsmpage->fp_nodes[rchild]);  //newvalue=左孩子和右孩子的空闲空间值中更大的那一个。

        /* oldvalue更新为原父亲的值 */
		oldvalue = fsmpage->fp_nodes[nodeno];
		if (oldvalue == newvalue)
			break;

        /* 父节点更新为newvalue */
		fsmpage->fp_nodes[nodeno] = newvalue;
	} while (nodeno > 0);

	/*
	 * 如果新值仍高于根节点的值，则树结构可能损坏
     * 若出现这种情况，重建页面
	 */
	if (value > fsmpage->fp_nodes[0])
		fsm_rebuild_page(page);

	return true;
}
```# 一、FSM的基本原理

FSM文件是Free Space Map（空闲空间映射）的缩写，用于跟踪和记录数据块（Page）中的空闲空间。随着数据表不断进行插入、更新和删除元组等操作，数据页内必然会存在空页空间。在插入新的元组时，有两种方式可以选择：直接选择新的页来存放、存放到已有页的空闲空间中。

如果采用第一种存放方式，会明显造成空间利用率的浪费；而采用第二种存放方式，可以明显地节约存储成本，但是这种方式会存在一个问题：如何快速知道哪个页有足够的空闲空间可以存放元组数据，如果每次插入都要遍历所有数据页、直到找到有满足条件的数据页，但是这种方式的查询效率非常低。因此，海山PG采用FSM来记录每个页的空闲空间信息。

通过FSM，在插入新的元组时可以快速地定位到足够空间的空闲页面进行存放，或者发现没有满足条件的页面，需要扩展出一个新页。
FSM机制采用一个字节表示空闲空间的大小范围，并将这个字节叫做FSM级别（category）。通过这种方式，可以减少FSM的存储空间，加快搜索查询效率。FSM级别和真实的FSM范围之间的映射关系如下表所示。

| 字节  | 空闲空间范围（字节） |
| --- | ---------- |
| 0   | 0～31       |
| 1   | 32～63      |
| ... | ...        |
| 255 | 8164~8191 |

为了实现快速查找，FSM文件并不是简单使用数组顺序存储每个表块的空闲空间，而是使用了树结构。在FSM块之间使用了一种三层树结构，其中第0层和第1层是辅助层，第二层FSM块实际存储各表块的FSM级别。第0层FSM块只有一个，作为树根；第1层FSM块可以有多个，作为第0层FSM块的子节点；第2层FSM块同理。每个FSM块内又构成一棵局部的最大堆二叉树，但每一层FSM块内的最大堆二叉树又略有不同。

（1）第2层FSM块内大根堆二叉树的每一个叶子节点对应一个表块的空闲空间级别。按照从左到右的顺序，最左边FSM块的最左边叶子节点代表表文件的第一块，左边第二个叶子节点代表表文件的第二块。

（2）第1层FSM块内大根堆二叉树的叶子节点从左到右对应第2层FSM块的根节点。

（3）第0层FSM块内大根堆二叉树的叶子节点从左到右对应第1层FSM块的根节点。

从上面的介绍可知，三层树结构形成了一个逻辑上的大根堆结构，其叶子节点从左到右依次对应表文件中的文件块。

在单个FSM块内，使用大根堆能保证所有叶子节点的最大值被上升到根节点处。因此只要看单个FSM块内的根节点值就可指导此FSM块内空闲空间的上限值。

每个FSM块大小为8KB，除去必要的页头信息，FSM块剩下的空间都用来存储块内的二叉树结构，每个叶子节点都用一个字节表示，因此FSM块内大约可以保存4000个叶子节点（这样，一个FSM文件如果采用三层树结构，大约可以记录4000^3 个叶子节点，对应于4000^3 个表块，远大于2^32 (单个表的最大块数，PG块号数据结构BlockIdData中定义块号长度为32，故单个表最多只能有（2^32-1）个表块)。因此，这样的三层树结构足以记录表文件所有文件块的空闲空间值。

一个FSM文件内所包含的FSM块和表块的映射关系如下图所示。

![图片1.png](https://p0-xtjj-private.juejin.cn/tos-cn-i-73owjymdk6/e052c9a36b0f44499a8fbd89a7b00530~tplv-73owjymdk6-jj-mark-v1:0:0:0:0:5o6Y6YeR5oqA5pyv56S-5Yy6IEAg55So5oi3MzExMjI5NjgxNjU=:q75.awebp?policy=eyJ2bSI6MywidWlkIjoiMTc2NjI3MDc3OTI3Mjc3OSJ9&rk3s=f64ab15b&x-orig-authkey=f32326d3454f2ac7e96d3d06cdbb035152127018&x-orig-expires=1727398961&x-orig-sign=%2B3pSHl934WygfxyeTh06nV6hCkE%3D)


# 二、FSM文件的管理

## 1、FSM结构体

```js
typedef struct
{
	/*
	 * fsm_search_avail() 函数尝试通过以循环方式返回不同页面给不同的后端来分散多个后端的负载
	 */
	int			fp_next_slot;  // 用于提示下一次开始查询二叉树时的叶子节点位置

	/*
	 * fp_nodes 包含以数组形式存储的二叉树。前NonLeafNodesPerPage个元素是上层节点
   * 后LeafNodesPerPage个元素是叶节点，未使用的节点为零
	 */
	uint8		fp_nodes[FLEXIBLE_ARRAY_MEMBER];
} FSMPageData;


/* 一个FSM块中可以保存的节点总数目（8192 - 24 - 4 = 8164 ） */
#define NodesPerPage (BLCKSZ - MAXALIGN(SizeOfPageHeaderData) - \
					  offsetof(FSMPageData, fp_nodes))

/* FSM块中保存的非叶子节点数目（8192/2 - 1 = 4095） */
#define NonLeafNodesPerPage (BLCKSZ / 2 - 1)

/* FSM块中保存的叶子节点数目 （8164 - 4095 = 4069） */
#define LeafNodesPerPage (NodesPerPage - NonLeafNodesPerPage)

2、FSM文件的创建

FSM文件并不是在创建表文件时立即创建的，而是在需要时才会创建，比如执行VACUUM操作时，或者为了插入行而第一次查询FSM文件时。在创建FSM文件时，会预先创建三个FSM块：第0号为根节点即第0层的FSM块，第1号为第1层的第一个节点，第2号为第2层的第一个结点。在第二号FSM块内叶子节点中一次存储从第0号开始的各表块的空闲空间值，若没有空闲空间或空闲空间太小，则记录为0。当第2号FSM块满了之后，将会扩展新的FSM块。该工作主要调用fsm_extend进行实现。

static void
fsm_extend(Relation rel, BlockNumber fsm_nblocks)
{
	BlockNumber fsm_nblocks_now;  // 当前FSM文件块数
	PGAlignedBlock pg;  // 结构体，用于存储页面数据
	SMgrRelation reln;  // 获取的存储管理器关系

	PageInit((Page) pg.data, BLCKSZ, 0);  // 初始化一个页面

	
	LockRelationForExtension(rel, ExclusiveLock);  // 加锁，防止其他后端同时扩展FSM文件或主文件

	/* 如果发生了缓存刷新，可能需要重新获取关系 */
	reln = RelationGetSmgr(rel);

	
	if ((reln->smgr_cached_nblocks[FSM_FORKNUM] == 0 ||
		 reln->smgr_cached_nblocks[FSM_FORKNUM] == InvalidBlockNumber) &&
		!smgrexists(reln, FSM_FORKNUM))   // 检查FSM文件是否存在；如果
		smgrcreate(reln, FSM_FORKNUM, false);  // 不存在，则创建；smgr_cached_nblocks是正数，则必定存在

	/* Invalidate cache so that smgrnblocks() asks the kernel. */
	reln->smgr_cached_nblocks[FSM_FORKNUM] = InvalidBlockNumber;
	fsm_nblocks_now = smgrnblocks(reln, FSM_FORKNUM);  // 获取当前FSM分支最新的块数

	/* Extend as needed. */
	while (fsm_nblocks_now < fsm_nblocks)  // 扩展条件
	{
		PageSetChecksumInplace((Page) pg.data, fsm_nblocks_now);  // 在新块上设置页面的校验和

		smgrextend(reln, FSM_FORKNUM, fsm_nblocks_now,
				   pg.data, false);  // 将新页面添加到FSM文件中

		fsm_nblocks_now++;
	}

	UnlockRelationForExtension(rel, ExclusiveLock);  // 释放锁
}

实现流程如下：

  1. 初始化一个空的页：首先，使用PageInit函数初始化一个PGAlignedBlock结构体pg的data字段，这个页被设置为一个空页，即所有位都填充为0，表示该页没有空闲空间。
  2. 加锁：通过LockRelationForExtension函数对关系加上扩展锁，以防止其他后端同时扩展FSM或主分叉。
  3. 获取SMgrRelation指针：通过RelationGetSmgr函数获取当前关系的存储管理器指针，以便后续进行存储层面的操作。
  4. 检查并创建FSM文件：如果FSM分叉不存在，则通过smgrcreate函数创建它。
  5. 更新缓存并获取当前FSM块数：将FSM分叉的缓存块数设置为InvalidBlockNumber，以强制smgrnblocks函数从内核获取最新的块数。然后，通过smgrnblocks函数获取当前FSM的块数。
  6. 扩展FSM：如果当前FSM的块数小于指定的fsm_nblocks，则进入一个循环，每次循环中都会创建一个新的空页，并使用PageSetChecksumInplace函数为该页设置校验和。然后，通过smgrextend函数将新页添加到FSM分叉中，并递增fsm_nblocks_now以跟踪当前FSM的块数。
  7. 解锁：扩展完成后，通过UnlockRelationForExtension函数释放之前获取的扩展锁。

3、FSM文件的查找

函数fsm_search利用FSM文件查找一个具有指定空闲空间的表块。该函数有两个参数：表的基本信息rel和最小空闲空间值min_cat，该函数将在rel中找到一个至少具有min_cat*32字节空闲空间的表块。

整体的逻辑如下：

  • 首先从FSM文件中获取根节点（root）的FSM块，在FSM块中开始寻找叶子节点：

  • 如果找到具有足够空间的叶子节点，判断当前是否是第2层：

  • 如果是第2层，直接返回结果

  • 如果不是，则继续向下遍历

  • 如果找不到有足够空间的叶子节点，判断当前是否是根节点：

    • 如果是根节点，说明当前FSM映射的所有表块都不够存储新元组，需要分配新的表块

    • 如果不是根节点，说明当搜索根节点的时候，是有足够空间，但是遍历到底层树的时候，空间被其它线程给分配了，这个时候，就需要更新上层节点的信息，重新从root FSM块开始重新搜索。

static BlockNumber
fsm_search(Relation rel, uint8 min_cat)
{
	int			restarts = 0;  // 初始化计数器跟踪搜索过程中的重启次数
	FSMAddress	addr = FSM_ROOT_ADDRESS;   // 从根地址开始搜索

	for (;;)  // 循环，直到找到符合条件的堆页面或确定没有符合条件的页面
	{
		int			slot;
		Buffer		buf;
		uint8		max_avail = 0;

		/* Read the FSM page. */
		buf = fsm_readbuf(rel, addr, false);  // 获取当前FSM页面的内容

		/* 在页面内部进行搜索 */
		if (BufferIsValid(buf))  // 页面有效
		{
			LockBuffer(buf, BUFFER_LOCK_SHARE);  // 加锁
			slot = fsm_search_avail(buf, min_cat, (addr.level == false);  // 尝试在该页面上找到具有至少min_cat类别空闲空间的槽位
			/* 如果当前块内无法找到满足条件的叶子节点，记录当前块内最大的FSM级别的max_avail */
			if (slot == -1)
				max_avail = fsm_get_max_avail(BufferGetPage(buf));
			UnlockReleaseBuffer(buf);  // 解锁
		}
		else
			slot = -1;

		/* 如果能找到满足条件的叶子节点 */
		if (slot != -1)
		{
			/* 如果在树的底层找到了合适的页面，则返回该页面 */
			if (addr.level == FSM_BOTTOM_LEVEL)
				return fsm_get_heap_blk(addr, slot);

			/* 如果未达到底层，则调用fsm_get_child获取下一个要搜索的FSM块，重新开始循环 */
			addr = fsm_get_child(addr, slot);
		}
		else if (addr.level == FSM_ROOT_LEVEL)
		{
			/* 如果在根级别没有找到，意味着整个FSM中没有足够的空闲空间。放弃搜索 */
			return InvalidBlockNumber;
		}
		else
		{
			uint16		parentslot;  // 父节点的块号
			FSMAddress	parent;  // 父节点的地址

			/*
			 * 在较低级别上搜索失败可能是因为上层节点的值没有反映下层页面的实际情况。
			 * 更新上层节点，避免再次陷入相同的陷阱，然后从头开始搜索
			 */
			parent = fsm_get_parent(addr, &parentslot);
			fsm_set_and_search(rel, parent, parentslot, max_avail, 0);  // 查找并更新父节点的最大空闲空间值

			/* 如果上层页面严重过时，可能需要多次循环更新 */
			if (restarts++ > 10000)
				return InvalidBlockNumber;

			/* 从根上开始重新搜索 */
			addr = FSM_ROOT_ADDRESS;
		}
	}
}

依赖的函数

上述代码中，查找具有足够空间的叶子节点这一关键功能是通过fsm_search_avail函数实现的。对于每个FSM块内部的二叉堆，并非从堆顶开始搜索，而是从fp_next_slot+NonLeafNodesPerPage的位置开始搜索。如果当前fp_next_slot不符合条件，则找到其右兄弟的父亲节点，继续判断，如果还不符合条件，则重复之前的操作继续向上搜索。

int
fsm_search_avail(Buffer buf, uint8 minvalue, bool advancenext, bool exclusive_lock_held)
{	
	Page		page = BufferGetPage(buf);
	FSMPage		fsmpage = (FSMPage) PageGetContents(page);
	int			nodeno;
	int			target;
	uint16		slot;

restart:

	/* 检查根节点，如果根节点的空闲空间小于minvalue，则直接返回-1 */
	if (fsmpage->fp_nodes[0] < minvalue)
		return -1;

	/* 从fp_next_slot开始搜索 */
	target = fsmpage->fp_next_slot;
	if (target < 0 || target >= LeafNodesPerPage)  // 目标节点错误
		target = 0;  // 将目标节点清零
	target += NonLeafNodesPerPage;  //目标节点加上非叶子节点的数量，指向第一个叶子节点

	/* 从目标节点开始搜索，在每一步中，向右移动一个节点，然后上升到父节点 */
	nodeno = target;
	while (nodeno > 0)
	{
		// 如果当前节点的FSM级别满足要求，直接跳出循环
		if (fsmpage->fp_nodes[nodeno] >= minvalue)
			break;

		/* 向右移动，必要时在同一层级内循环，即最右节点的右节点是最左节点 */
		nodeno = parentof(rightneighbor(nodeno));
	}

	/*
	 * 当在树的中间位置找到了有足够空间的节点，向下到底层
	 * 在向下寻径过程中，如果左右叶子节点都符合条件，优先选取左子节点
	 */
	while (nodeno < NonLeafNodesPerPage)
	{
		int			childnodeno = leftchild(nodeno);  // 优先寻找左节点

		if (childnodeno < NodesPerPage &&
			fsmpage->fp_nodes[childnodeno] >= minvalue)  // 左节点满足要求
		{
			nodeno = childnodeno;  // 设置当前节点为左节点
			continue;
		}
		childnodeno++;			/* 指向右子节点 */
		if (childnodeno < NodesPerPage &&
			fsmpage->fp_nodes[childnodeno] >= minvalue)  // 如果右节点满足要求
		{
			nodeno = childnodeno;  // 当前节点指向右节点
		}
		else
		{
			/* 如果出现了父节点承诺的空间不足的情况，修复损坏并重新开始 */
			RelFileNode rnode;
			ForkNumber	forknum;
			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);

			/* 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);  // 修复当前FSM块
			MarkBufferDirtyHint(buf, false);  // //将当前块变为脏块，写入磁盘
			goto restart;
		}
	}

	//跳出循环说明我们已经找到了符合条件的第2层的叶子节点
	slot = nodeno - NonLeafNodesPerPage;  //减去非叶子节点个数(直接获取在叶子层中的序号)

	/* 更新下一个目标指针 */
	fsmpage->fp_next_slot = slot + (advancenext ? 1 : 0);

	return slot;
}

4、FSM文件的调整

当从FSM文件中找到了一个具有合适空闲空间的表块并使用它进行了数据插入之后，需要对FSM文件中相关信息进行修改，需要调整该表块的空闲空间值，同时对其所属的FSM块内的最大堆二叉树进行相应的调整，整个调整的过程由函数RecordPageWithFreeSpace完成，其参数包括表块号，表的信息以及表块当前的空闲空间值。

void
RecordPageWithFreeSpace(Relation rel, BlockNumber heapBlk, Size spaceAvail)
{
	int			new_cat = fsm_space_avail_to_cat(spaceAvail);  // 获取新的空闲空间值
	FSMAddress	addr;  // FSM地址
	uint16		slot;  // 要修改的节点号

	/* 获取表示该页面在FSM中的地址和槽位 */
	addr = fsm_get_location(heapBlk, &slot);  

	fsm_set_and_search(rel, addr, slot, new_cat, 0);  // 设置并搜索相关信息，更新FSM中该页面的空闲空间值
}

依赖的函数

（1）fsm_set_and_search函数为RecordPageWithFreeSpace函数的核心部分，其作用是在给定的FSM页面和槽位中设置值。

过程大致如下：

  • 根据表块号读取块内容到缓冲区中并且上锁。

  • 调用fsm_set_avail函数对FSM块的内容进行修改

    • 如果新的空闲空间值和旧的空闲空间值相等，则无需修改。

    • 如果不相等，则赋新值给对应的叶子节点。

    • 调整根节点外的其他节点，维持大根堆的特性。

    • 如果新的空闲空间值比根节点的空闲空间值还大，则需要重新建树。

  • 如果发生了修改，则设置当前块为脏，写入到磁盘中。

static int
fsm_set_and_search(Relation rel, FSMAddress addr, uint16 slot,
				   uint8 newValue, uint8 minValue)
{
  Buffer		buf;  
	Page		page;
	int			newslot = -1;

	buf = fsm_readbuf(rel, addr, true);  // 读取指定的FSM页面到缓冲区中
	LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);   // 缓冲区加排他锁

	page = BufferGetPage(buf);  // 将缓冲区的内容转为块结构

	if (fsm_set_avail(page, slot, newValue))  // 在FSM页面的指定槽位上设置新值，判断是否成功
		MarkBufferDirtyHint(buf, false);  // 设置成功，则标记缓冲区为脏，以便后续将更改写回磁盘

	if (minValue != 0)
	{
		/* 在当前锁定的FSM页面中搜索具有至少 minValue 空闲空间的页面 */
		newslot = fsm_search_avail(buf, minValue, addr.level == true); 
	}

	UnlockReleaseBuffer(buf);  // 解锁

	return newslot;
}

（2）fsm_set_avail函数的作用是在页面上设置槽位的值，如果页面被修改，返回true。

bool
fsm_set_avail(Page page, int slot, uint8 value)
{
	int			nodeno = NonLeafNodesPerPage + slot;  // 计算槽位对应的节点编号
	FSMPage		fsmpage = (FSMPage) PageGetContents(page);   // 获取FSM页面内容
	uint8		oldvalue;

	Assert(slot < LeafNodesPerPage);  // 如果slot不是叶子节点，则报错

	oldvalue = fsmpage->fp_nodes[nodeno];  // 获取当前节点的旧值

	/* 若新值与旧值相同，不进行任何操作 */
	if (oldvalue == value && value <= fsmpage->fp_nodes[0]) 
		return false;

	fsmpage->fp_nodes[nodeno] = value;  // 设置新值

	/*
	 * 维护大根堆
	 * 向上传播更新，直到达到根节点或找到不需要更新的节点
	 */
	do
	{
		uint8		newvalue = 0;  // 新的空闲空间值，用于比较大小和修改
		int			lchild;  // 左节点
		int			rchild;  // 右节点
         
        /* 此时nodeno为目标节点的父节点 */
		nodeno = parentof(nodeno);  // 当前节点变为当前节点的父节点
		lchild = leftchild(nodeno); // 获取当前节点的左孩子
		rchild = lchild + 1;  // 获取当前节点的右孩子

		newvalue = fsmpage->fp_nodes[lchild];  // 将newvalue设置为左孩子的空闲空间值
		if (rchild < NodesPerPage)  // 如果右孩子不是叶子节点
			newvalue = Max(newvalue,
						   fsmpage->fp_nodes[rchild]);  //newvalue=左孩子和右孩子的空闲空间值中更大的那一个。

        /* oldvalue更新为原父亲的值 */
		oldvalue = fsmpage->fp_nodes[nodeno];
		if (oldvalue == newvalue)
			break;

        /* 父节点更新为newvalue */
		fsmpage->fp_nodes[nodeno] = newvalue;
	} while (nodeno > 0);

	/*
	 * 如果新值仍高于根节点的值，则树结构可能损坏
     * 若出现这种情况，重建页面
	 */
	if (value > fsmpage->fp_nodes[0])
		fsm_rebuild_page(page);

	return true;
}
he3db
「喜欢这篇文章，您的关注和赞赏是给作者最好的鼓励」
关注作者
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文章的来源（墨天轮），文章链接，文章作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

评论