應對海量數據檢索：分布式局部索引的架構

張滇 岳磅 江小燕 毛睿

摘 要： 通過理論分析對全局和分布式索引架構進行了比較，分析了分布式全局索引架構所能夠應對的數據規模的上界和分布式局部索引架構在特定數據規模下相應最優的機群規模等。可以證明，在海量數據背景條件下，由于需要求交集的查詢結果數據量過大，會導致全局索引架構在查詢結果求交集階段處理時間過長，以致信息檢索系統不能滿足用戶對系統響應時間的需求，因此局部索引架構會成為在面對海量數據時信息檢索系統的必然選擇。

關鍵詞： 分布式索引； 局部索引； 全局索引； 海量數據

中圖分類號：TP392 文獻標志碼：A 文章編號：1006-8228（2013）08-01-04

0 引言

信息檢索系統（IRS：Information Retrieval System）已成為人們日常生活和學習中經常會使用到的工具（如文獻檢索、網頁檢索等）。隨著數據規模的增大，信息檢索系統開始采用分布式系統架構來解決所面臨的大數據問題。由此而引出的索引如何在分布式系統之中組織與分布的問題即是分布式索引架構問題。全局索引架構（Global Index）與局部索引架構（Local Index）是兩種最主要的分布式索引架構，幾十年以來，大量的研究和實驗對它們的優缺點進行了詳細分析與比較。

全局索引架構針對整個數據集建立一個統一的索引，然后根據索引關鍵字的順序將索引切分成多個索引片段，每個索引片段存放在一個單獨的索引節點上。全局索引架構在執行一個檢索時所需要訪問的索引節點相對較少，但這也導致其每次讀取的數據量較大；由于數據的處理需要集中在中間節點上進行，全局索引架構網絡傳輸的數據量更大；所有的數據處理操作集中在中間節點上執行，在面對海量數據時這將成為全局索引架構不能滿足用戶需求的關鍵瓶頸；由于是針對整個數據集建立倒排索引，因此在全局索引架構在面對索引的更新與增量時相比局部索引架構難度更大。

分布式局部索引架構即是將大的數據集隨機或者按照一定的規則劃分成多個小數據集，針對每個小數據集建立單獨的索引塊，一般一個索引塊會存放在一個單獨的索引節點上。局部索引架構的每個索引節點獨立的完成檢索，因此具有較好的容災容錯性能；在索引更新及增量時，由于其每個索引節點相互獨立，因此更新與增量的影響范圍較小；由于索引節點返回給中間節點的數據都是經過處理的，因此相比全局索引架構而言局部索引架構網絡傳輸的數據量更小。局部索引架構的缺點在于檢索的開銷較大，其每一個檢索條件都會被發送到所有索引節點上去執行。

混合索引架構結合了全局索引架構與局部索引架構的優點，但高度的數據冗余造成了極大的數據膨脹，在大多數的應用當中這一點通常無法被用戶接受；同時副本數量過多也導致數據的更新與增量難度更大。由于混合索引架構的明顯缺陷，我們在后面的文章中將不再對其進行分析。

1 相關工作

分布式索引架構的研究從上世紀九十年代初開始，但早期有關分布式索引架構[1，2，5，7，9]的研究由于存在數據量較少、硬件環境限制、應用場景不同等問題，導致大家的研究結果有很大的分歧，對于當前海量數據背景下分布式索引架構研究的參考意義不大。Cambazoglu等在2006年通過實驗結果[8]說明局部索引架構有較快的響應速度，而全局索引架構的吞吐率較好，這和我們的觀點是一致的，但實驗的結果是在較少的數據集上取得的（30GB），因此沒有說明全局索引架構在響應時間上問題的嚴重性。

文獻[3，4，7]等都是針對全局索引架構進行優化，他們或者考慮如何減少網絡傳輸的數據量[3，6]，或者使用新的數據處理方式[4]，但都沒有從根本上解決全局索引架構的時間延遲問題，而且用于實驗的數據量都相對偏小，沒有以海量數據為應用背景。

2 理論及分析

