PostgreSQL源码分析之FSM

   看代码，之困难在于如何剥离繁芜的细节，直接到代码的核心，即代码到底要解决什么问题，代码用的什么算法或者思想来解决的，弄懂了这个，基本摧枯拉朽了。就像上一篇源码分析Page。Page要解决的问题是多条记录在8KB的空间内存储问题，这自然包含当前8KB的空间内有多大的剩余空间;如何插入一笔记录到8KB的空间;如何删除一笔记录;至于算法实现，对照Momjian绘制的那副Page的图片，足以理解Page的所有代码。
   我们在数据库的磁盘文件中可以发现以fsm后缀的文件名，这些文件是干啥的，另外这些文件最小是24KB三个block的大小，从未见过8KB的fsm文件，这又是为何，这篇文章将要讲述这些问题。

manu@manu:/usr/pgdata/base/16384$ ll
			
				....
-rw------- 1 manu manu  8192  6月 10 13:05 11882
-rw------- 1 manu manu     24576  6月  3 21:31 11882_fsm
...

    所谓FSM，指的是Free Space Map，空闲空间映射表。这个是干啥的呢？莫急，听我细细道来。一个relation有多个8KB大小的block，这些block存储在磁盘上。我们可以获取一个relation一共有多少个block。 

BlockNumber
smgrnblocks(SMgrRelation reln, ForkNumber forknum)
{
    return (*(smgrsw[reln->smgr_which].smgr_nblocks)) (reln, forknum);
}

typedef unit32 BlockNumber ;

    这个uinit32就决定了一个relation最大只能有4G个block，考虑到每个block大小为8KB，也就是说一个relation的磁盘大小最大为32TB,已经很大了。注意relation的不断的插入删除记录，会造成很多的block其实是有空闲空间的，Page的空闲空间管理的只是8KB空间内有多少剩余空间，而FSM管理的则是relation对应的所有的Block（或者说page，whatever，反正都是这8KB的空间）分别有多少剩余空间：
   FSM存储的并不是真是的剩余空间，而是近似值，用一个字节表示剩余空间的大小，也就是说 

  0        0～  31
  1       32～  63
  2       64～  95
  ...
255     8163～8192

剩余空间分成了256个档次，每8K/256=32为一档，那么，一个字节就足以表示一个block的剩余空间。
   如果让你来管理relation所有block的的剩余空间，你如何做？最容易想到的方法就是以数组的方法表示各个block的剩余空间，fsm[0]表示第0个block的剩余空间，fsm[1]表示第一个block的剩余空间，然后把这个信息存入fsm文件即可。比如我想知道第800个block（0-based）还剩下多少空间，只需要将对应的fsm文件的第800个字节（从0开始计数）读出来即可。方便可以扩展，比如relation新增一个block，只需要fsm文件新增一个字节即可。
   目前看起来很完美，可是数组有致命的缺陷，我要查找剩余空间的值最小为40的，那数组就傻了眼，因为他不得不挨个的比较，知道遇到值大于40的才能停下，如果block特别多，数组长度非常大，这个问题就会恶化。运气好很快就找到了，运气不好可能遍历了整个数组，效率太低。所以不能采用这种方法。
   PostgreSQL采用的方法是分层+堆的思想。想想看假如有100万人需要你管理，你如何管理？只能分层，每100人选出一个百夫长，每100个百夫长选出一个万夫长，我来管理100个万夫长。这就是分层管理的思想。
  PostgreSQL源码中有个比较有意思的常数：

/*
 * 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.
 */

#define FSM_TREE_DEPTH    ((SlotsPerFSMPage >= 1626) ? 3 : 4)

    如果SlotsPerPage>=1626,则为三层，否则，则为4层。什么意思？开始我也没看懂，看了注释方明白：刚才我们举例子是每100个人举出一个管理者，只需要三层就可以管理100万人。现在我们的需求是管理4G个block，到底是需要三层管理还是四层管理？就要看每层管理多少人。

manu@manu:~$ echo 1626*1626*1626|bc
4298942376
manu@manu:~$ echo 4*1024*1024*1024 |bc
4294967296
manu@manu:~$ echo 1625*1625*1625 |bc
4291015625
manu@manu:~$

    我们看到1626的立方是大于4G的，而1625的立方是小于4G的，所以要想三层管理4G的对象，必须每层次至少管理1626个子层。事实上，block大小为8KB，用一个字节管理一个子对象，每次管理的大约是4000左右 。4000×4000×4000 >>4G,三层管理结构，足以管理4G个block。

