PostgreSQL源码分析之page

    前面几篇博客分析了shared buffer,从shared buffer到磁盘文件的映射，到shared buffer的分配和替换，再到如何测量shared buffer的性能情况，配置是否合理，基本把shared buffer大概介绍了下，这篇博客主要分析page。
   page的源码落在/src/backend/storage/page，page对于PostgreSQL是个什么概念？page，block，file，这些概念怎么理解？
   文件是数据库的持久化存储，当然我们已经知道数据库的relation以文件的形式存在在磁盘上，无论是xxx文件还是xxx_fsm,还是xxx_vm，这是文件的概念。当relation的xxx的文件特别大，超过1G的时候，同一个relation还会分文件存储，出现xxx.1，xxx.2这种文件。Whatever，文件在，PostgreSQL数据库的信息就在。
   所谓block，指的是每次加载进内存的基本单位，如果PostgreSQL需要某个relation的信息，不会是直接relation对应的磁盘文件全部读入内存，而是分block载入内存。PostgreSQL有一定的规则知道自己需要的信息或者记录或者说tuple 落在磁盘文件的那个8K block上，然后将8K block加载入local buffer，或者shared buffer，总之加载入内存。简单的说，block是磁盘上文件和内存之间加载/驱逐的基本单位。
   page是个什么概念呢？page大小也是8K，就是上面提到的block，只不过，page仔细的端详了8KB的内容，分析了信息是如何组织，如何存放到8KB的block空间之内。注意每条记录内部的结构不是page关心的事情，他的视角没有这个细，我们关心的是这条记录作为一个整体如何存放到8K的page中去;当然8K的page可能存放多条记录，如何摆放到8K的page中去;当前page剩余空间还有多少;我有一条需要空间为size的记录，page是否有足够的空间容纳之;记录可能会插入，也可能会删除，page里面会不会因为删除动作，页面内部有很多的洞，或者页面碎片化，如何清理碎片，这些都是page要解决的问题。
   简而言之，page，就是管理8K大小的一亩三分地，他要把多条记录（Tuple）有条不紊地组织在这8K的空间之内。
    一条记录会插入到8KB的page之中，信息如何组织？自然大多数记录占用的空间不会超过8KB，以我们前边提到的friends为例：
   
    这个friends的设计不太好，不过我们的重点不在于此，我们关心的是这长度为8192（1个Block或者说1个page）的文件，到底存放的是啥内容？
   
   我们看到文件虽然有8K，但是实际上只有最前面的2行32字节，和最后面的64字节中包含信息，因为这个文件对应的就是我们的friends这张表，而这张表里面有Lee，Bean ，158XXXXX，Nan Jing等信息，当然了这是一条记录，或者一个Tuple，Tuple内部的组成或者layout我们不关心，但是这个16385文件作为一定记录了这些信息。我们用vbindiff查看之：
   
   
   我们看到了，我们的信息Bean，Nan Jing之类的，不管是如何组织的，的确存储在表friend对应文件16385之中。这条记录如何放入8K的空间之内，头部的一些字符有是干啥的，记录的信息为何放到了现在的这个位置，这就是page要管的事情，我们下面详查之。
  
    上图就是page的结构图，8K的空间包括一个头部Page Header，若干个Item，每个Item指向一条记录（Tuple），有些Page在初始化的时候，就page的末尾，预留出空间作为Special用，作什么用，我暂时不知，不过没关系，不影响我们理解Page。当然了，有些Page不需要Special空间，就没有预留。
   好我们可以分析源码了。
   INIT-page的初始化
    首当其冲的是PageInit函数。我们申请了一个新的干净的8K的page，把记录插入page之前，需要将page初始化，基本就是初始化一下Page Header。：  

