本节简单介绍了PostgreSQL在执行插入过程中与存储相关的函数RecordAndGetPageWithFreeSpace->fsm_search,该函数搜索FSM,找到有足够空闲空间(min_cat)的堆page. ### 一、数据结构 **宏定义** 包括FSM页面的叶子节点数/非叶子节点数/FSM树深度等等. ``` #define MaxFSMRequestSize MaxHeapTupleSize #define MaxHeapTupleSize (BLCKSZ - MAXALIGN(SizeOfPageHeaderData + sizeof(ItemIdData))) #define FSM_CAT_STEP (BLCKSZ / FSM_CATEGORIES) #define FSM_CATEGORIES 256 //块大小为8K则FSM_CAT_STEP = 32 #define SlotsPerFSMPage LeafNodesPerPage #define LeafNodesPerPage (NodesPerPage - NonLeafNodesPerPage) = 8156 - 4095 = 4061 #define NodesPerPage (BLCKSZ - MAXALIGN(SizeOfPageHeaderData) - \ offsetof(FSMPageData, fp_nodes)) = 8192 - 32 - 4 = 8156 #define NonLeafNodesPerPage (BLCKSZ / 2 - 1) = 4095 /* * Depth of the on-disk tree. We need to be able to address 2^32-1 blocks, * and 1626 is the smallest number that satisfies X^3 >= 2^32-1. Likewise, * 216 is the smallest number that satisfies X^4 >= 2^32-1. In practice, * this means that 4096 bytes is the smallest BLCKSZ that we can get away * with a 3-level tree, and 512 is the smallest we support. * 存储在磁盘上的树深度. * 我们需要为2^32 - 1个块定位寻址,1626是可以满足X^3 >= 2^32 - 1的最小数字. * 另外,216是可以满足X^4 >= 2^32 - 1的最小数字. * 在实践中,这意味着4096字节是三层数可以支撑的最小BLCKSZ,512是最小可支持的. */ #define FSM_TREE_DEPTH ((SlotsPerFSMPage >= 1626) ? 3 : 4) ``` **FSMAddress** 内部的FSM处理过程以逻辑地址scheme的方式工作,树的每一个层次都可以认为是一个独立的地址文件. ``` /* * The internal FSM routines work on a logical addressing scheme. Each * level of the tree can be thought of as a separately addressable file. * 内部的FSM处理过程工作在一个逻辑地址scheme上. * 树的每一个层次都可以认为是一个独立的地址文件. */ typedef struct { //层次 int level; /* level */ //该层次内的页编号 int logpageno; /* page number within the level */ } FSMAddress; /* Address of the root page. */ //根页地址 static const FSMAddress FSM_ROOT_ADDRESS = {FSM_ROOT_LEVEL, 0}; ``` **FSMPage** FSM page数据结构.详细可参看src/backend/storage/freespace/README. ``` /* * Structure of a FSM page. See src/backend/storage/freespace/README for * details. * FSM page数据结构.详细可参看src/backend/storage/freespace/README. */ typedef struct { /* * fsm_search_avail() tries to spread the load of multiple backends by * returning different pages to different backends in a round-robin * fashion. fp_next_slot points to the next slot to be returned (assuming * there's enough space on it for the request). It's defined as an int, * because it's updated without an exclusive lock. uint16 would be more * appropriate, but int is more likely to be atomically * fetchable/storable. * fsm_search_avail()函数尝试通过在一轮循环中返回不同的页面到不同的后台进程, * 从而分散在后台进程上分散负载. * 该字段因为无需独占锁,因此定义为整型. * unit16可能会更合适,但整型看起来更适合于原子提取和存储. */ int fp_next_slot; /* * fp_nodes contains the binary tree, stored in array. The first * NonLeafNodesPerPage elements are upper nodes, and the following * LeafNodesPerPage elements are leaf nodes. Unused nodes are zero. * fp_nodes以数组的形式存储二叉树. * 第一个NonLeafNodesPerPage元素是上一层的节点,接下来的LeafNodesPerPage元素是叶子节点. * 未使用的节点为0. */ uint8 fp_nodes[FLEXIBLE_ARRAY_MEMBER]; } FSMPageData; typedef FSMPageData *FSMPage; ``` **FSMLocalMap** 对于小表,不需要创建FSM来存储空间信息,使用本地的内存映射信息. ``` /* Either already tried, or beyond the end of the relation */ //已尝试或者已在表的末尾之后 #define FSM_LOCAL_NOT_AVAIL 0x00 /* Available to try */ //可用于尝试 #define FSM_LOCAL_AVAIL 0x01 /* * For small relations, we don't create FSM to save space, instead we use * local in-memory map of pages to try. To locate free space, we simply try * pages directly without knowing ahead of time how much free space they have. * 对于小表,不需要创建FSM来存储空间信息,使用本地的内存映射信息. * 为了定位空闲空间,我们不需要知道他们有多少空闲空间而是直接简单的对page进行尝试. * * Note that this map is used to the find the block with required free space * for any given relation. We clear this map when we have found a block with * enough free space, when we extend the relation, or on transaction abort. * See src/backend/storage/freespace/README for further details. * 注意这个map用于搜索给定表的请求空闲空间. * 在找到有足够空闲空间的block/扩展了relation/在事务回滚时,则清除这个map的信息. * 详细可查看src/backend/storage/freespace/README. */ typedef struct { BlockNumber nblocks;//块数 uint8 map[HEAP_FSM_CREATION_THRESHOLD];//数组 } FSMLocalMap; static FSMLocalMap fsm_local_map = { 0, { FSM_LOCAL_NOT_AVAIL } }; #define FSM_LOCAL_MAP_EXISTS (fsm_local_map.nblocks > 0) ``` **通用例程** 包括获取左子节点/右子节点/父节点等 ``` /* Macros to navigate the tree within a page. Root has index zero. */ //在page中遍历树.Root编号为0 #define leftchild(x) (2 * (x) + 1) #define rightchild(x) (2 * (x) + 2) #define parentof(x) (((x) - 1) / 2) /* * Find right neighbor of x, wrapping around within the level * 搜索x右边的邻居,如需要在同一个层次上需回卷 */ static int rightneighbor(int x) { /* * Move right. This might wrap around, stepping to the leftmost node at * the next level. * 移到右边.这可能会引起回卷,调到下一个层次最左边的节点上. */ x++; /* * Check if we stepped to the leftmost node at next level, and correct if * so. The leftmost nodes at each level are numbered x = 2^level - 1, so * check if (x + 1) is a power of two, using a standard * twos-complement-arithmetic trick. * 检查是否跳转到下一个层次最左边的节点上,如是则修正x. * 每一个层次上最左边的节点编号为x = 2^level - 1, * 因此检查(x+1)是否为2的幂,使用标准的twos-complement-arithmetic技巧即可. */ if (((x + 1) & x) == 0)//有符号整型,全1为0 x = parentof(x); return x; } /* * Returns the physical block number of a FSM page * 返回FSM page的物理块号 */ /* 计算公式: To find the physical block # corresponding to leaf page n, we need to count the number of leaf and upper-level pages preceding page n. This turns out to be y = n + (n / F + 1) + (n / F^2 + 1) + ... + 1 where F is the fanout . The first term n is the number of preceding leaf pages, the second term is the number of pages at level 1, and so forth. */ static BlockNumber fsm_logical_to_physical(FSMAddress addr) { BlockNumber pages;//块号 int leafno;//页号 int l;//临时变量 /* * Calculate the logical page number of the first leaf page below the * given page. * 在给定的page下,计算第一个叶子页面的逻辑页号 */ leafno = addr.logpageno; for (l = 0; l < addr.level; l++) leafno *= SlotsPerFSMPage; /* Count upper level nodes required to address the leaf page */ //统计用于定位叶子页面的上层节点数 pages = 0; for (l = 0; l < FSM_TREE_DEPTH; l++) { pages += leafno + 1; leafno /= SlotsPerFSMPage; } /* * If the page we were asked for wasn't at the bottom level, subtract the * additional lower level pages we counted above. * 如果请求的页面不在底层,减去上面技术的额外的底层页面数. */ pages -= addr.level; /* Turn the page count into 0-based block number */ //计数从0开始(减一) return pages - 1; } /* * Return the FSM location corresponding to given heap block. * 返回给定堆block的FSM位置. */ //addr = fsm_get_location(oldPage, &slot); static FSMAddress fsm_get_location(BlockNumber heapblk, uint16 *slot) { FSMAddress addr; addr.level = FSM_BOTTOM_LEVEL; //#define SlotsPerFSMPage LeafNodesPerPage //#define LeafNodesPerPage (NodesPerPage - NonLeafNodesPerPage) = 8156 - 4095 = 4061 //#define NodesPerPage (BLCKSZ - MAXALIGN(SizeOfPageHeaderData) - \ offsetof(FSMPageData, fp_nodes)) = 8192 - 32 - 4 = 8156 //#define NonLeafNodesPerPage (BLCKSZ / 2 - 1) = 4095 addr.logpageno = heapblk / SlotsPerFSMPage; *slot = heapblk % SlotsPerFSMPage; return addr; } ``` ### 二、源码解读 fsm_search函数搜索FSM,找到有足够空闲空间(min_cat)的堆page. ``` /* * Search the tree for a heap page with at least min_cat of free space * 搜索FSM,找到有足够空闲空间(min_cat)的堆page */ //return fsm_search(rel, search_cat); 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. */ //读取FSM page buf = fsm_readbuf(rel, addr, false); /* Search within the page */ //页内搜索 if (BufferIsValid(buf)) { LockBuffer(buf, BUFFER_LOCK_SHARE); //搜索可用的slot 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); } else //buffer无效,则设置为-1 slot = -1; if (slot != -1) { /* * Descend the tree, or return the found block if we're at the * bottom. * 如在树的底部,则返回找到的块. */ if (addr.level == FSM_BOTTOM_LEVEL) return fsm_get_heap_blk(addr, slot); addr = fsm_get_child(addr, slot); } else if (addr.level == FSM_ROOT_LEVEL) { /* * At the root, failure means there's no page with enough free * space in the FSM. Give up. * 处于根节点,失败意味着FSM中没有足够空闲空间的页面存在,放弃. */ return InvalidBlockNumber; } else { uint16 parentslot; FSMAddress parent; /* * At lower level, failure can happen if the value in the upper- * level node didn't reflect the value on the lower page. Update * the upper node, to avoid falling into the same trap again, and * start over. * 在低层上,如果上层节点没有反映更低层页面的值则会出现失败. * 更新高层节点,避免重复掉入同一个陷阱,重新开始. * * There's a race condition here, if another backend updates this * page right after we release it, and gets the lock on the parent * page before us. We'll then update the parent page with the now * stale information we had. It's OK, because it should happen * rarely, and will be fixed by the next vacuum. * 在我们释放后,另外的后台进程更新这个页面同时在我们之前锁定了父节点的话,会存在条件竞争. * 然后我们使用现有已知稳定的信息更新父页面. * 如OK,因为这种很少出现,那么会在下一个vacuum中修复此问题. */ parent = fsm_get_parent(addr, &parentslot); fsm_set_and_search(rel, parent, parentslot, max_avail, 0); /* * If the upper pages are badly out of date, we might need to loop * quite a few times, updating them as we go. Any inconsistencies * should eventually be corrected and the loop should end. Looping * indefinitely is nevertheless scary, so provide an emergency * valve. * 如果上层页面过旧,可能需要循环很多次,更新上层页面信息. * 不一致性会被周期性的纠正,循环会停止. * 但无限循环是很可怕的,因此设置阈值,超过此阈值则退出循环. */ if (restarts++ > 10000) return InvalidBlockNumber; /* Start search all over from the root */ //从root开始搜索 addr = FSM_ROOT_ADDRESS; } } } ``` ### 三、跟踪分析 N/A ### 四、参考资料 [PG Source Code](https://doxygen.postgresql.org) [Database Cluster, Databases, and Tables](http://www.interdb.jp/pg/pgsql01.html) [free space map README](https://github.com/postgres/postgres/tree/master/src/backend/storage/freespace)