#define NodesPerPage (BLCKSZ - MAXALIGN(SizeOfPageHeaderData) -
                      offsetof(FSMPageData, fp_nodes))

#define NonLeafNodesPerPage (BLCKSZ / 2 - 1)
#define LeafNodesPerPage (NodesPerPage - NonLeafNodesPerPage)

    现在我们分了层，但是仅仅分层是不够的。想想下面的场景，如果用户请求大小为620字节的空间，我一算（620+31）/32 = 20,需要freespace值为20的block。总领袖招来了4000个下属，问，你们谁的树下有超过20个freespace啊。我的4000个下属分别向自己的4000个下属询问，谁的下属有超过20的freespace，下属再向下属的下属询问...，这个场面很鸡飞狗跳，原因在于，没有管理好下属，不了解下属的情况。
   这就要用到堆的思想了。我有4000个下属，管理颇为不便，毕竟我不能挨个去问，你有没有超过20的剩余空间。那怎么办能，这就是heap的思想了：

   4
 4   2
3    4   0    2

   我们以管理4个下属为例，3和4一组PK，胜者是4,0和2一组PK，胜者是2 ，然后胜者4和2继续PK，胜者是4,依次类推，在最顶端的就是能力最强的下属。管理4000个下属其实也一样。两两一组，从最底层开始PK，得到两人中的优胜者，然后两人中的优胜者在两两PK，得到4人中的优胜者，以此类推，最终得到4000下属中的优胜者。如果4000下属的最终优胜者都不能满足需求，那么就不能满足需求了。如果可以的话，可以找到最接近需求的那个下属，比如我需要3,而顶层是4，表示可以找到，然后询问左右孩子，哪个可以办到。
  
   上图解释了分层管理，每个FSM的block有个逻辑块号，也有个物理块号。逻辑块号采用如下的方式表示：

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};

    level表示第几层，logpageno表示该层的第几个下属。就是上图方框里面的数字，最顶层的是（2,0），他的第一个下属是（1,0），以此类推。
   除了逻辑号，还有物理块号，这些管理信息是以block的形式存放在FSM文件中。比如最顶层的root（2,0），对应fsm文件的第0个块号,就是上图中椭圆中的数。请注意，relation文件比较小的时候，比如只有一个block，那么其实只可能有三个fsm文件的block。因为（0,0）本身就可以管理4000个block，而（1，0）暂时管理（0,0）一个下属，而（2,0）管理（1,0）一个下属，其他的fsm block暂时不存在。虽然只有1个relation的block，但是需要个FSM block去管理。当然了（0～3999）个relaiton的block，也只需要这三个FSM block 块管理就够了。这也就解释了为什么FSM文件最少也是24KB，因为三层管理结构，哪怕只有1个block需要管理，也需要3个FSM blcok。
   
    原理都讲清楚了，剩下的都是细节了。比较典型的应用是：

BlockNumber
GetPageWithFreeSpace(Relation rel, Size spaceNeeded)
{
    uint8        min_cat = fsm_space_needed_to_cat(spaceNeeded);

    return fsm_search(rel, min_cat);
}

这个函数就是典型的FSM的作用：给你一个relation,和spaceNeed，获取relation的哪个块的剩余空间可以满足要求。

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. */
        buf = fsm_readbuf(rel, addr, false); //第一次读取的是FSM 文件 ROOT block，逻辑块号为（2,0），


        /* Search within the page */
        if (BufferIsValid(buf))
        {
            LockBuffer(buf, BUFFER_LOCK_SHARE);
            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
            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);             //到达了最底层，直接可以计算出relation的哪个块满足要求

            addr = fsm_get_child(addr, slot);                    //未到底层，需要再次获取自己的那个下属满足要求
        }
        else if (addr.level == FSM_ROOT_LEVEL)                   //最高层表示，自己没有一个下属满足要求，可以直接return失败了
        {
            /*
             * At the root, failure means there's no page with enough free
             * space in the FSM. Give up.
             */
            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.
             */
            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 */
            addr = FSM_ROOT_ADDRESS;
        }
    }
}

    前面讲的都是根据FSM文件查找，一直没有讲述FSM文件信息的更新，relation的block不是固定不变的，假如relation的第N个block的剩余空间发生了变化，FSM文件就会发生改变，首先第0层会变化，如果必要会通知1层和2层的相关信息。
   我就不展开讲解细节了。太晚了。

参考文献：
1 PostgreSQL数据库内核分析
2 PostgreSQL 9.1.9源码