余俊良，楊正益

重慶大學(xué)軟件學(xué)院，重慶 401331

基于虛擬單元可智能增長的內(nèi)存池研究

余俊良，楊正益

重慶大學(xué)軟件學(xué)院，重慶 401331

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

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

1 引言

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

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

2 傳統(tǒng)內(nèi)存池技術(shù)及其存在的缺陷

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

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

圖1 傳統(tǒng)內(nèi)存池結(jié)構(gòu)

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

3 基于虛擬單元可智能增長的內(nèi)存池技術(shù)

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

3.1 設(shè)計核心和層級結(jié)構(gòu)

圖2 SVMP整體結(jié)構(gòu)

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

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

圖3 SVMP的內(nèi)存塊結(jié)構(gòu)

3.2 內(nèi)存分配/回收策略

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

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

當(dāng)釋放內(nèi)存時，首先仍需索引list_collection中維護(hù)待回收虛擬單元的鏈表，再將指向該單元的指針壓入free_stack，回收完畢。

3.3 智能增長算法

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

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

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

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

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

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

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

同時還將移出其他進(jìn)程，回收內(nèi)存空間。

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

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

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

4 性能分析及測試

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

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

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

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

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

表1 三種不同內(nèi)存管理方式的運行時間對比

5 結(jié)語

表2 三種不同內(nèi)存管理方式消耗內(nèi)存空間對比

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

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

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

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

[4]馮宏華.C++應(yīng)用程序性能優(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].武漢：華中科技大學(xué)出版社，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.

國家自然科學(xué)基金（No.51105396）；國家創(chuàng)新實驗計劃（No.1110611066）。

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

2012-08-26

2012-10-26

1002-8331（2014）16-0127-04

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