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

余俊良，楊正益

重慶大學軟件學院，重慶 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