PG 内存上下文

Posted by zhangxiaojian on October 16, 2015

本文首先大体讲一个内存上下文是干什么的,结构是怎么样的。然后具体介绍PG中现有的一套分配策略,并不详细分析源码的每一处(可以参考PG内核分析这本书),而是说说其中思路流程,如何调节参数进行优化。最后介绍如何使用C++重写其中的源码,让内存上下文不仅仅是PG中的一个特性,而是可以作为一个内存分配的库,供其它程序使用。并附上重写后的源码供大家参考。

大体概述

PostgreSQL 从7.1开始支持内存上下文,因为数据库在查询过程中需要不断申请内存空间,但是只有当查询结束后才能够释放内存,这执行之间,就有可能发生内存泄漏问题。内存对于数据库而言极其重要,为了避免内存泄漏,引入了内存上下文机制,所有的内存分配回收工作都在一个特定的内存上下文中进行,这样,即使有申请的内存忘了回收,也一定是在内存上下文中,可由它统一交还给操作系统。如图所示,内存上下文使用malloc, free向OS申请空间,通过某种分配管理策略向PG提供申请和释放内存的接口。OS申请来的内存都在MemoryContext中,那么PG在使用中未释放的空间也可以由MemoryContext来释放。大概就是这么一回事。

pg1

既然可以在一个内存上下文中完成内存分配与回收,自然就会想到不同的情况使用不同的内存上下文,比如查询用一个,错误处理用一个等等,这样释放起来就不会相互影响。为了方便管理,所有的不同的内存上下文互相连接起来形成一颗树,树的根节点是全局变量TopMemoryContext,在初始化内存上下文中定义。有了它就可以很方便的管理每一个内存上下文。如图:

pg2

每一个节点都只知道它的parent节点和firstchild节点,而同级的兄弟节点之间互相连接。

分配策略

PG到目前为止只实现了一种内存分配策略——AllocSetContext,因此所有的内存上下文虽然名字不同,其实本质上都是AllocSetContext对象结构。因为数据库中使用内存方式情形复杂,有时需要尽可能多的保留已经申请的内存,避免下次使用再申请。有时又为了减少系统负载,需要释放一些内存。所以,理想的情况是可以根据不同情形有不同的内存分配策略。PG是纯C的代码,如果了解C++或是面向对象的特性,看完内存上下文这块的代码就知道,使用纯C的代码也完全能够写出继承,多态的味道。看一下源码:

typedef struct MemoryContextData
{
    NodeTag		type;			/* identifies exact kind of context */
    MemoryContextMethods *methods;		/* virtual function table */
    MemoryContext parent;		/* NULL if no parent (toplevel context) */
    MemoryContext firstchild;	/* head of linked list of children */
    MemoryContext nextchild;	/* next child of same parent */
    char	   *name;			/* context name (just for debugging) */
    bool		isReset;		/* T = no space alloced since last reset */
} MemoryContextData;

MemoryContextData是所有内存上下文实现类的父类,前两个参数type表示实际指向的内存上下文类型,这个功能在c++中可以使用typeid来完成。而method是虚函数表,MemoryContextMethod类型包含了内存上下文能够向外提供的函数,在初始化内存上下文对象的时候,指向具体实现类的函数,这样,对外使用的接口不变,而因为指向了不同的实现类函数,可以获得不同的内存分配策略。看一下MemoryContextMethod类里面到底有什么:

typedef struct MemoryContextMethods
{
    void	   *(*alloc) (MemoryContext context, Size size);
    /* call this free_p in case someone #define's free() */
    void		(*free_p) (MemoryContext context, void *pointer);
    void	   *(*realloc) (MemoryContext context, void *pointer, Size size);
    void		(*init) (MemoryContext context);
    void		(*reset) (MemoryContext context);
    void		(*delete_context) (MemoryContext context);
    Size		(*get_chunk_space) (MemoryContext context, void *pointer);
    bool		(*is_empty) (MemoryContext context);
    void		(*stats) (MemoryContext context, int level);
#ifdef MEMORY_CONTEXT_CHECKING
    void		(*check) (MemoryContext context);
#endif
} MemoryContextMethods;

不出所料,有分配,释放,重置等等。其中所有函数的第一个参数都相同,因为需要知道这些操作是在哪一个内存上下文中的,如果使用c++,那么就可以省去这个参数,由隐含的this指针代替。(其中,get_chunk_space函数我觉得放在这不合适,这本是一个抽象的函数接口,所有实现类都要实现这些接口,PG目前的AllocSetContext有chunk的概念,但不能保证以后实现的分配策略就会有chunk)

