PostgreSQL源码分析之FSM

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

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

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

1. BlockNumber
   
2. smgrnblocks(SMgrRelation reln, ForkNumber forknum)
   
3. {
   
4.     return (*(smgrsw[reln->smgr_which].smgr_nblocks)) (reln, forknum);
   
5. }
   
6. 
   
7. typedef unit32 BlockNumber ;

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

1.   0        0～  31
   
2.   1       32～  63
   
3.   2       64～  95
   
4.   ...
5. 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源码中有个比较有意思的常数：

1. /*
   
2.  * Depth of the on-disk tree. We need to be able to address 2^32-1 blocks,
   
3.  * and 1626 is the smallest number that satisfies X^3 >= 2^32-1. Likewise,
   
4.  * 216 is the smallest number that satisfies X^4 >= 2^32-1. In practice,
   
5.  * this means that 4096 bytes is the smallest BLCKSZ that we can get away
   
6.  * with a 3-level tree, and 512 is the smallest we support.
   
7.  */
   
8. 
   
9. #define FSM_TREE_DEPTH    ((SlotsPerFSMPage >= 1626) ? 3 : 4)

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

1. manu@manu:~$ echo 1626*1626*1626|bc
   
2. 4298942376
   
3. manu@manu:~$ echo 4*1024*1024*1024 |bc
   
4. 4294967296
   
5. manu@manu:~$ echo 1625*1625*1625 |bc
   
6. 4291015625
   
7. manu@manu:~$

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

1. #define NodesPerPage (BLCKSZ - MAXALIGN(SizeOfPageHeaderData) -
   
2.                      offsetof(FSMPageData, fp_nodes))
   
3. 
   
4. #define NonLeafNodesPerPage (BLCKSZ / 2 - 1)
   
5. #define LeafNodesPerPage (NodesPerPage - NonLeafNodesPerPage)

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

1.    4
   
2.  4   2
   
3. 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有个逻辑块号，也有个物理块号。逻辑块号采用如下的方式表示：

1. typedef struct
   
2. {
   
3.     int            level;            /* level */
   
4.     int            logpageno;        /* page number within the level */
   
5. } FSMAddress;
   
6. 
   
7. /* Address of the root page. */
   
8. 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。
   
    原理都讲清楚了，剩下的都是细节了。比较典型的应用是：

1. BlockNumber
   
2. GetPageWithFreeSpace(Relation rel, Size spaceNeeded)
   
3. {
   
4.     uint8        min_cat = fsm_space_needed_to_cat(spaceNeeded);
   
5. 
   
6.     return fsm_search(rel, min_cat);
   
7. }

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

1. static BlockNumber
   
2. fsm_search(Relation rel, uint8 min_cat)
   
3. {
   
4.     int            restarts = 0;
   
5.     FSMAddress    addr = FSM_ROOT_ADDRESS;
   
6. 
   
7.     for (;;)
   
8.     {
   
9.         int            slot;
   
10.         Buffer        buf;
    
11.         uint8        max_avail = 0;
    
12. 
    
13.         /* Read the FSM page. */
    
14.         buf = fsm_readbuf(rel, addr, false); //第一次读取的是FSM 文件 ROOT block，逻辑块号为（2,0），
15.                                             
    
16. 
    
17.         /* Search within the page */
    
18.         if (BufferIsValid(buf))
    
19.         {
    
20.             LockBuffer(buf, BUFFER_LOCK_SHARE);
    
21.             slot = fsm_search_avail(buf, min_cat,
    
22.                                     (addr.level == FSM_BOTTOM_LEVEL), //自己的哪个下属满足要求。
    
23.                                     false);
    
24.             if (slot == -1)
    
25.                 max_avail = fsm_get_max_avail(BufferGetPage(buf));
    
26.             UnlockReleaseBuffer(buf);
    
27.         }
    
28.         else
    
29.             slot = -1;
    
30. 
    
31.         if (slot != -1)
    
32.         {
    
33.             /*
    
34.              * Descend the tree, or return the found block if we're at the
    
35.              * bottom.
    
36.              */
    
37.             if (addr.level == FSM_BOTTOM_LEVEL)
    
38.                 return fsm_get_heap_blk(addr, slot);             //到达了最底层，直接可以计算出relation的哪个块满足要求
    
39. 
    
40.             addr = fsm_get_child(addr, slot);                    //未到底层，需要再次获取自己的那个下属满足要求
    
41.         }
    
42.         else if (addr.level == FSM_ROOT_LEVEL)                   //最高层表示，自己没有一个下属满足要求，可以直接return失败了
    
43.         {
    
44.             /*
    
45.              * At the root, failure means there's no page with enough free
    
46.              * space in the FSM. Give up.
    
47.              */
    
48.             return InvalidBlockNumber;                           
    
49.         }
    
50.         else                        //最高层表示有自己的下属可以满足，可是往下找的过程中却找不到满足要求的，
    
51.                                     //这表示高层掌握的信息和下属的实际情况不符合，需要重新整理信息。               
52.         {
    
53.             uint16        parentslot;
    
54.             FSMAddress    parent;
    
55. 
    
56.             /*
    
57.              * At lower level, failure can happen if the value in the upper-
    
58.              * level node didn't reflect the value on the lower page. Update
    
59.              * the upper node, to avoid falling into the same trap again, and
    
60.              * start over.
    
61.              *
    
62.              * There's a race condition here, if another backend updates this
    
63.              * page right after we release it, and gets the lock on the parent
    
64.              * page before us. We'll then update the parent page with the now
    
65.              * stale information we had. It's OK, because it should happen
    
66.              * rarely, and will be fixed by the next vacuum.
    
67.              */ 
    
68.             parent = fsm_get_parent(addr, &parentslot);             
    
69.             fsm_set_and_search(rel, parent, parentslot, max_avail, 0);
    
70. 
    
71.             /*
    
72.              * If the upper pages are badly out of date, we might need to loop
    
73.              * quite a few times, updating them as we go. Any inconsistencies
    
74.              * should eventually be corrected and the loop should end. Looping
    
75.              * indefinitely is nevertheless scary, so provide an emergency
    
76.              * valve.
    
77.              */
    
78.             if (restarts++ > 10000)
    
79.                 return InvalidBlockNumber;
    
80. 
    
81.             /* Start search all over from the root */
    
82.             addr = FSM_ROOT_ADDRESS;
    
83.         }
    
84.     }
    
85. }

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

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