GaussDB(DWS)行存表的数据膨胀与空间重用

数据膨胀，指的是物理数据文件的大小明显高于实际存储的数据量。甚至某些特殊场景下，一个表中只有一条简单的数据，但是表对应的物理文件可能已经达到M级甚至G级。
为了解决数据膨胀，GaussDB(DWS)通过vacuum和FSM来清理和重用物理空间。本文简单介绍FSM的设计和原理，并通过一个例子对FSM功能进行简单的测试和验证。

数据膨胀的原因

想弄清楚数据膨胀的原因，首先要了解GaussDB(DWS)行存表数据基于MVCC的存储机制：

1. INSERT很简单，就是将元组插入到页面的空闲空间中；
2. DELETE则是将元组标记为旧版本，但是即使这个旧版本对所有事务都不可见了，这个元组占用的空间也不会归还给文件系统；
3. UPDATE相当于DELETE+INSERT，等于是占用了两条元组的位置，类似DELETE，旧版本的元组依然占用着物理空间。

很明显，在一通增删改操作之后，页面上的旧版本元组势必是占有一定比重的。这就导致了物理文件大小明显高于实际的数据量。

FSM的来由

为了解决无效元组占用空间的问题，GaussDB(DWS)提供了vacuum功能，在旧版本元组过期（对所有事务都不可见）后，vacuum可以将元组物理删除，这样页面上被清理出来的空闲空间就可以被再次使用了。

但是每个页面的空闲空间又不是固定大小的，所以如果要利用这些空间空间，就需要遍历一遍数据页面来找到它们，但是这样会造成比较大的开销。因此就设计了用来记录每个页面剩余空间的空闲空间映射表FSM（Free Space Mapping），以便高效的将空闲空间管理起来，方便查找和重新使用。

FSM的设计

FSM是以 _fsm 为后缀的文件对外展现的，每个行存表都有一个fsm文件。在表创建时，fsm文件并不会一起创建出来，而是在第一次vacuum时才会被创建。

因为不同页面上的元组长度各不相同，为了快速高效的管理空闲空间，没必要非常精确的管理每一个字节。将一个8K的数据页面（data block）分成256份，从页面头到页面尾顺序计算，排除页面头等固定支出，最多可以有255份空闲空间，这样FSM用1个Byte就可以标识出一个数据页面的空闲空间的大小。

在空闲空间查询时，我们只需要找到能满足需求的页面即可，所以FSM将每个页的空余空间信息通过一个大根堆结构进行维护。这样只需要从堆的根获取当前最大的剩余空间就可以知道有没有能符合要求的页面。堆中的每个叶子节点都对应一个数据页，叶子节点上记录的是数据页的可用单元的个数。

然后FSM机制通过在不同的FSM页间维护了一个类似FSM本身的树形结构，来管理所有的FSM block：一个3层的多叉树结构。

FSM页面也是大小为8K的块（FSM block），所以每个FSM block最多可以描述4096个数据页面（粗略计算，肯定是达不到的，因为有页头等信息）。按照3层计算：4096（0层）4096（1层）（8k*4096）（2层） = 2PB。可以管理2PB的数据，这对描述一张行存表，完全够用了。

整个FSM机制如下图：

1. level root和level medium都是用来查找level 2中的FSM页面的
2. level bottom是用来查找符合要求的heap页面的

FSM信息的可视化读取

FSM查找和维护的逻辑并不复杂，但是整个过程对外是不可见的。因此GaussDB（DWS）提供了pagehack工具来读取FSM文件，帮助查看当前数据页的空闲空间情况。
下面结合pagehack工具解析FSM文件进一步理解FSM机制：

初始化数据

1. 首先新建行存表并插入大量数据。分布列数据固定，为了让数据都落入一个dn，方便后面分析。
2. 删掉 2 条位于第一个heap page的数据。因为是新建的表，所以数据会从前往后顺序的落到数据页面里，c2等于1和2的两条数据一定在第一个页面上。

create table t1(c1 int, c2 int);	-- 建行存表
insert into t1 values(15, generate_series(1,100000000)); -- 插入数据
delete from t1 where c2= 1 and c2=2; --删掉 2 条位于第一个heap page的数据。

生成FSM文件并落盘

vacuum t1; -- 生成FSM文件
checkpoint; -- 刷盘

用pagehack解析FSM文件

1. pagehack 解析FSM文件并输出到文件中

pagehack -t fsm -f 73916_fsm > 73916_fsm.log

1. 打开文件，从第一个fsm block开始看。第一个fsm block属于 level root，看到一共111个fsm block，下层的最大空闲空间是31，且在数组0的位置上
   

2. 接着看到第二个fsm block，属于level medium，记录的最大空闲空间为31，数组0位置代表下层的fsm block 0有2个slot，数组108位置代表fsm block 108 有31个slot，其他都是0。0~108中间的0表示没有这些页面都没有空闲空间了，108之后的表示页面还没有扩展出来
   

3. 再往后面是第三个fsm block，这个及以后的block都属于level bottom，这层的FSM页面都是直接对应数据页面的。可以看到最大剩余空间为2，数组0位置代表heap page 0 有2个位置，正好是刚才删除的两条数据。
   

4. 第4个及后面的一直到110的block的信息如下，可以看到整个heap page都没有剩余空间了，这是因为这些页面一直在插入，没有删除数据。
   

5. 第111个block显示，最大空闲空间为31。FSM总块111个，块号110，减去前面的两个非叶子层的block，为108，正好对应前面第二个block中的第108个slot（存31）。
   
   从12553这行开始算，到12628的第26个位置为31，（12628-12553）40+26 = 3026。用page range算：439452+3026 = 442478。按 8k 页面算： 4424788192 = ‭3,624,779,776‬；
   
   
   看一下实际文件大小：1073741824*3+403554304 = ‭3,624,779,776‬，与刚才算的结果相同。
   

总结刚才的测试

1. 我们一开始向空表顺序插入了大量的数据，页面也是顺序的扩展
2. 在442478页面的时候，最后的数据插入完毕，并且还留有31个空间可用
3. 当我们从第一个页面删除了两条数据后，第一个页面空余出了2个空间
4. fsm树的样子类似：

fsm block 0
(31,0,0...0）
/
fsm block 1
(2,0,0...0,31,0...0)
/ 
fsm block 2 fsm block 110
(2,0,0...0) (0,0...0,31,0...0)

1. 在level bottom这层的fsm block中，按顺序存放的就是heap block的空闲空间值。
2. 1亿条数据用了108个slot，而一个fsm block 有4000+个叶子，所以肯定是用不完的。