void
PageInit(Page page, Size pageSize, Size specialSize)
{
    PageHeader    p = (PageHeader) page;

    specialSize = MAXALIGN(specialSize);

    Assert(pageSize == BLCKSZ);
    Assert(pageSize > specialSize + SizeOfPageHeaderData);

    /* Make sure all fields of page are zero, as well as unused space */
    MemSet(p, 0, pageSize);

    /* p->pd_flags = 0;                                done by above MemSet */
    p->pd_lower = SizeOfPageHeaderData;
    p->pd_upper = pageSize - specialSize;
    p->pd_special = pageSize - specialSize;
    PageSetPageSizeAndVersion(page, pageSize, PG_PAGE_LAYOUT_VERSION);
    /* p->pd_prune_xid = InvalidTransactionId;        done by above MemSet */
}

    对于pageSize，默认情况下就是8K即BLCKSZ，而specialSize，某些情况下为0,某些情况下不为0,这都没关系。
    Init做的事情是
    1 给special预留空间     

    specialSize = MAXALIGN(specialSize);         //4 字节对齐
    p->pd_special = pageSize - specialSize;

    page header的成员变量pd_special相当于画了一条线，从pd_special这个位置到page的结尾，都是special的地盘，普通插入Tuple，都不许进入这个私有地盘。而且这个pd_special一旦初始化之后，这个值就不会动了。
    2 设置pd_lower和pg_upper
   当初始化的时候，pd_lower设置为SizeOfPageHeaderData，pd_upper设置为和pd_special一样。但是注意，这个lower和upper不是固定的，随着Tuple的不断插入，lower变大，而upper不断变小。当我们每插入一条Tuple，需要在当前的lower位置再分配一个Item，记录Tuple的长度，Tuple的起始位置offset，还有flag信息。这个Page Header中的pd_lower就是记录分配下一个Item的起始位置。所以如果不断插入，lower不断增加，每增加一条Tuple，就要分配一个Item（4个字节）。同样道理，Tuple的存放位置，根据upper提供的信息，可以找到将Tuple分配到何处比较合。分配之后，pd_upper就会减少，减少Tuple的长度（对齐也考虑进去）。
    3 设置 page的size 和version

#define PageSetPageSizeAndVersion(page, size, version)
(
    AssertMacro(((size) & 0xFF00) == (size)),
    AssertMacro(((version) & 0x00FF) == (version)),
    ((PageHeader) (page))->pd_pagesize_version = (size) | (version)
)

   这个不多说，基本就是将版本号和page的长度记录在16bit的结构里面。
   下面我们比较刚初始化和插入一条记录之后的情形：
   
     
   一个记录对应两个部分，就头部附近Item空间和真正记录信息的Tuple。Item记录的是Tuple在Page的offset，size等信息。
   AddItem-page增加一个记录
   Page是用来存放Tuple的，增加一个Tuple删除一个Tuple都是Page份内的事情，我们首先看下Page如何增加一个Tuple：
   function PageAddItem是完成这件事情。因为这个接口是很通用的接口，要满足上层的各种需求，所以稍显复杂，不过整体还好。

OffsetNumber
PageAddItem(Page page,
            Item item,
            Size size,
            OffsetNumber offsetNumber,
            bool overwrite,
            bool is_heap)

   item是我的当前记录的指针，size记录记录的长度，（item，item+size）这部分地址是Tuple的信息。 Page表示从这个page中查找空间保存当前的Tuple。这我们很好理解，因为这是基本的要求：在当前页随便找个空间保存我的item。咱的要求比较简单，可是有些客户要求可就不简单了，比如客户要求，就要将我的记录拜放到page的第三个item，这就是比较坑爹的客户了。就像去饭馆吃饭，我到了饭馆，喊了一嗓子，小二，给哥随便找个8人桌，小二很happy，因为我的要求低。也有客官直接喊了一嗓子，小二，我要去三楼最好的那个雅间，如果有客人，让他给我腾地方，我们有8个人。得，小二就傻了眼，但是还得办不是。PageAddItem也是一样，offsetNumber这个如参表示，大爷我就要将记录存放在这个位置。overwrite则这个参数就更拽了，如果有记录放在我要的位置，让原来那条记录给大爷滚蛋，。如果overwrite =0 表示，大爷要的位置如果有人，原来位置的记录换个地方，给大爷我腾地方。OK，这几个参数是干啥的，我基本交代清楚了
   
   因为Page Header的长度是固定，而紧跟其后的Item的长度也是固定的，而每增加一个Item,pd_lower就增加一个Item的长度，这样，根据pd_lower就可以算出当前的页面已经有几个Tuple了。

    #define PageGetMaxOffsetNumber(page)
    (((PageHeader) (page))->pd_lower <= SizeOfPageHeaderData ? 0 :
     ((((PageHeader) (page))->pd_lower - SizeOfPageHeaderData)
      / sizeof(ItemIdData)))

