基于虚拟单元可智能增长的内存池研究

余俊良，杨正益

重庆大学软件学院，重庆 401331

基于虚拟单元可智能增长的内存池研究

余俊良，杨正益

重庆大学软件学院，重庆 401331

针对内存数据库系统对空间利用率和系统健壮性的要求，提出了一种新型的基于虚拟单元可智能增长的内存池（SVMP）。该内存池吸收了传统内存池的优点，改进了内存管理策略，提出了对连续内存区进行逻辑划分以提高空间利用率的虚拟单元和一种以AIMD（Additive Increase Multiplicative Decrease）为核心的智能增长算法，并通过C++的new-handler机制解决了内存池增长中可能会出现的内存不足的问题。理论分析和性能测试表明，该内存池结构具有良好的时间、空间特性和健壮性，能够显著提升内存数据库系统的运行效率。

内存数据库；内存池；虚拟单元；AIMD算法

1 引言

随着科学技术的发展，新的应用需求和客观应用条件的成熟使得内存数据库（MMDB）应运而生。内存数据库将数据库的工作版本放在内存中，大部分操作都在内存中进行，从而磁盘I/O不再是内存数据库的瓶颈，如何提高数据库的效率和存储空间的利用率成为内存数据库的设计目标。

在内存数据库中，大量的数据存取和事务处理使得内存频繁地进行分配和回收。而数据库中最常见的对象——数据集又是以不定长的形式存在，小到十几字节，大到几十几百字节。大量小型数据集空间的申请/释放极易产生内存碎片，从而导致存储空间的浪费并使得系统在内存分配时将大部分的时间消耗在寻找适宜内存块上[1]。因此，在内存数据库系统中，选择正确的内存空间动态管理策略以减少碎片数量，提高空间利用率，是系统性能提升的关键。目前内存数据库主要采用的内存管理方案有位图分配法和内存池两种[2]。

2 传统内存池技术及其存在的缺陷

内存池（M emory Pool）[3]是用来解决内存频繁分配和释放问题的首选方法。通常人们习惯直接使用new、malloc等API申请分配内存，这样做的缺点在于：由于所申请内存块的大小不定，当频繁使用时会造成大量的内存碎片进而降低性能。而内存池则是在真正使用内存之前，先申请分配一定数量的、大小相等的内存块留作备用。当有新的内存需求时，就从内存池中取出一部分内存块，若内存块不够再继续申请新的内存。这样做的一个显著优点是尽量避免内存碎片，使得内存分配效率得到提升。

传统的内存池[4]主要由三层结构组成（如图1），第一层为内存池初始化时通过new方法申请的大块内存（M emory Chunk）；第二层是用于满足不同大小的内存分配请求的链表；第三层则是一定数量的不同大小的内存节点（node）。内存池采用双向链表的方式组织内存块和内存节点，块与块之间，节点与节点之间都通过指针相连，未分配的节点由空闲链表维护。当需要申请内存时，从对应大小的空闲链表中取出一个节点返回给申请者；当节点使用完毕需要释放时，回收的节点将被挂载到对应空闲列表的表头或尾部，等待下次分配。

图1 传统内存池结构

由于传统内存池结构简单，在分配/回收内存时只需简单地移动指针，通常情况下时间复杂度为O(1)，仅在内存块耗尽，需要调用new函数向堆申请新的内存块时才会产生额外开销。然而，尽管在时间性能上表现优异，传统内存池在空间利用上却存在一定缺陷。由内存节点的成员变量组成的头部将会占用一定大小节点空间，对于较小的节点，头部的大小甚至超过了数据区的大小，造成了空间的浪费。举一个例子，当有1 000万个8字节数据区大小的节点被分配时，用于存储数据的空间为8×107=80 MB，而用于存储节点的双向指针的空间同样为8×107=80 MB，加上其他变量所占空间，实际空间利用率不足50%。当内存数据库应用于内存容量较小的移动终端设备时，这样低的空间利用率是不能接受的。此外，传统内存池缺少合理的内存块增长控制策略和异常恢复机制，当出现内存不足，无法满足分配请求的情况时，系统将陷入瘫痪。可见，传统内存池尽管拥有不错的时间性能，但在空间利用率和健壮性方面，远远不能满足内存数据库系统的需要。

