原 PostgreSQL的FSM分析记录

   近来由于工作原因对PG的FSM(Free Space Map,空闲空间映射表)源码进行了学习。下面给大家简单讲述一下。

        什么是FSM呢,这不得不说一下PG的存储机制了。PG的更新(更新是删除和插入的结合)和删除都是将元组(数据库对我们插入的每一行数据封装后称为元组)标记为无效,而后通过VACUUM进行物理删除。无效的元组被删除后,若是不利用那么会造成存储的浪费,但是如果遍历一遍数据库文件块(Page),以此来找到合适的空闲空间,则会造成比较大的开销。所以,空闲空间映射表FSM就应运而生了,是用来记录每一个文件块剩余的空间。

        这里要注意的是,为了减少对FSM文件I/O的开销,空闲值不是以字节为单位的,而是8字节为单位的,进行了有损压缩。如下所示:

0       0~31
1       32~63
2       64~95
……
255     8159~8191

        下面来介绍一下FSM文件的结构,如下图所示:

        要对其分析,应该先从最下层进行分析,第三层才是对真是文件块空闲空间的记录,而第一层的0号块以及第二层都是为了快速定位合适空间块所产生的辅助块。

        这里的所谓0、1、2、3号块以及辅助块都是FSM的文件块,文件块的结构定义为:

typedef struct
{
	int		fp_next_slot;
	uint8		fp_nodes[1];
} FSMPageData;

        在内存中表现为:

        看起来这没什么,下面我来说一下数据库如何将之便为一棵树来进行遍历寻找空间空间块的。最开始的时候,PG仅仅利用FSM去记录每一个块的空闲值,这样其实效率还是比较低,后来采用了二叉树结构。这里盗用一下Bean_lee的说法:总领袖招来了4000个下属,问,你们谁的树下有超过20个freespace啊。我的4000个下属分别向自己的4000个下属询问,谁的下属有超过20的freespace,下属再向下属的下属询问...,这个场面很鸡飞狗跳,原因在于,没有管理好下属,不了解下属的情况。 要想明白怎么形成树形结构的,首先要写几个算式:

#define leftchild(x)(2 * (x) + 1)//父亲节点指向左子节点
#define rightchild(x)(2 * (x) + 2)//父亲节点指向右子节点
#define parentof(x)(((x) - 1) / 2)//子节点指向父亲节点 

        现在画出二叉树的示意图,数字为数组的序号:

                                                                             0

                                                   /                                                      \                                                   1                                                        2                                     /                          \                             /                           \                                    3                           4                           5                             6                              /           \              /            \               /             \               /             \                             7            8            9            10            11            12            13            14

                            ……

                    4095             4096             4097     4098             ……                                         8191

        (太难画了……)

        这样大家就可以看到上面算式如何把数组fp_nodes作为树搭建起来了,数组说完了,还有一个fp_next_slot这是个什么呢,我通过printf查看数据库行为,发现这个值是我们得到值是空闲节点数+1,还有就是只有当空闲文件块使用完毕后才会改变其值,他是在当前块空闲值为0后,去查询下一个块,还有就是防止同一个表块的竞争。还有一个比较有意思的循环,我在这里描述一下:同一层的最后一个节点的右节点指向该层的第一个节点。算式如下:

static int
rightneighbor(int x)
{
        x++;
        if (((x + 1) & x) == 0)
        x = parentof(x);
        return x;
} 

nodeno = parentof(rightneighbor(nodeno)); 

        当当前节点是6(括号表示二进制110)时,如何找到该层的第一个呢,6的右子节点是6*2+2 = 14,14+1 = 15(1111) ,15+1 = 16(10000),10000 & 1111 = 0,x = (15-1)/2, x = 7,(7-1)/ 2 = 3。这样就能找到同层的第一个节点。这里便还有许多公式,具体都在src/backend/storage/freespace/fsmpage.c内。 

        其次数据库为了方便查找FSM文件,使用了以下数据结构来表示FSM块在树中的位置。