在介紹本文方法之前，先說明將用到的數據結構。倒排索引記錄是Key-Value結構的，其中Key是檢索關鍵字，Value是由數據項組成的有序集合。數據項的格式為（ID，score），其中ID表示某個檢索對象的編號（例如文檔編號），該檢索對象中含有檢索關鍵字Key，Value中的數據項都是依據ID排序的；score表示檢索關鍵字Key在該檢索對象中相關性的大小。實際應用之中檢索關鍵字在一個檢索對象中的相關性信息比較復雜，我們在模擬實驗中簡單的使用一個浮點型的非負數值score表示。

2.1 實現全局索引的關鍵步驟

在全局索引架構下對用戶檢索的處理步驟如下。

⑴ 用戶提交檢索條件，檢索條件中含有一個或多個檢索關鍵字Key，中間節點分析檢索條件并將各個不同的檢索關鍵字Key發到其相對應的索引節點；

⑵ 收到檢索關鍵字Key的索引節點即在倒排索引中檢索對應的倒排記錄并將檢索結果返回給中間節點，檢索結果即是倒排記錄中Value；

⑶ 中間節點會收到多個檢索結果（Value），這些檢索結果都是以ID排序的數據項集合，中間節點以ID對這些數據項集合求交集，交集中數據項的相關性值（score）是原來各個集合中有相同ID的數據項的相關性值（score）之和；

⑷ 檢索對象返回給用戶時一般需要分頁，中間節點依據相關性值（score）的大小對交集中的數據項進行排序，相關性值（score）大的數據項對應的檢索對象會先返回給用戶，具體返回的檢索對象需要依據數據項中的ID查找得到。

磁盤讀取、網絡傳輸等不是本文研究的重點。本文主要的關注點在于數據的處理過程，全局索引架構對數據的處理主要是在中間節點上完成的。假設：

A.在一個用戶檢索里面會有m個檢索關鍵字（k1、k2…km）；

B.每個關鍵字ki所對應的Value是由ni個數據項組成的串，設；

C.最終的交集里面有R個數據項。

根據假設，可知中間節點上求交集過程的計算操作次數約為n。如果對交集依據相關性大小進行全排序的話，其時間復雜度為o（Rlog2R），但是一般情況下R較大，而用戶可能只需要查看最相關的幾個文檔，這樣我們既可以將相關性值（score）大的結果找出來并先返回給用戶，而不需要對全部的結果集進行排序。具體操作上可以在求交集的過程中將相關性值（score）大于某個閾值的數據項存在一個桶里，求交集完成后只要先將桶里面的數據項依據其相關性值（score）的大小進行排序即可，桶里面的數據項數量是應用通過閾值控制的，一般遠小于R。閾值一般由數據的規模和每次返回給用戶的檢索對象數量決定。

假設：

D.桶里面等待排序的數據項數量為R'。

則可以將全局索引架構中間節點的計算操作次數tgm表示為：tgm=m+n+R'log2R'。

關鍵字的個數m大多數情況下都是個位數，相比較而言可以忽略不計；在海量數據背景下，n的大小可能是幾千萬、幾億，而存在桶里等待排序的數據項的個數一般只有幾百、幾千，因而n要遠大于R'log2R'，因此也可以簡單地認為：tgm≈n。

2.2 實現局部索引的關鍵步驟

局部索引架構對用戶檢索的處理過程相比全局索引架構而言，在求交集等關鍵步驟上實現了并行化，其具體的處理過程如下。

⑴ 用戶提交檢索條件，中間節點將檢索條件發到每一個索引節點上；

⑵ 局部索引架構索引節點所執行的操作與全局索引架構整個系統所執行的操作相同，包括檢索條件的分析、檢索關鍵字查詢、檢索結果求交集、根據相關性值（score）對交集排序等，只不過這些操作都是本地執行，最后索引節點將按相關性值排序后的檢索結果返回給中間節點；

⑶ 中間節點接收各個索引節點的檢索結果，這些檢索結果都是以相關性值大小排序后的數據項集合，中間節點依據相關性值（score）的大小對這些數據項集合進行歸并排序，同樣，相關性值大的數據項對應的檢索對象將優先返回給用戶。

除使用2.1小節的假設條件外，這里再補充兩個假設：

E.分布式信息檢索系統中有N個索引節點；

F.每次返回給用戶的結果集中數據項的個數為M。

這里需要說明的一點是，M的值并不是分頁后一個頁面所展示的檢索對象的數量，一般而言M是一個頁面所展示檢索對象數量的倍數，比如10倍，用于應對用戶可能的翻頁，而且M小于R'。

