高并發(fā)搜索系統(tǒng)下內(nèi)存池的設(shè)計(jì)和實(shí)現(xiàn)

陸兆攀，劉萍萍,盧　穎

(西安工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，西安 710021)

?

高并發(fā)搜索系統(tǒng)下內(nèi)存池的設(shè)計(jì)和實(shí)現(xiàn)

陸兆攀，劉萍萍,盧穎

(西安工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，西安 710021)

摘要：為了在輸入關(guān)鍵詞后能從網(wǎng)絡(luò)搜索中快速、準(zhǔn)確地返回信息，并有效降低搜索系統(tǒng)在高并發(fā)狀態(tài)下頻繁分配和回收內(nèi)存對(duì)程序性能的影響.文中根據(jù)搜索引擎中不同的場(chǎng)景，設(shè)計(jì)出了可回收定長(zhǎng)內(nèi)存池，可回收變長(zhǎng)內(nèi)存池和只分配不釋放內(nèi)存池.實(shí)例計(jì)算結(jié)果表明：與系統(tǒng)默認(rèn)的內(nèi)存分配器對(duì)比，可回收定長(zhǎng)內(nèi)存池的效率提升了70.20%；可回收變長(zhǎng)內(nèi)存池的效率提升了13.84%；只分配不釋放內(nèi)存池的效率提升了90.80%.

關(guān)鍵詞：高并發(fā)；搜索引擎；內(nèi)存池；分配器器

搜索引擎是互聯(lián)網(wǎng)最重要的應(yīng)用之一，涉及信息檢索、分布式處理、語(yǔ)意網(wǎng)、數(shù)據(jù)挖掘等多個(gè)領(lǐng)域理論和技術(shù).合理的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、索引，高并發(fā)系統(tǒng)結(jié)構(gòu)的設(shè)計(jì)等都是影響查詢速度的因素.搜索引擎基本工作原理己經(jīng)很穩(wěn)定，但其在服務(wù)方式、質(zhì)量和性能等方面依然急需優(yōu)化.

傳統(tǒng)搜索引擎大都采用關(guān)鍵詞匹配模式，在申請(qǐng)釋放不太頻繁的情況下，通常讓系統(tǒng)進(jìn)行內(nèi)存管理即可，但面對(duì)海量數(shù)據(jù)的處理和存儲(chǔ)，搜索引擎顯得無(wú)能為力.在直接使用系統(tǒng)調(diào)用Malloc/Free、New/Delete[1]進(jìn)行內(nèi)存分配和釋放，存在一定的弊端：比如調(diào)用Malloc/New系統(tǒng)根據(jù)“最先匹配”、“最優(yōu)匹配”或其他算法在內(nèi)存空閑塊表中查找一塊空閑內(nèi)存，內(nèi)存使用效率不高；調(diào)用Free/Delete，系統(tǒng)可能需要進(jìn)行空閑內(nèi)存塊合并操作，這會(huì)帶來(lái)額外時(shí)間和空間上的開(kāi)銷(xiāo)；頻繁使用時(shí)容易產(chǎn)生大量?jī)?nèi)存碎片，從而降低程序運(yùn)行效率和穩(wěn)定性；容易出現(xiàn)內(nèi)存泄漏[2]造成內(nèi)存大小持續(xù)增加，甚至內(nèi)存耗盡.對(duì)于內(nèi)存的分配問(wèn)題，西安郵電大學(xué)的王小銀副教授在Linux 內(nèi)核中內(nèi)存池的實(shí)現(xiàn)及應(yīng)用[3]一文中對(duì)內(nèi)存池的創(chuàng)建方法和調(diào)用原理進(jìn)行了分析研究.在內(nèi)存池上分配的內(nèi)存不需要釋放，在內(nèi)存池銷(xiāo)毀時(shí)會(huì)釋放從內(nèi)存池分配出去的內(nèi)存.具有的優(yōu)點(diǎn)：加快內(nèi)存分配速度(快于標(biāo)準(zhǔn)的Malloc)，內(nèi)存塊夠用時(shí)，僅是大小判斷和指針偏移等簡(jiǎn)單操作；小塊內(nèi)存的有效載荷高(沒(méi)有合并內(nèi)存塊所需的指針)，需要的額外信息少；內(nèi)存池上分配的內(nèi)存通常不需要再單獨(dú)釋放，而是統(tǒng)一回收；除了使用內(nèi)存分配函數(shù)代替Malloc，沒(méi)有使用上的其他特殊約定.

