應對海量數(shù)據(jù)檢索：分布式局部索引的架構

張滇 岳磅 江小燕 毛睿

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

關鍵詞： 分布式索引； 局部索引； 全局索引； 海量數(shù)據(jù)

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

0 引言

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

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

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

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

1 相關工作

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

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

2 理論及分析

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

2.1 實現(xiàn)全局索引的關鍵步驟

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

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

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

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

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

磁盤讀取、網(wǎng)絡傳輸?shù)炔皇潜疚难芯康闹攸c。本文主要的關注點在于數(shù)據(jù)的處理過程，全局索引架構對數(shù)據(jù)的處理主要是在中間節(jié)點上完成的。假設：

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

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

C.最終的交集里面有R個數(shù)據(jù)項。

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

假設：

D.桶里面等待排序的數(shù)據(jù)項數(shù)量為R'。

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

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

2.2 實現(xiàn)局部索引的關鍵步驟

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

⑴ 用戶提交檢索條件，中間節(jié)點將檢索條件發(fā)到每一個索引節(jié)點上；

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

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

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

E.分布式信息檢索系統(tǒng)中有N個索引節(jié)點；

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

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

局部索引架構索引節(jié)點所執(zhí)行的操作與全局索引架構整個系統(tǒng)所執(zhí)行的操作相同，參考2.1小節(jié)的分析，可以將局部索引架構索引節(jié)點的計算操作次數(shù)tli表示如下：

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

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

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

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

G.中間節(jié)點核心線程數(shù)目為L。

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

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

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

tlm3=M*（N-1）

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

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

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

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

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

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

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

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

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

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

2.4 數(shù)據(jù)擴展和索引架構的選擇

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

以上分析看似合情合理，但從另一個角度來考慮的話，就會發(fā)現(xiàn)問題并非如此。我們把局部索引架構索引節(jié)點的個數(shù)N考慮進來，那么關于執(zhí)行時間Y的方程就有兩個自變量（n與N）。由于局部索引架構索引節(jié)點的計算操作與全局索引架構中間節(jié)點的計算操作相同，取N為最優(yōu)值，那么當數(shù)據(jù)規(guī)模變?。╪的值變?。┑揭欢ǖ脑葧r，N一定會變?yōu)?，那么此時因為只有一個索引節(jié)點，全局索引架構與局部索引架構就完全的相同了，因此計算的執(zhí)行時間也必然相同。

通過上面的分析可以發(fā)現(xiàn)，在N取最優(yōu)值的情況下，當全局索引架構與局部索引架構的執(zhí)行時間相同時，局部索引架構就會退化為全局索引架構。

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

3 結束語

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

參考文獻：

[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