limit = OffsetNumberNext(PageGetMaxOffsetNumber(page));

    这个limit记录的是当前记录数+1 ，用这个来判段新来的AddItem请求有没有指定既有的位置

if (OffsetNumberIsValid(offsetNumber)) //大爷型请求，值定了记录的存储位置
{
        if (overwrite)   //原有的记录删除，属于要求改写
        {
            if (offsetNumber < limit)
            {
                itemId = PageGetItemId(phdr, offsetNumber);
                if (ItemIdIsUsed(itemId) || ItemIdHasStorage(itemId))
                {
                    elog(WARNING, "will not overwrite a used ItemId");
                    return InvalidOffsetNumber;
                }
            }
        }
        else            //新增加的客户要求这个位置，需要将原来位于这个位置的记录迁移到其他位置。
        {
            if (offsetNumber < limit)
                needshuffle = true;        /* need to move existing linp's */
        }
}
else   //普通客户
{

}

    上面分析了文艺青年式的AddItem，下面我们分析下普通青年的AddItem，普通青年要求低，随便找个地儿存放当年记录：

    if (OffsetNumberIsValid(offsetNumber))
    {
          ...
    }
    else
    {
        /* offsetNumber was not passed in, so find a free slot */
        /* if no free slot, we'll put it at limit (1st open slot) */
        if (PageHasFreeLinePointers(phdr))
        {
            /*
             * Look for "recyclable" (unused) ItemId. We check for no storage
             * as well, just to be paranoid --- unused items should never have
             * storage.
             */
            for (offsetNumber = 1; offsetNumber < limit; offsetNumber++)
            {
                itemId = PageGetItemId(phdr, offsetNumber);
                if (!ItemIdIsUsed(itemId) && !ItemIdHasStorage(itemId))
                    break;
            }
            if (offsetNumber >= limit)
            {
                /* the hint is wrong, so reset it */
                PageClearHasFreeLinePointers(phdr);
            }
        }
        else
        {
            /* don't bother searching if hint says there's no free slot */
            offsetNumber = limit;
        }
    }

    比较容易想到的是offsetNumber = limit = 当前记录数 + 1,这个太顺理成章了，那个PageHasFreeLinePointers是搞什么飞机？我们看下：

#define PageHasFreeLinePointers(page)
    (((PageHeader) (page))->pd_flags & PD_HAS_FREE_LINES)

    这个标志是啥意思？看名字的意思是 表征是否有free line。我们会把一些Item状态置为LP_UNUSED，这时候，Item和它原来的Tuple就没有映射关系。这样原来对应Tuple，就成了垃圾。后面会有会PageRepairFragmentation清理这些空间，但是仍然不会删除这个LP_UNUSED状态的Item，只是打上一个标志，表示存在无主的Item，可以被复用。

    if (offsetNumber == limit || needshuffle)
        lower = phdr->pd_lower + sizeof(ItemIdData); //新增一个Item
    else
        lower = phdr->pd_lower;

    alignedSize = MAXALIGN(size);

    upper = (int) phdr->pd_upper - (int) alignedSize;

    if (lower > upper)
        return InvalidOffsetNumber;

    /*
     * OK to insert the item. First, shuffle the existing pointers if needed.
     */
    itemId = PageGetItemId(phdr, offsetNumber);

    if (needshuffle)
        memmove(itemId + 1, itemId,
                (limit - offsetNumber) * sizeof(ItemIdData));

    /* set the item pointer */
    ItemIdSetNormal(itemId, upper, size);

    /* copy the item's data onto the page */
    memcpy((char *) page + upper, item, size);

    /* adjust page header */
    phdr->pd_lower = (LocationIndex) lower;
    phdr->pd_upper = (LocationIndex) upper;

    return offsetNumber;

    因为新增个Tuple，需要alignedSize存储这记录的Tuple部分，所以pd_upper - alignedSize作为新的pd_upper.
    ItemIdSetNormal把Tuple的size，offset信息记录在Item中：

