余俊良，楊正益

重慶大學軟件學院，重慶 401331

基于虛擬單元可智能增長的內存池研究

余俊良，楊正益

重慶大學軟件學院，重慶 401331

針對內存數(shù)據(jù)庫系統(tǒng)對空間利用率和系統(tǒng)健壯性的要求，提出了一種新型的基于虛擬單元可智能增長的內存池（SVMP）。該內存池吸收了傳統(tǒng)內存池的優(yōu)點，改進了內存管理策略，提出了對連續(xù)內存區(qū)進行邏輯劃分以提高空間利用率的虛擬單元和一種以AIMD（Additive Increase Multiplicative Decrease）為核心的智能增長算法，并通過C++的new-handler機制解決了內存池增長中可能會出現(xiàn)的內存不足的問題。理論分析和性能測試表明，該內存池結構具有良好的時間、空間特性和健壯性，能夠顯著提升內存數(shù)據(jù)庫系統(tǒng)的運行效率。

內存數(shù)據(jù)庫；內存池；虛擬單元；AIMD算法

1 引言

隨著科學技術的發(fā)展，新的應用需求和客觀應用條件的成熟使得內存數(shù)據(jù)庫（MMDB）應運而生。內存數(shù)據(jù)庫將數(shù)據(jù)庫的工作版本放在內存中，大部分操作都在內存中進行，從而磁盤I/O不再是內存數(shù)據(jù)庫的瓶頸，如何提高數(shù)據(jù)庫的效率和存儲空間的利用率成為內存數(shù)據(jù)庫的設計目標。

在內存數(shù)據(jù)庫中，大量的數(shù)據(jù)存取和事務處理使得內存頻繁地進行分配和回收。而數(shù)據(jù)庫中最常見的對象——數(shù)據(jù)集又是以不定長的形式存在，小到十幾字節(jié)，大到幾十幾百字節(jié)。大量小型數(shù)據(jù)集空間的申請/釋放極易產生內存碎片，從而導致存儲空間的浪費并使得系統(tǒng)在內存分配時將大部分的時間消耗在尋找適宜內存塊上[1]。因此，在內存數(shù)據(jù)庫系統(tǒng)中，選擇正確的內存空間動態(tài)管理策略以減少碎片數(shù)量，提高空間利用率，是系統(tǒng)性能提升的關鍵。目前內存數(shù)據(jù)庫主要采用的內存管理方案有位圖分配法和內存池兩種[2]。

2 傳統(tǒng)內存池技術及其存在的缺陷

內存池（M emory Pool）[3]是用來解決內存頻繁分配和釋放問題的首選方法。通常人們習慣直接使用new、malloc等API申請分配內存，這樣做的缺點在于：由于所申請內存塊的大小不定，當頻繁使用時會造成大量的內存碎片進而降低性能。而內存池則是在真正使用內存之前，先申請分配一定數(shù)量的、大小相等的內存塊留作備用。當有新的內存需求時，就從內存池中取出一部分內存塊，若內存塊不夠再繼續(xù)申請新的內存。這樣做的一個顯著優(yōu)點是盡量避免內存碎片，使得內存分配效率得到提升。

傳統(tǒng)的內存池[4]主要由三層結構組成（如圖1），第一層為內存池初始化時通過new方法申請的大塊內存（M emory Chunk）；第二層是用于滿足不同大小的內存分配請求的鏈表；第三層則是一定數(shù)量的不同大小的內存節(jié)點（node）。內存池采用雙向鏈表的方式組織內存塊和內存節(jié)點，塊與塊之間，節(jié)點與節(jié)點之間都通過指針相連，未分配的節(jié)點由空閑鏈表維護。當需要申請內存時，從對應大小的空閑鏈表中取出一個節(jié)點返回給申請者；當節(jié)點使用完畢需要釋放時，回收的節(jié)點將被掛載到對應空閑列表的表頭或尾部，等待下次分配。

圖1 傳統(tǒng)內存池結構

