應(yīng)對海量數(shù)據(jù)檢索：分布式局部索引的架構(gòu)

張滇 岳磅 江小燕 毛睿

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

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

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

0 引言

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

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

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

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

1 相關(guān)工作

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

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

2 理論及分析

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

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

在全局索引架構(gòu)下對用戶檢索的處理步驟如下。

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

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

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

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

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

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

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

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

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

假設(shè)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

tlm1的計算表達式是在線程并發(fā)度足夠大的情況下取得的，實際的線程并發(fā)度是由中間節(jié)點CPU總的核心線程數(shù)目決定的，假設(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é)合中間節(jié)點上計算操作的執(zhí)行次數(shù)，則局部索引架構(gòu)下整個計算過程的計算操作次數(shù)tltx可表示如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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