一種改進的分布式搜索引擎模型

錢立兵，季振洲，吳 昊

(哈爾濱工業大學計算機科學與技術學院，150001哈爾濱)

大規模文檔數據使得分布式引擎的檢索和查詢都面臨性能的壓力，為了提高分布式搜索模型的性能，在索引合并和查詢算法方面，很多學者開展了研究工作.針對索引合并，Heinz等［1］討論了合并的索引構建方法及其相對于排序方法的優勢;Büttcher等［2］研究了 Logarichmic 合并算法并驗證該算法對于索引合并的高效性;Hao等 提出對索引壓縮和查詢預處理來優化文檔排序.關于查詢算法，document-at-a-time(DAAT)和termat-a-time(TAAT)是兩種經典的算法［4-5］;Turtle等［6］根據詞項的最大得分策略(max score)優化了查詢過程;Strohman等［7］使用預處理剪裁前k個最好結果的得分下界改進查詢效率.然而，這些改進均建立在傳統模型基礎上，并沒有改變傳統模型自身的一些局限，如宏觀上索引文檔結構劃分的無序性，用戶全局性查詢的盲目性以及系統擴展性不強等.

本文優化了傳統分布式搜索模型的結構，按照文檔主題對索引文檔進行分類，提出高效、可擴展的并行分布式模型結構;以優化模型為基礎，改進索引倒排表結構，并利用MaxScore策略，對堆排序進行優化，設計出針對索引節點的并行查詢算法.

1 傳統分布式搜索引擎

1.1 分布式搜索模型

分布式搜索引擎有沙漏模型、Map/Reduce模型、P2P網絡模型等，其中，沙漏模型應用最為廣泛.圖1是經典的沙漏模型［8］，系統包含前端應用展現層(processing of front，PF)、結果匯聚層(merge)和獨立引擎層(search engine，SE).

圖1 分布式引擎的沙漏模型結構

PF層主要處理不同業務需求，每一類應用都會根據該應用特征解析query，然后訪問merge層.merge層起到承上啟下作用，接受PF層傳遞的多個請求，向SE層多個獨立引擎發送;合并各個引擎請求結果后發送給PF層.SE層是分布式引擎系統中的基礎層，承擔海選、相關性、精選等過程，是系統搜索核心過程.

1.2 分布式查詢過程

PF層接收用戶請求(query)，經過詞干提取、用戶行為、查詢意圖［10-11］分析得到若干個特征詞{q1，q2，…，qm}，再由 merge 層將這些特征詞轉發到SE層的各個獨立引擎.每個獨立引擎根據特征詞對其倒排表進行海選、普通排序、精排，堆排序得到各自Top N結果.merge層根據SE層的各個獨立引擎所得到結果集，進行除重、過濾、相關性排序得到最終Top N個結果，返回用戶.若獨立引擎數為n，特征詞數目為m，則用戶一次請求在merge層會產生獨立引擎查詢次數m*n．

這種分布式查詢過程使得整個系統處于繁忙狀態.高并發用戶請求，使得merge層的請求任務與結果合并任務成倍增加;同時索引節點的增加，也會導致merge層增加負載任務.因此，如何提高系統擴展性，適應高并發查詢是搜索引擎研究的關鍵目標之一.

2 并行分布式搜索

2.1 并行模型提出

為了克服沙漏模型的不足，本文根據文檔主題對文檔集進行分類，建立分類索引.文檔主題的分類方法是根據用戶的請求，提取用戶查詢特征詞，以特征詞代表文檔，按照二元分類方法的NN算法［12］，計算各種類別模式下特征詞的得分，與最低閥值比較，保留大于最低閥值的類別作為分類結果.特征詞的提取按照文獻［13］的詞項權重為

式中:wt，d為詞 t在文檔 d 中權重;tft，d為詞 t在文檔d中的詞頻;N為文檔總數;dft為出現t的所有文檔數．

