1、引言：

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

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

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

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

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

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

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

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

3.1 设计核心和层级结构    

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

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