局部索引架構索引節點所執行的操作與全局索引架構整個系統所執行的操作相同，參考2.1小節的分析，可以將局部索引架構索引節點的計算操作次數tli表示如下：

該表達式不一定準確，因為不可能每個索引節點在處理檢索時的時間復雜度都是一樣的，實際上由于局部索引架構中數據的劃分是隨機的，具有較好的負載均衡，雖然會有偏差，但是可以接受。

與全局索引架構一樣，局部索引架構的索引節點也可以設置閾值，從而只需對桶里的R'個數據項進行排序，索引節點在給中間節點返回數據時，不必返回全部R'個數據項，只需返回前M個相關性值（score）較大的數據項即可。中間節點會收到N個數據項集合，每個集合M個元素，同樣，中間節點也只需歸并求出前M個相關性值（score）較大的數據項即可。

中間節點使用二路歸并算法對N個數據項集合進行歸并排序，因為多線程并行處理時二路歸并是最優的。局部索引架構中間節點的計算操作次數tlm1可以表示如下：

tlm1的計算表達式是在線程并發度足夠大的情況下取得的，實際的線程并發度是由中間節點CPU總的核心線程數目決定的，假設：

G.中間節點核心線程數目為L。

中間節點共需要運行N-1個線程，則更為精確計算操作次數tlm2可以表示如下：

在實際計算中，計算處理程序獨占整個CPU是最優的情況，這種情況很難達到，所以tlm2的表達式中增加了一個系數eL和一個常數因子bL，并且有eL?1成立。具體eL和bL的值可以通過實驗數據計算得到。

由于系統吞吐率、數據到達中間節點有先后等因素，可以考慮在中間節點上不使用多線程并行，而只是簡單的串行執行即可，這樣得到的中間節點計算操作次數tlm3可以表示如下：

tlm3=M*（N-1）

由于索引節點對檢索的處理都是并行的，因此只需考慮單個索引節點即可，結合中間節點上計算操作的執行次數，則局部索引架構下整個計算過程的計算操作次數tltx可表示如下：

tltx=eltxtli+tlmx+bltx（x=1，2，3）

當tli=tlmx時，即中間節點與索引節點的計算操作次數相同時，但是由于二者計算過程的具體實現不同導致實際測得的計算時間是不同的，因此引入上述表達式中的平衡因子elt以及常數blt。平衡因子elt及常數blt可以結合實際的測量數據，利用線性回歸模型求出來，在2.3小節有更為詳細的分析。

分析比較全局索引架構與局部索引架構的計算操作，可以發現在海量數據背景條件下，局部索引架構明顯優于全局索引架構。同時也應該看到，針對同一個檢索，局部索引架構使用的索引節點更多，一般情況下局部索引架構相比全局索引架構在處理一個檢索時的開銷更大。

2.3 分析局部索引的簇的大小

將局部索引架構的計算操作次數tlt看成N的函數，即：

以執行時間復雜度最小值為目標，對于給定的n值（數據規模），可以求出最優的N值（機群規模），該結論對于在具體應用當中確定分布式機群的規模有參考價值。

對于平衡因子eltx（x=1，2，3）需要結合試驗數據利用線性回歸模型求解，這里先給出具體的回歸模型。實驗時取tlmx=tli（x=1，2，3），即局部索引架構索引節點與中間節點的計算操作次數相同，分別將二者的實際執行時間記為tlmx（x=1，2，3）和Tli，elmx是Tlmx與tlmx的相關系數（x=1，2，3），eli是Tli與tli的相關系數，bli和blmx（x=1，2，3）都是常數因子，則回歸模型可表示如下（x=1，2，3）：

根據條件tlmx=tli（x=1，2，3），由上面的數學模型可得：

計算機的實際計算時間和算法時間復雜度的關系是線性的，所以文章中使用的是線性回歸模型。

2.4 數據擴展和索引架構的選擇

僅就計算的執行時間分析，可以看出在海量數據背景下（即n的值較大時），局部索引架構在計算執行時間上相對于全局索引架構有明顯的優勢；但當數據量較小時（即n的值較小時），這個優勢并不明顯；可以預見當n變小到一定程度時，全局索引架構與局部索引架構的執行時間數據就會相同，這時n的值對于根據數據規模的大小決定采用哪一種索引架構具有一定的參考價值；當n的值再變小時，局部索引架構的表現可能會比較差。