与c++中实现虚函数表的方式类似,MemoryContextData结构是放在实现类结构体中第一个位置,方便指针的转型操作。看一下AllocSetContext是以什么策略分配内存的吧:

pg3

如图,AllocSetData中的header是父类该有的东西,已经介绍过了。在这种策略下,有两个重要的概念,Block和Chunk。Block是从OS分配的一段连续的内存空间,而Chunk是内存上下文返回给用户的一段内存空间。它们分别由AllocBlockData和AllocChunkData结构来描述。AllocSet的第二个数据成员blocks,是AllocBlockData类型的指针,指向一个Block链表,这个链表就是内存上下文中所有向OS申请的内存。

AllocBlockData中第一个参数aset表示这个block属于哪个内存上下文,freeptr和endptr指向一个Block中尚未分配的内存起点和终点。AllocBlockData结构本身所占用的空间也在Block中,图中深蓝色区域。用户申请内存时,从Block中未分配内存拿出一块,也就是一个Chunk,同样,如图中蓝色区域表示AllocChunkData结构本身占用空间,剩下空间是返回给用户的内存区域,其中size成员表示chunk的大小。

为了消除外部碎片,Block和Chunk的大小都必须是2的n次方。PG中定义的一个最小的chunk是2^3 byte,最大是2^13 byte。所以假设用户申请一个5byte的空间,实际上会给8 byte,内部碎片无法避免。

当一个chunk使用完毕需要回收,由于chunk在Block中,无法归还(当然也不想归还)给OS,就需要收集起来以便再分配。AllocSetData的第三个参数freelist数据用来管理空闲的chunk。freelist数组大小11,用来管理11种不同大小的空闲chunk,从8byte到 8kb。相同大小的chunk链接成一个链表,有合适大小的内存申请操作就去对应的freelist找一个空闲的chunk分配出去即可,这样既不会有浪费,也不用频繁的向OS申请内存。其中一个小细节,AllocBlockData和AllocChunkData 都有一个数据成员aset指向对应的内存上下文,但AllocChunkData中的类型却是void*,因为空闲的chunk属于哪个内存上下文是没有意义的,正好用来当作链表的指针。

AllocSetData中还有几个非常重要的参数

initBlockSize: 初始化时首个Block的大小,至少会有1kb。

maxBlockSize: 最大的Block大小,因为每次新申请一个Block,它的大小都会是上一个的两倍,maxBlockSize就是为了限制新申请的Block最大的增长上限。

nextBlockSize: 下一个Block的大小,初始的时候和initBlockSize相同,当不断进行分配,每次都会增大一倍。

allocChunkLimit: 一个重要的临界值,如果申请的空间大于这个值,就分配一个独立的Block,而不是一个chunk,并且回收的时候也会直接把这个Block还给OS。

keeper: 指向第一个Block,当内存上下文重置的时候,keeper指向的block会保留下来不还给OS,就避免了每次重置后使用都要立刻malloc内存。

分配和回收的流程:

在AllocSetData的blocks链表中,只有第一个Block是活动块,申请chunk的时候也只能从这个Block中申请。当用户申请内存,首先会判断申请的内存大小是否超过allocChunkLimit,如果超过,就按照申请的大小malloc一个大小适当的独立Block,并且把这个Block链接到活动块之后的位置。如果小于allocChunkLimit,表示此次申请可以被当作一个chunk处理,就去freelist里面查找对应大小的空闲块,如果找到就从空闲链表里拿出去,返回给用户用。如果没找到就要去活动块里面申请一个新的chunk。那么活动块剩余的未分配内存不一定够用,如果不够就要重新申请一个Block来用,并且把新的Block放在第一个位置作为活动块。但此时之前的活动块虽然空间有限,但仍有未分配的内存,为了不浪费,就分配尽可能大的chunk,链接到freelist链表里。

回收的时候,同样需要判断回收的空间是否超过allocChunkLimit, 如果超过,表示这是一个独立的Block,就把它free,归还给OS。如果没有超过,就回收chunk到freelist里面即可。

评价与优化:

其实如何占有内存,如何归还内存本就是艺术。在AllocSetContext中,并不贪婪,尽可能把一次申请较大的内存块及时用完归还,而是把较小的块保留在内存上下文中,减少系统占用内存的同时,增加频繁对小内存块申请的效率。是一个不错的折中。PG是关系型数据库,可能在一次查询或者写入过程中比较频繁的是对小内存块的申请,这样确实可以增加效率,而且管理方便。但是如果将此种分配策略放到NoSql数据库或其它需要申请较大内存块的场景下,也许就会低效。

