建站合肥网络公司seo,iis7建网站,浙江省建设执业注册中心网站,金蝶二次开发1、引言#xff1a; 随着科学技术的发展#xff0c;新的应用需求和客观应用条件的成熟使得内存数据库#xff08;MMDB#xff09;应运而生。内存数据库将数据库的工作版本放在内存中#xff0c;大部分操作都在内存中进行#xff0c;从而磁盘 I/O 不再是内存数据库的瓶颈 随着科学技术的发展新的应用需求和客观应用条件的成熟使得内存数据库MMDB应运而生。内存数据库将数据库的工作版本放在内存中大部分操作都在内存中进行从而磁盘 I/O 不再是内存数据库的瓶颈如何提高数据库的效率和存储空间的利用率成为了内存数据库的设计目标。 在内存数据库中大量的数据存取和事务处理使得内存频繁的进行分配和回收。而数据库中最常见的对象——数据集又是以不定长的形式存在小到十几字节大到几十几百字节。大量小型数据集空间的申请/释放极易产生内存碎片从而导致存储空间的浪费并使得系统在内存分配时将大部分的时间消耗在寻找适宜内存块上。因此在内存数据库系统中选择正确的内存空间动态管理策略以减少碎片数量提高空间利用率是系统性能提升的关键。目前内存数据库主要采用的的内存管理方案有位图分配法和内存池两种。
2、传统内存池技术及其存在的缺陷 内存池Memory Pool是用来解决内存频繁分配和释放问题的首选方法。通常我们习惯直接使用new、malloc等API申请分配内存这样做的缺点在于由于所申请内存块的大小不定当频繁使用时会造成大量的内存碎片进而降低性能。而内存池则是在真正使用内存之前先申请分配一定数量的、大小相等的内存块留作备用。当有新的内存需求时就从内存池中取出一部分内存块若内存块不够再继续申请新的内存。这样做的一个显著优点是尽量避免了内存碎片使得内存分配效率得到提升。 传统的内存池主要由三层结构组成如图1第一层为内存池初始化时通过new方法申请的大块内存Memory Chunk第二层是用于满足不同大小的内存分配请求的链表第三层则是一定数量的不同大小的内存节点(node)。内存池采用双向链表的方式组织内存块和内存节点块与块之间节点与节点之间都通过指针相连未分配的节点由空闲链表维护。当需要申请内存时从对应大小的空闲链表中取出一个节点返回给申请者当节点使用完毕需要释放时回收的节点将被挂载到对应空闲列表的表头或尾部等待下次分配。 由于传统内存池结构简单在分配/回收内存时只需简单的移动指针通常情况下时间复杂度为O(1)仅在内存块耗尽需要调用new函数向堆申请新的内存块时才会产生额外开销。然而尽管在时间性能上表现优异传统内存池在空间利用上却存在一定缺陷。由内存节点的成员变量组成的头部将会占用一定大小节点空间对于较小的节点头部的大小几乎和数据区大小相当造成了节点空间的浪费。举一个例子当有1000万个8字节数据区大小的节点被分配时用于存储数据的空间为8B×10^780MB而用于存储节点的双向指针的空间同样为8B×10^780MB加上其他变量所占空间实际空间利用率不足50%。当内存数据库应用于内存容量较小的移动终端设备时这样低的空间利用率是不能接受的。此外传统内存池缺少合理的内存块增长控制策略和异常恢复机制当出现内存不足无法满足分配请求的情况时系统将陷入瘫痪。可见传统内存池尽管拥有不错的时间性能但在空间利用率和健壮性方面远远不能满足内存数据库系统的需要。
3、基于虚拟单元可智能增长的内存池技术 本文提出了一种新型的基于虚拟单元智能增长的内存池SVMPSmart-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指向的虚拟单元即为下一次将被分配的单元。 3.2 内存分配/回收策略 SVMP在传统内存池的基础上改进了内存的分配回收策略使得其能够更好的应用于内存数据库系统。 SVMP支持8~1024字节的分配请求如果申请的空间大小超过上限MAX_BYTES1024字节则将这种大块空间的分配返回给操作系统处理。当提出内存申请请求时由于不同的链表维护的虚拟单元的上调边界ALIGN8字节如果分配的空间达不到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模型中解决拥塞控制的AIMDAdditive Increase Multipli- cative Decrease算法的启发。AIMD算法是TCP/IP模型中运输层为解决拥塞控制的一种方法即加性增乘性减或者叫做“和式增加积式减少”。当TCP发送方感受到端到端路径无拥塞时就线性的增加其发送窗口长度当察觉到路径拥塞时就乘性减小其发送窗口长度。 SVMP在初始化时所有链表向堆申请一定大小的内存块随着系统运行时间增长处理的数据增多将会出现没有虚拟单元可供分配的情况必须再次向堆申请内存空间。在SGI STL的allocator设计中,当没有空闲节点可用时默认每次返回新的定长的20块内存节点这种每次新增同样大小内存块的方式虽然简单但无法较好的适应持续增长的数据区请求SVMP中为了减少直接调用new函数的次数当需要再次申请内存块时SVMP将在之前内存块大小的基础上进行扩容。用M表示新申请的块容量M表示前一次申请的块容量V表示初始化时申请的内存块容量则
MMVnV(n表示申请内存块的次数)。
M的大小也不可能无限量增加,当到达既定的最大上限MAX_SIZE1000个页大小4MB时以后新申请的内存块容量跟之前的块将保持一致。
算法实现如下 #define MAX_SIZE 4*1024*1024 //最大块容量
#define INITIAL_SIZE 1024//初始块容量
void Sg_Mem_List::__expandStorage() //扩展存储空间
{expand_count; //申请次数1//不超过最大块容量时if(INITIAL_SIZE * expand_count MAX_SIZE) { current_chunk-nextnew sg_Mem_Chunk (unit_size, INITIAL_SIZE * expand_count); /*新申请内存块,由于申请次数增加新块容量因此线性增加*/ }else { //超过最大块容量后current_chunk-nextnew sg_Mem_Chunk (unit_size,MAX_SIZE); //始终申请最大块}
} 这样逐步线性增加新申请的内存块大小将更好的适应不断增长的数据量需求降低未来的向系统申请内存操作的次数同时节约内存空间避免了传统内存池中可能出现的大块内存闲置的现象并且可以根据实际需求调整线性增长的初始值和增长速率以达到最佳的空间性能。 然而当数据量足够大时SVMP将不断向堆申请空间内存的分配速度远大于回收速度最终可能导致某个时间出现操作系统无法满足新的分配请求系统将不能继续正常工作。在C语言中当出现无法满足内存分配请求的情况时将会抛出std::bad_alloc类型的异常。而在抛出异常之前操作系统将调用预先指定的一个出错处理函数该函数通常被称为new-handler。为了装载用户自定义的new-handler必须调用set-new -handler函数,将new-handler函数作为参数传递。在SVMP中指定的new-handler函数将修改申请的空间字节数用M表示无法满足分配请求时申请的空间大小M表示修改后的大小V表示初始化时申请的内存块容量则
MM/2nV/2(n表示申请内存块的次数),
同时还将移出其他进程回收内存空间。
算法实现如下 //内存不足情况处理函数即自定义的new-handler函数
void __handle_Mem_Alloc_Error() { if(reqSize unit_size)sleep(1000);
/*当一个虚拟单元的空间都无法被申请时,分配线程休眠1 秒等待空间被回收*/reqSize reqSize / 2; //乘性减少申请字节数
}
//构造新的内存块
Sg_Mem_Chunk::Sg_Mem_Chunk(size_t size,size_t reqSize):unit_size(size),cursor_pos(0) {new_handler global_handler std::set_new_handler(__handle_Mem_Alloc_Error);//设置自定义的new-handler,返回全局的new-handlermem new char[reqSize]; //申请的数据区大小//此处请求无法满足时将调用new-handler函数std::set_new_handler(global_handler);//重新设置全局的new-handlerchunk_bytes reqSize;
} 在分配请求无法被满足前new-handler函数将被循环调用直到申请需求被满足。这样乘性的减少申请空间的大小将使得系统能够很快的恢复工作。
4、性能分析及测试 SVMP技术是一个高效的内存管理解决方案其性能优势在各个方面都得到了体现。 (1)时间性能较直接使用new向堆申请内存有显著提高。SVMP通过分配预先申请的内存块中的虚拟单元避免了扫描内存区来查找匹配内存块同时减少了碎片使得整个分配/回收操作都能在常数时间O(1)完成。(2)空间性能较直接使用new/delete和传统内存池有一定幅度提升。因为虚拟单元只是逻辑上对内存空间的划分不存在物理结构极大的节省了内存空间智能增长算法的“和式增加”方式既满足了不断增长的数据量对于更多内存空间的需求同时也避免了大块内存的闲置。(3)解决了内存不足的问题增强了系统健壮性。通过调用set_new_handler函数指定new-handler,在bad_alloc类型异常抛出之前回收内存空间并乘性减少申请的空间大小使得SVMP能够很快从内存不足的状态下恢复。 性能测试中模拟了300万个数据集的内存空间的申请和释放大小从8字节到1024字节不等。测试平台为Inter Core2 Duo T6600 CPU,4GB DDR2内存Windows 7 32操作系统。 表1是分别使用传统内存池和SVMP以及直接调用new/delete这三种不同的内存管理方式得到的时间性能比较结果。可以明显看出在使用了内存池技术之后时间性能产生了飞跃所耗时较直接调用new/delete对内存进行管理减小了一个数量级而SVMP在传统内存池的基础之上有了更进一步的提升将时间再次缩短了50% 内存管理方式 消耗时间/s 传统内存池 0.067 SVMP 0.034 new/delete 0.593
表1三种不同内存管理方式的运行时间对比 表2是分别使用传统内存池和SVMP以及直接调用new/delete这三种不同的内存管理方式消耗的内存空间大小数据。存储相同大小的数据量传统内存池消耗了1.2GB内存空间SVMP消耗了722MB内存空间直接调用new/delete消耗了748MB内存空间。SVMP的虚拟单元结构和智能增长算法使得内存空间利用率较传统内存池提升了一个层次与直接直接调用new/delete消耗的内存空间基本相当。 内存管理方式 消耗内存/MB 传统内存池 1273 SVMP 722 new/delete 748
表2三种不同内存管理方式消耗内存空间对比
5、结语 SVMP吸收了传统内存池的优点改进了内存分配/回收策略利用虚拟单元提高了空间利用率同时依然具备良好的时间性能。此外SVMP具备智能增长特性并为内存不足的情况设定了恢复机制具有较强的健壮性十分适用于内存数据库系统。