由于傳統(tǒng)內存池結構簡單，在分配/回收內存時只需簡單地移動指針，通常情況下時間復雜度為O(1)，僅在內存塊耗盡，需要調用new函數(shù)向堆申請新的內存塊時才會產生額外開銷。然而，盡管在時間性能上表現(xiàn)優(yōu)異，傳統(tǒng)內存池在空間利用上卻存在一定缺陷。由內存節(jié)點的成員變量組成的頭部將會占用一定大小節(jié)點空間，對于較小的節(jié)點，頭部的大小甚至超過了數(shù)據(jù)區(qū)的大小，造成了空間的浪費。舉一個例子，當有1 000萬個8字節(jié)數(shù)據(jù)區(qū)大小的節(jié)點被分配時，用于存儲數(shù)據(jù)的空間為8×107=80 MB，而用于存儲節(jié)點的雙向指針的空間同樣為8×107=80 MB，加上其他變量所占空間，實際空間利用率不足50%。當內存數(shù)據(jù)庫應用于內存容量較小的移動終端設備時，這樣低的空間利用率是不能接受的。此外，傳統(tǒng)內存池缺少合理的內存塊增長控制策略和異?；謴蜋C制，當出現(xiàn)內存不足，無法滿足分配請求的情況時，系統(tǒng)將陷入癱瘓。可見，傳統(tǒng)內存池盡管擁有不錯的時間性能，但在空間利用率和健壯性方面，遠遠不能滿足內存數(shù)據(jù)庫系統(tǒng)的需要。

3 基于虛擬單元可智能增長的內存池技術

本文提出了一種新型的基于虛擬單元智能增長的內存池SVMP（Smart-grow th&Virtual-unit-based M emory Pool），在繼承了傳統(tǒng)內存池的優(yōu)點之余，改進了內存分配/回收機制，為提高空間利用率提出了虛擬單元（Virtualunit）的概念，并設計了智能增長算法（Smart-grow th A lgorithm）用于解決內存池的增長問題。

3.1 設計核心和層級結構

圖2 SVMP整體結構

SVMP技術的核心是虛擬單元和智能增長算法。虛擬單元并不是實際對象，而是一種抽象存在，通過游標移動，將前后兩次移動的間隔長度大小的內存區(qū)稱為一個單元，是一種完全邏輯意義上的劃分。由于虛擬單元沒有頭部信息，盡可能多的內存空間將被用作數(shù)據(jù)區(qū)，從而極大提高了內存的空間利用率。智能增長算法以TCP模型中擁塞控制的AIMD思想為核心，對內存池的增長進行了合理控制，減少了直接調用new函數(shù)的次數(shù)，并通過C++的new-handler機制處理多次申請后產生的內存不足的問題。

SVMP在層級結構上繼承了傳統(tǒng)內存池的池-表-塊三層設計，但又有所區(qū)別（圖2）。針對數(shù)據(jù)集不定長的特點，第一層的池結構sv_mem_pool初始化了128個unit_size分別為8～1 024字節(jié)大小的的鏈表，以指針數(shù)組list_collection[NUM_OF_LIST]索引，能夠在較小粒度上提供內存。第二層的鏈表sv_mem_list以單向指針連接第三層的內存塊，其中head_chunk指針指向該鏈表的第一個內存塊，current_chunk指針則指向當前正在用于分配的內存塊，此外還擁有一個緩沖棧free_stack，負責對應大小的虛擬單元的回收。第三層的sv_mem_chunk（圖3）在設計上放棄了傳統(tǒng)內存池的node結構和空閑鏈表，而是直接向堆申請一塊連續(xù)內存空間作為數(shù)據(jù)區(qū)，然后根據(jù)鏈表中指定的unit_size將內存空間劃分為n個虛擬單元，游標cursor_pos指向的虛擬單元即為下一次將被分配的單元。

圖3 SVMP的內存塊結構

3.2 內存分配/回收策略

SVMP在傳統(tǒng)內存池的基礎上改進了內存的分配回收策略，使得其能夠更好地應用于內存數(shù)據(jù)庫系統(tǒng)。

SVMP支持8～1 024字節(jié)的分配請求，如果申請的空間大小超過上限MAX_BYTES=1 024字節(jié)，則將這種大塊空間的分配返回給操作系統(tǒng)處理。當提出內存申請請求時，由于不同的鏈表維護的虛擬單元的上調邊界ALIGN=8字節(jié)，如果分配的空間達不到8字節(jié)，將按照8字節(jié)分配，如果需要的空間超過8字節(jié)，則將分配的空間上調為8字節(jié)的倍數(shù)，即用ALIGN整除申請的空間大小，以此索引list_collection中維護對應虛擬單元的鏈表。在索引到正確的鏈表后，首先查看緩沖棧free_stack中是否為空，如果free_stack中存在指向已回收的虛擬單元的指針，則將指針彈出棧并返回，該虛擬單元再次被利用，分配結束；如果free_stack為空，將申請?zhí)峤划斍皟却鎵Kcurrent_chunk，檢查current_chunk是否存在虛擬單元可供分配，如果存在，則將cursor_pos指向的虛擬單元地址返回給用戶，并將cursor_pos移動到指向下一個虛擬單元，分配結束；否則鏈表將構造新的內存塊，調用全局new函數(shù)向堆申請新的內存空間，current_chunk指針將指向新構造的塊，并返回新申請塊的第一個虛擬單元，分配結束。