因此，綜合對(duì)比了傳統(tǒng)搜索引擎的內(nèi)存分配方式和采用內(nèi)存池的分配方式，本課題主要針對(duì)不同的搜索應(yīng)用場(chǎng)景設(shè)計(jì)不同的內(nèi)存池，管理內(nèi)存分配以得到最快的分配和釋放速度.針對(duì)用戶的一次查詢，系統(tǒng)將內(nèi)存管理完全由程序員接管，比較利于問(wèn)題的排查和系統(tǒng)的優(yōu)化，能夠快速地返回一個(gè)令客戶滿意的結(jié)果.

1搜索引擎原理及關(guān)鍵技術(shù)

搜索引擎是通過(guò)從互聯(lián)網(wǎng)上提取的各個(gè)網(wǎng)站的信息來(lái)建立數(shù)據(jù)庫(kù)，檢索與用戶查詢條件匹配的相關(guān)記錄，然后按一定的排列順序?qū)⒔Y(jié)果返回給用戶.搜索引擎的工作原理[4]主要分成四個(gè)步驟：首先是利用網(wǎng)絡(luò)爬蟲(chóng)程序技術(shù)[5]從互聯(lián)網(wǎng)上去自動(dòng)抓取網(wǎng)頁(yè)，然后再根據(jù)抓取到的原始網(wǎng)頁(yè)進(jìn)行分析，接著建立索引數(shù)據(jù)庫(kù)，最后在索引數(shù)據(jù)庫(kù)中搜索并排序.當(dāng)有多個(gè)線程在操作時(shí)，如果系統(tǒng)只有一個(gè)CPU，則他根本不可能真正同時(shí)進(jìn)行一個(gè)以上的線程，他只能把CPU運(yùn)行時(shí)間劃分成若干個(gè)時(shí)間段，再將時(shí)間段分配給各個(gè)線程執(zhí)行，在一個(gè)時(shí)間段的線程代碼運(yùn)行時(shí)，其他線程處于掛起狀，這種方式我們稱(chēng)之為并發(fā).在高并發(fā)狀態(tài)下，搜索系統(tǒng)頻繁的分配和回收內(nèi)存會(huì)嚴(yán)重地降低程序的性能，而且應(yīng)用程序可能會(huì)以某種特定的方式使用內(nèi)存，并且為不需要的功能付出性能上的代價(jià).

對(duì)于長(zhǎng)期運(yùn)行的后臺(tái)服務(wù)系統(tǒng)來(lái)說(shuō)，性能降低的主要原因在于默認(rèn)的內(nèi)存管理是通用的，而通用的內(nèi)存管理通?？紤]了較多的因素，包括線程、大小、回收時(shí)間、分配頻率等等，以致于對(duì)于效率有所影響.基于這個(gè)原因，通常會(huì)考慮使用內(nèi)存池來(lái)管理服務(wù)的內(nèi)存分配，而不是簡(jiǎn)單使用Malloc/Free，New/Delete來(lái)進(jìn)行動(dòng)態(tài)內(nèi)存分配.通過(guò)設(shè)計(jì)專(zhuān)用的內(nèi)存池來(lái)為搜索系統(tǒng)在不用搜索應(yīng)用場(chǎng)景查詢時(shí)分配特定的內(nèi)存來(lái)優(yōu)化性能，并提升海量數(shù)據(jù)存儲(chǔ)及搜索速度，以解決通用內(nèi)存的問(wèn)題.

1.1內(nèi)存池原理

內(nèi)存池[6](Memory Pool)是一種內(nèi)存分配方式，是動(dòng)態(tài)分配內(nèi)存的設(shè)備，只能被特定的內(nèi)核成分(即池的“擁有者”)使用.擁有者通常不直接使用內(nèi)存池，當(dāng)普通內(nèi)存分配失敗時(shí)，內(nèi)核才調(diào)用特定的內(nèi)存池函數(shù)來(lái)提取內(nèi)存池，以得到所需的額外內(nèi)存.因此內(nèi)存池只是內(nèi)核內(nèi)存的一個(gè)儲(chǔ)備，用在特定的時(shí)刻.

