余俊良,楊正益
重慶大學(xué)軟件學(xué)院,重慶 401331
基于虛擬單元可智能增長的內(nèi)存池研究
余俊良,楊正益
重慶大學(xué)軟件學(xué)院,重慶 401331
針對(duì)內(nèi)存數(shù)據(jù)庫系統(tǒng)對(duì)空間利用率和系統(tǒng)健壯性的要求,提出了一種新型的基于虛擬單元可智能增長的內(nèi)存池(SVMP)。該內(nèi)存池吸收了傳統(tǒng)內(nèi)存池的優(yōu)點(diǎn),改進(jìn)了內(nèi)存管理策略,提出了對(duì)連續(xù)內(nèi)存區(qū)進(jìn)行邏輯劃分以提高空間利用率的虛擬單元和一種以AIMD(Additive Increase Multiplicative Decrease)為核心的智能增長算法,并通過C++的new-handler機(jī)制解決了內(nèi)存池增長中可能會(huì)出現(xiàn)的內(nèi)存不足的問題。理論分析和性能測試表明,該內(nèi)存池結(jié)構(gòu)具有良好的時(shí)間、空間特性和健壯性,能夠顯著提升內(nèi)存數(shù)據(jù)庫系統(tǒng)的運(yùn)行效率。
內(nèi)存數(shù)據(jù)庫;內(nèi)存池;虛擬單元;AIMD算法
隨著科學(xué)技術(shù)的發(fā)展,新的應(yīng)用需求和客觀應(yīng)用條件的成熟使得內(nèi)存數(shù)據(jù)庫(MMDB)應(yīng)運(yùn)而生。內(nèi)存數(shù)據(jù)庫將數(shù)據(jù)庫的工作版本放在內(nèi)存中,大部分操作都在內(nèi)存中進(jìn)行,從而磁盤I/O不再是內(nèi)存數(shù)據(jù)庫的瓶頸,如何提高數(shù)據(jù)庫的效率和存儲(chǔ)空間的利用率成為內(nèi)存數(shù)據(jù)庫的設(shè)計(jì)目標(biāo)。
在內(nèi)存數(shù)據(jù)庫中,大量的數(shù)據(jù)存取和事務(wù)處理使得內(nèi)存頻繁地進(jìn)行分配和回收。而數(shù)據(jù)庫中最常見的對(duì)象——數(shù)據(jù)集又是以不定長的形式存在,小到十幾字節(jié),大到幾十幾百字節(jié)。大量小型數(shù)據(jù)集空間的申請(qǐng)/釋放極易產(chǎn)生內(nèi)存碎片,從而導(dǎo)致存儲(chǔ)空間的浪費(fèi)并使得系統(tǒng)在內(nèi)存分配時(shí)將大部分的時(shí)間消耗在尋找適宜內(nèi)存塊上[1]。因此,在內(nèi)存數(shù)據(jù)庫系統(tǒng)中,選擇正確的內(nèi)存空間動(dòng)態(tài)管理策略以減少碎片數(shù)量,提高空間利用率,是系統(tǒng)性能提升的關(guān)鍵。目前內(nèi)存數(shù)據(jù)庫主要采用的內(nèi)存管理方案有位圖分配法和內(nèi)存池兩種[2]。
內(nèi)存池(M emory Pool)[3]是用來解決內(nèi)存頻繁分配和釋放問題的首選方法。通常人們習(xí)慣直接使用new、malloc等API申請(qǐng)分配內(nèi)存,這樣做的缺點(diǎn)在于:由于所申請(qǐng)內(nèi)存塊的大小不定,當(dāng)頻繁使用時(shí)會(huì)造成大量的內(nèi)存碎片進(jìn)而降低性能。而內(nèi)存池則是在真正使用內(nèi)存之前,先申請(qǐng)分配一定數(shù)量的、大小相等的內(nèi)存塊留作備用。當(dāng)有新的內(nèi)存需求時(shí),就從內(nèi)存池中取出一部分內(nèi)存塊,若內(nèi)存塊不夠再繼續(xù)申請(qǐng)新的內(nèi)存。這樣做的一個(gè)顯著優(yōu)點(diǎn)是盡量避免內(nèi)存碎片,使得內(nèi)存分配效率得到提升。
傳統(tǒng)的內(nèi)存池[4]主要由三層結(jié)構(gòu)組成(如圖1),第一層為內(nèi)存池初始化時(shí)通過new方法申請(qǐng)的大塊內(nèi)存(M emory Chunk);第二層是用于滿足不同大小的內(nèi)存分配請(qǐng)求的鏈表;第三層則是一定數(shù)量的不同大小的內(nèi)存節(jié)點(diǎn)(node)。內(nèi)存池采用雙向鏈表的方式組織內(nèi)存塊和內(nèi)存節(jié)點(diǎn),塊與塊之間,節(jié)點(diǎn)與節(jié)點(diǎn)之間都通過指針相連,未分配的節(jié)點(diǎn)由空閑鏈表維護(hù)。當(dāng)需要申請(qǐng)內(nèi)存時(shí),從對(duì)應(yīng)大小的空閑鏈表中取出一個(gè)節(jié)點(diǎn)返回給申請(qǐng)者;當(dāng)節(jié)點(diǎn)使用完畢需要釋放時(shí),回收的節(jié)點(diǎn)將被掛載到對(duì)應(yīng)空閑列表的表頭或尾部,等待下次分配。
圖1 傳統(tǒng)內(nèi)存池結(jié)構(gòu)
由于傳統(tǒng)內(nèi)存池結(jié)構(gòu)簡單,在分配/回收內(nèi)存時(shí)只需簡單地移動(dòng)指針,通常情況下時(shí)間復(fù)雜度為O(1),僅在內(nèi)存塊耗盡,需要調(diào)用new函數(shù)向堆申請(qǐng)新的內(nèi)存塊時(shí)才會(huì)產(chǎn)生額外開銷。然而,盡管在時(shí)間性能上表現(xiàn)優(yōu)異,傳統(tǒng)內(nèi)存池在空間利用上卻存在一定缺陷。由內(nèi)存節(jié)點(diǎn)的成員變量組成的頭部將會(huì)占用一定大小節(jié)點(diǎn)空間,對(duì)于較小的節(jié)點(diǎn),頭部的大小甚至超過了數(shù)據(jù)區(qū)的大小,造成了空間的浪費(fèi)。舉一個(gè)例子,當(dāng)有1 000萬個(gè)8字節(jié)數(shù)據(jù)區(qū)大小的節(jié)點(diǎn)被分配時(shí),用于存儲(chǔ)數(shù)據(jù)的空間為8×107=80 MB,而用于存儲(chǔ)節(jié)點(diǎn)的雙向指針的空間同樣為8×107=80 MB,加上其他變量所占空間,實(shí)際空間利用率不足50%。當(dāng)內(nèi)存數(shù)據(jù)庫應(yīng)用于內(nèi)存容量較小的移動(dòng)終端設(shè)備時(shí),這樣低的空間利用率是不能接受的。此外,傳統(tǒng)內(nèi)存池缺少合理的內(nèi)存塊增長控制策略和異?;謴?fù)機(jī)制,當(dāng)出現(xiàn)內(nèi)存不足,無法滿足分配請(qǐng)求的情況時(shí),系統(tǒng)將陷入癱瘓??梢姡瑐鹘y(tǒng)內(nèi)存池盡管擁有不錯(cuò)的時(shí)間性能,但在空間利用率和健壯性方面,遠(yuǎn)遠(yuǎn)不能滿足內(nèi)存數(shù)據(jù)庫系統(tǒng)的需要。
本文提出了一種新型的基于虛擬單元智能增長的內(nèi)存池SVMP(Smart-grow th&Virtual-unit-based M emory Pool),在繼承了傳統(tǒng)內(nèi)存池的優(yōu)點(diǎn)之余,改進(jìn)了內(nèi)存分配/回收機(jī)制,為提高空間利用率提出了虛擬單元(Virtualunit)的概念,并設(shè)計(jì)了智能增長算法(Smart-grow th A lgorithm)用于解決內(nèi)存池的增長問題。
3.1 設(shè)計(jì)核心和層級(jí)結(jié)構(gòu)
圖2 SVMP整體結(jié)構(gòu)
SVMP技術(shù)的核心是虛擬單元和智能增長算法。虛擬單元并不是實(shí)際對(duì)象,而是一種抽象存在,通過游標(biāo)移動(dòng),將前后兩次移動(dòng)的間隔長度大小的內(nèi)存區(qū)稱為一個(gè)單元,是一種完全邏輯意義上的劃分。由于虛擬單元沒有頭部信息,盡可能多的內(nèi)存空間將被用作數(shù)據(jù)區(qū),從而極大提高了內(nèi)存的空間利用率。智能增長算法以TCP模型中擁塞控制的AIMD思想為核心,對(duì)內(nèi)存池的增長進(jìn)行了合理控制,減少了直接調(diào)用new函數(shù)的次數(shù),并通過C++的new-handler機(jī)制處理多次申請(qǐng)后產(chǎn)生的內(nèi)存不足的問題。
SVMP在層級(jí)結(jié)構(gòu)上繼承了傳統(tǒng)內(nèi)存池的池-表-塊三層設(shè)計(jì),但又有所區(qū)別(圖2)。針對(duì)數(shù)據(jù)集不定長的特點(diǎn),第一層的池結(jié)構(gòu)sv_mem_pool初始化了128個(gè)unit_size分別為8~1 024字節(jié)大小的的鏈表,以指針數(shù)組list_collection[NUM_OF_LIST]索引,能夠在較小粒度上提供內(nèi)存。第二層的鏈表sv_mem_list以單向指針連接第三層的內(nèi)存塊,其中head_chunk指針指向該鏈表的第一個(gè)內(nèi)存塊,current_chunk指針則指向當(dāng)前正在用于分配的內(nèi)存塊,此外還擁有一個(gè)緩沖棧free_stack,負(fù)責(zé)對(duì)應(yīng)大小的虛擬單元的回收。第三層的sv_mem_chunk(圖3)在設(shè)計(jì)上放棄了傳統(tǒng)內(nèi)存池的node結(jié)構(gòu)和空閑鏈表,而是直接向堆申請(qǐng)一塊連續(xù)內(nèi)存空間作為數(shù)據(jù)區(qū),然后根據(jù)鏈表中指定的unit_size將內(nèi)存空間劃分為n個(gè)虛擬單元,游標(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é)的分配請(qǐng)求,如果申請(qǐng)的空間大小超過上限MAX_BYTES=1 024字節(jié),則將這種大塊空間的分配返回給操作系統(tǒng)處理。當(dāng)提出內(nèi)存申請(qǐng)請(qǐng)求時(shí),由于不同的鏈表維護(hù)的虛擬單元的上調(diào)邊界ALIGN=8字節(jié),如果分配的空間達(dá)不到8字節(jié),將按照8字節(jié)分配,如果需要的空間超過8字節(jié),則將分配的空間上調(diào)為8字節(jié)的倍數(shù),即用ALIGN整除申請(qǐng)的空間大小,以此索引list_collection中維護(hù)對(duì)應(yīng)虛擬單元的鏈表。在索引到正確的鏈表后,首先查看緩沖棧free_stack中是否為空,如果free_stack中存在指向已回收的虛擬單元的指針,則將指針彈出棧并返回,該虛擬單元再次被利用,分配結(jié)束;如果free_stack為空,將申請(qǐng)?zhí)峤划?dāng)前內(nèi)存塊current_chunk,檢查current_chunk是否存在虛擬單元可供分配,如果存在,則將cursor_pos指向的虛擬單元地址返回給用戶,并將cursor_pos移動(dòng)到指向下一個(gè)虛擬單元,分配結(jié)束;否則鏈表將構(gòu)造新的內(nèi)存塊,調(diào)用全局new函數(shù)向堆申請(qǐng)新的內(nèi)存空間,current_chunk指針將指向新構(gòu)造的塊,并返回新申請(qǐng)塊的第一個(gè)虛擬單元,分配結(jié)束。
當(dāng)釋放內(nèi)存時(shí),首先仍需索引list_collection中維護(hù)待回收虛擬單元的鏈表,再將指向該單元的指針壓入free_stack,回收完畢。
3.3 智能增長算法
在增長算法的設(shè)計(jì)上,SVMP吸收了TCP/IP模型中解決擁塞控制的AIMD(Additive Increase M ultiplicative Decrease)算法的思想,即:加性增,乘性減,或者叫做“和式增加,積式減少”[5]。AIMD算法是TCP/IP模型中,運(yùn)輸層為解決擁塞控制的一種方法,當(dāng)TCP發(fā)送方感受到端到端路徑無擁塞時(shí)就線性地增加其發(fā)送窗口長度,當(dāng)察覺到路徑擁塞時(shí)就乘性減小其發(fā)送窗口長度。
SVMP在初始化時(shí)所有鏈表向堆申請(qǐng)一定大小的內(nèi)存塊,隨著系統(tǒng)運(yùn)行時(shí)間增長,處理的數(shù)據(jù)增多,將會(huì)出現(xiàn)沒有虛擬單元可供分配的情況,必須再次向堆申請(qǐng)內(nèi)存空間。在SGI STL的allocator設(shè)計(jì)中,當(dāng)沒有空閑節(jié)點(diǎn)可用時(shí),默認(rèn)每次返回新的定長的20塊內(nèi)存節(jié)點(diǎn)[6],這種每次新增同樣大小內(nèi)存塊的方式雖然簡單,但無法較好地適應(yīng)持續(xù)增長的數(shù)據(jù)區(qū)請(qǐng)求,SVMP中為了減少直接調(diào)用new函數(shù)的次數(shù),當(dāng)需要再次申請(qǐng)內(nèi)存塊時(shí),SVMP將在之前內(nèi)存塊大小的基礎(chǔ)上進(jìn)行擴(kuò)容。用M表示新申請(qǐng)的塊容量,M′表示前一次申請(qǐng)的塊容量,V表示初始化時(shí)申請(qǐng)的內(nèi)存塊容量,則:
M=M′+V=nV(n表示申請(qǐng)內(nèi)存塊的次數(shù))
同時(shí)M的大小不能無限量增加,當(dāng)?shù)竭_(dá)既定的最大上限MAX_SIZE(1 000個(gè)頁大小4 MB)時(shí),以后新申請(qǐng)的內(nèi)存塊容量跟之前的塊將保持一致。
算法實(shí)現(xiàn)如下:
這樣逐步線性增加新申請(qǐng)的內(nèi)存塊大小,將更好地適應(yīng)不斷增長的數(shù)據(jù)量需求,降低未來的向系統(tǒng)申請(qǐng)內(nèi)存操作的次數(shù),同時(shí)節(jié)約內(nèi)存空間,避免了傳統(tǒng)內(nèi)存池中可能出現(xiàn)的大塊內(nèi)存閑置的現(xiàn)象,并且可以根據(jù)實(shí)際需求調(diào)整線性增長的初始值和增長速率以達(dá)到最佳的空間性能(內(nèi)存數(shù)據(jù)庫系統(tǒng)在工作高峰期時(shí)對(duì)于內(nèi)存塊的增速可能將超過線性增長提供的增速,SVMP為應(yīng)對(duì)此情況預(yù)留了按指數(shù)增長的接口,當(dāng)線性增長不能滿足需求時(shí),將按指數(shù)增長)。
然而當(dāng)數(shù)據(jù)量足夠大時(shí),SVMP將不斷向堆申請(qǐng)空間,內(nèi)存的分配速度遠(yuǎn)大于回收速度,最終可能導(dǎo)致在某個(gè)時(shí)段出現(xiàn)操作系統(tǒng)無法滿足新的分配請(qǐng)求,系統(tǒng)將不能繼續(xù)正常工作。在C++語言中,當(dāng)出現(xiàn)無法滿足內(nèi)存分配請(qǐng)求的情況時(shí),將會(huì)拋出std::bad_alloc類型的異常[7]。而在拋出異常之前,操作系統(tǒng)將調(diào)用預(yù)先指定的一個(gè)出錯(cuò)處理函數(shù),該函數(shù)通常被稱為new-handler。為了裝載用戶自定義的new-handler,必須調(diào)用set-newhandler函數(shù),將new-handler函數(shù)作為參數(shù)傳遞[8]。在SVMP中,指定的new-handler函數(shù)將修改申請(qǐng)的空間字節(jié)數(shù),用M′表示無法滿足分配請(qǐng)求時(shí)申請(qǐng)的空間大小,M表示修改后的大小,V表示初始化時(shí)申請(qǐng)的內(nèi)存塊容量,則:
同時(shí)還將移出其他進(jìn)程,回收內(nèi)存空間。
算法實(shí)現(xiàn)如下:
//內(nèi)存不足情況處理函數(shù),即自定義的new-handler函數(shù)
在分配請(qǐng)求無法被滿足前,new-handler函數(shù)將被循環(huán)調(diào)用直到申請(qǐng)需求被滿足。這樣乘性的減少申請(qǐng)空間的大小,將使得系統(tǒng)能夠很快地恢復(fù)工作。
SVMP技術(shù)是一個(gè)高效的內(nèi)存管理解決方案,其性能優(yōu)勢在各個(gè)方面都得到了體現(xiàn)。
(1)時(shí)間性能較直接使用new向堆申請(qǐng)內(nèi)存有顯著提高。SVMP通過分配預(yù)先申請(qǐng)的內(nèi)存塊中的虛擬單元,避免了掃描內(nèi)存區(qū)來查找匹配內(nèi)存塊,同時(shí)減少了碎片,使得整個(gè)分配/回收操作都能在常數(shù)時(shí)間O(1)完成。(2)空間性能較直接使用new/delete和傳統(tǒng)內(nèi)存池有一定幅度提升。因?yàn)樘摂M單元只是邏輯上對(duì)內(nèi)存空間的劃分,不存在物理結(jié)構(gòu),極大地節(jié)省了內(nèi)存空間,智能增長算法的“和式增加”方式,既滿足了不斷增長的數(shù)據(jù)量對(duì)于更多內(nèi)存空間的需求同時(shí)也避免了大塊內(nèi)存的閑置。(3)解決了內(nèi)存不足的問題,增強(qiáng)了系統(tǒng)健壯性。通過調(diào)用set_new_handler函數(shù)指定new-handler,在bad_alloc類型異常拋出之前回收內(nèi)存空間并乘性減少申請(qǐng)的空間大小,使得SVMP能夠很快從內(nèi)存不足的狀態(tài)下恢復(fù)。
性能測試中模擬了300萬個(gè)數(shù)據(jù)集的內(nèi)存空間的申請(qǐng)和釋放,大小從8字節(jié)到1 024字節(jié)不等。測試方案為:將300萬數(shù)據(jù)集分成3個(gè)批次,每次隨機(jī)選擇大小不同的共100萬數(shù)據(jù)集,為其分配內(nèi)存空間,分配完畢后再進(jìn)行釋放,重復(fù)3次,記錄整個(gè)過程耗時(shí)并比較。測試平臺(tái)為: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)存申請(qǐng)空間的次數(shù)和碎片的數(shù)量,時(shí)間性能產(chǎn)生了飛躍,所耗時(shí)較直接調(diào)用new/delete對(duì)內(nèi)存進(jìn)行管理減小了一個(gè)數(shù)量級(jí);而SVMP較之傳統(tǒng)內(nèi)存池,在內(nèi)存塊大小增長上更加智能,進(jìn)一步減少了直接向內(nèi)存申請(qǐng)空間的次數(shù),將時(shí)間再次縮短了25%左右。
表2是分別使用傳統(tǒng)內(nèi)存池和SVMP以及直接調(diào)用new/delete這三種不同的內(nèi)存管理方式消耗的內(nèi)存空間大小數(shù)據(jù)。存儲(chǔ)相同大小的數(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)存池提升了一個(gè)層次,與直接直接調(diào)用new/delete消耗的內(nèi)存空間基本相當(dāng)。
表1 三種不同內(nèi)存管理方式的運(yùn)行時(shí)間對(duì)比
表2 三種不同內(nèi)存管理方式消耗內(nèi)存空間對(duì)比
SVMP吸收了傳統(tǒng)內(nèi)存池的優(yōu)點(diǎn),改進(jìn)了內(nèi)存分配/回收策略,利用虛擬單元提高了空間利用率,同時(shí)依然具備良好的時(shí)間性能。此外,SVMP具備智能增長特性,并為內(nèi)存不足的情況設(shè)定了恢復(fù)機(jī)制,具有較強(qiáng)的健壯性,十分適用于內(nèi)存數(shù)據(jù)庫系統(tǒng)。
[1]Bryant R E,O’Hallaron D R.深入理解計(jì)算機(jī)系統(tǒng)[M].龔奕利,雷迎春,譯.北京:機(jī)械工業(yè)出版社,2010.
[2]鐘寶榮,袁文亮.內(nèi)存數(shù)據(jù)庫中存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)機(jī)制[J].計(jì)算機(jī)工程與設(shè)計(jì),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)新實(shí)驗(yàn)計(jì)劃(No.1110611066)。
余俊良(1990—),男,本科生,主要研究方向:計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),數(shù)據(jù)庫技術(shù);楊正益(1979—),男,博士研究生,講師,主要研究方向:程序性能設(shè)計(jì),高性能數(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