#define ItemIdSetNormal(itemId, off, len)
(
    (itemId)->lp_flags = LP_NORMAL,
    (itemId)->lp_off = (off),     //记录offset， page + off = Tuple的起始位置
    (itemId)->lp_len = (len)      //记录Tuple的size 。 （page + off ，page + off + len）记录的是Tuple的信息
)

    PageIndexTupleDelete-page删除一条记录   
    我们下面讲述删除一条记录：

void
PageIndexTupleDelete(Page page, OffsetNumber offnum)

    offnum指示第几个记录，offnum是从1开始计数的，查找对应item 是offnum-1.
   我们找到Item，就可以找到Tuple对应的offset和size：    

    tup = PageGetItemId(page, offnum);
    Assert(ItemIdHasStorage(tup));
    size = ItemIdGetLength(tup);
    offset = ItemIdGetOffset(tup);

 
   删除第二个记录之后，我们得到的Page布局如下：
 
   我们可以看到，至少发生两次memmove
   1 删除记录的Item后面的item都要往迁移，防止出现一个空洞

    nbytes = phdr->pd_lower -
        ((char *) &phdr->pd_linp[offidx + 1] - (char *) phdr);

    if (nbytes > 0)
        memmove((char *) &(phdr->pd_linp[offidx]),
                (char *) &(phdr->pd_linp[offidx + 1]),
                nbytes);

   2 删除记录的Tuple后面的Tuple，也要移动，否则，会出现Tuple-2对应的空洞。 

    addr = (char *) page + phdr->pd_upper;

    if (offset > phdr->pd_upper)
        memmove(addr + size, addr, (int) (offset - phdr->pd_upper));

    除了移动内存，item对应的指针也要发生相应的改变：比如洋红色的两个item需要修改offset  

    if (!PageIsEmpty(page))
    {
        int            i;

        nline--;                /* there's one less than when we started */
        for (i = 1; i <= nline; i++)
        {
            ItemId        ii = PageGetItemId(phdr, i);

            Assert(ItemIdHasStorage(ii));
            if (ItemIdGetOffset(ii) <= offset)  //在前面Tuple2 前面的Tuple，发生了移位，所以对应Item的lp_off要修改。
                ii->lp_off += size;
        }
    }

    Page还剩多少剩余空间这是很重要的，这决定我们能否插入一条记录到当前Page。 原理就非常简单了，pd_upper - pd_lower ,就是剩余空间，但是，还需要存放Item，所以还需要减Item占据的空间，剩下的才能存放Tuple的空间：   

Size
PageGetFreeSpace(Page page)
{
    int            space;

    /*
     * Use signed arithmetic here so that we behave sensibly if pd_lower >
     * pd_upper.
     */
    space = (int) ((PageHeader) page)->pd_upper -
        (int) ((PageHeader) page)->pd_lower;

    if (space < (int) sizeof(ItemIdData))
        return 0;
    space -= sizeof(ItemIdData);

    return (Size) space;
}

   文章写的已经很长了，PageIndexMultiDelete 和 PageRepairFragmentation核心逻辑是类似的，我就不写这两个。原来也不难，把这些碎片化的Tuple排个序，重新连接成一个连续的空间。

参考文献：
1 PostgreSQL 9.1.9 源码