當釋放內存時，首先仍需索引list_collection中維護待回收虛擬單元的鏈表，再將指向該單元的指針壓入free_stack，回收完畢。

3.3 智能增長算法

在增長算法的設計上，SVMP吸收了TCP/IP模型中解決擁塞控制的AIMD（Additive Increase M ultiplicative Decrease）算法的思想，即：加性增，乘性減，或者叫做“和式增加，積式減少”[5]。AIMD算法是TCP/IP模型中，運輸層為解決擁塞控制的一種方法，當TCP發(fā)送方感受到端到端路徑無擁塞時就線性地增加其發(fā)送窗口長度，當察覺到路徑擁塞時就乘性減小其發(fā)送窗口長度。

SVMP在初始化時所有鏈表向堆申請一定大小的內存塊，隨著系統(tǒng)運行時間增長，處理的數(shù)據(jù)增多，將會出現(xiàn)沒有虛擬單元可供分配的情況，必須再次向堆申請內存空間。在SGI STL的allocator設計中，當沒有空閑節(jié)點可用時，默認每次返回新的定長的20塊內存節(jié)點[6]，這種每次新增同樣大小內存塊的方式雖然簡單，但無法較好地適應持續(xù)增長的數(shù)據(jù)區(qū)請求，SVMP中為了減少直接調用new函數(shù)的次數(shù)，當需要再次申請內存塊時，SVMP將在之前內存塊大小的基礎上進行擴容。用M表示新申請的塊容量，M′表示前一次申請的塊容量，V表示初始化時申請的內存塊容量，則：

M=M′+V=nV（n表示申請內存塊的次數(shù)）

同時M的大小不能無限量增加，當?shù)竭_既定的最大上限MAX_SIZE（1 000個頁大小4 MB）時，以后新申請的內存塊容量跟之前的塊將保持一致。

算法實現(xiàn)如下：

這樣逐步線性增加新申請的內存塊大小，將更好地適應不斷增長的數(shù)據(jù)量需求，降低未來的向系統(tǒng)申請內存操作的次數(shù)，同時節(jié)約內存空間，避免了傳統(tǒng)內存池中可能出現(xiàn)的大塊內存閑置的現(xiàn)象，并且可以根據(jù)實際需求調整線性增長的初始值和增長速率以達到最佳的空間性能（內存數(shù)據(jù)庫系統(tǒng)在工作高峰期時對于內存塊的增速可能將超過線性增長提供的增速，SVMP為應對此情況預留了按指數(shù)增長的接口，當線性增長不能滿足需求時，將按指數(shù)增長）。

然而當數(shù)據(jù)量足夠大時，SVMP將不斷向堆申請空間，內存的分配速度遠大于回收速度，最終可能導致在某個時段出現(xiàn)操作系統(tǒng)無法滿足新的分配請求，系統(tǒng)將不能繼續(xù)正常工作。在C++語言中，當出現(xiàn)無法滿足內存分配請求的情況時，將會拋出std：：bad_alloc類型的異常[7]。而在拋出異常之前，操作系統(tǒng)將調用預先指定的一個出錯處理函數(shù)，該函數(shù)通常被稱為new-handler。為了裝載用戶自定義的new-handler，必須調用set-newhandler函數(shù)，將new-handler函數(shù)作為參數(shù)傳遞[8]。在SVMP中，指定的new-handler函數(shù)將修改申請的空間字節(jié)數(shù)，用M′表示無法滿足分配請求時申請的空間大小，M表示修改后的大小，V表示初始化時申請的內存塊容量，則：

同時還將移出其他進程，回收內存空間。

算法實現(xiàn)如下：

//內存不足情況處理函數(shù)，即自定義的new-handler函數(shù)

在分配請求無法被滿足前，new-handler函數(shù)將被循環(huán)調用直到申請需求被滿足。這樣乘性的減少申請空間的大小，將使得系統(tǒng)能夠很快地恢復工作。

4 性能分析及測試