typedef struct  
{  
	int  level;  //第一层为2,第三层为0,第二层为1
	Int  logpageno;  //该层的位置
}  FSMAddress;

        对于FSM文件内的逻辑结构,现在已经比较明了了,但是这是怎么去查找一个空闲块的呢?文字叙述肯定难以理解,下面就数据库给出的例子,进行解读。

        例如, 空闲块值树如下,fp_next_slot为(4,7)(fp_next_slot是int,这里为了看起来方便),找寻一个空闲值为6的空闲块:             7             7   6             5 7 6 5             4 5 5 7 2 6 5 2 

        第一步:找到根节点,为7(0,0),有足够的空闲值,去寻找;         第二步:查看第四层第三个空闲块,空闲值为5(4,7),不满足,找寻父节点;         第三步:父节点为5(3,4),也不符合;         第四步:找到父节点7(2,1)可以,找寻右子节点7(3,2),找寻子节点(4,4)符合;         第五步:返回 slot(4-1= 3),设置fp_next_slot = slot +1 ;(3+1 = 4).

        以上就是说如何去找的。         对于数据库对FSM的调整,不是及时的,首先在缓存中进行修改,而后再刷入到磁盘中。

        以上就是对FSM文件的分析记录。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏owent

Rust的第二次接触-写个小服务器程序

蛮久前入门了一下 Rust 语言。它的设计模型非常地吸引C/C++的开发者。但是学习语言嘛还是要练习一下,之前也用它给我们项目写了个命令行小工具。这回拿来写个小...

1.4K30
来自专栏向治洪

qq安全原理

    故事总要有缘由,那么这个故事的缘由就是,当我以前写了一个获取其它进程密码框密码的时候(前几篇博客中有描述),我抱着试一试的心情去试探了一下能不能得到 Q...

17980
来自专栏我的博客

原生JavaScript第一天

首先:感谢李炎恢老师的无私奉献 其次:下面的学习总结都是根据李炎恢老师的视频以及参考网络资料编写,转载请注明出处:http://www.0377joyous.c...

29340
来自专栏HansBug's Lab

一个很逗的东西——Jd

这个嘛是本人专门为了NOI上面对拍程序写的对拍程序,已经经历了NOI2015的考验;更重要的是——纯Pascal的哦(HansBug:其实是我不会写.sh脚本T...

318120
来自专栏一名合格java开发的自我修养

java使用Map做缓存你真的用对了吗?弱引用WeakHashMap了解一下

序:使用java的Map做缓存,你是否考虑过容量导致的OOM问题,是否考虑命中率对性能的影响??

36410
来自专栏小樱的经验随笔

CTF---Web入门第十一题 PHP大法

PHP大法分值:20 来源: DUTCTF 难度:中 参与人数:8205人 Get Flag:2923人 答题人数:3042人 解题通过率:96% 注意备份文件...

467110
来自专栏程序员宝库

给Python新手的一些编码建议

每天你都应该努力提升自己的编码技能,今天我给Python新手带来了一些编程建议。 Python箴言 打开Python交互终端并运行下面命令 ? 然后命令会有一...

387100
来自专栏瓜大三哥

UVM(七)之phase及objection

UVM(七)之phase及objection 这两个概念与UVM验证平台息息相关,phase就好比铁轨,让UVM这趟列车在铁轨上向前运行,不会脱轨,不...

56480
来自专栏JavaQ

拒绝一针串到底式参数类

当参数个数多于三个的时候,通常会将这些参数封装到一个类中,进而形成参数类。参数类通常是类间或方法间进行通信的纽带,起到承上启下的作用。 基本上一个稍微有些规模的...

28680
来自专栏魏琼东

一步一步教你使用AgileEAS.NET基础类库进行应用开发-WinForm应用篇-实例一个模块(商品字典)

        本文是一步一步教你使用AgileEAS.NET基础进行应用开发系统的WinForm应用篇的开篇,从本文起开始大家将看到一个距离真实应用非常接的开...

20650

扫码关注云+社区

领取腾讯云代金券