如圖1所示，該內(nèi)存池一共包含4個(gè)內(nèi)存塊.在內(nèi)存池初次生成時(shí)，只向系統(tǒng)申請(qǐng)了一個(gè)內(nèi)存塊，返回的指針作為整個(gè)內(nèi)存池的頭指針.之后隨著應(yīng)用程序?qū)?nèi)存的不斷需求，內(nèi)存池判斷需要?jiǎng)討B(tài)擴(kuò)大時(shí)，才再次向系統(tǒng)申請(qǐng)新的內(nèi)存塊，并把所有這些內(nèi)存塊通過(guò)指針鏈接起來(lái).

圖1　內(nèi)存池工作原理

對(duì)于操作系統(tǒng)來(lái)說(shuō)，他已經(jīng)為該應(yīng)用程序分配了4個(gè)等大小的內(nèi)存塊.例如，對(duì)第4個(gè)內(nèi)存塊放大來(lái)看，其中包含一部分內(nèi)存池塊頭信息和3個(gè)大小相等的內(nèi)存池單元.單元1和單元3是空閑的，單元2已經(jīng)分配.當(dāng)應(yīng)用程序需要通過(guò)該內(nèi)存池分配一個(gè)單元大小的內(nèi)存時(shí)，只需要簡(jiǎn)單遍歷所有的內(nèi)存池塊頭信息，快速定位到還有空閑單元的那個(gè)內(nèi)存池塊.然后根據(jù)該塊的塊頭信息直接定位到第 1個(gè)空閑的單元地址，把這個(gè)地址返回，并且標(biāo)記下一個(gè)空閑單元即可；當(dāng)應(yīng)用程序釋放某一個(gè)內(nèi)存池單元時(shí)，直接在對(duì)應(yīng)的內(nèi)存池塊頭信息中標(biāo)記該內(nèi)存單元為空閑單元即可.

1.2小型對(duì)象分配技術(shù)

由于所申請(qǐng)內(nèi)存池內(nèi)存塊的大小不定，通常習(xí)慣直接使用New、Malloc等API申請(qǐng)分配內(nèi)存，對(duì)小對(duì)象分配并不有效，當(dāng)頻繁使用時(shí)會(huì)造成大量的內(nèi)存碎片并進(jìn)而降低性能，在這里使用適用于小對(duì)象內(nèi)存分配的小型對(duì)象分配技術(shù)[7].

小型對(duì)象分配器可在建構(gòu)期間設(shè)定區(qū)塊的大小和數(shù)量.Chunk層包含邏輯信息，可以從該大塊內(nèi)存中配置和歸還區(qū)塊.一旦Chunk之中沒(méi)有剩余區(qū)塊，函數(shù)便傳回零.SmallObjectPool層內(nèi)置一個(gè)Vector，里邊存儲(chǔ)Chunk對(duì)象，對(duì)Chunk層進(jìn)行了擴(kuò)展.其中有一個(gè)Chunk隊(duì)列，存儲(chǔ)全部的信息，有兩個(gè)Chunk的指針，一個(gè)指向當(dāng)前可分配的Chunk，一個(gè)指向當(dāng)前帶釋放指針位于的Chunk.

1.3搜索引擎系統(tǒng)場(chǎng)景分析

本課題主要針對(duì)搜索引擎中的定長(zhǎng)場(chǎng)景、大小不固定場(chǎng)景、多次分配場(chǎng)景這個(gè)三個(gè)場(chǎng)景的特點(diǎn)進(jìn)行分析，設(shè)計(jì)出相應(yīng)的內(nèi)存池.

1) 定長(zhǎng)場(chǎng)景.現(xiàn)有的搜索引擎系統(tǒng)內(nèi)部，緩存設(shè)計(jì)利用到了哈希表，原有系統(tǒng)針對(duì)哈希表的每一個(gè)節(jié)點(diǎn)的分配和釋放利用了系統(tǒng)的New和Delete函數(shù)，而這些節(jié)點(diǎn)本身的大小是固定的，可以針對(duì)固定大小節(jié)點(diǎn)的分配和釋放，設(shè)計(jì)一個(gè)內(nèi)存池，來(lái)提升緩存分配和釋放的速度.而且在現(xiàn)有的搜索系統(tǒng)中，很多地方用到了STL容器[9]中的Map，而Map中每個(gè)節(jié)點(diǎn)內(nèi)存的分配和釋放利用STL內(nèi)的分配器去管理，自己接管這些固定節(jié)點(diǎn)內(nèi)存的分配和釋放，提升效率，容易排錯(cuò).