SVMP技術是一個高效的內存管理解決方案，其性能優(yōu)勢在各個方面都得到了體現(xiàn)。

（1）時間性能較直接使用new向堆申請內存有顯著提高。SVMP通過分配預先申請的內存塊中的虛擬單元，避免了掃描內存區(qū)來查找匹配內存塊，同時減少了碎片，使得整個分配/回收操作都能在常數(shù)時間O(1)完成。（2）空間性能較直接使用new/delete和傳統(tǒng)內存池有一定幅度提升。因為虛擬單元只是邏輯上對內存空間的劃分，不存在物理結構，極大地節(jié)省了內存空間，智能增長算法的“和式增加”方式，既滿足了不斷增長的數(shù)據(jù)量對于更多內存空間的需求同時也避免了大塊內存的閑置。（3）解決了內存不足的問題，增強了系統(tǒng)健壯性。通過調用set_new_handler函數(shù)指定new-handler，在bad_alloc類型異常拋出之前回收內存空間并乘性減少申請的空間大小，使得SVMP能夠很快從內存不足的狀態(tài)下恢復。

性能測試中模擬了300萬個數(shù)據(jù)集的內存空間的申請和釋放，大小從8字節(jié)到1 024字節(jié)不等。測試方案為：將300萬數(shù)據(jù)集分成3個批次，每次隨機選擇大小不同的共100萬數(shù)據(jù)集，為其分配內存空間，分配完畢后再進行釋放，重復3次，記錄整個過程耗時并比較。測試平臺為：Inter Core2 Duo T6600 CPU，4 GB DDR2內存，W indow s 7 32操作系統(tǒng)。

表1是分別使用傳統(tǒng)內存池和SVMP以及直接調用new/delete這三種不同的內存管理方式得到的性能測試結果?？梢悦黠@看出：在使用了內存池技術之后，由于減少了直接向內存申請空間的次數(shù)和碎片的數(shù)量，時間性能產生了飛躍，所耗時較直接調用new/delete對內存進行管理減小了一個數(shù)量級；而SVMP較之傳統(tǒng)內存池，在內存塊大小增長上更加智能，進一步減少了直接向內存申請空間的次數(shù)，將時間再次縮短了25%左右。

表2是分別使用傳統(tǒng)內存池和SVMP以及直接調用new/delete這三種不同的內存管理方式消耗的內存空間大小數(shù)據(jù)。存儲相同大小的數(shù)據(jù)量，傳統(tǒng)內存池消耗了1.2 GB內存空間，SVMP消耗了722 MB內存空間，直接調用new/delete消耗了748 MB內存空間。SVMP的虛擬單元結構和智能增長算法使得內存空間利用率較傳統(tǒng)內存池提升了一個層次，與直接直接調用new/delete消耗的內存空間基本相當。

表1 三種不同內存管理方式的運行時間對比

5 結語

表2 三種不同內存管理方式消耗內存空間對比

SVMP吸收了傳統(tǒng)內存池的優(yōu)點，改進了內存分配/回收策略，利用虛擬單元提高了空間利用率，同時依然具備良好的時間性能。此外，SVMP具備智能增長特性，并為內存不足的情況設定了恢復機制，具有較強的健壯性，十分適用于內存數(shù)據(jù)庫系統(tǒng)。

[1]Bryant R E，O’Hallaron D R.深入理解計算機系統(tǒng)[M].龔奕利，雷迎春，譯.北京：機械工業(yè)出版社，2010.

[2]鐘寶榮，袁文亮.內存數(shù)據(jù)庫中存儲結構的實現(xiàn)機制[J].計算機工程與設計，2007，28（5）.

[3]Bulka D，Mayhew D.提高C++性能的編程技術[M].左飛，譯.北京：電子工業(yè)出版社，2011.

[4]馮宏華.C++應用程序性能優(yōu)化[M].北京：電子工業(yè)出版社，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版.侯捷，譯.北京：電子工業(yè)出版社，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）；國家創(chuàng)新實驗計劃（No.1110611066）。

余俊良（1990—），男，本科生，主要研究方向：計算機系統(tǒng)結構，數(shù)據(jù)庫技術；楊正益（1979—），男，博士研究生，講師，主要研究方向：程序性能設計，高性能數(shù)據(jù)庫。

2012-08-26

2012-10-26

1002-8331（2014）16-0127-04

CNKI網絡優(yōu)先出版：2012-11-21,http://www.cnki.net/kcm s/detail/11.2127.TP.20121121.1102.033.htm l