3 基于虚拟单元可智能增长的内存池技术

本文提出了一种新型的基于虚拟单元智能增长的内存池SVMP（Smart-grow th&Virtual-unit-based M emory Pool），在继承了传统内存池的优点之余，改进了内存分配/回收机制，为提高空间利用率提出了虚拟单元（Virtualunit）的概念，并设计了智能增长算法（Smart-grow th A lgorithm）用于解决内存池的增长问题。

3.1 设计核心和层级结构

图2 SVMP整体结构

SVMP技术的核心是虚拟单元和智能增长算法。虚拟单元并不是实际对象，而是一种抽象存在，通过游标移动，将前后两次移动的间隔长度大小的内存区称为一个单元，是一种完全逻辑意义上的划分。由于虚拟单元没有头部信息，尽可能多的内存空间将被用作数据区，从而极大提高了内存的空间利用率。智能增长算法以TCP模型中拥塞控制的AIMD思想为核心，对内存池的增长进行了合理控制，减少了直接调用new函数的次数，并通过C++的new-handler机制处理多次申请后产生的内存不足的问题。

SVMP在层级结构上继承了传统内存池的池-表-块三层设计，但又有所区别（图2）。针对数据集不定长的特点，第一层的池结构sv_mem_pool初始化了128个unit_size分别为8～1 024字节大小的的链表，以指针数组list_collection[NUM_OF_LIST]索引，能够在较小粒度上提供内存。第二层的链表sv_mem_list以单向指针连接第三层的内存块，其中head_chunk指针指向该链表的第一个内存块，current_chunk指针则指向当前正在用于分配的内存块，此外还拥有一个缓冲栈free_stack，负责对应大小的虚拟单元的回收。第三层的sv_mem_chunk（图3）在设计上放弃了传统内存池的node结构和空闲链表，而是直接向堆申请一块连续内存空间作为数据区，然后根据链表中指定的unit_size将内存空间划分为n个虚拟单元，游标cursor_pos指向的虚拟单元即为下一次将被分配的单元。

图3 SVMP的内存块结构

3.2 内存分配/回收策略

SVMP在传统内存池的基础上改进了内存的分配回收策略，使得其能够更好地应用于内存数据库系统。

SVMP支持8～1 024字节的分配请求，如果申请的空间大小超过上限MAX_BYTES=1 024字节，则将这种大块空间的分配返回给操作系统处理。当提出内存申请请求时，由于不同的链表维护的虚拟单元的上调边界ALIGN=8字节，如果分配的空间达不到8字节，将按照8字节分配，如果需要的空间超过8字节，则将分配的空间上调为8字节的倍数，即用ALIGN整除申请的空间大小，以此索引list_collection中维护对应虚拟单元的链表。在索引到正确的链表后，首先查看缓冲栈free_stack中是否为空，如果free_stack中存在指向已回收的虚拟单元的指针，则将指针弹出栈并返回，该虚拟单元再次被利用，分配结束；如果free_stack为空，将申请提交当前内存块current_chunk，检查current_chunk是否存在虚拟单元可供分配，如果存在，则将cursor_pos指向的虚拟单元地址返回给用户，并将cursor_pos移动到指向下一个虚拟单元，分配结束；否则链表将构造新的内存块，调用全局new函数向堆申请新的内存空间，current_chunk指针将指向新构造的块，并返回新申请块的第一个虚拟单元，分配结束。

当释放内存时，首先仍需索引list_collection中维护待回收虚拟单元的链表，再将指向该单元的指针压入free_stack，回收完毕。

3.3 智能增长算法