基于以上兩個(gè)場(chǎng)景，通過(guò)分析可以看出來(lái)共性就是如何處理固定大小的節(jié)點(diǎn)，設(shè)計(jì)一個(gè)可回收定長(zhǎng)內(nèi)存池針對(duì)固定大小的節(jié)點(diǎn)內(nèi)存的分配和釋放.

2) 大小不固定場(chǎng)景.現(xiàn)有的搜索系統(tǒng)的緩存管理中，搜索結(jié)果每次要放入緩存里，利于下一次的查找，緩存中每個(gè)節(jié)點(diǎn)的大小不確定，進(jìn)入緩存和提出緩存的時(shí)間也不可預(yù)估.現(xiàn)有的搜索系統(tǒng)的的更新模塊中，他管理文檔的更新和刪除，但是文檔的大小和更新的時(shí)間未知.

針對(duì)這個(gè)場(chǎng)景可以設(shè)計(jì)一個(gè)可回收變長(zhǎng)內(nèi)存池，針對(duì)Cache的多線程特點(diǎn)[10]，可以加入鎖來(lái)處理.

3) 多次分配場(chǎng)景.現(xiàn)有的搜索引擎在輸入一個(gè)關(guān)鍵詞之后，返回的結(jié)果大小預(yù)估在10 M之內(nèi)，而附帶結(jié)果存儲(chǔ)的很多信息的分配和釋放用New和Delete來(lái)實(shí)現(xiàn)，會(huì)頻繁的調(diào)用New來(lái)分配很多小對(duì)象，影響效率，以及產(chǎn)生內(nèi)存碎片[11].

經(jīng)過(guò)分析，在返回結(jié)果的同時(shí)，會(huì)頻繁去分配，而釋放的次數(shù)僅僅只有當(dāng)查詢結(jié)果返回之后才會(huì)進(jìn)行，所以這里需要對(duì)頻繁分配這種因素進(jìn)行考慮，且已知總的容量不超過(guò)10 M，因此可以考慮預(yù)先分配很大的內(nèi)存塊，之后所有的小內(nèi)存都在其中去分配，最后通過(guò)接口來(lái)釋放，基于這個(gè)場(chǎng)景設(shè)計(jì)只分配不釋放內(nèi)存池.

2高并發(fā)搜索系統(tǒng)內(nèi)存池的設(shè)計(jì)和實(shí)現(xiàn)

通過(guò)分析現(xiàn)有的搜索引擎得到了三個(gè)場(chǎng)景：哈希表的插入刪除，緩存的更新和文檔的更新模塊，查詢結(jié)果返回.針對(duì)三個(gè)場(chǎng)景設(shè)計(jì)三種內(nèi)存池：可回收定長(zhǎng)內(nèi)存池，可回收變長(zhǎng)內(nèi)存池，只分配不釋放內(nèi)存池以優(yōu)化高并發(fā)搜索系統(tǒng).搜索系統(tǒng)內(nèi)存池的設(shè)計(jì)結(jié)構(gòu)框架如圖2所示.

圖2　搜索系統(tǒng)內(nèi)存池的設(shè)計(jì)結(jié)構(gòu)框架

2.1可回收定長(zhǎng)內(nèi)存池