按照主題分類使得有些文檔可能屬于多個類別(跨類文檔)，對于這種跨類文檔，可以采用簡單的URL近似匹配，前提要對各個類別保存主體的URL前綴，具體做法是對跨類文檔的URL分別匹配所屬類別的URL集，保留URL匹配的最大文檔，確定跨類文檔最終只屬于一個類別，按照單個類別建立索引.

圖2是基于傳統的分布式引擎所設計的可擴展的分布式模型.在merge層，按照文檔主題建立1～M個類別的索引集，每個merge節點管理一類索引節點，例如merge1節點管理索引Index(1，1)～Index(1，c1)節點，使得查詢請求所訪問的索引節點具有針對性.

圖2 具有分類索引結構的分布式模型結構

依據圖2建立的模型，分類查詢過程如下:當應用層得到用戶查詢請求query后，經過分詞得到查詢關鍵詞Keyword，由Keyword確定待查詢的merge節點，被觸發的merge節點查詢本類索引節點，查找的結果返回到merge層，merge層合并本類索引節點的結果返回給應用層.

該模型的查詢類別識別方法為:首先，應用層需要保存merge層各個類別模式的特征詞和近義詞，匹配用戶查詢Keyword;然后，應用層根據識別類別向所屬的所有類別的merge層發送請求，被觸發的merge節點再按照本節點的文檔類別訪問獨立引擎層的索引節點.如圖2所示，merge層只是被動接收應用層發送的請求，識別用戶過程由應用層負責，這樣能夠提早識別出類別，避免全局查找.

2.2 索引倒排表的改進

上述建立的并行模型，對于倒排記錄經常發生變化的文檔集合，需要更好的索引結構.索引合并是檢索系統的重要任務.一種優化歸并的方法是采用跳表(skip list)［14］策略能夠獲得很好的性能，即在構建索引時構建一個跳表，當跳表指針的目標項小于另一個表的當前比較項時可以采用跳表指針直接跳過.如圖3所示，對 t1=“Information”和t2=“Retrieval”進行合并，假如t1的指針移到17，t2的指針移到65，較小項為17．此時并不需要移動t1，而是檢查跳表指針，此時為30，仍然比65小，t1直接跳到30，即跳過了21和24．

圖3 帶有跳表指針的倒排記錄表

倒排記錄經常發生變化的文檔，使得倒排記錄表指針頻繁發生變化，從而喪失了跳表的性能.為了解決跳表結構的性能問題，對于較長的倒排表的詞項設計一個位圖(Bitmap)結構(考慮Bitmap結構本身的內存開銷，較短的記錄表無須設計Bitmap).Bitmap結構的存儲順序號與文檔ID對應，若文檔存在倒排記錄表中，對應位標記為1，否則為0.例如:ID=1 027的文檔記錄在第1 027 bit存儲位，即存儲在Bitmap結構的第128 B的第3位(1 027=128*8+3).

如圖 4所示，對 t1=“Information”、t2=“Retrieval”和 t3=“Organization”，對較長倒排列表的詞項t1和t2建立Bitmap，t3鏈表長度較短無需建立Bitmap，先對t1和t2的Bitmap合并保存到中間的Bitmap merge中，再遍歷t3得到記錄表的文檔號，添加到Bitmap merge，即得到合并結果.

圖4 帶有Bitmap結構的倒排記錄表

本文針對較長記錄表的選擇依據設計了兩種方法:1)采用固定常數γ，記錄大于γ時建立Bitmap;2)設計一個可調參數λ(0＜λ＜1)，設文檔集數目N，L(t)為詞項t的倒排表長度，當L(t)＞λN時，建立Bitmap.兩種方法中γ或λ需要通過根據內存容量情況去選擇．