在增长算法的设计上，SVMP吸收了TCP/IP模型中解决拥塞控制的AIMD（Additive Increase M ultiplicative Decrease）算法的思想，即：加性增，乘性减，或者叫做“和式增加，积式减少”[5]。AIMD算法是TCP/IP模型中，运输层为解决拥塞控制的一种方法，当TCP发送方感受到端到端路径无拥塞时就线性地增加其发送窗口长度，当察觉到路径拥塞时就乘性减小其发送窗口长度。

SVMP在初始化时所有链表向堆申请一定大小的内存块，随着系统运行时间增长，处理的数据增多，将会出现没有虚拟单元可供分配的情况，必须再次向堆申请内存空间。在SGI STL的allocator设计中，当没有空闲节点可用时，默认每次返回新的定长的20块内存节点[6]，这种每次新增同样大小内存块的方式虽然简单，但无法较好地适应持续增长的数据区请求，SVMP中为了减少直接调用new函数的次数，当需要再次申请内存块时，SVMP将在之前内存块大小的基础上进行扩容。用M表示新申请的块容量，M′表示前一次申请的块容量，V表示初始化时申请的内存块容量，则：

M=M′+V=nV（n表示申请内存块的次数）

同时M的大小不能无限量增加，当到达既定的最大上限MAX_SIZE（1 000个页大小4 MB）时，以后新申请的内存块容量跟之前的块将保持一致。

算法实现如下：

这样逐步线性增加新申请的内存块大小，将更好地适应不断增长的数据量需求，降低未来的向系统申请内存操作的次数，同时节约内存空间，避免了传统内存池中可能出现的大块内存闲置的现象，并且可以根据实际需求调整线性增长的初始值和增长速率以达到最佳的空间性能（内存数据库系统在工作高峰期时对于内存块的增速可能将超过线性增长提供的增速，SVMP为应对此情况预留了按指数增长的接口，当线性增长不能满足需求时，将按指数增长）。

然而当数据量足够大时，SVMP将不断向堆申请空间，内存的分配速度远大于回收速度，最终可能导致在某个时段出现操作系统无法满足新的分配请求，系统将不能继续正常工作。在C++语言中，当出现无法满足内存分配请求的情况时，将会抛出std：：bad_alloc类型的异常[7]。而在抛出异常之前，操作系统将调用预先指定的一个出错处理函数，该函数通常被称为new-handler。为了装载用户自定义的new-handler，必须调用set-newhandler函数，将new-handler函数作为参数传递[8]。在SVMP中，指定的new-handler函数将修改申请的空间字节数，用M′表示无法满足分配请求时申请的空间大小，M表示修改后的大小，V表示初始化时申请的内存块容量，则：

同时还将移出其他进程，回收内存空间。

算法实现如下：

//内存不足情况处理函数，即自定义的new-handler函数

在分配请求无法被满足前，new-handler函数将被循环调用直到申请需求被满足。这样乘性的减少申请空间的大小，将使得系统能够很快地恢复工作。

4 性能分析及测试

SVMP技术是一个高效的内存管理解决方案，其性能优势在各个方面都得到了体现。

（1）时间性能较直接使用new向堆申请内存有显著提高。SVMP通过分配预先申请的内存块中的虚拟单元，避免了扫描内存区来查找匹配内存块，同时减少了碎片，使得整个分配/回收操作都能在常数时间O(1)完成。（2）空间性能较直接使用new/delete和传统内存池有一定幅度提升。因为虚拟单元只是逻辑上对内存空间的划分，不存在物理结构，极大地节省了内存空间，智能增长算法的“和式增加”方式，既满足了不断增长的数据量对于更多内存空间的需求同时也避免了大块内存的闲置。（3）解决了内存不足的问题，增强了系统健壮性。通过调用set_new_handler函数指定new-handler，在bad_alloc类型异常抛出之前回收内存空间并乘性减少申请的空间大小，使得SVMP能够很快从内存不足的状态下恢复。

性能测试中模拟了300万个数据集的内存空间的申请和释放，大小从8字节到1 024字节不等。测试方案为：将300万数据集分成3个批次，每次随机选择大小不同的共100万数据集，为其分配内存空间，分配完毕后再进行释放，重复3次，记录整个过程耗时并比较。测试平台为：Inter Core2 Duo T6600 CPU，4 GB DDR2内存，W indow s 7 32操作系统。

