Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3880613
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8585
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: Mysql/postgreSQL

2013-06-16 22:18:47

   看代码,之困难在于如何剥离繁芜的细节,直接到代码的核心,即代码到底要解决什么问题,代码用的什么算法或者思想来解决的,弄懂了这个,基本摧枯拉朽了。就像上一篇源码分析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. 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. #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. #define NonLeafNodesPerPage (BLCKSZ / 2 - 1)
  4. #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. /* Address of the root page. */
  7. 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.     return fsm_search(rel, min_cat);
  6. }
这个函数就是典型的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.     for (;;)
  7.     {
  8.         int            slot;
  9.         Buffer        buf;
  10.         uint8        max_avail = 0;

  11.         /* Read the FSM page. */
  12.         buf = fsm_readbuf(rel, addr, false); //第一次读取的是FSM 文件 ROOT block,逻辑块号为(2,0),
  13.                                             

  14.         /* Search within the page */
  15.         if (BufferIsValid(buf))
  16.         {
  17.             LockBuffer(buf, BUFFER_LOCK_SHARE);
  18.             slot = fsm_search_avail(buf, min_cat,
  19.                                     (addr.level == FSM_BOTTOM_LEVEL), //自己的哪个下属满足要求。
  20.                                     false);
  21.             if (slot == -1)
  22.                 max_avail = fsm_get_max_avail(BufferGetPage(buf));
  23.             UnlockReleaseBuffer(buf);
  24.         }
  25.         else
  26.             slot = -1;

  27.         if (slot != -1)
  28.         {
  29.             /*
  30.              * Descend the tree, or return the found block if we're at the
  31.              * bottom.
  32.              */
  33.             if (addr.level == FSM_BOTTOM_LEVEL)
  34.                 return fsm_get_heap_blk(addr, slot);             //到达了最底层,直接可以计算出relation的哪个块满足要求

  35.             addr = fsm_get_child(addr, slot);                    //未到底层,需要再次获取自己的那个下属满足要求
  36.         }
  37.         else if (addr.level == FSM_ROOT_LEVEL)                   //最高层表示,自己没有一个下属满足要求,可以直接return失败了
  38.         {
  39.             /*
  40.              * At the root, failure means there's no page with enough free
  41.              * space in the FSM. Give up.
  42.              */
  43.             return InvalidBlockNumber;                           
  44.         }
  45.         else                        //最高层表示有自己的下属可以满足,可是往下找的过程中却找不到满足要求的,
  46.                                     //这表示高层掌握的信息和下属的实际情况不符合,需要重新整理信息。               
  47.         {
  48.             uint16        parentslot;
  49.             FSMAddress    parent;

  50.             /*
  51.              * At lower level, failure can happen if the value in the upper-
  52.              * level node didn't reflect the value on the lower page. Update
  53.              * the upper node, to avoid falling into the same trap again, and
  54.              * start over.
  55.              *
  56.              * There's a race condition here, if another backend updates this
  57.              * page right after we release it, and gets the lock on the parent
  58.              * page before us. We'll then update the parent page with the now
  59.              * stale information we had. It's OK, because it should happen
  60.              * rarely, and will be fixed by the next vacuum.
  61.              *
  62.             parent = fsm_get_parent(addr, &parentslot);             
  63.             fsm_set_and_search(rel, parent, parentslot, max_avail, 0);

  64.             /*
  65.              * If the upper pages are badly out of date, we might need to loop
  66.              * quite a few times, updating them as we go. Any inconsistencies
  67.              * should eventually be corrected and the loop should end. Looping
  68.              * indefinitely is nevertheless scary, so provide an emergency
  69.              * valve.
  70.              */
  71.             if (restarts++ > 10000)
  72.                 return InvalidBlockNumber;

  73.             /* Start search all over from the root */
  74.             addr = FSM_ROOT_ADDRESS;
  75.         }
  76.     }
  77. }
    前面讲的都是根据FSM文件查找,一直没有讲述FSM文件信息的更新,relation的block不是固定不变的,假如relation的第N个block的剩余空间发生了变化,FSM文件就会发生改变,首先第0层会变化,如果必要会通知1层和2层的相关信息。
   我就不展开讲解细节了。太晚了。

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

   
阅读(8625) | 评论(3) | 转发(3) |
给主人留下些什么吧!~~

sangli002016-11-04 22:15:33

nice