對于k個長度為L的記錄表合并，普通算法采用多路合并，時間復雜度為O(L*k*lg k)．采用Bitmap策略時，滿足條件的倒排記錄表建立Bitmap的時間復雜度為O(k*t)，即k個Bitmap按位運算時間開銷(t為兩個Bitmap合并開銷，通常為常量)，提高了查詢速度.空間上需要對每個較長記錄表設計 N位的 Bitmap，即建立O(r*N/8)(r為滿足建立Bitmap條件的記錄表個數).在查詢過程中，對多個查詢詞的請求，先對詞項的Bitmap合并(對于不存在Bitmap結構的詞項，按照正常的遍歷方式得到文檔號信息，然后加入到Bitmap結構中).在動態更新文檔時，只需要添加或刪除Bitmap中對應的文檔號位置.較少的內存空間開銷所帶來倒排表合并的速度優勢很重要，對較長鏈表直接進行位圖合并，能夠較好地提高查詢速度.在實際應用中，根據內存開銷允許的程度去選擇γ或λ，對倒排記錄表選擇建立Bitmap結構，能夠優化系統性能.

2.3 并行查詢算法設計

針對文中設計的搜索模型，提出一種優化的并行查詢算法.查詢算法中的評分函數是依據Robertson 等［15］使用的 Okapi BM25.

式中:N為文檔集數量;Nt為包含詞項t的文檔數;ft，d為詞項t在文檔d中出現次數;k1(默認是1.2)用來調節TF的飽和度;b(默認是0.75)用于歸一化文檔長度;ld為文檔d詞條數;lavg為文檔集中所有文檔平均詞條數．

算法中設計3類數據結構:詞項(term)堆用于管理查詢詞項{t1，t2，…，tm}，追蹤每個查詞項項t的下一個文檔;Bitmapmerge結構(位圖結構)用于存儲倒排表合并后文檔ID的存在狀態;result堆用于維護當前找到的Top k個搜索結果．采用線程池(thread pool)分配和管理3類數據結構，每個線程都有獨立的3種結構，線程初始化時構建3類數據結構，3種結構都是隨著當前用戶的查詢詞項加入，查詢結束后清空.

如圖5所示，對于查詢詞集合 queryterms={“computer”，“science”，“technical”}，啟動線程池中的線程1，建立3個元素的term堆，分配一個Bitmap merge，同時分配含Top k的result堆(按得分建立小根堆).term堆中每個詞項連接的文檔按照ID排序，result堆在運行中保存當前最好的k個文檔，根節點是當前第k個最好的文檔，當找到一個新文檔比根節點分數高時，利用新文檔替換根節點，進而調整堆結構.

圖5 線程池結構與并行查詢方法示例

根據turtle和flood的maxscore策略優化查詢過程，式(2)中 TF得分貢獻不超過 k1+1=2.2(k1取默認值1.2)，即詞項總得分不超過2.2lg(N/Nt)．改進的查詢算法采用了此種技術優化查詢過程．

在支撐多核的硬件平臺下，設計thread pool結構管理并行執行的線程.倒排記錄表作為所有查詢線程的公共訪問資源，查找過程不會改變公共資源，因此對倒排列表的訪問本身存在高度并發訪問優點.由于線程本身開啟和切換存在開銷，盡可能使分配的線程任務飽滿，而不是分配過多的任務量輕的線程.

對于搜索引擎業務，設請求任務并發數為n/s，線程最大處理任務數為Cmax，為了避免過多的輕量線程開銷，要求每個線程至少處理任務數為Cmin，線程池最多數目為p(由硬件限制，一般為核數2倍最優)，實際開啟線程數Pnum．當n≤Cmin*p時，Pnum=n/Cmin，即開啟n/Cmin個線程;當Cmin*p＜n≤Cmax*p時，開啟的線程數Pnum=2*p/(Cmin+Cmax);當n＞Cmax*p時，線程處于超負載情況，充分利用硬件資源，開啟Pnum=p個線程．通過實驗測得Cmin=2，Cmax=6，即任務數小于2時，屬于輕量線程;任務數大于6時，屬于超負荷線程．

圖6 對堆排序裁剪的一種多線程并行查詢算法

通過上述計算得到開啟線程數Pnum，得到如圖6所示的MMSH算法，每次處理n個請求queryList［1…n］:每個線程平均處理任務數n/Pnum．每個線程調用改進的堆排序裁減MSH(max score heap)算法處理請求任務，如圖7所示.

圖7 MSH算法

