0. 前言
主要记录对彭智勇和彭煜玮老师所著《PostgreSQL数据库内核分析》一书的观后总结，用于读薄这本经典著作，同时也方便自己时常温习，加深印象。
本文主要对PG内部的空闲空间映射表机制进行了简析，结合源码，分析了其实现过程。
1. 空闲空间映射表（FreeSpaceMap）原理
FSM机制的必要性：
随着表中不断插入和删除元组，文件块中必然会产生空闲空间（Free Space）。在插入元组时优先选择将其存放在空闲空间内是利用存储的好方法。如何管理这些空闲空间才能最大化地提高效率呢？ PG8.4以前采用了一种全局FSM文件来记录所有表文件的空闲状况，复杂且低效。PG8.4以后采用了新的策略，即对于每个表文件（包括系统表在内），同时创建一个名为“关系表OID_fsm” 的文件，用于记录该表的空闲空间大小。
FSM机制的基本原理：
FSM机制采用一个字节表示空闲空间的大小范围，我们将这个字节叫做FSM级别（category）。FSM级别和真实的FSM范围之间的映射关系如表3-1所示。
表3-1 FSM级别和空闲空间范围之间的映射关系
| 字节取值 | 表示的空闲空间范围（字节） |
|---|---|
| 0 | 0 ~ 31 |
| 1 | 32 ~ 63 |
| ...... | ...... |
| 255 | 8164 ~ 8192 |
为了实现快速查找，FSM文件并不是简单使用数组顺序存储每个表块的空闲空间，而是使用了树结构。在FSM块之间使用了一种三层树结构，其中第0层和第1层是辅助层，第二层FSM块实际存储各表块的空闲空间级别（category）。第0层FSM块只有一个，作为树根；第1层FSM块可以有多个，作为第0层FSM块的子节点；第2层FSM块同理。每个FSM块内又构成一棵局部的最大堆二叉树，但每一层FSM块内的最大堆二叉树又略有不同。
- 第2层FSM块内大根堆二叉树的每一个叶子节点对应一个表块的空闲空间级别。按照从左到右的顺序，最左边FSM块的最左边叶子节点代表表文件的第一块，左边第二个叶子节点代表表文件的第二块。
- 第1层FSM块内大根堆二叉树的叶子节点从左到右对应第2层FSM块的根节点。
- 第0层FSM块内大根堆二叉树的叶子节点从左到右对应第1层FSM块的根节点。
从上面的介绍可知，三层树结构形成了一个逻辑上的大根堆结构，其叶子节点从左到右依次对应表文件中的文件块。
在单个FSM块内，使用大根堆能保证所有叶子节点的最大值被上升到根节点处。因此我们只要看单个FSM块内的根节点值就可指导此FSM块内空闲空间的上限值。
每个FSM块大小为8KB，除去必要的页头信息，FSM块剩下的空间都用来存储块内的二叉树结构，每个叶子节点都用一个字节表示，因此FSM块内大约可以保存4000个叶子节点（实际为4069，计算方法见宏定义SlotsPerFSMPage，这里为了简化描述将其近似为4000）。这样，一个FSM文件如果采用三层树结构，大约可以记录4000^3 个叶子节点，对应于4000^3 个表块，远大于2^32 (单个表的最大块数，PG块号数据结构BlockIdData中定义块号长度为32，故单个表最多只能有（2^32-1）个表块)。因此，这样的三层树结构足以记录表文件所有文件块的空闲空间值。
一个FSM文件内所包含的FSM块和表块的映射关系如图3-7所示。
图3-7 FSM物理块与逻辑地址对照.jpg
由上图可知：
- 第0层FSM块的叶子节点记录了第1层所有FSM块的根节点。
- 第1层FSM块的叶子节点记录了第2层所有FSM块的根节点。
- 第2层FSM块的叶子节点按从左到右的顺序就是对应表块在表文件中的顺序。
- FSM文件中第一个文件块（第0号FSM块）中二叉树根节点所存储的是所有表块空闲空间级别的最大值（图3-7中的120）。
2. FSM相关数据结构、宏和函数声明
1. FSM块的数据结构：FSMPageData
/*
* FSM块的数据结构. See src/backend/storage/freespace/README for
* details.
*/
typedef struct
{
/*
* fp_next_slot是一个整数，用于提示下一次开始查询二叉树时的叶子节点位置
*（也就是一个满足请求的二叉树叶子节点序号，从零开始计数，用slot表示），
* 若该FSM块是叶子节点，则将fp_next_slot置为 slot + 1, 否则置为slot。
*/
int fp_next_slot;
/*
* fp_nodes数组表示当前FSM块内存储的大根堆二叉树结构。
*/
uint8 fp_nodes[FLEXIBLE_ARRAY_MEMBER];
} FSMPageData;
typedef FSMPageData *FSMPage;
2. 一个FSM块中可以保存的节点总数目（8192 - 24 - 4 = 8164 ）
#define NodesPerPage (BLCKSZ - MAXALIGN(SizeOfPageHeaderData) - \
offsetof(FSMPageData, fp_nodes))
3. FSM块中保存的非叶子节点数目（8192/2 - 1 = 4095）
#define NonLeafNodesPerPage (BLCKSZ / 2 - 1)
4. FSM块中保存的叶子节点数目 （8164 - 4095 = 4069）
#define LeafNodesPerPage (NodesPerPage - NonLeafNodesPerPage)
5. FSM块中的slots个数（即FSM块中可以保存的叶子节点总数，4069）
#define SlotsPerFSMPage LeafNodesPerPage
6. fsmpage.c中的函数原型
/* Prototypes for functions in fsmpage.c */
extern int fsm_search_avail(Buffer buf, uint8 min_cat, bool advancenext,
bool exclusive_lock_held);
extern uint8 fsm_get_avail(Page page, int slot);
extern uint8 fsm_get_max_avail(Page page);
extern bool fsm_set_avail(Page page, int slot, uint8 value);
extern bool fsm_truncate_avail(Page page, int nslots);
extern bool fsm_rebuild_page(Page page);
\src\backend\storage\freespace\freespace.c
7. FSM相关宏定义
/*
* 我们仅使用一个字节来存储文件块上的空闲空间，
* 所以我们将空闲空间划分为256个级别，
* 最高级别, 255, 表示一个文件块的空闲空间不少于
* MaxFSMRequestSize 字节 , 第二高级别
* 代表空闲空间大小从 254 * FSM_CAT_STEP 到
* MaxFSMRequestSize字节，左闭右开区间.
*
* 对于默认的BLCKSZ 等于8k , MaxFSMRequestSize的值为8164 字节,
* 空闲空间级别的划分如下所示:
*
*
* 范围 级别
* 0 - 31 0
* 32 - 63 1
* ... ... ...
* 8096 - 8127 253
* 8128 - 8163 254
* 8164 - 8192 255
*
*/
事实上，大小在0~31字节的空闲空间将不会被使用，而当申请空闲空间大小在8164~8192字节之间时，系统将为请求分配MaxFSMRequestSize大小的空闲空间，也即一个空闲的表块。
//FSM空闲空间的级别总数（256）
#define FSM_CATEGORIES 256
// FSM空闲空间级别的步长（8192/256 = 32）
#define FSM_CAT_STEP (BLCKSZ / FSM_CATEGORIES)
// 可申请的空闲空间的最大值，就是表块内元组的最大大小（8164字节）
#define MaxFSMRequestSize MaxHeapTupleSize
/*
* FSM树结构的总深度，默认是3. 我们需要能够寻址2^32-1 个表块,
* 而1626 是能满足 X^3 >= 2^32-1的最小的整数. 类似的,
* 216 能满足 X^4 >= 2^32-1的最小的整数.
*/
#define FSM_TREE_DEPTH ((SlotsPerFSMPage >= 1626) ? 3 : 4)
// FSM三层树结构根节点所在的层号（3-1 =2）
#define FSM_ROOT_LEVEL (FSM_TREE_DEPTH - 1)
// FSM三层树结构叶子节点所在的层号（0）
#define FSM_BOTTOM_LEVEL 0
/*
* FSM块的逻辑地址数据结构.
* 可以调用fsm_logical_to_physical从逻辑地址计算出物理地址，也即该FSM块的物理块号
*/
typedef struct
{
int level; /* 层号*/
int logpageno; /* 当前层内的块号 */
} FSMAddress;
/* FSM三层树结构根节点的逻辑地址. */
static const FSMAddress FSM_ROOT_ADDRESS = {FSM_ROOT_LEVEL, 0};
/* FSM三层树结构内定位FSM块涉及到的相关函数声明 */
static FSMAddress fsm_get_child(FSMAddress parent, uint16 slot);
static FSMAddress fsm_get_parent(FSMAddress child, uint16 *slot);
static FSMAddress fsm_get_location(BlockNumber heapblk, uint16 *slot);
static BlockNumber fsm_get_heap_blk(FSMAddress addr, uint16 slot);
static BlockNumber fsm_logical_to_physical(FSMAddress addr);
static Buffer fsm_readbuf(Relation rel, FSMAddress addr, bool extend);
static void fsm_extend(Relation rel, BlockNumber fsm_nblocks);
/* functions to convert amount of free space to a FSM category */
static uint8 fsm_space_avail_to_cat(Size avail);
static uint8 fsm_space_needed_to_cat(Size needed);
static Size fsm_space_cat_to_avail(uint8 cat);
/* workhorse functions for various operations */
static int fsm_set_and_search(Relation rel, FSMAddress addr, uint16 slot,
uint8 newValue, uint8 minValue);
static BlockNumber fsm_search(Relation rel, uint8 min_cat);
static uint8 fsm_vacuum_page(Relation rel, FSMAddress addr, bool *eof);
static BlockNumber fsm_get_lastblckno(Relation rel, FSMAddress addr);
static void fsm_update_recursive(Relation rel, FSMAddress addr, uint8 new_cat);
2. 源码分析
2.1 FSM的创建
FSM文件并不是在创建表文件的时候就被创建，而是推迟到需要使用FSM文件的时候，即执行VACUUM操作时或为了插入元组而第一次查找FSM文件时才创建。
在创建FSM文件时，会预先创建三个FSM块：0号FSM块，1号FSM块，2号FSM块，分别对应第0层FSM块，第1层最左FSM块，第二层最左FSM块。在2号FSM块内叶子节点一次存储从0号开始的各表块的空闲空间级别，当2号FSM块填满后，会调用fsm_extend函数扩展一个新的FSM块
/*
* 确保FSM文件至少有fsm_nblocks个FSM块，如不足，填充空块补齐。
* 如果文件不存在，调用函数smgrcreate创建之。
*/
static void
fsm_extend(Relation rel, BlockNumber fsm_nblocks)
{
BlockNumber fsm_nblocks_now;
PGAlignedBlock pg;
PageInit((Page) pg.data, BLCKSZ, 0);
/*
* 对关系rel上互斥锁，防止并发调用
*/
LockRelationForExtension(rel, ExclusiveLock);
RelationOpenSmgr(rel);
/*
* 如果FSM文件不存在，创建之
*/
if ((rel->rd_smgr->smgr_fsm_nblocks == 0 ||
rel->rd_smgr->smgr_fsm_nblocks == InvalidBlockNumber) &&
!smgrexists(rel->rd_smgr, FSM_FORKNUM))
smgrcreate(rel->rd_smgr, FSM_FORKNUM, false);
// 获取当前FSM文件有多少FSM块
fsm_nblocks_now = smgrnblocks(rel->rd_smgr, FSM_FORKNUM);
// 如果FSM块不足，扩充FSM块
while (fsm_nblocks_now < fsm_nblocks)
{
PageSetChecksumInplace((Page) pg.data, fsm_nblocks_now);
smgrextend(rel->rd_smgr, FSM_FORKNUM, fsm_nblocks_now,
pg.data, false);
fsm_nblocks_now++;
}
/* 更新本地缓存 */
rel->rd_smgr->smgr_fsm_nblocks = fsm_nblocks_now;
UnlockRelationForExtension(rel, ExclusiveLock);
}
依赖的函数：
2.1.1 PageInit
/*
* PageInit
* 初始化Page.
* 注意这里我们不初始化pd_checksum
*/
void
PageInit(Page page, Size pageSize, Size specialSize)
{
PageHeader p = (PageHeader) page;
specialSize = MAXALIGN(specialSize);
Assert(pageSize == BLCKSZ);
Assert(pageSize > specialSize + SizeOfPageHeaderData);
/* 重置page中的所有比特位为0 */
MemSet(p, 0, pageSize);
p->pd_flags = 0;
p->pd_lower = SizeOfPageHeaderData;
p->pd_upper = pageSize - specialSize;
p->pd_special = pageSize - specialSize;
PageSetPageSizeAndVersion(page, pageSize, PG_PAGE_LAYOUT_VERSION);
/* p->pd_prune_xid = InvalidTransactionId; done by above MemSet */
}
2.1.2 smgrextend
/*
* smgrextend() -- 为文件添加文件块.
*/
void
smgrextend(SMgrRelation reln, ForkNumber forknum, BlockNumber blocknum,
char *buffer, bool skipFsync)
{
(*(smgrsw[reln->smgr_which].smgr_extend)) (reln, forknum, blocknum,
buffer, skipFsync);
}
2.2 FSM的查找
函数fsm_search利用FSM文件查找一个具有指定空闲空间级别的表块。
fsm_search函数的源码分析如下：
/*
* 在三层树结构中寻找至少具有min_cat FSM级别的表块
* 入参：
* rel: 缓存中的表的基本信息
* min_cat：最小空闲空间级别
* 出参：
* BlockNumber：满足条件的表块的块号
*/
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;
/* 将FSM块装入缓冲区. */
buf = fsm_readbuf(rel, addr, false);
/* 在当前FSM块内的大根堆内搜索满足条件的叶子节点的序号slot */
// 主要调用函数fsm_search_avail完成块内搜索
if (BufferIsValid(buf))
{
LockBuffer(buf, BUFFER_LOCK_SHARE);
slot = fsm_search_avail(buf, min_cat,
(addr.level == FSM_BOTTOM_LEVEL),
false);
//如果当前块内无法找到满足条件的叶子节点，记录当前块内
//最大的FSM级别为max_avil
if (slot == -1)
max_avail = fsm_get_max_avail(BufferGetPage(buf));
UnlockReleaseBuffer(buf);
}
else
slot = -1;
//如果在当前FSM内能找到满足条件的叶子节点，
if (slot != -1)
{
//并且如果当前的块指针
//已经到达了三层树结构的底层，调用fsm_get_heap_blk函数计算
//出slot对应的表块号作为返回值返回
if (addr.level == FSM_BOTTOM_LEVEL)
return fsm_get_heap_blk(addr, slot);
//如果当前块指针还未到达三层树结构底层，
// 说明还在第0层或第1层辅助层，调用fsm_get_child函数获取下一个要搜索的FSM块，重新开始循环
addr = fsm_get_child(addr, slot);
}
//如果在当前FSM内不能找到满足条件的叶子节点，且已到达三层
//树结构的底层，说明整个FSM文件都没有满足要求的，返回
//InvalidBlockNumber
else if (addr.level == FSM_ROOT_LEVEL)
{
return InvalidBlockNumber;
}
//如果在当前FSM内不能找到满足条件的叶子节点，且未到达三层
//树结构的底层，这种情况有可能是因为更低层的FSM块的最大空闲
//空间值发生变化后没有反应到高层的FSM块中去，这时需要更新
//相关FSM的最大空闲空间值。更新后将块指针重新指向第0块FSM
//块，再次从头开始搜索。设置一个计数器，如果从头开始搜索失败
//的趟数超过10000次，返回无效块号。
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;
/* Start search all over from the root */
addr = FSM_ROOT_ADDRESS;
}
}
}
依赖的函数：
2.2.1 fsm_readbuf
/*
* 读取指定FSM块逻辑地址addr对应的FSM块.
*
* 如果FSM块不存在，返回InvalidBuffer is returned。如果指定了'extend'
* 扩展FSM文件.
*/
static Buffer
fsm_readbuf(Relation rel, FSMAddress addr, bool extend)
{
BlockNumber blkno = fsm_logical_to_physical(addr);
Buffer buf;
RelationOpenSmgr(rel);
/*
* If we haven't cached the size of the FSM yet, check it first. Also
* recheck if the requested block seems to be past end, since our cached
* value might be stale. (We send smgr inval messages on truncation, but
* not on extension.)
*/
if (rel->rd_smgr->smgr_fsm_nblocks == InvalidBlockNumber ||
blkno >= rel->rd_smgr->smgr_fsm_nblocks)
{
if (smgrexists(rel->rd_smgr, FSM_FORKNUM))
rel->rd_smgr->smgr_fsm_nblocks = smgrnblocks(rel->rd_smgr,
FSM_FORKNUM);
else
rel->rd_smgr->smgr_fsm_nblocks = 0;
}
/* Handle requests beyond EOF */
if (blkno >= rel->rd_smgr->smgr_fsm_nblocks)
{
if (extend)
fsm_extend(rel, blkno + 1);
else
return InvalidBuffer;
}
buf = ReadBufferExtended(rel, FSM_FORKNUM, blkno, RBM_ZERO_ON_ERROR, NULL);
if (PageIsNew(BufferGetPage(buf)))
{
LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);
if (PageIsNew(BufferGetPage(buf)))
PageInit(BufferGetPage(buf), BLCKSZ, 0);
LockBuffer(buf, BUFFER_LOCK_UNLOCK);
}
return buf;
}
2.2.2 fsm_logical_to_physical
/*
* 根据FSM块的逻辑地址计算其物理块号
*/
static BlockNumber
fsm_logical_to_physical(FSMAddress addr)
{
BlockNumber pages;
int leafno;
int l;
/*
* 计算给定FSM块的第一个叶子节点对应的表块的逻辑编号
*/
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 */
return pages - 1;
}
2.2.3 fsm_search_avail
/*
* 在指定FSM块内的大根堆查找一个空闲空间级别不小于指定值的叶子节点，
* 返回叶子节点在fp_nodes[]数组中的编号或-1（无法找到叶子节点）
*
* 调用者至少需持有对此FSM块的共享锁。
*
* 如果advancenext被设置为false，fp_next_slot =slot , 否则
* fp_next_slot = slot+1.
*/
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:
/*
* 首先检查此FSM块内大根堆的根节点，如果其级别小于指定的minvalue,
* 说明整棵大根堆二叉树所有节点的空闲空闲都不符合要求，直接返回-1并退出。
*/
if (fsmpage->fp_nodes[0] < minvalue)
return -1;
/*
* 根据fsmpage->fp_next_slot的值，设置当前节点指针nodeno = NonLeafNodesPerPage +
* fsmpage->fp_next_slot。
*/
target = fsmpage->fp_next_slot;
if (target < 0 || target >= LeafNodesPerPage)
target = 0;
target += NonLeafNodesPerPage;
// 以target为起点，沿着大根堆二叉树，寻找满足条件的叶子节点
nodeno = target;
while (nodeno > 0)
{
// 如果当前节点的FSM级别满足要求（不低于指定的值），直接跳出循环。
if (fsmpage->fp_nodes[nodeno] >= minvalue)
break;
/*
* 设置当前节点指针nodeno为当前节点右兄弟（可回环的，同层最右节点的右兄弟是本层最左节点）的父节点，继续循环
*/
nodeno = parentof(rightneighbor(nodeno));
}
/*
* 从上面找到的节点指针nodeno开始，向下寻找一条通往叶子节点的路径。
* 在向下寻径过程中，如果左右子节点都符合条件，优先选取左子节点。该路径最终到达的叶子节点即为最终的结果，将其序号记录为slot。
*/
while (nodeno < NonLeafNodesPerPage)
{
int childnodeno = leftchild(nodeno);
if (childnodeno < NodesPerPage &&
fsmpage->fp_nodes[childnodeno] >= minvalue)
{
nodeno = childnodeno;
continue;
}
childnodeno++; /* point to right child */
if (childnodeno < NodesPerPage &&
fsmpage->fp_nodes[childnodeno] >= minvalue)
{
nodeno = childnodeno;
}
else
{
/*
* 左右子节点FSM级别都不满足条件，可能是在写FSM块时发生了崩溃导致
*
* 重建此崩溃FSM块并重新开始.
*/
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);
MarkBufferDirtyHint(buf, false);
goto restart;
}
}
/* 已到达最底层，从nodeno指针中减去非叶子节点个数，得到叶子节点的索引号. */
slot = nodeno - NonLeafNodesPerPage;
//如果advancenext 为true，fp_next_slot= slot+1， 否则fp_next_slot = slot
fsmpage->fp_next_slot = slot + (advancenext ? 1 : 0);
return slot;
}
2.2.4 大根堆二叉树相关函数
/* Macros to navigate the tree within a page. Root has index zero. */
#define leftchild(x) (2 * (x) + 1)
#define rightchild(x) (2 * (x) + 2)
#define parentof(x) (((x) - 1) / 2)
/*
* 在大根堆中寻找编号为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.
*/
if (((x + 1) & x) == 0)
x = parentof(x);
return x;
}
2.2.5 fsm_get_parent
/*
* Given a logical address of a child page, get the logical page number of
* the parent, and the slot within the parent corresponding to the child.
*/
static FSMAddress
fsm_get_parent(FSMAddress child, uint16 *slot)
{
FSMAddress parent;
Assert(child.level < FSM_ROOT_LEVEL);
parent.level = child.level + 1;
parent.logpageno = child.logpageno / SlotsPerFSMPage;
*slot = child.logpageno % SlotsPerFSMPage;
return parent;
}