表1是分别使用传统内存池和SVMP以及直接调用new/delete这三种不同的内存管理方式得到的性能测试结果。可以明显看出：在使用了内存池技术之后，由于减少了直接向内存申请空间的次数和碎片的数量，时间性能产生了飞跃，所耗时较直接调用new/delete对内存进行管理减小了一个数量级；而SVMP较之传统内存池，在内存块大小增长上更加智能，进一步减少了直接向内存申请空间的次数，将时间再次缩短了25%左右。

表2是分别使用传统内存池和SVMP以及直接调用new/delete这三种不同的内存管理方式消耗的内存空间大小数据。存储相同大小的数据量，传统内存池消耗了1.2 GB内存空间，SVMP消耗了722 MB内存空间，直接调用new/delete消耗了748 MB内存空间。SVMP的虚拟单元结构和智能增长算法使得内存空间利用率较传统内存池提升了一个层次，与直接直接调用new/delete消耗的内存空间基本相当。

表1 三种不同内存管理方式的运行时间对比

5 结语

表2 三种不同内存管理方式消耗内存空间对比

SVMP吸收了传统内存池的优点，改进了内存分配/回收策略，利用虚拟单元提高了空间利用率，同时依然具备良好的时间性能。此外，SVMP具备智能增长特性，并为内存不足的情况设定了恢复机制，具有较强的健壮性，十分适用于内存数据库系统。

[1]Bryant R E，O’Hallaron D R.深入理解计算机系统[M].龚奕利，雷迎春，译.北京：机械工业出版社，2010.

[2]钟宝荣，袁文亮.内存数据库中存储结构的实现机制[J].计算机工程与设计，2007，28（5）.

[3]Bulka D，Mayhew D.提高C++性能的编程技术[M].左飞，译.北京：电子工业出版社，2011.

[4]冯宏华.C++应用程序性能优化[M].北京：电子工业出版社，2007：185-190.

[5]Guillem in D，Robert P，Zwart B.AIMD algorithms and exponential functionals[J].Ann Appl Probab，2004，14 （1）：90-117.

[6]Ronell M.A C++pooled，shared memory allocator for simulator development[C]//37th Annual on Simulation Symposium，2004：187-195.

[7]Meyers S.Effective C++[M].3版.侯捷，译.北京：电子工业出版社，2011.

[8]侯捷.STL源码剖析[M].武汉：华中科技大学出版社，2002.

YU Junliang,YANG Zhengyi

School of Software,Chongqing University,Chongqing 401331,China

Main-memory database system requires good space utilization and system robustness.Based on the advantages of the traditional memory pool,a new memory pool structure named Smart-grow th&Virtual-unit-based（SVMP）is presented.SVMP improves the original memory management strategy according to a new concept of virtual-unit,which increases the space utilization rate via logic partitioning in the contiguous memory area,and a smart-grow th algorithm with AIMD as its core.It can solve the problem of insufficient memory which might turn up in the process of memory pool grow th through the new-handler mechanism of C++.Theoretical analysis and performance testing show that it can significantly improve operation efficiency of main memory database system.

MeMory DataBase（MMDB）;memory pool;virtual-unit;Additive Increase Multiplicative Descrease（AIMD）

A

TP311

10.3778/j.issn.1002-8331.1208-0326

YU Jun liang,YANG Zhengyi.Smart-grow th and virtual-unit-based memory pool.Computer Engineering and Applications,2014,50（16）：127-130.

国家自然科学基金（No.51105396）；国家创新实验计划（No.1110611066）。

余俊良（1990—），男，本科生，主要研究方向：计算机系统结构，数据库技术；杨正益（1979—），男，博士研究生，讲师，主要研究方向：程序性能设计，高性能数据库。

2012-08-26

2012-10-26

1002-8331（2014）16-0127-04

CNKI网络优先出版：2012-11-21,http://www.cnki.net/kcm s/detail/11.2127.TP.20121121.1102.033.htm l