PostgreSQL中fsm_search函数有什么作用

本篇内容介绍了"PostgreSQL中fsm_search函数有什么作用"的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

一、数据结构

宏定义
包括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 intrightneighbor(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 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 number of pages at level 1,and so forth.*/static BlockNumberfsm_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 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 */            //从root开始搜索            addr = FSM_ROOT_ADDRESS;        }    }}

"PostgreSQL中fsm_search函数有什么作用"的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注网站，小编将为大家输出更多高质量的实用文章！