MMSH算法的核心處理是MSH算法，如圖7所示，通過對堆排序的剪裁，在保證結果一致性情況下，優化了查詢性能.MSH算法能夠保證算法的結果與堆排結果一樣，但速度要快很多，這是因為一旦發現某個文檔不可能為前k個結果，立即被忽略.

3 實驗與討論

硬件資源:IBMX360f服務器，16核處理器、16 G內存;通過商業引擎Ha3+hadoop技術，分別構建如圖1的分布式引擎的沙漏模型(Search1)和如圖2改進的分布式引擎(Search2)架構.通過比較改進模型和傳統模型的查詢算法效率和系統吞吐量，說明設計的有效性.

1)實驗環境搭建.為了實驗條件的一致性，兩種結構均使用8個節點服務器.Search1和Search2都使用4個索引節點，2個merge節點，2個PF節點.

2)實驗數據.借助于商業引擎的Hadoop集群抓取得到50 G文檔數據;查詢請求時根據查詢日志，得到1萬查詢query，作為query集.

3)實驗方式.通過腳本程序對query集定時請求系統，模擬用戶訪問，訪問數由實驗進行調節.

4)查詢語法.分類索引建立后，需要額外產生類別屬性category，在應用端識別出本次查詢的category，語法如:category=3＆＆query=”MP3”＆＆hit=10＆＆…，其含義為查詢類別3的merge節點，查詢詞為MP3，用戶感興趣的前10條文檔信息等.

Search 1的merge層采用集中方式，索引按照文檔劃分;Search2進行分類和動態化處理，按照多個節點的非集中方式管理.由于索引結構的不同，導致二者查詢方式很大差異，使得查詢速度相差較大.同時，實驗將要驗證并行查詢算法對高并發任務的有效性.

3.1 merge層負載

為了驗證改進的模型結構，在不同并發請求情況下，對Search1和Search2兩種結構的merge層負載進行試驗.圖8和圖9分別記錄多個并發query的merge層節點的CPU和內存平均開銷，實驗中設置返回用戶Top 100個結果，隨著請求并發數增多，內存和CPU變化明顯.CPU開銷與并發數幾乎是線性增大，Search2的merge節點CPU占用率約為Search1的75%.merge層節點的內存開銷主要對所屬類別索引節點的查詢中間結果的緩存，并發任務越多，Search1和Search2之間的內存開銷相差越大，其原因是未分類Search1使得各個索引節點返回結果數以索引節點數的倍數增大，花費更多內存開銷.

圖9 Search1和Search2在不同并發數query的平均內存占用率

由于傳統分布式模型對各個索引節點查詢結果需要進行多次合并、排序等工作，使得merge成為系統的瓶頸，query的并發數直接影響merge節點性能;而改進分布式模型根據索引類別，按照各類查詢的merge節點處理查詢信息，具有很強的針對性，從而減少merge節點的負載.

3.2 搜索節點的并行查詢性能

為了驗證MMSH算法優越性，實驗中采用Search2模型.由于在倒排表索引不能完全存入內存情況下，TAAT算法不需要磁盤訪問，優勢高于DAAT算法，而文中實驗側重討論此種情況下MMSH算法優勢，為此MMSH算法只與TAAT算法進行比較.在相同的并發用戶請求和多線程執行下，從搜索引擎層的平均搜索時間和吞吐量兩個方面比較二者性能.實驗中兩個重要參數是:線程數p和參數Top k(用戶選取前k個結果，k=10是系統默認值).

圖10中，通過比較MMSH算法和TAAT算法的平均查找時間可以看出，MMSH算法具有明顯的優勢，從圖10可以看出，多線程體現并行查詢的優越性，平均查找時間幾乎隨著線程數目增大，下降趨勢明顯.當線程數達到一定數量時，線程本身存在開銷，如繼續開啟更多線程，會降低系統性能，如實驗中開啟64個線程效果沒有32線程好.這是由于在搜索過程中，改進算法中利用MaxScore排除不必要計算過程，從而提高了查詢速度.

