Shulou(Shulou.com)05/31 Report--

This article introduces the relevant knowledge of "what is the role of fsm_search function in PostgreSQL". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

I. data structure

Macro definition

Including FSM page leaf node number / non-leaf node number / FSM tree depth and so on.

# define MaxFSMRequestSize MaxHeapTupleSize#define MaxHeapTupleSize (BLCKSZ-MAXALIGN (SizeOfPageHeaderData + sizeof (ItemIdData)) # define FSM_CAT_STEP (BLCKSZ / FSM_CATEGORIES) # define FSM_CATEGORIES 256 define FSM_CATEGORIES / Block size 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. * the tree depth stored on disk. * We need to locate and address 2 ^ 32-1 blocks, and 1626 is the minimum number that satisfies X ^ 3 > = 2 ^ 32-1. * in addition, 216 is the minimum number that satisfies X ^ 4 > = 2 ^ 32-1. In practice, this means that 4096 bytes is the minimum BLCKSZ,512 that can be supported by three layers and the smallest can be supported. * / # define FSM_TREE_DEPTH ((SlotsPerFSMPage > = 1626)? 3: 4)

FSMAddress

The internal FSM process works as a logical address scheme, and each level of the tree can be thought of as an independent address file.

/ * The internal FSM routines work on a logical addressing scheme. Each * level of the tree can be thought of as a separately addressable file. * the internal FSM process works on a logical address scheme. * each level of the tree can be thought of as a separate address file. * / typedef struct {/ / hierarchical int level; / * level * / / the page number within this hierarchy is int logpageno; / * page number within the level * /} FSMAddress;/* Address of the root page. * / / Root page address static const FSMAddress FSM_ROOT_ADDRESS = {FSM_ROOT_LEVEL, 0}

FSMPage

FSM page data structure. For details, please refer to src/backend/storage/freespace/README.

/ * Structure of a FSM page. See src/backend/storage/freespace/README for * details. * FSM page data structure. For details, please refer to 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. The fsm_search_avail () function attempts to spread the load over background processes by returning different pages to different background processes in a loop. * this field is defined as an integer because it does not require an exclusive lock. * unit16 may be more appropriate, but integers seem to be more suitable for atomic extraction and storage. * / 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 stores the binary tree as an array. * the first NonLeafNodesPerPage element is the node of the previous layer, and the next LeafNodesPerPage element is the leaf node. * the unused node is 0. * / uint8 fp_ Nodes [flex _ ARRAY_MEMBER];} FSMPageData;typedef FSMPageData * FSMPage

FSMLocalMap

For small tables, there is no need to create a FSM to store spatial information, using local memory mapping information.

/ * Either already tried, or beyond the end of the relation * / / has been tried or has been at the end of the table # define FSM_LOCAL_NOT_AVAIL 0x00 * Available to try * / / can be used to try # define FSM_LOCAL_AVAIL 0x01max * * 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. * for small tables, there is no need to create a FSM to store space information, using local memory mapping information. In order to locate free space, we don't need to know how much free space they have, but simply try 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. * Note that this map is used to search the request free space for a given table. * when a block/ with enough free space is found to extend relation/ in a transaction rollback, the map is cleared. * for more information, please see src/backend/storage/freespace/README. * / typedef struct {number of BlockNumber nblocks;// blocks uint8 map [heap _ FSM_CREATION_THRESHOLD]; / / Array} FSMLocalMap;static FSMLocalMap fsm_local_map = {0, {FSM_LOCAL_NOT_AVAIL}}; # define FSM_LOCAL_MAP_EXISTS (fsm_local_map.nblocks > 0)

General routine

Including obtaining the left child node / right child node / parent node, etc.

/ * Macros to navigate the tree within a page. Root has index zero. * / / traverse the tree in page. Root is numbered 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 * search for neighbors to the right of x If you need to roll back * / static intrightneighbor (int x) {/ * * Move right at the same level. This might wrap around, stepping to the leftmost node at * the next level. * move to the right. This may cause rollback to the leftmost node at the next level. * / xbirthday; / * * 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. * check whether to jump to the leftmost node of the next level, and if so, correct x. * the leftmost node at each level is numbered x = 2 ^ level-1, * so check whether (x ^ 1) is a power of 2, using the standard twos-complement-arithmetic technique. * / if ((x + 1) & x) = = 0) / / signed integer, all 1 is 0 x = parentof (x); return x } / * Returns the physical block number of a FSM page * returns the physical block number of FSM page * / / * calculation formula: To find the physical block # corresponding to leaf page n, we need tocount the number of leaf and upper-level pages preceding page n.This turns out to bey = n + (n / F + 1) + (n / F ^ 2 + 1) +. + 1where F is the fanout. The first term n is the numberof preceding leaf pages, the second term is the numberof pages at level 1 Calculate the logical page numberof the first leaf page below the and so forth.*/static BlockNumberfsm_logical_to_physical (FSMAddress addr) {BlockNumber pages;// block number int leafno;// page number int lnterbank / temporary variable / * * Calculate the logical page numberof the first leaf page below the * given page. * under the given page, calculate the logical page number of the first leaf 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 FSMAddressfsm_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 BlockNumberfsm_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 * / / start with root search addr = FSM_ROOT_ADDRESS;} the content of "what is the function of fsm_search in PostgreSQL" is introduced here, thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.