可回收定長(zhǎng)內(nèi)存池即小型對(duì)象分配器內(nèi)存池，其分為4層結(jié)構(gòu).如圖3所示，最底層是Chunk對(duì)象，每一個(gè)Chunk管理一大塊內(nèi)存，此大塊內(nèi)存本身包含整數(shù)個(gè)固定大小的區(qū)塊(block).Chunk內(nèi)含邏輯信息，使用者可根據(jù)他來(lái)配置和歸還區(qū)塊.當(dāng)Chunk之中不再剩余blocks時(shí)，配置失敗并傳回零.第二層是FixAllocator，他以第一層為基礎(chǔ)，利用已知的vector對(duì)第一層做了擴(kuò)展，保證了分配的大小可擴(kuò)展.第三層是SmallObjectAllocator提供通用分配/歸還函數(shù)，針對(duì)第二層做了擴(kuò)展，提供多個(gè)第二層對(duì)象，將定長(zhǎng)的分配技術(shù)變成了變長(zhǎng)分配的技術(shù).第四層是SmallObject，他對(duì)第三層做了封裝，提供了一些通用的接口，以及線程的因素，將其擴(kuò)展成多線程可用的分配器.通過(guò)一層一層的擴(kuò)展，既保證了分配釋放效率，也能更好的將內(nèi)部結(jié)構(gòu)封裝起來(lái)，對(duì)外部不可見(jiàn).通過(guò)提供通用的接口，使其使用起來(lái)就像操作系統(tǒng)自帶的默認(rèn)內(nèi)存分配器一樣.

圖3　小型對(duì)象分配器結(jié)構(gòu)

2.2可回收變長(zhǎng)內(nèi)存池

可回收變長(zhǎng)內(nèi)存池是一個(gè)多線程、變長(zhǎng)、可回收的內(nèi)存池，類(lèi)似于哈希表，一個(gè)鏈表指示可分配的大小區(qū)間，鏈表內(nèi)的每一個(gè)元素為特定大小的內(nèi)存塊指針，指向多個(gè)內(nèi)存塊鏈表，每次分配通過(guò)對(duì)齊找到特定的頭指針，然后在鏈表中分配一個(gè)節(jié)點(diǎn)出去.在范圍內(nèi)的元素會(huì)通過(guò)New分配，釋放的時(shí)候會(huì)歸還到池里保存，用于下次分配，而超出范圍內(nèi)的元素也通過(guò)New分配，不過(guò)在釋放的時(shí)候，會(huì)直接調(diào)用delete，歸還給操作系統(tǒng).關(guān)于線程因素，通過(guò)構(gòu)造函數(shù)指定后，加鎖保證線程安全.主要包括BlockHeader層、tragCtrlUnit層和RecycleLitePool層.其整體結(jié)構(gòu)圖如圖4所示.

BlockHeader層為最底層的分配結(jié)構(gòu)，nCtrlIndex指示塊的實(shí)際分配大小，pNextBlock指示下一個(gè)塊，組成鏈表結(jié)構(gòu)，整體為union類(lèi)型，節(jié)省了空間，提高了效率.tragCtrlUnit層為每一個(gè)BlockHeader層的頭指針，還包含一個(gè)指示BlockHeader對(duì)象個(gè)數(shù)的成員.RecycleLitePool層包含線程元素，鎖元素，以及tagCtrlUnit層的指針，還有一些計(jì)數(shù)的元素和一個(gè)內(nèi)存分配器，默認(rèn)為New分配，Delete刪除.

2.3只分配不釋放內(nèi)存池

只分配不釋放內(nèi)存池分四層如下：

1) MemoryChunk層.最底層的分配塊，內(nèi)部三個(gè)成員，一個(gè)指示塊的大小，一個(gè)指示初始地址的位置，一個(gè)指示當(dāng)前可分配的位置.

2) Chain Of Memory Chunk層.將Memory Chunk對(duì)象組織成雙向鏈表.

圖4　RecycleLitePool整體結(jié)構(gòu)

3) SimpleAllocatePoilcy層此層接受分配的請(qǐng)求，將待分配的大小改變?yōu)椴恍∮贛emoryChunk的大小，然后加入到雙向鏈表中，將當(dāng)前可分配塊指針指向新建的塊.

4) StagePool層.為最外層，默認(rèn)的模板參數(shù)為SimpleAllocatePolicy類(lèi)型，提供對(duì)外的接口進(jìn)行分配、釋放.

StagePool的整體結(jié)構(gòu)包含一個(gè)Chunk型別的指針，指向當(dāng)前正在分配的塊，每次的分配請(qǐng)求都從當(dāng)前塊里尋找，余量不足的時(shí)候就新建一個(gè)塊插入到鏈表中，通過(guò)模板參數(shù)AllocatePolicy來(lái)選擇分配策略，總體結(jié)構(gòu)如圖5所示.

圖5　StagePool整體結(jié)構(gòu)

3性能測(cè)試和分析

