共计 9355 个字符，预计需要花费 24 分钟才能阅读完成。
本篇内容介绍了“PostgreSQL 中 fsm_search 函数有什么作用”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让丸趣 TV 小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
一、数据结构
宏定义
包括 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;
}
}
}“PostgreSQL 中 fsm_search 函数有什么作用”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注丸趣 TV 网站，丸趣 TV 小编将为大家输出更多高质量的实用文章！
正文完
发表至： 数据库
2023-07-24