以上分析看似合情合理，但從另一個角度來考慮的話，就會發現問題并非如此。我們把局部索引架構索引節點的個數N考慮進來，那么關于執行時間Y的方程就有兩個自變量（n與N）。由于局部索引架構索引節點的計算操作與全局索引架構中間節點的計算操作相同，取N為最優值，那么當數據規模變小（n的值變小）到一定的曾度時，N一定會變為1，那么此時因為只有一個索引節點，全局索引架構與局部索引架構就完全的相同了，因此計算的執行時間也必然相同。

通過上面的分析可以發現，在N取最優值的情況下，當全局索引架構與局部索引架構的執行時間相同時，局部索引架構就會退化為全局索引架構。

實際應用之中的情況可能會不同，計算執行時間的最優值并不是用戶最為重要的目標，由于全局索引架構相對比較節省資源，所以在滿足應用需求的情況下用戶可能更愿意使用全局索引架構。

3 結束語

本文以海量數據為背景條件，研究了信息檢索系統中分布式索引組織架構問題。通過分析說明了面對海量數據時分布式局部索引架構是信息檢索系統的必然選擇，分布式全局索引架構由于不可接受的時間延遲問題而被排除。本文對海量數據背景下分布式索引架構問題的研究成果不僅僅適用于一般信息檢索系統，對于數據庫的多條件聯合查詢、相似性搜索中的度量空間索引等也有一定的參考意義，雖然應用環境與具體的問題都不相同，但索引的分布式架構組織問題是相同的。未來的工作我們希望可以在完善的實驗環境下將分布式索引架構的其他關鍵因素納入考慮范圍，例如磁盤讀取、網絡傳輸等。由于全局索引架構在檢索成本上占有優勢，我們下一步的工作還包括優化全局索引架構的處理模式，目標是通過優化滿足用戶的需求。本文所有的討論與實驗都是基于現有的軟、硬件環境，相信在未來，隨著計算機軟、硬件技術的發展，我們解決這些問題將會更加的便利。

參考文獻：

[1] RIBEIRO-NETO， B. AND BARBOSA， R. Query performance for tightly coupled distributed digital libraries.In Proceedings of the ACM Digital Libraries， Pittsburgh， PA， I. Witten， R. Akscyn， and F. M. S. III， Eds. 1998. ACM Press，182-190

[2] A. MacFarlane， J. McCann， and S. Robertson. Parallel search using partitioned inverted files. In Proceedings of the 7th International Symposium on String Processing and Information Retrieval， pages 209-220， La Coruna， Spain， September 2000. IEEE Computer Society.

[3] Zhang J， Suel T. Optimized inverted list assignment in distributed search engine architectures[C]. Parallel and Distributed Processing Symposium， 2007. IPDPS 2007. IEEE International. IEEE，2007：1-10

[4] Moffat A， Webber W， Zobel J， et al. A pipelined architecture for distributed text query evaluation[J]. Information Retrieval，2007.10（3）：205-231

[5] Badue C， Baeza-Yates R， Ribeiro-Neto B， et al. Distributed query processing using partitioned inverted files[C]. Proc. SPIRE，2001：10-20

[6] Kayaaslan E， Aykanat C. Efficient query processing on term-based-partitioned inverted indexes[R]. Technical Report BU-CE-1102， Bilkent University， Computer Engineering Department， 2011. Also available at： http：//www. cs. bilkent. edu. tr/tech-reports，2011.

[7] Xi W， Sornil O， Luo M， et al. Hybrid partition inverted files：Experimental validation[M]. Research and Advanced Technology for Digital Libraries. Springer Berlin Heidelberg，2002：422-431

[8] Cambazoglu B B， Catal A， Aykanat C. Effect of inverted index partitioning schemes on performance of query processing in parallel text retrieval systems[M] Computer and Information Sciences-ISCIS 2006. Springer Berlin Heidelberg，2006：717-725

[9] Tomasic A， Garcia-Molina H. Performance of inverted indices in shared-nothing distributed text document information retrieval systems[C].Parallel and Distributed Information Systems， 1993. Proceedings of the Second International Conference on. IEEE，1993：8-17