通過(guò)Centos操作系統(tǒng)，vim，g++，scons的編譯器和調(diào)試工具，設(shè)計(jì)一些場(chǎng)景模擬搜索引擎中的實(shí)際場(chǎng)景，來(lái)測(cè)試默認(rèn)的內(nèi)存分配器和設(shè)計(jì)的分配器之間的性能差異.

3.1小型對(duì)象分配器性能測(cè)試和分析

1) 對(duì)于小型對(duì)象分配器的測(cè)試，當(dāng)數(shù)據(jù)量為100 000的時(shí)候(數(shù)據(jù)量可配置)，通過(guò)對(duì)系統(tǒng)函數(shù)New/Delete和內(nèi)存池的接口函數(shù)Allocate/Deallocate進(jìn)行測(cè)試.記錄5組數(shù)據(jù)見(jiàn)表1，通過(guò)分析計(jì)算時(shí)間差，小型對(duì)象分配器內(nèi)存池相對(duì)New而言提升了70.20%，相對(duì)delete而言，提升較小，為2.29%.

2) 對(duì)于小型對(duì)象分配器用于哈希表的測(cè)試，利用NodeAllocator類(lèi)來(lái)適配與哈希表(通過(guò)哈希表的模板參數(shù))，同理構(gòu)造一個(gè)相同的類(lèi)DefaultAllocator內(nèi)部的分配函數(shù)使用New/Delete來(lái)實(shí)現(xiàn)，用模板參數(shù)來(lái)適配哈希表.單線程測(cè)試：對(duì)于NodeAllocator和DefaultAllocator使用50 000個(gè)block的申請(qǐng)和釋放的方法，程序運(yùn)行固定時(shí)間(假設(shè)為10 s)，在這段時(shí)間內(nèi)進(jìn)行重復(fù)的插入刪除操作；多線程測(cè)試：對(duì)于NodeAllocator和DefaultAllocator，開(kāi)啟相同數(shù)目的線程，執(zhí)行線程函數(shù)，對(duì)各自對(duì)應(yīng)的哈希表里插入刪除數(shù)據(jù).表2指示了哈希表的測(cè)試數(shù)據(jù)，通過(guò)分析計(jì)算得到：?jiǎn)尉€程情況下，針對(duì)分配而言，Node的效率提升了22.61%，針對(duì)釋放而言，Node的效率降低了18.94%；多線程情況下，針對(duì)分配而言，Node的效率提升了13.80%，針對(duì)釋放而言，Node的效率降低了1.20%.

3) 對(duì)小型對(duì)象分配器適配與Map容器的測(cè)試，實(shí)現(xiàn)一個(gè)Small Object Alloator類(lèi)型，內(nèi)部通過(guò)Small Object Pool來(lái)實(shí)現(xiàn)分配釋放，通過(guò)Map的構(gòu)造函數(shù)，將Small Object Allocator適配到Map中，Map節(jié)點(diǎn)的分配釋放調(diào)用Small Object Pool的Allocate/Deallocate接口；同理實(shí)現(xiàn)一個(gè)New Allocator類(lèi)型，內(nèi)部通過(guò)New/Delete實(shí)現(xiàn)分配釋放接口，也通過(guò)構(gòu)造函數(shù)映射到Map中；利用系統(tǒng)提供的分配器類(lèi)型來(lái)做對(duì)比.單線程測(cè)試：對(duì)三個(gè)Map分別進(jìn)行插入100 000個(gè)數(shù)據(jù)；多線程測(cè)試：對(duì)三個(gè)Map在一定時(shí)間內(nèi)循環(huán)插入和清空Map數(shù)據(jù).表3為適配Map的測(cè)試數(shù)據(jù)，對(duì)于單線程而言，相對(duì)于Default提升了48.30%，相對(duì)于New提升了54.50%；對(duì)于多線程而言，相對(duì)于Default而言提升了35.90%，相對(duì)New而言提升了33.10%.

表1　小型對(duì)象分配器測(cè)試數(shù)據(jù)(μs)

表2　哈希表測(cè)試數(shù)據(jù)(μs)

表3　小型對(duì)象分配器適配Map測(cè)試數(shù)據(jù)(μs)

3.2可回收變長(zhǎng)內(nèi)存池性能測(cè)試和分析

