北京大學碩士學位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計與實現(xiàn) 1 1 序言 信息檢索 (計算機科學與工程領(lǐng)域長久以來被廣泛研究的技術(shù)，有很多專門討論它的期刊和學術(shù)會議，例如美國國家標準局 (文本信息檢索會議 (1美國計算機協(xié)會 (有自己的會議 究信息檢索。同時信息檢索還和數(shù)據(jù)管理技術(shù) (比如數(shù)據(jù)庫 )的研究交叉在一起，可以說，自從人類使用計算機管理數(shù)據(jù)等信息，就產(chǎn)生了信息檢索的需求。計算機 在人類社會的廣泛應(yīng)用，促使我們進入了所謂的“信息化時代”，以計算機作為強有力的工具人類才有能力處理、存儲大量電子化的信息，信息規(guī)模與日俱增，也使人類面臨“信息爆炸”的威脅。如果不能有效的使用這些信息，我們就會被淹沒在信息的海洋里，造成“信息過?！焙汀靶畔⒗?。信息檢索的目的就是幫助用戶找到自己感興趣的信息，過程可以簡單描述為：用戶提交查詢請求 (通常是關(guān)鍵字 )，系統(tǒng)返回與用戶查詢相關(guān)的信息。信息檢索要解決的問題不是一成不變，它必須跟上人類信息爆炸式增長的現(xiàn)實。 九十年代以來，獲得了飛速發(fā)展，徹底的 改變著人類的工作和生活。據(jù)計算機世界網(wǎng) ()報道，美國網(wǎng)址專家凱利研究后指出：“ 自網(wǎng)景公司于 1995 年申請上市以來的 2000 天中，人類居然創(chuàng)寫了 30 億網(wǎng)頁，建立了 2000 萬個網(wǎng)址，而傳送的電 子 郵 件 就達 3 兆 5 億則之多 。 網(wǎng)址還將繼續(xù)擴張多元發(fā)展，但只有少部分是為了營利賺錢，而其他部分則是啟發(fā)自熱情、熱心及公共責任，亦即是一種對未來也許可用于經(jīng)濟用途的信心。在這 30 億網(wǎng)頁中，事實上只有 30%是由公司企業(yè)所創(chuàng)寫，其他 70%都是由非營利機構(gòu)與一般民眾所創(chuàng)作，顯現(xiàn)網(wǎng)址人所要的是相 互分享。 ”總之，互聯(lián)網(wǎng) (漸成為了信息時代人類發(fā)布、交流和共享信息的載體，極大地促進了人類知識的增長和傳播。 中國也獲得驚人的發(fā)展。根據(jù) 國互聯(lián)網(wǎng)絡(luò)信息中心 )在 2002 年1 月的統(tǒng)計信息表明 1，我國上網(wǎng)計算機數(shù)約 1254 萬臺，其中專線上網(wǎng)計算機數(shù)為 234萬臺，撥號上網(wǎng)計算機數(shù)為 1020 萬臺；我國上網(wǎng)用戶人數(shù)約 3370 萬人，其中專線上網(wǎng)的用戶人數(shù)為 672 萬，撥號上網(wǎng)的用戶人數(shù)為 2133 萬，同時使用專線與撥號的用戶人數(shù)為 565 萬。除計算機外同時使用其它設(shè)備（移動 終端、信息家電）上網(wǎng)的用戶人數(shù)為 118萬。我們北京大學計算機系網(wǎng)絡(luò)與分布式系統(tǒng)實驗室開發(fā)的“天網(wǎng)”系統(tǒng)在對中國國內(nèi)互聯(lián)網(wǎng)的一次搜集結(jié)果顯示 2，共收集到網(wǎng)頁 47,707,998 個，涉及到 46,669 個 中不重復的網(wǎng)頁為 22,382,623 個，平均每個站點有 不重復的網(wǎng)頁。 不斷增長形成了人類歷史上最大規(guī)模的分布式海量信息系統(tǒng)，如何幫助人們有效的利用這些信息就成為當務(wù)之急，而首要的任務(wù)便是發(fā)現(xiàn)信息 人們迫切需要有效的 航工具，協(xié)助用戶找到所需的信息。信息檢索和 術(shù)二者結(jié)合，就催生了 的搜索引擎 (它代替原始的人工目錄系統(tǒng)，成為人們在互北京大學碩士學位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計與實現(xiàn) 2 聯(lián)網(wǎng)上查找信息的有效工具，被認為是在 除電子郵件、瀏覽器之外使用最多的服務(wù)。 提供良好的搜索引擎服務(wù)，是各類大型門戶網(wǎng)站的一個基本配置，而且對任何一個網(wǎng)站，提供對站內(nèi)網(wǎng)頁信息的搜索服務(wù)也是方便訪問者必不可少的部分。 許多商業(yè)化搜索引擎伴隨著 潮被開發(fā)出來，代表性的是 。 在提供對 30 億文檔 (其中包括 2,073,418,204 張網(wǎng)頁 )的訪問，利用高效的算法和龐大的機器資源，可以幫助用戶準確地找到所需信息。 2001年調(diào)查報告顯示， 借純粹的搜索服務(wù)，在全球互聯(lián)網(wǎng)絡(luò)市場中取得 市場份額，名列第二，排名在雅虎之后，成為最成功的互聯(lián)網(wǎng)絡(luò)公司之一。與此同時，搜索引擎也成為各科研機構(gòu)和大學學術(shù)研究的熱點，每年的 術(shù)會議上和搜索引擎有關(guān)的研究題目都占很大比例， 是 學研究成果的商業(yè)化。如何有效的獲取互聯(lián)網(wǎng)上的信息，其重要性不言而喻。北京大學計算機系網(wǎng)絡(luò)與分布式系統(tǒng)實驗室研究開發(fā)的“天網(wǎng) ” (索引擎自 1997 年 10 月正式在 提供查詢服務(wù)以來，受到學術(shù)界和用戶的廣泛好評。我們一直致力于研制更高性能的搜索引擎，有效地開發(fā)利用 息資源。 在當今的信息社會，往往信息不是不足，而是太多，從大量無關(guān)、冗余和紛亂的信息海洋中方便快捷地找到對用戶有價值的信息，就是信息檢索 (解決的問題。不僅僅是 息資源，信息化的發(fā)展使得社會中的每個組織都有大量公開和非公開的信息資源，它們是社會組織自身擁有的寶貴財富，如何有效利用這些財富就是必須面臨的問題。辦公自動化系統(tǒng) (文檔數(shù)據(jù)庫 (以及數(shù)字圖書館 (數(shù)字化資源的建立和使用，都需要一個高效的信息檢索系統(tǒng)。信息檢索被認為是解決信息過剩 (有效途徑，可以說是信息社會的一項核心技術(shù)。 人類的數(shù)字化信息不僅有文本 (還包括圖形、圖像、電影和音樂等多媒體信息，但是文字信息是最基本和最重要的形式，也比較容易被檢索和識別，相對其他多媒體信息有比較成熟的技術(shù)。本文 研究的對象限制在對文本數(shù)據(jù)庫的檢索，對于非純文本文檔通常要轉(zhuǎn)換成文本信息，這并不降低我們所研究問題的重要意義。以“天網(wǎng)”搜索引擎為背景，通過對信息檢索相關(guān)問題的研究、分析和實驗，我們給出如何建立一個大規(guī)模文檔數(shù)據(jù)庫 (達到 )的信息檢索系統(tǒng)，它首先是分布式（ 和具備很高的可擴展性（ 而且在并發(fā)查詢負載下滿足一定的性能要求 響應(yīng)時間 (系統(tǒng)吞吐量 (以及由于系統(tǒng)硬件所產(chǎn)生的種種限制。最后，我們試圖 分析在運行“天網(wǎng)”這類大規(guī)模系統(tǒng)中具體遇到的管理難題，結(jié)合學術(shù)界和工業(yè)界在系統(tǒng)管理研究領(lǐng)域的最新成果和方向，討論了解決這個問題誘人的技術(shù)前景，并且對“天網(wǎng)”系統(tǒng)管理提出了自己試探性的研究建議。 北京大學碩士學位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計與實現(xiàn) 3 2 基本問題 信息檢索的目的是從大量的信息資源庫中找出用戶所需要的信息，所以它涉及兩個基本的方面。首先是如何表示、存儲和組織所擁有的海量信息資源，使它可以被迅速訪問；其次，我們?nèi)绾伪碚饔脩舻男畔⑿枨?，如何確定哪些信息是用戶所需要。前者是從計算機系統(tǒng)的角度看問題，后者是從人 用戶的角度看問題，二者決定了信息檢索的復雜性和研究的困難。廣泛使用數(shù)據(jù)庫 (術(shù)處理結(jié)構(gòu)化信息，操作的數(shù)據(jù)對象是固定的，用戶的每個操作執(zhí)行的結(jié)果是確定的；信息檢索處理的對象包羅萬象，可以是半結(jié)構(gòu)化、非結(jié)構(gòu)化的信息，這決定了它們的本質(zhì)區(qū)別。由于要處理任何可能的文檔，高質(zhì)量的信息檢索系統(tǒng)需要擁有對自然語言內(nèi)涵的理解能力，即獲取信息 (不只是數(shù)據(jù) (自然語言往往是模糊的和有隱含意義的，因此信息檢索對用戶查詢生成的結(jié)果是非精確的，往往也無法精確化。 因此，衡量一個 統(tǒng)，必須從兩個方面考慮：效率 (和效果(“效率”幾乎存在于所有計算機領(lǐng)域，任何算法都需要從時間和空間上考慮取舍，比如響應(yīng)時間、內(nèi)存和磁盤空間需求。對于聯(lián)機運行的信息檢索系統(tǒng)，最重要的效率指標就是系統(tǒng)的查詢響應(yīng)時間和系統(tǒng)的查詢吞吐量，沒有它，系統(tǒng)就不可能被用戶使用?！靶Ч敝笝z索返回結(jié)果集的準確性，通常有兩個指標：查準率 (查全率 (查準率定義為檢索結(jié)果集中與用戶查詢相關(guān)的文檔所占的百分比，查全率則是檢索結(jié)果集中的相關(guān)文檔占整個文檔集合中的相關(guān)文檔的百分比。由 于一個文檔是否和用戶查詢相關(guān)很難精確判定，實際運行的系統(tǒng)并不大可能用這兩個指標準確評價，但是它對研究仍然有很大參考價值。這兩個指標可以被形式定義如下：假設(shè)整個文檔集合是 D， D 的文檔數(shù)是 N=|D|，用戶查詢是 Q， Q 的返回文檔集合是 S(Q)，用函數(shù) R(x , y)表示文檔集合 x 中與查詢 y 相關(guān)的部分。則查詢 Q 的查準率是 |R(S(Q),Q)|/|S(Q)|,查全率是 |R(S(Q),Q)|/|R(D,Q)|。 信息檢索的基礎(chǔ)是數(shù)據(jù)管理和自然語言處理 (接限制著信息檢索的方式和效果。用戶需求可以用自然語言表達出來，但是計算機系統(tǒng)還無法準確的理解其內(nèi)涵。因此，用戶的意圖必須首先被翻譯成 統(tǒng)可以處理的形式。通常用戶查詢被表示成一系列關(guān)鍵字 (系統(tǒng)依據(jù)給出的關(guān)鍵字判定文檔是否和查詢相關(guān)。為了使得信息檢索有較好的效果， 統(tǒng)必須利用 技術(shù)，從語義上理解信息資源，評價它和用戶查詢的相關(guān)度 (并依據(jù)相關(guān)度的排序后將結(jié)果返回給用戶。 排文件 通過將用戶查詢和文檔資源分解成獨立的信息單元 (關(guān)鍵字 )，信息檢索的問題 被簡化 以關(guān)鍵字為信息單位檢索。在數(shù)據(jù)的組織與管理上，對文檔按照分解后的關(guān)鍵字建立索引，可以加快查詢訪問的速度。信息檢索中建索引的技術(shù)有三種：倒排文件(下標數(shù)組 (簽名文件 ( 4比較后得出結(jié)論：北京大學碩士學位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計與實現(xiàn) 4 無論從時間和空間上，倒排文件都明顯優(yōu)于簽名文件。下標數(shù)組空間需求太大，可是說是倒排文件的一種擴充形式。倒排文件則靈活而高效，可以根據(jù)需要做不同的變通，成為最廣泛使用的索引方法。 倒排文件分兩部分：第一部分是由詞匯組成的索引 (第二部分是記錄對應(yīng)的每個詞的所有出現(xiàn)的文檔集合，稱為記錄文件 (每個詞的對應(yīng)部分稱為引文件的每個數(shù)據(jù)項是由詞（關(guān)鍵字）和指向記錄文件的指針組成。記錄文件的每個數(shù)據(jù)項記錄和一個詞對應(yīng)出現(xiàn)文檔的列表。設(shè) 示第 j 個單詞（關(guān)鍵字），示第 i 個文檔， 第 l 次出現(xiàn)表示為 ( 示此次出現(xiàn)的屬性 ,它除了包含出現(xiàn)的位置 l,在非純文本中還可以有其它被賦予的屬性，比如此次 可 以根據(jù)單詞出現(xiàn)處字體的大小計算。一個文檔按照單詞切分后，相同的單詞出現(xiàn)合并在一起，形成 ( , 表示 所有文檔的 ( )按照前面所述兩級結(jié)構(gòu)組織成根據(jù)單詞的索引后，倒排文件就建立起來了，如圖 示，單詞 應(yīng)的 ( a*)+( di+k , fi+k, a*)+ ， 示 出現(xiàn)次數(shù)，也是后面 a 的數(shù)量。這是倒排文件的全文本索引 (式 ,它記錄了每次出現(xiàn)的位置等信息，要占用較多的存儲空間。簡化的形式是 ( 可以設(shè)定的權(quán)值函數(shù) f( , 更簡單的方法是 于 現(xiàn)的頻率 n。 圖 2 . 1 倒排文件 長記錄 短記錄 索引文件 記錄文件 索引文件項格式： w o r d + p o i n t e r ( 指向記錄文件 ) 記錄文件項格式： ( ) + ( k, )+ 記錄項內(nèi)部按文檔號成增序排列 利用倒排文件，系統(tǒng)可以根據(jù)用戶提交查詢中的關(guān)鍵詞快速找到相關(guān)文檔。當對大量文檔索引時，會出現(xiàn)一些關(guān)鍵字對應(yīng)的記錄項很大，嚴重 影響檢索的性能，后面我們會詳細討論。信息檢索中用戶的查詢有兩種基本的形式： I. 布爾 (詢，用邏輯操作 (接關(guān)鍵字。 北京大學碩士學位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計與實現(xiàn) 5 位置鄰近查詢 (要求關(guān)鍵字在相鄰的范圍內(nèi)。這對查詢詞組(重要，可以提高檢索的準確度，但是要求必須在索引中保留關(guān)鍵字的位置信息，增大了對磁盤空間的需求和查詢時的 I/O 操作。 倒排文件可以有效的支持這兩種查詢操作，由于每個關(guān)鍵詞的記錄項內(nèi)按文檔升序排列，只要順序掃描數(shù)據(jù)就能過濾不相關(guān)文檔，在內(nèi)存中的運算很快。 為優(yōu)化查詢速度，可以不支持“或”，使每次操作的結(jié)果集始終不斷縮小。操作應(yīng)該從對應(yīng)文檔集合最少的關(guān)鍵詞開始，能降低算法復雜度。假設(shè)關(guān)鍵詞 應(yīng)的文檔記錄集合為 P(則兩個關(guān)鍵詞 作的復雜度是 P(, |P()。每次操作的結(jié)果會成為下次操作的輸入，影響后面操作的復雜度。在內(nèi)存允許下，使多個關(guān)鍵詞一次同時參與運算，會大大提高執(zhí)行速度。 關(guān)度評價 信息檢索的一個核心算法是如何在用戶查詢 (文檔 (間做相關(guān)度評價 (這直接關(guān)系到查詢“效果”。最基本的評價方法是利用向量空間模型 (概念 ,查詢和文檔都被認為是由所有關(guān)鍵詞組成的 關(guān)度可以根據(jù)它們的向量計算出來。這種方法重要的改進是注意到每個單詞在向量中應(yīng)該被賦予不同的權(quán)重參與計算相關(guān)度。自然語言中信息單位出現(xiàn)的頻度是不一樣的，甚至相差很大。信息論原理告訴我們：事物出現(xiàn)頻率越大，攜帶的信息量越小。 s 0表示為： (2這意味著語言的信息項 出現(xiàn)的頻率和它的權(quán)值成反比，出現(xiàn)頻率很高的單詞攜帶的意義非常少，比如英語中的“ ,漢語中的“的”，這些高頻詞在信息檢索中可能需要特殊處理。著名的 此得出，它可以被表示成： d lo g（ 2 N 是所有文檔的總數(shù)， 示單詞 t 的文檔頻率 (由于 單詞在語言中的統(tǒng)計特性，新文檔的加入對它影響很小，可以在一次計算出后作為單詞的屬性使用。單詞 文檔 的出現(xiàn)頻率表示為 ，那么它的復合權(quán)值是： = * (25提出了一個經(jīng)驗公式，用文檔的長度修正復合權(quán)值，消除因文檔大小不同帶來的誤差。文檔向量 d 和查詢向量 q 的相關(guān)度比較通過兩個向量的夾角計算： c o s (2n 是向量的維數(shù)， 向量 q 和 d 的分量。結(jié)果越大，兩者的相關(guān)度就越高。 北京大學碩士學位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計與實現(xiàn) 6 我們考慮另一個語言統(tǒng)計特性 語言信息單位的 TF( 單詞在語言中出現(xiàn)的概率。設(shè)文檔 分后的單詞數(shù)是 DL(它可以作為文檔的長度。所有文檔切分后的單詞總數(shù) ： )( (2那么，單詞 TF(： 1) di t j,()( (2語言中單 詞的 TF(信息檢索的效率 (效果 (個方面都有很大影響。一種語言的詞匯可以分為兩部分 基本詞匯和專業(yè)詞匯，它們表現(xiàn)出不同的 TF(專業(yè)詞匯具有高的 較低 TF(可以區(qū)分不同領(lǐng)域的文檔，在信息檢索中更具意義。然而，語言中單個的“詞”的含義往往沒有足夠的含義，要用多個單詞組合成的詞組 (示更確切的意思 6。比如英語中的“ 屬于計算機中的專業(yè)詞匯， 切分以后的任何單字都不能表示這種含義。所以，詞組的 TF(能由它的各組成部分計算出來（例如相加得出）。如果對詞組索引匹配，檢索的準確度將大大提高。 這種情況對漢語尤為重要。漢語的造詞功能很強，通過字的組合創(chuàng)造概念，英語更多的是造單詞。比如漢語中“激光”用“激”和“光”組合，在英語中則創(chuàng)造新詞“ 漢語中用詞組表達確切的含義，在單獨一個“字”的意義很弱。漢語文檔的索引可以是基于“字”或者基于“詞組”，基于“字”的索引會造成詞組的整體語義的丟失，比如查詢“華人”會檢索出“中華人民 共和國”。根據(jù)單個的字統(tǒng)計規(guī)律得出的 漢語中的有效性也大大降低。在英語檢索中，通常將高頻的“ a, 單詞視為“ 忽略詞），不會對檢索的效果有太大影響。漢語中，高頻詞（比如“的，中，在，大，有”等）可能參與組成詞組，如果這些字被忽略會嚴重影響某些查詢，例如“美的”（作為商品的商標）和“王大中”（人名），“的”“大”“中”字是不能被忽略的?？傊?，由于漢語和英語的差別，漢語傾向于使用基于詞組的索引，后面我們將詳細討論這對檢索效率的影響。 統(tǒng)運行模型 一個完整 的現(xiàn)代信息檢索系統(tǒng)不僅要對用戶提供檢索 (能，還要同時支持瀏覽 (檔 7，如圖 示，這兩個功能現(xiàn)在都可以通過 術(shù)實現(xiàn)統(tǒng)一的用戶接口。檢索系統(tǒng)可以由用戶和文檔數(shù)據(jù)庫分成兩部分，和用戶交互的部分視為系統(tǒng)前端，數(shù)據(jù)庫相關(guān)部分視為系統(tǒng)后臺，它們通過中間的檢索和瀏覽兩大功能子系統(tǒng)連接起來。 北京大學碩士學位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計與實現(xiàn) 7 圖 2 . 2 用戶和檢索系統(tǒng)的交互（取自 7 ） R e t r i e v a l B r o w s i n g 數(shù)據(jù)庫 ( D a t a b a s e ) 后臺部分完成系統(tǒng)中文檔資源的維護功能，可以設(shè)想它是整個系統(tǒng)的起點，原始的文檔信息由此才能進入系統(tǒng)內(nèi)部。在后臺操作員 的控制下，數(shù)據(jù)庫的文檔可能不斷變化，如文檔增加和刪除。根據(jù)具體的應(yīng)用不同，這種變化會定期或不定期導致檢索和瀏覽兩個子系統(tǒng)數(shù)據(jù)的更新，雖然大部分信息檢索系統(tǒng)并不需要這種變化被實時處理。檢索子系統(tǒng)中索引必須重建，根據(jù)需要可以采取不同的策略（動態(tài)的、增量的、實時的、批量的），由于重建索引的代價巨大，必須盡可能減少它發(fā)生的頻度。 前端負責和用戶接口，它不僅向用戶提供信息（返回查詢結(jié)果，讓用戶瀏覽文檔），還可以通過和用戶交互獲得有用的信息 8。系統(tǒng)應(yīng)該可以全程跟蹤用戶使用系統(tǒng)的行為，比如在某段時間內(nèi)查詢的內(nèi)容（用戶 感興趣的主題和事物），瀏覽的文檔。這種信息包括用戶的個體行為和用戶的整體行為（統(tǒng)計結(jié)果），它可反饋回系統(tǒng)，改進系統(tǒng)的檢索質(zhì)量，比如根據(jù)用戶的查詢詞學習新詞，對用戶經(jīng)常查詢的關(guān)鍵字做緩存，甚至可以根據(jù)用戶瀏覽文檔的行為改變文檔的重要性，以此影響查詢結(jié)果的排序。我們對信息檢索系統(tǒng)中用戶的行為模型做出如下推斷： 1) 信息檢索系統(tǒng)中的個體活動模型。每個用戶的活動是帶有目的性的 查找某一方面的信息，檢索和瀏覽兩種行為交替進行，相鄰的查詢相關(guān)度很大，后面的查詢可能是前面查詢的優(yōu)化（ 即： 查詢 瀏覽 優(yōu)化的查詢 。這里的瀏覽包括用戶閱讀查詢結(jié)果集合和閱讀文檔，它可能是一個很長的時間間隔，甚至用戶可能終止進一步查詢，稱它為思考時間（ 2) 信息檢索系統(tǒng)中的用戶統(tǒng)計模型。單個用戶和系統(tǒng)的長時間交互中，檢索內(nèi)容呈現(xiàn)出個人的偏好，這與他的本身的工作、學習和興趣有關(guān)。大量用戶在某段時間的檢索內(nèi)容表現(xiàn)出相關(guān)性，同一主題被許多人感興趣，這就是所謂的“熱門檢索詞”。 由此可見，檢索系統(tǒng)和數(shù)據(jù)庫系統(tǒng)的用戶活動的巨大差別，認識到這一點很重要。根據(jù)這兩個推斷，我們可以采取一系列措施優(yōu)化檢索系統(tǒng) 的性能和質(zhì)量，分析系統(tǒng)真實的工作負載和用戶查詢的并發(fā)度。 檢索和瀏覽子系統(tǒng)對前端服務(wù)接口可以被抽象成如下的基本命令： 北京大學碩士學位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計與實現(xiàn) 8 I. 查詢命令（ 輸入?yún)?shù)為用戶的查詢字符串和其它信息字段，返回查詢結(jié)果集合。 讀取文檔命令（ 輸入?yún)?shù)為文檔標識，返回該文檔的內(nèi)容本身供用戶閱讀。 讀取摘要命令（ 輸入?yún)?shù)為文檔標識，返回該文檔的摘要信息。 提供讀取文檔摘要命令，使用戶可以快速了解文檔的內(nèi)容。用戶在瀏覽查詢結(jié)果時，系統(tǒng)顯示文檔的摘要部分， 這是信息檢索系統(tǒng)必要的功能。 圖 2 . 3 信息檢索系統(tǒng)運行模型 前端交互系統(tǒng) 文檔瀏覽系統(tǒng) 查詢處理 文檔數(shù)據(jù)庫 索引數(shù)據(jù)庫 數(shù)據(jù)管理系統(tǒng) 索引系統(tǒng) 查找 相關(guān)度評定 索引重建系統(tǒng) 后臺維護系統(tǒng) 用 戶 反 饋用戶反饋 檢索和瀏覽子系統(tǒng)對后臺的維護服務(wù)接口很簡單，輸入?yún)?shù)是要被刪除的文檔和增加的文檔，它由后臺維護系統(tǒng)選擇時機調(diào)用。實現(xiàn)這部分功能的困難在于，如何降低索引重建的代價（對大規(guī)模數(shù)據(jù)重建索引需要執(zhí)行幾個小時）和在系統(tǒng)提供正常檢索服務(wù)的情況下執(zhí)行重建，同時要保持系統(tǒng)中索引、文檔和摘要三部分的一致性和進行失敗恢復。如果將此功能當作“事務(wù)”執(zhí)行，應(yīng)該歸為“長事務(wù)”（ 9，不能用傳統(tǒng)的事務(wù)很好描 述。 11描述在一定資源限制下大規(guī)模文本的索引創(chuàng)建問題， 1213北京大學碩士學位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計與實現(xiàn) 9 討論動態(tài)和增量方式更新索引中的不同方法和會遇到的各種問題，雖然具體實現(xiàn)和底層的數(shù)據(jù)管理系統(tǒng)有很大關(guān)系，前面所指出的困難卻是普遍的，必須根據(jù)不同方面的要求做出一定取舍。 根據(jù)以上對各系統(tǒng)部分的分析，我們得出如圖 系統(tǒng)工作模型。數(shù)據(jù)管理系統(tǒng)在底層提供文檔及索引的存儲管理功能，前端交互系統(tǒng)和后臺維護系統(tǒng)是系統(tǒng)和外界交互的窗口，檢索、文檔瀏覽和索引重建是系統(tǒng)運行的核心（關(guān)于索引重建的詳細流程并沒有在模型圖中表示出來）。這個系統(tǒng)模型，作為 一個通用框架，有助于我們在具體應(yīng)用中對問題的分析、理解和設(shè)計。 用案例 現(xiàn)代信息檢索最重要同時也是使用最廣泛的應(yīng)用毫無疑問當屬 的信息檢索服務(wù)（ 搜索引擎，如前所述，這是和互聯(lián)網(wǎng)一起飛速發(fā)展的技術(shù)。搜索引擎的特殊性表現(xiàn)在： 要索引海量數(shù)據(jù)。平均每個網(wǎng)頁的大小是 10K 字節(jié)， 20 億網(wǎng)頁就是 20T 字節(jié)的數(shù)據(jù)，并且網(wǎng)頁的數(shù)量每天都在增加。 信息通過搜集系統(tǒng)從互聯(lián)網(wǎng)上獲取，由于網(wǎng)頁處于不斷更新狀態(tài)，如何建立高效的搜集器和動態(tài)更新索引，就非常關(guān)鍵。 信息的 異構(gòu)性很強，沒有任何前提限定，有多種語言存在。 信息存在形式主要是 內(nèi)部包含豐富的格式信息，以超級鏈接相互引用，這決定了它有獨特的相關(guān)度評價（ 術(shù)。 圖 14給出的一個搜索引擎通用結(jié)構(gòu)，相對一般的信息檢索系統(tǒng)增加了從 搜集網(wǎng)頁的功能，更大的差別在于系統(tǒng)內(nèi)部對網(wǎng)頁的分析技術(shù)，它對提高搜索引擎質(zhì)量至關(guān)重要。 的網(wǎng)頁通常比較短小，缺乏足夠的自我描述信息，而它們之間的相互鏈接正好在全局對網(wǎng)頁作了補充說明。超鏈分析（ 以挖 掘 的隱含信息，改進查詢的準確度，比較典型的技術(shù)是 14有較為詳盡的描述。 具體的索引數(shù)據(jù)結(jié)構(gòu)和系統(tǒng)實現(xiàn)，可參閱 15，它是 一個原型系統(tǒng)。搜索引擎在擴大數(shù)據(jù)規(guī)模的同時，必須滿足互聯(lián)網(wǎng)上大量用戶查詢產(chǎn)生的系統(tǒng)負載，所以“效率”也是商業(yè)搜索引擎系統(tǒng)成敗的關(guān)鍵。 信息檢索另一個重要的應(yīng)用是“數(shù)字圖書館”（ 它利用數(shù)字化技術(shù)擴充和增強傳統(tǒng)的圖書館業(yè)務(wù)。所以，數(shù)字圖書館不單是一個信息訪問的工具，而是要支持各種數(shù)字圖書業(yè)務(wù)的 環(huán)境。和 息搜索不同，圖書館的信息是要經(jīng)過“整理”后的，比如目錄分類。 16提出一個被廣泛接受的數(shù)字圖書館構(gòu)架，它包括用戶界面（ 文檔庫（ , 句柄系統(tǒng)（ 查找系統(tǒng)（ ,如圖 示。 北京大學碩士學位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計與實現(xiàn) 10 圖 2 . 4 搜索引擎的通用結(jié)構(gòu)（摘自 1 4 ） 圖 2 . 5 數(shù)字圖書館的主要構(gòu)成（摘自 1 6 ） 用戶界面包括兩個部分，一個是對圖書館的用戶，一個是對圖書管理員和管理信息資源 (系統(tǒng)管理員。每個界面都是由兩部分組成 標準的瀏覽器（ 京大學碩士學位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計與實現(xiàn) 11 和客戶端服務(wù)系統(tǒng)（ 后者是前者與系統(tǒng)交互的中介。文檔庫管理和存儲數(shù)字化對象， 議（ 是它的統(tǒng)一訪問接口。 來識別各種資源的全局標識符，可以很長時間存在，是資源的元數(shù)據(jù)（ 查找系統(tǒng)發(fā)現(xiàn)文檔庫中的信息，屬于很典型的信息檢索。從計算機系統(tǒng)看，這個結(jié)構(gòu)和前面的信息檢索模型本質(zhì)相同，現(xiàn)實中，數(shù)字圖書館還 涉及到法律的問題。 以上我們較為詳細介紹了信息檢索系統(tǒng)的原理和應(yīng)用實例，顯示出它的具體應(yīng)用實際上是由多個部分相互協(xié)作組成的有機整體，復雜的結(jié)構(gòu)和運行環(huán)境決定整個系統(tǒng)必須以分布式實現(xiàn)，搜索引擎和數(shù)字圖書館都證明了這一點。系統(tǒng)數(shù)據(jù)規(guī)模的不斷擴大，使得“效率”始終是必須考慮的問題。我們開發(fā)的新一代“天網(wǎng)”搜索引擎，要求規(guī)模從原來的索引幾百萬網(wǎng)頁擴大到可以支持上億篇網(wǎng)頁，同時必須保證良好的性能，為此，搜集系統(tǒng)和檢索系統(tǒng)都分別被分布式化。下面根據(jù)我們在“天網(wǎng)”系統(tǒng)開發(fā)中的實踐，討論實現(xiàn)分布式檢索系統(tǒng)中如何解決規(guī)模和 效率這兩個問題，其方法對于任何信息檢索應(yīng)用都有普遍意義。 北京大學碩士學位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計與實現(xiàn) 12 3 單機系統(tǒng)的檢索性能分析 單機系統(tǒng)的檢索性能是分布式系統(tǒng)的基礎(chǔ)，為了預測在分布式環(huán)境下的系統(tǒng)整體性能，必須確定單機系統(tǒng)中數(shù)據(jù)規(guī)模和性能的相互關(guān)系。我們的問題是利用當前水平計算能力的商用機器（ ，工作站），在一定性能（ 求下，可能支持的數(shù)據(jù)規(guī)模（ 并且討論系統(tǒng)的瓶頸和提高系統(tǒng)性能的各種方法。 用計算機性能分析 由于集成電路和計算機體系結(jié)構(gòu)等方面的發(fā)展，計算機的性能獲 得長足的進步。但是，計算機系統(tǒng)不同組成部分之間的增長是不均衡的，使得系統(tǒng)在實際應(yīng)用中性能下降。在過去二十年中， 性能幾乎增長了 10， 000 倍；單機系統(tǒng)的內(nèi)存容量也從少于 1B 的量級 ,大約增長了 1， 000 倍，存取時間達到 ；磁盤容量也從幾百 加到現(xiàn)在的 30是， I/O 的訪問速度卻僅提高了不到一百倍（從 00在應(yīng)用領(lǐng)域，大量信息處理的快速增長和多媒體信息普遍應(yīng)用，增加了對數(shù)據(jù)存取的需求，使 I/O 系統(tǒng)和外部存儲設(shè)備訪問愈發(fā)成為計算 機系統(tǒng)的瓶頸。信息檢索作為一個數(shù)據(jù)密集應(yīng)用（ I/O 乃是系統(tǒng)性能的關(guān)鍵，在 三個因素中，我們重點討論磁盤 I/O 對系統(tǒng)產(chǎn)生的限制。 表 族樹 us us 5 MB/s 0 10 MB/s 0 6 20 MB/s 0 20 MB/s 0 6 40 MB/s 0 6 80 MB/s 0 6 160 MB/s ， 相對于 面用的 線 ( 較高的速度，可以接多個設(shè)備，在 I/O 高負載下消耗 間少（ 耗 間 5%,0。其各種標準的性能如表 示，從最初的 5MB/s）到即將出現(xiàn)的 320MB/s） ,性能提升很快。實際可用的帶寬要小于標準值，比如現(xiàn)在用的 際帶寬是 150MB/s。 北京大學碩士學位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計與實現(xiàn) 13 磁盤容量的雖然不斷擴大，訪問速度卻改進很少，這由磁盤本身的特性決定（包含機械部分）。磁盤包含度多個盤片（ 1盤片表面分成多個磁道（ 所有盤面在同一垂直位置的磁道組成柱面（ 每個磁道被分成固定大小的扇區(qū)（ ,它是磁盤最小的尋址單位，又稱作塊（ 磁盤訪問（讀、寫）某個塊，必須首先將磁頭轉(zhuǎn)到所在磁道（尋道時間， 然后等待所在扇區(qū)到磁頭下面（旋轉(zhuǎn)延遲，最后是讀取扇區(qū)上的數(shù)據(jù)塊（傳輸時間， ,總的磁盤訪問時間還要加上磁盤控制器執(zhí)行 I/O 的代價，稱為控制器時間（ 尋道時間取決于當前磁頭位置和目的磁道的距離，通常取平均值表示性能，現(xiàn)在高性能磁盤的平均尋道時間大約在 10下，是 I/O 訪問延遲的主要部分。旋轉(zhuǎn)延遲取決于磁盤轉(zhuǎn)速，10000磁盤平均旋轉(zhuǎn)延遲（轉(zhuǎn)半圈）是 3據(jù)的傳輸時間是數(shù)據(jù)大小除以內(nèi)部傳輸速率，較高性能磁盤的內(nèi)部傳輸速率可以達到 20s。表 一些磁盤的性能數(shù)據(jù)， 表示磁盤每秒鐘可以執(zhí)行的隨機 I/O 操作，它可以根據(jù)平均訪問時間計算得到?？偟膩碚f，磁盤的響應(yīng)時間在毫秒級以上（平均 10每秒鐘可 以完成的I/O 操作也很有限（ 均是 100，即達到平均每秒種 100 次 I/O 訪問）。而且，具體的性能受數(shù)據(jù)存儲的位置和應(yīng)用訪問的模式影響，不良的數(shù)據(jù)存儲管理將使性能嚴重下降。 表 一些磁盤的性能數(shù)據(jù) MB/s) 6 36 0,000 119 15 0,000 715 5,000 83 0,000 116 2655 ,200 9前單個磁盤的平均數(shù)據(jù)傳輸速率 僅 25MB/s，不能完全利用 線的全部帶寬，進一步提高性能的方法之一是采用并行磁盤技術(shù) N 個磁盤組成的陣列可以使數(shù)據(jù)傳輸速率獲得接近 N 倍的提升，并且可以提高 I/O 請求的響應(yīng)時間（同時也增加了 這是以增加系統(tǒng)硬件成本為代價的。為解決 I/O 產(chǎn)生的瓶頸，工業(yè)界開發(fā)出了更加先進的外部存儲技術(shù)，如光纖通道（ 存儲區(qū)域網(wǎng)絡(luò)（ （的 15 就是一種 光纖通道，其性能指標要高出普通硬盤很多）?？梢哉J為，隨著磁盤的平均數(shù) 據(jù)傳輸速率從 10MB/s 到 100MB/s 甚至更高的提升，成本北京大學碩士學位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計與實現(xiàn) 14 也會隨之上升。應(yīng)用中要根據(jù)實際需求，在成本和性能之間做出選擇。 引數(shù)據(jù)管理 存儲設(shè)備性能可否充分利用，還要受操作系統(tǒng)、應(yīng)用程序（存儲管理、緩存管理）的影響。 應(yīng)用程序要調(diào)用操作系統(tǒng)提供的 I/O 服務(wù)功能 ,它有幾種不同的方式，如圖 文件系統(tǒng)的調(diào)用接口或 I/O 庫函數(shù)，優(yōu)點是可以利用文件系統(tǒng)的緩存和預讀機制，缺點是數(shù)據(jù)要經(jīng)過多次拷貝。原始 I/O 不通過文件系統(tǒng)，直接讀寫磁盤。一些操作系統(tǒng)提供直接 I/O（ ），它在文件系統(tǒng)支持 下實現(xiàn)和原始 I/O 類似的功能，沒有系統(tǒng)緩存、多次拷貝等開銷。另一種減少 I/O 開銷的方法是用文件映射（ 統(tǒng)調(diào)用），將數(shù)據(jù)映射到內(nèi)存空間，直接讀寫內(nèi)存，不存在多次拷貝的問題。文件映射的缺點是失去了 I/O 操作的原子性語義，在并發(fā)讀寫中要實現(xiàn)互斥操作。 圖 3 . 1 L I N U X 操作系統(tǒng)的 I / O I / O 類型： 原始（ R a w ） I / O ，在數(shù)據(jù)庫中使用。 其它是通過內(nèi)存映像訪問數(shù)據(jù)。 U s e r U s e r b u f f e r S y s t e m c a c h e M e m o r y m a p p e d D e v i c e 1 2 3 4 5 1 不通過文件系統(tǒng)的原始 I/O 。 2 用 r e a d / w r i t e 系統(tǒng)調(diào)用的 I/O 。 3 用 f r e a d / f w r i t e 標準庫函數(shù)調(diào)用的 I/O 。 4 文件系統(tǒng)的元數(shù)據(jù)。 5 文件系統(tǒng)元數(shù)據(jù)更 新。 使用文件系統(tǒng)的另一個缺點是文件系統(tǒng)的數(shù)據(jù)組織往往不能提供應(yīng)用程序最好的性能。 文件空間分配是直接索引、一級索引、二級索引和三級索引的組合，最壞情況下訪問數(shù)據(jù)要讀四次塊（大文件）。文件系統(tǒng)一 般的預讀策略是提前讀，數(shù)據(jù)塊緩存用 法，這些都是對應(yīng)用程序透明的，不能做到應(yīng)用級優(yōu)化（ 數(shù)據(jù)庫一般繞過文件系統(tǒng)，使用自己的存儲管理和緩存，優(yōu)化應(yīng)用的性能。 倒排文件本質(zhì)上是關(guān)鍵字到它對應(yīng)項的索引，一般地，關(guān)鍵字通過字典（ 找，轉(zhuǎn)換成整數(shù)作為關(guān)鍵字的標識（ ,索引管理實現(xiàn)從 對應(yīng)項的訪北京大學碩士學位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計與實現(xiàn) 15 問。在“天網(wǎng)”中，用兩級文件模擬這種結(jié)構(gòu)，如圖 示的，第一級文件中每個結(jié)構(gòu)項是 ( 向二級文件的指針（ 應(yīng)項的開始） , 應(yīng)項大小。每次建索引，關(guān)鍵字的 是重新生成，是連續(xù)的整數(shù)，數(shù)量大約 200 萬個。由于一級文件并不大（可以讀入內(nèi)存），每次只讀取幾個字節(jié)，其代價可以不考慮。二級文件中，一些關(guān)鍵詞的對應(yīng)項很大，才是影響倒排表查詢性能的關(guān)鍵。用文件實現(xiàn)的缺點如前所述，好處是簡單易于實現(xiàn)。 如果系統(tǒng)維護統(tǒng)一的字典，關(guān)鍵字和標識（ 映射不變，每次創(chuàng)建倒排文件產(chǎn)生的 不是連續(xù)的，二級索引將不再適合，更一般的方法是用 B+樹 組織倒排文件。 17討論在關(guān)系數(shù)據(jù)庫之上實現(xiàn)倒排文件，利用成熟產(chǎn)品提供的高性能數(shù)據(jù)管理，缺點是增加了不必要的開銷，比如 詢接口。面向?qū)ο蟮母拍罡芎啙嵉孛枋龅古盼募慕Y(jié)構(gòu)，采用面向?qū)ο髷?shù)據(jù)庫系統(tǒng)（ 更好的選擇。 1819用持久對象存儲（ 理倒排文件， 但提供基于對象的數(shù)據(jù)緩存和良好的磁盤空間分配策略，還可以用它高度的可擴展性，根據(jù)數(shù)據(jù)的特性定制存儲。 021是商業(yè)上最成功的面向?qū)ο髷?shù)據(jù) 庫 系統(tǒng)（ 之一，它用內(nèi)存映射技術(shù)實現(xiàn) 持久對象存儲，和程序語言（ C,C+,全集成，既有程序設(shè)計語言的靈活，又可以高效的存儲數(shù)據(jù)，是另一個很好的索引管理工具。 嵌入式數(shù)據(jù)庫系統(tǒng) B） 22,是一個開放源代碼產(chǎn)品，它提供簡單高效的功能（三種訪問方法 B+，實現(xiàn) 存取，這已完全能滿足索引管理的需求。 B 以庫的形式存在，在多種程序設(shè)計語言（ C, C+, 中支持顯式的數(shù)據(jù)庫訪問編程接口。 23討論了在 目中用B 管理倒排文件的具體實現(xiàn)細節(jié)，由于它的開放源碼特點，也是一個不錯的選擇。 由于前面所述的磁盤結(jié)構(gòu)特點，提高訪問效率的存儲分配策略可歸結(jié)為：將同時訪問的數(shù)據(jù)塊分配在磁盤相鄰的扇區(qū)，稱“簇集”（ 如果系統(tǒng)存在多個磁盤（ ,可以將同時訪問的數(shù)據(jù)塊分配在不同的物理磁盤上，稱“解簇” （ 在查詢處理時，倒排文件中 應(yīng)的 被順序掃描（ ,過濾后得到滿足條件的文檔集合，這種順序訪問模式要求每個 好存放在連續(xù)的扇區(qū)， 面向?qū)ο髷?shù)據(jù)庫 系統(tǒng)通常可以提供此種能力（比如 用戶可以定制對象的存儲分配管理 ）。 倒排文件中 度差別很大，為提高效率可以區(qū)別對待。高頻詞（ 度通常 1上（隨著文檔數(shù)據(jù)庫規(guī)模增大，它會快速增長），稱作“ 如果對它作順序訪問，從磁盤讀入內(nèi)存會耗費很長時間，同時占用系統(tǒng)大量的 I/O 帶寬，從而降低整個系統(tǒng)的吞吐量。解決的方法是將對 順序訪問變成隨機訪問（ 24， 25, 按照“文檔號”分割成長度較小的數(shù)據(jù)塊，在“ “ 作時可以有選擇地訪問部分數(shù)據(jù)，不可能相關(guān)的文檔所在數(shù)據(jù)塊被“跳過”（ 它增加了按照“文檔號”索引數(shù)據(jù)，以空間換取時 間。假設(shè)關(guān)鍵詞 應(yīng)的 ( |P(表示 P(文檔的數(shù)量，兩個詞 “ “ 北京大學碩士學位論文 “天網(wǎng)”高性能分布式檢索系統(tǒng)的設(shè)計與實現(xiàn) 16 |P( 遠遠小于 |P( ，讀 P(內(nèi)存中，程序只需根據(jù) P(文檔號，讀取 P(包含該文檔的數(shù)據(jù)塊。算法的效率提高取決于 |P( 要遠遠小于 |P(，即至少有一個運算項的 高（關(guān)鍵詞只在以一小部分文檔中出現(xiàn)），這對多個運算項的同時操作一樣適用。 自索引倒排文件（ 24表明， 以大幅度降低查詢所用時間。然而，此算法要求 以被定制存儲和組織，必須使用 面向?qū)ο髷?shù)據(jù)庫 系統(tǒng)管理倒排文件，或者從頭開發(fā)全新的索引管理系統(tǒng)。 另一個改善性能的技術(shù)是緩沖區(qū)管理，利用文件系統(tǒng)的緩存往往不能得到最佳的性能。前面得出的個體用戶行為模型表明，在一段時間內(nèi)相同的關(guān)鍵詞可能被同一個用戶反復查詢。根據(jù) 順序訪問模式，可以采用基于對象 的緩存，對象持久存儲中的雙向緩沖區(qū) 27將對象和分頁緩存結(jié)合起來，是一種更佳的策略。在信息檢索中，低頻詞的 度小于一頁，被檢索的頻度也很低（很少在短時間被不同的用戶查詢），應(yīng)該將多個小對象合并緩存在同一頁中。對很高頻的單詞，由于它對查詢準確度的提高很有限（有些系統(tǒng)將它們作為 略，不建索引），緩存整個它的 占用大量內(nèi)存，少量的高頻詞就可以耗盡所有的內(nèi)存 ，所以緩存高頻詞的 得