圖11的系統吞吐量是指整個搜索引擎層平均每秒鐘所能夠處理的merge層發送的請求數，而不是單個引擎的吞吐量.對于merge層發送的每一類請求，需要多個搜索節點并行搜索，然后把各種結果匯總到對應的merge節點.從圖9可以看出，在線程數達到32前，多線程技術幾乎能夠得到線性的加速比;TAAT算法在吞吐量方面落后于MMSH算法，體現了MMSH算法優越性.線程數為32時，MMSH算法和TAAT算法的性能優于64個線程數情況，這是由于過多的線程數導致線程開啟和切換的開銷較大.

圖10 搜索引擎層使用TAAT算法和MMSH算法平均查詢時間

圖11 搜索引擎層使用TAAT算法和MMSH算法時系統吞吐量

從圖10、11的Top k，可以看出啟動相同的線程數目，k越大，查詢時間越長，吞吐量越小，并且MMSH算法優于TAAT算法，即系統開銷越大.這是因為用戶Top k中的k選擇，直接影響查詢過程中待計算的文檔得分數量，導致系統性能差異.由于MMSH算法使用maxscore的提前打分策略，同等條件下，可以提高系統性能.

4 結論

1)根據文檔主題特征，對索引進行分類，設計分類查詢方法，解決查詢盲目性.

2)對較長倒排記錄表設計Bitmap結構，有效降低倒排表合并的查詢時間復雜度，實現快速的倒排合并工作.

3)利用maxscore策略和多線程方法，在查詢過程中建立詞項堆、結果堆和Bitmapmerge結構，能夠提前結束查詢打分，從而優化了倒排表查詢算法.

［1］HEINZ S，ZOBEL J.Efficient single-pass index construction for text databases［J］.Journal of the American Society for Information Science and Technology，2003，54(8):713-729.

［2］BüTTCHER S，CLARKE C L A.Indexing time vs.Query time trade-offs in dynamic information retrieval systems［C］//Proceedings of the 14th ACM International Conference on Information and Knowledge Management.New York，NY:ACM，2005:317-318.

［3］HAO Y，SHUAID，TORSTEN S.Inverted index compression and query processing with optimized document ordering［C］//Proceedings of the 18th International Conference on World Wide Web.New York，NY:ACM，2009:401-410.

［4］MANNING C D，RAGHAVAN P，SCHüTZE H.An introduction to information retrieval［M］.New York，NY:Cambridge University Press，2009:124-136.

［5］BüTTCHER S，CLARKE C L A，CORMACK G V.Information retrieval implementing and evaluating search engine［M］.Cambridge，MA:MIT Press，2010:137-173.

［6］TURTLE H，TOMPA F W.Query-evaluation:strategies and optimization［J］. Information Proceeding ＆Mangagement，1995，31(1):831-850.

［7］STROHMAN T，TURTLE H，CROFT W B.Optimization strategies for complex queries［C］//Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York，NY:ACM，2005:219-225.

［8］BARROSO L A，DEAN J，HOLZLE U.Web search for a planet:the google cluster architecture［J］.IEEE Micro，2003，23(2):22-28.

［9］王曉春，李生，楊沐昀，等.查詢會話中的用戶行為分析［J］.哈爾濱工業大學學報，2011，43(5):76-78.

［10］靳巖欽，張敏，劉奕群，等.搜索引擎用戶查詢的廣告點擊意圖分析［J］.哈爾濱工業大學學報，2013，45(1):124-128.

［11］黎玲利，王宏志，高宏，等.XML數據流上Top-K關鍵字查詢處理［J］.軟件學報，2012，114(4):1561-1577.

［12］李曉明，閆宏飛，王繼民.搜索引擎——原理、技術與系統［M］.2版.北京:科學出版社，2012:253-282.

［13］易明.基于 Web挖掘的個性化信息推薦［M］.北京:科學出版社，2010:93-110.

［14］STROHMAN T，CROFT W B.Efficient document retrieval in main memory［C］//Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York，NY:ACM，2007:175-182.

［15］ROBERSTON S，ZARAGOZA H，TAYLOR M.Simple BM25 extension to multiple weight fields［C］//Proceedings of the Thirteenth ACM International Coference on Information and Knowledge Management.New York，NT:ACM，2004:42-49.