給定一組帶分配大小的數(shù)組，從1～10 000，4個(gè)線程，5 000個(gè)插入刪除動(dòng)作，然后用變長(zhǎng)內(nèi)存池分配給一個(gè)指針數(shù)組存儲(chǔ)，釋放再分配，循環(huán)20次得到測(cè)試數(shù)據(jù)結(jié)果；利用Malloc來(lái)開(kāi)辟對(duì)應(yīng)字節(jié)的內(nèi)存，分配給另外一個(gè)指針數(shù)組存儲(chǔ).相同條件下，對(duì)比系統(tǒng)的分配和釋放函數(shù)消耗的時(shí)間.測(cè)試數(shù)據(jù)見(jiàn)表4，通過(guò)計(jì)算分析可知：RecycleLitePool相對(duì)于系統(tǒng)New而言提升了13.84%.

表4　可回收變長(zhǎng)內(nèi)存池測(cè)試數(shù)據(jù)(ms)

3.3只分配不釋放內(nèi)存池性能測(cè)試和分析

新建一個(gè)池結(jié)構(gòu)，alloc為內(nèi)存池接口，利用池內(nèi)的空間每次分配4字節(jié)大小，分配10 000次；作為對(duì)比，利用系統(tǒng)調(diào)用New函數(shù)來(lái)每次分配4字節(jié)，50 000次的申請(qǐng)動(dòng)作時(shí)間統(tǒng)計(jì).測(cè)試記錄的數(shù)據(jù)見(jiàn)表5，通過(guò)計(jì)算分析可知：StagepPool相對(duì)系統(tǒng)New而言提升了90.80%.

表5　分配不釋放內(nèi)存池測(cè)試數(shù)據(jù)(μs)

4結(jié) 論

1) 通過(guò)分析現(xiàn)有的搜索引擎，得到了哈希表的插入刪除、緩存的更新和文檔的更新模塊、查詢結(jié)果返回三個(gè)場(chǎng)景.根據(jù)三個(gè)場(chǎng)景的特點(diǎn)分別設(shè)計(jì)了可回收定長(zhǎng)內(nèi)存池、可回收變長(zhǎng)內(nèi)存池和只分配不釋放內(nèi)存池三種內(nèi)存池.

2) 采用系統(tǒng)默認(rèn)的內(nèi)存管理函數(shù)malloc/free、new/delete，分析函數(shù)中各種情景的因素，在堆上分配和釋放內(nèi)存增加了開(kāi)銷(xiāo).設(shè)計(jì)的內(nèi)存池應(yīng)用到搜索引擎系統(tǒng)，優(yōu)化了系統(tǒng)內(nèi)部?jī)?nèi)存的管理，提升了搜索速度.對(duì)設(shè)計(jì)的三個(gè)內(nèi)存池的進(jìn)行測(cè)試，并與系統(tǒng)默認(rèn)的內(nèi)存分配器對(duì)比，其效率分別提升了70.20%，13.84%，90.80%.

參 考 文 獻(xiàn)：

[1]戴春燕,徐智文.對(duì)C++中Malloc/Free和New/Delete的探討[J].包鋼科技,2009(35):59.

DAI Chunyan,XU Zhiwen.Discussion of Malloc/Free and New/Delete in C++[J].Science & Technology of Baotou Steel (Group)Corporation,2009(35):59.

(in Chinese)

[2]李倩,潘敏學(xué),李宣東.內(nèi)存泄漏檢測(cè)工具與評(píng)估方法[J].計(jì)算機(jī)科學(xué)與探索,2010(1):29.

LI Qian,PAN Minxue,LI Xuandong.Benchmark of Tools for Memory Leak[J].Journal of Frontiers of Computer Science and Technology,2010(1):29.

(in Chinese)

[3]王小銀,陳莉君.Linux 內(nèi)核中內(nèi)存池的實(shí)現(xiàn)及應(yīng)用[J].西安郵電學(xué)院學(xué)報(bào),2011(4):40.

WANG Xiaoyin,CHEN Lijun.Implementation and Application of the Memory Pool in Linux Kernel[J].Journal of Xi’an University of Posts and Telecommunications,2011(4):40.(in Chinese)