allocChunkLimit是一个重要的参数,如果大部分的申请都小于它,占用内存多,但分配速度快。相反,假如大部分申请都大于它,就和直接使用mallo/free是一样的,比较低效。allocChunkLimit最大不会超过freelist数组中最大能表示的chunk大小,freelist能表示的大小取决于宏ALLOCSET_NUM_FREELIST。同时程序设定allocChunkLimit不能超过maxBlockSize的ALLOC_CHUNK_FRACTION分之一。这样当maxBlockSize比较小的时候,能够保证一个Block可以缓冲至少ALLOC_CHUNK_FRACTION的chunk。

关于优化,主要是要控制上述几个关键的参数,如果系统内存充足,那么尽量把allocChunkLimt调大,尽可能的缓冲chunk,同时对应的要改变freelist大小和maxBlockSize的大小。这还要根据具体的应用场景,使申请空间的大小都落在freelist能够表示的范围内。

重写:

还记得本科OS实验,就在想两片连着的内存都回收了就应该融合成一个大内存块。研一上课的时候接触内存上下文机制,就好奇两个chunk能不能和在一块。答案是不能。初学只以为是PG自己的一种内存分配机制,后来读Architecture of a Database System这篇文章,提到内存上下文可以自由切换分配策略,觉得很好,可能不止可以只为PG所用。今年实验室的分布式数据库项目中,节点之间传输的数据内存不能很快回收,遇到了内存泄漏问题,而且想为它实现一种类似环形的内存分配策略,就想到了内存上下文,方便管理,而且可以一套接口不同策略。于是就用C++把它重写了一下,作为一个独立的组件或是库,可以应用到其它需要分配内存的地方。为了能够更方便的优化,还增加了更多的统计信息,比如一共分配了多少次,其中有多少是独立Block分配的,有多少是Chunk分配的等等,这样对内存的使用就有一个比较清楚的了解。重写之后的类图如下:

pg4

其实一看就是一个策略模式,函数都是虚函数,用子类的实现覆盖。同时在初始化中保留了全局变量TopMemoryContex作为根节点,毕竟其它内存上下文的本身占用的空间都要从这里分配。没有实现类似palloc,pfree这样的库函数,而是在一个对象中分配,显得直观。使用方式如下:

MemoryContextData::memoryContextInit();

MemoryContextData* myContext = 
AllocSetContext::allocSetContextCreate(TopMemoryContext, "myContext", 1000, 4000, 8000);

MemoryContextData* errorContext = 
AllocSetContext::allocSetContextCreate(TopMemoryContext, "errorContext", 1024, 2048, 8092);

MemoryContextData* normalErrorContext =
AllocSetContext::allocSetContextCreate(errorContext, "normalErrorContext", 1024, 2048, 4096);

//分配空间
void* memory = myContext->jalloc(1024);
void* error = errorContext->jalloc(2098);
void* normalerror = normalErrorContext->jalloc(1025);

//释放空间
errorContext->jfree(error);
errorContext->jstats(0);
//输出统计信息
TopMemoryContext->memoryContextStats();

输出统计信息会从根节点开始,输出每一个子节点的统计状态信息:

pg6

如果需要更加详细的统计信息就需要打开AllocSetContext.h的宏定义:

/** 是否需要在统计函数中输出分析记录的数据 **/
#define ALLOCSETCONTEXT_ANALY

打开之后输出errorContext的统计信息:

pg5

从统计信息中就可以发现,一共经历了多少次内存分配,多少次回收,这些分配和回收都是哪种类型的,目前的参数是多少,内存上下文中使用了多少空间,还有多少空间。有了这些数据,就可以按需调整参数,达到优化的目的。重写之后的源码已经上传github,点这里。欢迎使用,修改,添加~

15/11/8 补充:

之前的统计信息还是不够直观,更改之后如下:

pg7

增加了更多更细致的统计,表头不同大小表示FreeList中Chunk的大小,最大的值即为allocChunkLimit的值,下面的统计数据表示在相应大小Chunk上的操作。包括:分配内存的次数,浪费的空间,每次分配平均浪费空间,释放内存次数,命中率。其中命中率表示分配次数在Block中以Chunk进行分配,而不是分配一个独立的Block。接下来一行是内存上下文当前的状态数据。上下两个表格中模拟了10000次的相同的内存分配请求。下面表格命中率较低,耗时9s多,上面命中率较高,耗时4s多。但上面平均每次分配会浪费345B,下面平均每次只会浪费5B。有了这些数据,就能够很好的在空间和时间上做一个折中选择。