[4]曲衛(wèi)華,王群.搜索引擎原理介紹與分析[J].電腦知識(shí)與技術(shù),2006(6):113.

QU Weihua,WANG Qun.Introduction to and Analysis of Search Engine Principle[J].Computer Knowledge and Technology，2006(6):113.(in Chinese)

[5]段兵營(yíng).搜索引擎中網(wǎng)絡(luò)爬蟲(chóng)的研究與實(shí)現(xiàn)[D].西安：西安電子科技大學(xué),2014.

DUAN Bingying.Study and Design of Web Crawler in A Search Engine[D].Xi’an:Xidian University,2014.

(in Chinese)

[6]郭丙軒,張京莉,張志超.基于內(nèi)存池的空間數(shù)據(jù)調(diào)度算法[J].計(jì)算機(jī)工程，2008,34(6):63.

GUO Bingxuan,ZHANG Jingli,ZHANG Zhichao.Algorithm for Spatial Data Scheduling Based on Memory Pool[J].Computer Engineering,2008,34(6):63.(in Chinese)

[7]劉濤,聶曉峰,荊繼武,王躍武.基于小型對(duì)象分配技術(shù)的GTNetS蠕蟲(chóng)仿真內(nèi)存管理[J].中國(guó)科學(xué)院研究生學(xué)報(bào),2012,29(1):131.

LIU Tao,NIE Xiaofeng,JING Jiwu,WANG Yuewu.Memory Management in Worm Simulation Based on Small Object Memory Allocation Technique on The GTNetS[J].Journal of Graduate University of Chinese Academy of Sciences,2012,29(1):131.

(in Chinese)

[8]郭旭峰,于芳,劉忠立.基于哈希表的高效存儲(chǔ)器內(nèi)建自修復(fù)方法[J].電子學(xué)報(bào),2013(7):1371.

GUO Xufeng,YU Fang,LIU Zhongli.An Efficient Memory Built-in Self-Repair Method Based on Hash Table[J].Acta Electronica Sinica,2013(7):1371.

(in Chinese)

[9]賴(lài)祥芳.選擇合適的STL容器[J].數(shù)字技術(shù)與應(yīng)用,2015(9):177.

LAI Xiangfang.Selecting The Appropriate STL Containers[J].Digital Technology and Application,2015(9):177.(in Chinese)

[10]ALEXANDRESCU A.Modern C++ Design:Generic Programming and Design Patterns Applied[M].Boston:Addison-Wesley Professional,2001.

[11]ROBERT W P,Luka,Wai Lamb.Efficient In-Memory Extensible Inverted File[J].Information Systems,2007(32):733.

(責(zé)任編輯、校對(duì)張立新)

Design and Implementation of Memory Pool Under High Concurrent Search System

LUZhaopan,LIUPingping,LUYing

(School of Computer Science and Engineering,Xi’an Technological University,Xi’an 710021,China)

Abstract:In order to quickly and accurately return the information to the user after the keywords are entered,and to effectively reduce the effect on the performance of the program when the search system allocates and deallocates memory frequently under the high concurrency,the Recoverable Fixed Length Memory Pool,Recoverable Variable Length Memory pool and Allocate Not Free Memory Pool were designed.A according to the different scenes features of the search engine.The result shows that,compared with the default system memory allocator,the efficiency of the Recoverable Fixed Length Memory Pool efficiency is increased by 70.20%,the efficiency of the Recoverable Variable Length Memory Pool is increased by 13.84% and the efficiency of the Allocate Not Free Memory Pool is increased by 90.80%.

Key words:high concurrency;search engine;memory pool;distributor

文獻(xiàn)標(biāo)志碼:中圖號(hào)：TP393A

文章編號(hào)：1673-9965(2016)03-0187-07

作者簡(jiǎn)介：陸兆攀(1991-)，男，西安工業(yè)大學(xué)碩士研究生.通訊作者：劉萍萍(1971-)，女，西安工業(yè)大學(xué)副教授，主要研究方向?yàn)槿斯ぶ悄?E-mail：Liupp@163.com.

收稿日期：2015-11-26

DOI:10.16185/j.jxatu.edu.cn.2016.03.004

基金資助：陜西省科技廳項(xiàng)目資助(2013K13-04-07);陜西省教育廳自然科學(xué)專(zhuān)項(xiàng)(2013JK1158)