高性能海量數(shù)據(jù)檢索系統(tǒng)的設計與實現(xiàn)

1、北京大學碩士研究生學位論文題目：海量文檔高速檢索系統(tǒng)的設計與實現(xiàn)姓名：謝翰學號：10280040系別：信息科學技術學院專業(yè)：計算機軟件與理論研究方向：網(wǎng)絡與分布式系統(tǒng)導師：李曉明教授二零零五年六月版權聲明任何收存和保管論文各種版本的單位和個人，未經本論文作者授權，不得將本論文轉借他人，亦不得隨意復印、抄錄、拍照或以任何方式傳播。否則，引起有礙作者著作權益之問題，將可能承擔法律責任。摘要搜索引擎的檢索效率是評價搜索引擎質量的一個重要指標，面對互聯(lián)網(wǎng)上信息量的不斷增加以及搜索引擎網(wǎng)頁庫的不斷增大，對檢索系統(tǒng)性能要求也越來越高。本文詳細介紹了一個搜索引擎檢索系統(tǒng)的設計與實現(xiàn)，針對搜索引擎檢索系統(tǒng)的性

2、能問題進行了研究，討論了影響檢索性能的幾個因素，并分別提出改進的方法和途徑。這些方法包括設計出結構更加良好的倒排文件結構，改進整數(shù)壓縮編碼，引入倒排文件cache,預先計算關鍵詞與文檔相關度，減少關鍵詞相對位置計算開銷，改進站點聚類算法等。另外，論文還闡述了系統(tǒng)中使用的新的相關度計算方法，這個算法使得在最終的結果排序上比原有系統(tǒng)有了一些改進。論文的組織形式以實際系統(tǒng)中各模塊為主線，這些模塊包括倒排文件結構，底層數(shù)據(jù)接口，查詢，計分和站點聚類等。在論文最后給出了系統(tǒng)的綜合測試結果，指出系統(tǒng)中還存在的不足，并對后續(xù)工作提出了一些建議。關鍵詞：搜索引擎，檢索系統(tǒng)，倒排文件，檢索效率，相關度計算The

3、DesignandImplementationofaHighPerformanceRetrievalSystemXIEHan(ComputerSoftwareandTheory)DirectedbyLIXiaomingAbstractTheperformanceofretrievingiscrucialformodernsearchengine.Thisarticleintroducesthedesignandimplementationofaretrievalsystemforwebsearchengine.Especially,wewilldiscussthefactorsthataffe

4、ctretrievalperformance,andgivethesolutionsforeachofthem,suchasdesigninganewformatforinvertedfileandanewencodingalgorithmforintegers,introducingcachefortheindex,pre-computingthesimilarityoftermsanddocuments,anddesigningabettersitegroupingalgorithm.Anewrankingalgorithmusedinthesystemwillbediscussedtoo

5、.Thearticleisorganizedbymodules,includinginvertedfile,datainterface,queryscoringandsitegrouping.Inthelastchapterwewillmakeanoverallevolution,andsomeadvicesforitsfurtherimprovementwillbegiven.Keywords:searchengine,retrievalsystem,invertedfile,performance,ranking.目錄第1章緒論1.1.1 搜索引擎原理1.1.2 倒排文件2.1.3 檢索系

6、統(tǒng)分布式結構.4.1.4 現(xiàn)有系統(tǒng)的不足與本文的主要貢獻5第2章倒排文件設計 基本原則 整數(shù)壓縮編碼方法 系統(tǒng)使用的倒排文件結構定義81 描述文件8.1 索引文件101 記錄文件10第3章底層數(shù)據(jù)組織131.1.< 影響檢索效率的主要因素1.31.2.< 創(chuàng)建索引1.51.3.< 獲得文檔列表18< 接口與數(shù)據(jù)組織1.8< 性能測試201.4.< 獲得位置列表231.5.< 模塊的一些不足26第4章查詢過程274.2 文檔列表求交274.3 相關度計算284.3.1 關鍵詞與文檔相關度284.3.2 相對位置得

7、分304.4 站點聚類314.5 查詢模塊接口33第5章綜合評測與總結35系統(tǒng)整體結構35實驗設計36實驗結果37總結39第1章緒論搜索引擎原理眾所周知，搜索引擎是從互聯(lián)網(wǎng)上搜尋信息的重要工具。隨著互聯(lián)網(wǎng)規(guī)模的不斷增大，網(wǎng)上信息量的不斷增長，搜索引擎的作用越來越明顯?；ヂ?lián)網(wǎng)上搜索引擎雖然大小不同，功能各異，但它們都包含以下一些基本的功能模塊。.網(wǎng)頁收集網(wǎng)頁收集是搜索引擎的第一步工作，要進行網(wǎng)頁搜索顯然必須先有一個網(wǎng)頁庫。除了少量手工加入的網(wǎng)頁，大多數(shù)網(wǎng)頁都是通過被稱為spider的自動網(wǎng)頁收集程序收集下來的。spider的基本工作原理很簡單：以一些重要的網(wǎng)頁為種子，先收集這些網(wǎng)頁，提取這些網(wǎng)頁

8、上的鏈接，再收集被鏈向的網(wǎng)頁。如此不斷地循環(huán)下去，就可收集到互聯(lián)網(wǎng)上大量的網(wǎng)頁。另外也可通過端口掃描的方法發(fā)現(xiàn)隱藏的web服務器。評價spider的質量有幾個重要的指標，包括網(wǎng)頁收集的速度，網(wǎng)頁質量與重復率，發(fā)現(xiàn)新增網(wǎng)頁和變化網(wǎng)頁的速度，動態(tài)網(wǎng)頁的收集策略，對對方web服務器的禮貌性等。目前大多數(shù)的研究都集中在網(wǎng)頁質量和增量式的網(wǎng)頁收集上。.頁面預處理從互聯(lián)網(wǎng)上收集到了網(wǎng)頁，到真正的提供搜索服務還有很多的事情要做。首先是對網(wǎng)頁進行一些預處理。對網(wǎng)頁進行預處理的原因是，網(wǎng)頁上的很多信息實際上與網(wǎng)頁的主題毫無關系，比如廣告，我們稱這些為噪音信息。如果不把這些噪音信息去除則會影響到最后的查詢質量。止

9、匕外，很多網(wǎng)頁之間在排版，字體等方面雖不一樣，但正文的內容卻是相同的，如是讓它們都出現(xiàn)在查詢結果中顯然是多余的，必須去掉一個。還有一些無內容的垃圾網(wǎng)頁，作弊網(wǎng)頁，也必須在這個階段消除掉。.建立索引從頁面預處理模塊得到了凈化過的頁面，要高效進行查詢，還必須對頁面建立從關鍵詞到其出現(xiàn)位置的索引。這個索引稱為倒排索引，對應的索引文件稱為倒排文件。對于索引的建立應該說技術已經很成熟，關鍵是要定義出良好的索引結構，以支持檢索模塊對頁網(wǎng)進行快速而準確的檢索。其次要保證建立索引的速度，才能讓新收集到的網(wǎng)頁盡快地被查詢到，提高搜索引擎的時新性。.網(wǎng)頁檢索網(wǎng)頁檢索模塊是最終與搜索引擎用戶交互的模塊。系統(tǒng)根據(jù)用戶

10、提供的查詢，從建立好索引的網(wǎng)頁庫中找到與查詢最相關的頁面，根據(jù)相關度及網(wǎng)頁的重要性計算出一個綜合的得分，把得分最高的網(wǎng)頁按順序返回給用戶?？梢哉f，網(wǎng)頁檢索方面還有很多問題需要研究，包括：查詢與網(wǎng)頁相關度的計算，這直接影響查詢結果的排序；查詢的響應時間和系統(tǒng)吐吞率，一個大型的搜索引擎瞬間之內就會有大量用戶發(fā)出請求，面對這么多用戶，如何以最快的速度響應，如果提高一段時間內可處理的最大查詢個數(shù)，是現(xiàn)代搜索引擎面臨的一個重要問題；檢索系統(tǒng)的可擴展性和容錯性也尤為重要，檢索是搜索引擎中對硬件需求最大的部分，往往是幾百臺甚至上萬臺計算機協(xié)同工作，這么多的計算機如何協(xié)調，在部分機器出現(xiàn)故障的時候如何讓系統(tǒng)繼

11、續(xù)工作，也是一個研究領域。除了這上述的幾個基本模塊，現(xiàn)代的搜索引擎還包含其它的一些功能。例如網(wǎng)頁重要性的計算，網(wǎng)頁的自動分類等?？傊?，搜索引擎的研究還遠遠沒有到盡頭，搜索引擎離它最終的目標還很遠。本文將著重研究搜索引擎檢索模塊中的檢索效率問題，同時也會涉及索引與相關度計算等方面。倒排文件倒排文件由搜索引擎的索引模塊生成，并被檢索模塊所使用。前面提到，倒排文件是從關鍵詞到其出現(xiàn)位置(occurrence)的一種索引。對于搜索引擎來說，關鍵詞的出現(xiàn)位置信息必須包括出現(xiàn)關鍵詞的文檔列表，以及關鍵詞在各文檔內的位置列表。一般而言倒排文件由索引文件和記錄文件組成，索引文件每個記錄包含一個關鍵詞和一個指針

12、，該指針指向記錄文件中存放關鍵詞信息的位置。大致結構如下圖所示：索引文件記錄文件圖1.1倒排文件利用倒排文件，檢索系統(tǒng)可以快速的找到查詢詞對應的文檔列表。對由多個關鍵詞所組成的查詢，還可以根據(jù)各個詞在各個文檔中出現(xiàn)的位置，來計算查詢與文檔的相關度。倒排索引是迄今為止發(fā)現(xiàn)的用于搜索引擎最好的索引結構，既方便建立，又很好的支持各種查詢操作。在實際應用中的倒排文件遠比上圖的復雜：為了更好的計算相關度，倒排文件中還要加入其它的一些信息，例如關鍵詞在文檔中的屬性信息；為了提高檢索效率，可能要調整倒排文件的結構，例如先存放出現(xiàn)關鍵詞的所有文檔列表，再存放所有的位置信息，把上圖中位置信息的形式：<do

13、c1><pos1pos2Pos3><doc2><pos1'pos2'pos3'><doc3><pos1'pbs2'pos3'，>變換為：<doc1doc2doc3><pos1pos2Pos3pos1'pos2'pos3'pos1'p'os2'pos3''>通過這種變換，當我們不關心詞在文檔中位置列表的時候，就可以一次地讀入詞對應的文檔列表，減少對外存的訪問次數(shù)。在后面我們還將詳細討論倒排文件的設

14、計，我們會發(fā)現(xiàn)倒排文件結構的好壞直接影響檢索速度。檢索系統(tǒng)分布式結構現(xiàn)代搜索引擎搜索的網(wǎng)頁都數(shù)量巨大，目前的北大天網(wǎng)e.pku搜索引擎搜索的網(wǎng)頁量就有1.2億，而一般的商業(yè)搜索引擎搜索的網(wǎng)頁量至少都有數(shù)億，甚至是達到數(shù)十億。在這種情況下，一個單機的檢索系統(tǒng)顯然無法處理每秒成百上千的用戶查詢請求。此時，設計出一個結構良好的分布式檢索系統(tǒng)顯得尤為重要。一般成言，分布式檢索系統(tǒng)至少包括兩個部分：一臺或多臺用于接收入用戶查詢請求的前臺服務器，和多個用于實際數(shù)據(jù)檢索的后臺服務器。具結構如下圖所示:后臺檢索機群圖1.2檢索系統(tǒng)分布式結構當用戶在搜索框中填入一個查詢，點擊搜索按鈕，其查詢就被隨機的發(fā)送到任意

15、一臺前臺服務器上。而前臺服務器實際上并不保存網(wǎng)頁的索引信息，它將用戶的查詢通過廣播的方式發(fā)送到后臺的檢索機群上。后臺檢索機群中，每臺機器中都存放有部分網(wǎng)頁的倒排索引，當它收入到廣播過來的查詢，便在其索引中查找出與查詢其關的網(wǎng)頁，并根據(jù)一定的相關度算法計算出得分，把相關度最高的若干個網(wǎng)頁的文檔號與得分一起發(fā)送回前臺的服務器。前臺服務器收集幾個檢索機器上的結果，按得分歸并后把最相關的網(wǎng)頁返回給用戶。由于時間的關系本文必沒有詳細的研究檢索系統(tǒng)的分布式結構，而是更多的關注各個檢索節(jié)點上的效率。可以說，這兩方面共同決定了一個檢索系統(tǒng)的性能。現(xiàn)有系統(tǒng)的不足與本文的主要貢獻現(xiàn)有的天網(wǎng)檢索系統(tǒng)，是從天網(wǎng)1.0

16、開始，經過不斷的完善和發(fā)展起來的。在幾年里為老師和同學們的科研工作提供了一個重要的平臺。但它還存在了一些問題需要我們去改善。例如以下幾個方面：.檢索效率不高。每個檢索節(jié)點檢索的網(wǎng)頁量大約在二百多萬，每秒只能處理十幾個的查詢請求。主要原因是沒有為倒排文件建立cache每次查詢都要多次訪問外存，磁盤成了系統(tǒng)的瓶頸。止匕外，其分布式結構也不太好，前臺服務器與檢索節(jié)之間基于同步的多進程的交互方式，也影響和整個系統(tǒng)的效率。.倒排文件信息量不夠?，F(xiàn)在的倒排文件中，關鍵詞在文檔中的屬性信息很少，只用兩個bit分別表示詞是否在網(wǎng)頁title和摘要中，并且不能為關鍵詞在文檔中各個位置設立屬性信息。由于信息量的缺

17、乏，在計算詞與文檔相關性的時候，往往不夠準確。.系統(tǒng)的可擴展性和容錯性不足。系統(tǒng)現(xiàn)在運行在由一臺前臺服務器，19個檢索節(jié)點構成的分布式環(huán)境中。對于增加檢索節(jié)點可能帶來的廣播風爆，以及增加前臺服務器查詢策略的變化，都沒有考慮到。此外，數(shù)據(jù)沒有冗余，當系統(tǒng)中部分機器出現(xiàn)故障，則會影響查詢結果。本文針對檢索效率的問題進行了研究。設計出來更加良好的倒排文件結構，改進整數(shù)壓縮算法，并增加倒排文件的信息量。通過有效的cache策略，讓索引盡量的在內存中可以找到，減少訪問磁盤的開銷。通過一些有效的預處理，減少了浮點運算的次數(shù)，也進一步的提高了檢索效率。對于相關度計算，本文也做了一些改進，使得在最后的結果排序

18、上更符合用戶需求。止匕外，一個具有良好程序結構的可用系統(tǒng)，也很好的支持了文中提出的觀點。在以下章節(jié)中，我們將詳細的分析整個系統(tǒng)的設計與實現(xiàn)，以及設計背后的理論基礎。第2章倒排文件設計基本原則前面提到過倒排文件的作用和基本結構，在新的系統(tǒng)中，為了讓應用程序進行高效檢索，并改進結果的排序，我們設計了新的倒排文件結構。在系統(tǒng)的開發(fā)過程中，這個結構被修改了很多次，每個設計都各有利弊，最終確定的結構也不是在各方面都最優(yōu)。但倒排文件的設計都必須遵循幾個基本的原則：文件必須是沒有二義性，可以正確的還原出數(shù)據(jù)。例如當我們保存記錄<doc1><pos1pos2><doc2>&

19、lt;pos1pos2'>,在讀取的時候就無法確定<doc2>處保存的是出現(xiàn)該關鍵詞的新的一個文檔號，還是該關鍵詞在docl中的下一個出現(xiàn)位置。因此必須多保存一個詞頻信息，例如<doc1><tf1><pos1pos2><doc2><tf2><pos1'pos2'>°tf1和tf2分別表示詞在docl和doc2中的出現(xiàn)次數(shù)。這樣才可正確的還原出信息。文件的規(guī)模應當盡量小，記錄文件中每條記錄應該占用盡可能小的空間，以減少讀取記錄時傳輸?shù)臄?shù)據(jù)量。方法是進行索引壓縮Scholer

20、,etal.,2002：使用變長的整數(shù)編碼，用較少的空間保存較小的整數(shù)；整數(shù)使用差值存放，例如把文檔號按升序排列，第一個文檔號保存實際值，之后的都保存與前一個文檔號的差值。關鍵詞在文檔中的位置也用類似的保存方法。差值表示法的另一個好處就是可以更方便的求多個文檔列表的交集，并且更方便的計算多個關鍵詞在同一文檔中的相對位置，在后面我們還會介紹。雖然對索引進行壓縮會帶來額外的數(shù)據(jù)解壓開銷，但相對于它帶來的好處，這種開銷完全是值得的。索引壓縮減少了讀取數(shù)據(jù)時從磁盤傳輸?shù)臄?shù)據(jù)量，但在檢索時平均每個查詢對磁盤的訪問次數(shù)，更大的影響了檢索效率。因此，設計倒排文件時，應當支持程序在最少次數(shù)內讀取到需要的信息。

21、例如在上一章中提到的，把文檔列表連續(xù)的保存。倒排文件的設計還必須考慮方便索引模塊的建立，以及方便檢索模塊的操作，因此結構不應該太復雜。例如，在設計過程中參考了文獻彭波,2003中的倒排文件分塊組織技術，把文檔根據(jù)屬性的不同分塊保存。表面上看查詢時可以先讀重要的文檔列表，但在實現(xiàn)過程中卻發(fā)現(xiàn)對于多個關鍵詞組成的查詢，操作起來異常的復雜，最終不得不放棄整數(shù)壓縮編碼方法變長的整數(shù)編碼可分為兩類，字節(jié)對齊整數(shù)編碼和非字節(jié)對齊整數(shù)編碼。前者優(yōu)勢有較高的壓縮比率，后者則有更高的壓縮與解壓效率。文獻彭波,2003認為，在搜索引擎的應用中，檢索效率比索引數(shù)據(jù)占用的空間更為重要。文中對比了字節(jié)對齊編碼ByteC

22、ode和非字節(jié)對齊編碼GolombWitten,etal.,1994,其壓縮比率分別為0.3359和0.2635,解碼時間比為1:6。目前天網(wǎng)系統(tǒng)中使用的ByteCode編碼在文獻趙江華,2002中有描述，它可對數(shù)值從0至230-1的正整數(shù)進行壓縮編碼。用第一個字節(jié)的最高兩位表示整數(shù)所占的字節(jié)數(shù)，則1字節(jié)的壓縮整數(shù)包含6個有效位，可表示整數(shù)0至63;2字節(jié)的壓縮整數(shù)包含14個有效位，表示整數(shù)范圍從64至214-1。3字節(jié)可表示從214至222-1,4字節(jié)可表示從222至230-1。在新的系統(tǒng)設計依然使用字節(jié)對齊的整數(shù)編碼方式，用ByteCodeEx表示，但與ByteCode不同，ByteCod

23、eEx使用了可變長的位數(shù)來表示壓縮整數(shù)的所占字節(jié)數(shù)，并且根據(jù)計算機的字節(jié)序(ByteOrder)使用不相同的編碼方式，加快解碼速度。以BigEndian的字節(jié)序為例，第一字節(jié)的最高位開始，如果連續(xù)n個位為1,則表示壓縮整數(shù)長度為n+1個字節(jié)，有效位從第一個為0的位開始。例如第一個字節(jié)110001101,從最高位開始連續(xù)出現(xiàn)2個1,則說明整數(shù)占3個字節(jié)；又例如第一個字節(jié)01100101,最高一位就是0,說明整數(shù)占1個字節(jié)，該整數(shù)為的值為99。由此我們可以得出，m個字節(jié)的壓縮整數(shù)可表示的整數(shù)最大值為28xm"(m-2)-1o這種方法比ByteCode的優(yōu)勢是只需一個字節(jié)就可表示從0至12

24、7,對于小整數(shù)占多數(shù)的倒排文件來說，壓縮率比較高，可以為每個從64至127的整數(shù)節(jié)省去一個字節(jié)的空間。但當整數(shù)的范圍從221到222-1時，則會多占用一個字節(jié)。ByteCodeEx可擴展到無限大的正整數(shù)。以下是為2576933個文檔建立倒排索引，對整數(shù)的使用情況統(tǒng)計：表2.1整數(shù)統(tǒng)Ih整數(shù)范圍06364127128216-1216221-1221222-1>222出現(xiàn)次數(shù)2,822,189,488245,763,9511,191,448,54421,135,917206,38929ByteCode字節(jié)數(shù)122334ByteCodeEx字節(jié)數(shù)112344可以算出，用ByteCodeEx方法

25、節(jié)省了倒排文件的空間45763951-206389245MB，整數(shù)的壓縮率為0.3221,比起B(yǎng)yteCode有不小的提高。對于LittleEndian的計算機系統(tǒng)，編碼方式略有不同，表示壓縮整數(shù)長度的位從第一個字節(jié)的最低位開始，并且也先存放低字節(jié)。這樣做是為了提高編碼和解碼的效率。系統(tǒng)使用的倒排文件結構定義新系統(tǒng)的倒排文件由描述文件，索引文件和記錄文件組成，下面分別對它們進行定義。描述文件描述文件記錄了倒排文件自身的屬性信息?？捎肂NF表示如下:des-file=(attributeCRLF)*CRLFattribute=namevaluename=1*<anyCHARexceptCT

26、LsorseparatorsCTLs=<octets031and127>separators(r'|<”|>"|"|：”|""|v”>i門rr門?”|=t'廣't飛value=*<anyoctetexceptCTLs>CRLF=Rn”也就是說，描述文件包括零個或多個<屬性名：屬性值>的行，最后以一個空行為結尾。這與HTTP協(xié)議RFC2616中消息頭的定義類似。現(xiàn)在已定義的屬性有：Byte-Order屬性：表示倒排文件中使用整數(shù)的字節(jié)序，包含壓縮整數(shù)和非壓縮整數(shù)。如果我們使用統(tǒng)一

27、的節(jié)字序，如BigEndian,那么在UttleEndian的機器上使用倒排文件則需要進行字節(jié)的交換，影響效率。所以我們允許自定義倒排文件的字節(jié)序。Byte-Order的屬性值可以是Big-Endian或Little-Endian。默認值為Big-Endian。Align-Bits屬性：前面說過，索引文件中保存的是關鍵詞和其位置信息在記錄文件中的偏移量。為了節(jié)省空間(主要是節(jié)省應用程序內存開銷)，我們在這個文件格式中，使用了32位的偏移量。但是32位的偏移量最多可以表示4GB的空間，而當文檔的數(shù)量比較多，記錄文件的大小肯定是要超過4GB的。因此，這個格式中允許讓記錄文件中每個記錄在某個邊界上對

28、齊，也就是說，讓每個記錄偏移量的低若干位總是0,在索引文件中只保存高32位，再通過移位來獲得記錄的實際偏移量。Align-bits屬性就是表示移動的位數(shù)，默認為0位。由于要讓記錄在邊界上對齊，勢必引起一些空間的浪費。我們假設，Align-bits為n,倒排文件總關鍵詞數(shù)為m。則記錄文件的大小應該在4GX2n-1到4Gx2n之間(如果小于前者，則Align-bits等于n-1就足夠了)，平均每條記錄的空間浪費是2n-1-1字節(jié)，于是，整個倒排文件中，浪費的空間總數(shù)為mx(2n-1-1)字節(jié)。浪費的空間最大可能比例為mX(2n-1-1)/4GX2n-1<m/4G。在實際應用中，m一般不超過5

29、00萬，由此可算出，這個比例不會超過0.125%。Attr-Size屬性：在這個格式中，允許關鍵詞在每個出現(xiàn)它的文檔中，有0個或多個字節(jié)的屬性信息，例如term-><doc1><attr1><doc2><attr2><doc3><attr3>。這個屬性信息的意義在本格式中無定義，完全由應用程序決定。但規(guī)定屬性信息必須是整字節(jié)的，并且所有的屬性信息必須等長。這個長度就是倒排文件的Attr-size屬性。如果未標明，默認為0。Uint-Encoding屬性：壓縮整數(shù)的編碼方式。格式中有規(guī)定哪些整數(shù)是必須壓縮(如文檔號)，

30、哪些是整數(shù)必須是非壓縮(如記錄信息偏移量)，但沒有規(guī)定使用的壓縮編碼算法，應用程序可自行定義。Uint-Encoding屬性默認為上節(jié)描述的ByteCodeEx。索引文件索引文件的結構比較簡單，文件頭用4個字節(jié)的非壓縮整數(shù)表示索引文件中總的關鍵詞量，之后連續(xù)存放記錄。用BNF8示如下：idx-file=term_cntterm_info*term_info=term_lentermoffsetdoclist_lenterm_len=<1字節(jié)無符號整數(shù)>term=*<anyoctet>offset=<4字節(jié)無符號整數(shù)>doclist_len=<壓縮整數(shù)&

31、gt;可以看出，每個t己錄由<term_len><term><offset><doclist_len>組成，分別表示關鍵詞長度，關鍵詞(長度為term_len),關鍵詞的出現(xiàn)位置信息在記錄文件中的偏移量，以及關鍵詞對應文檔列表的字節(jié)長度。當我們要獲得某個關鍵詞的文檔列表，首先獲得關鍵詞上述索引信息，把記錄文件的文件指針移動到對應位置，再調用讀操作，例如：lseeko(fd,(u_int64_t)offset<<align_bits,SEEK_SET);n=read(fd,buf,doclist_len);記錄文件的文檔列表信息中，包含

32、了各文檔號以及關鍵詞在各文檔中的屬性信息，但不包含關鍵詞在各文檔中的位置列表信息。對于單個關鍵詞的查詢來說，位置列表信息沒有必要讀取，上面的信息已經足夠計算相關度了。也就是說，對于單個關鍵詞的查詢，一次讀操作就足夠了。記錄文件記錄文件是整個倒排文件中最重要，也是最復雜的部分。用BNF表示如下:recd-file=(occurpadding)*occur=doclistposinfodoclist=dfdoc*doc=docidattrposlistlenposinfo=poslist*poslist=tfpos*df,docid,poslistlen,tf,pos=<壓縮正整數(shù)>p

33、adding=<占位的字節(jié)，使記錄大小總是2ali9kbits的整倍數(shù)>attr=<長度為attr-size字節(jié)的用>由BNFW見，每個記錄由文檔列表信息（doclist）和在文檔中的位置信息（posinfo）組成，doclist的開始位置用一個壓縮整數(shù)保存了doclist中文檔的個數(shù)，也就是詞的文檔頻率（df）,之后連續(xù)保存每個文檔（doc）的信息，包括文檔號（docid）,關鍵詞在文檔中的屬性（attr）和關鍵詞在本文檔中位置列表的字節(jié)長度（poslistlen）,docid使用差值存放。posinfo由df個位置列表（poslist）所組成，依次對應每一個文檔。每

34、個poslist開始位置存放了關鍵詞在該文檔中的出現(xiàn)次數(shù)，即詞頻（tf）,接下來用差值的形式連續(xù)存放各個位置（pos）。記錄文件和索引文件的示意圖如圖2.1所示（align-bits=3）?？梢钥闯?，記錄文件中每個記錄里又包含了一級的索引，這個索引是從文檔號到位置列表。但是從BNF中發(fā)現(xiàn)，我們只保存了每個文檔的位置列表的長度，并沒有保存位置列表在記錄文件中的實現(xiàn)位置，那么我們得到一個docid之后，如何讀取到位置列表呢？這就與我們對文檔列表的訪問方式有關。我們看到，<docid><attr><len>這個記錄中，只有attr是定長的，其它兩個都是變長整數(shù)，因

35、此我們是不可能對文檔列表進行隨機訪問的，只能順序地讀取。在搜索引擎的檢索系統(tǒng)中，這種訪問模式已經足夠了。從圖中我們又可以看出，所有的文檔列表和位置列表都是連續(xù)存放的，所以，當我們讀取文檔列表的時候，只需把位置列表的長度累加起來，就可以得到下一個位置列表的相對于文檔列表末尾的偏移。例如，第n個文檔的位置列表，在文件中的實際位置為：n-1alignbitsoffsetx2一+doclist_len+工poslist_lenii=1其中，offset和doclist_len都是從索引文件中獲得。這樣的設計使程序在讀取倒排文件的過程中，必須多保留一些信息，并增加了一些計算上的開銷，但offset1=X

36、XXXoffset2=YYYY由此帶來的好處是減少了對空間的占用，這也就減少了讀取磁盤的開銷，同時可能減少應用程序cache的空間開銷。這個交換完全是值得的。<term_len1><termn1><doclist_len1><offset1><term_len2><termn2><doclist_len2><offset2>索引文件XXXX000<df><docid1><attr1><len1><docid2><attr2>&l

37、t;len2><tf1><pos1><pos2><pos3>tf2><pos1'><pos2'><pos3'>tf3><pos1'><pos2'><pos3'><padding>YYYY000<df'><docid1'><attr1'><len1'><docid2'><attr2'>

38、;<len2'>tf1'><pos1><pos2><pos3>tf2'><pos1'><pos2'><pos3'>tf3'><pos1'><pos2'><pos3'><padding>ZZZZ000記錄文件圖2.1記錄文件和索引文件的示意第3章底層數(shù)據(jù)組織影響檢索效率的主要因素首先，我們有必要先了解一下一個查詢被執(zhí)行的過程。如圖1.2所示，當前臺服務器通過廣播的方式把

39、查詢發(fā)送到檢索節(jié)點上，檢索節(jié)點首先對查詢進行預處理，例如切詞，如果支持布爾查詢還必須對查詢表達式進行分析生成一棵查詢語法樹。得到一系列的關鍵詞之后，檢索系統(tǒng)分別從倒排索引中找出各個關鍵詞所對應的文檔列表。一般而言，搜索引擎返回的各文檔里都包含每個查詢關鍵詞，于是我們必須對獲得到的文檔列表求交集，查詢的結果必然就落在這個交集里。接著對交集里的每一個文檔，我們首先計算每個關鍵詞與文檔的相關度得分，再累加起來。這時候我們還沒有利用到詞在文檔中的位置信息。例如我們的查詢是“北京大學”，并且被切為“北京”和“大學”兩個關鍵詞，那么，交集中這兩個詞連續(xù)出現(xiàn)的文檔顯然相關度更高一些。此時我們就要利用到關鍵詞

40、在文檔中的位置信息，對于那些連續(xù)出現(xiàn)這兩個詞的文檔，再增加一些相對位置的得分。在算得每個文檔與查詢的相關度得分之后，我們還不能直接把排好序的結果返回給用戶，因為結果中很多的文檔都是在同一個站點之下的，對用戶來說可能每個站點只需一個結果就夠了，如果有需要可以再點擊站內查詢。于是，我們還需要根據(jù)站點對結果集進行聚類，每個站點內只保留一個或兩個結果，把最重要的一些結果連同相關度得分返回給前臺服務器。前臺服務器收集到各檢索節(jié)點發(fā)來的結果，進行歸并再把得分最高的返回給搜索引擎用戶。本文現(xiàn)在只關心檢索節(jié)點做的事情，其中切詞與檢索效率關系不大，我們也不討論。其它的包含以下五個部分：.獲取文檔列表從倒排文件的

41、結構中我們可以看出，要獲得給定關鍵詞的文檔列表，首先要從索引文件中找到對應的入口，得到offset和doclist_len之后再到記錄文件中讀取文檔列表信息。顯然，從索引文件頭開始順序查找關鍵詞是不現(xiàn)實的，與原有天網(wǎng)系統(tǒng)相同，我們把term-><offset,doclist_len>這個索引信息常駐內存。而對于記錄文件中的文檔列表信息，要讓它們都常駐內存似乎就有一些困難了。但根據(jù)文獻王建勇等,2001,Saraiva,etal.,2001,用戶查詢詞的分布具有很強的局部性，大多數(shù)經常被檢索的詞都是集中在一個很小的范圍之內的。另外，該文獻還提到，用戶查詢有一定的穩(wěn)定性，用戶在一

42、段時間內發(fā)出的查詢往往有一些相似。這兩方面說明了對倒排文件使用cache的有效性，通過良好的cache結構，讓盡可能多的查詢詞在內存中找到對應的文檔列表，減少訪問磁盤的開銷，正是本系統(tǒng)中提高檢索效率的一個重要方法。.文檔列表求交集前面提到，從倒排索引中獲得的文檔列表一定是按文檔號升序排列的，這就為我們求文檔列表的交集帶來了很多方便。新系統(tǒng)中，求文檔交集的算法也有一些改進，由原來的每次兩列進行求交，改為多列同時求交。但實驗說明這一步操作并非影響檢索效率的關鍵。.計算關鍵詞與文檔相關度對各個關鍵詞和文檔求相關度得分是檢索過程中使用CPU最多的一個步驟，主要是浮點運算的操作。例如使用傳統(tǒng)的tf*id

43、f的計算方法，每個關鍵詞相對于每篇文檔，都至少要進行3次的取對數(shù)運算。雖然在檢索系統(tǒng)中，對外存的訪問時間是決定系統(tǒng)性能的關鍵，但如果可以節(jié)省相關度計算的時間，也可以在一定的程度上提高檢索效率。.計算相對位置對于由多個關鍵詞組成的查詢，計算它們相對位置應該說是整個檢索過程最耗時的部分。特別是當關鍵詞都是高頻詞的時候，文檔列表的交集中的文檔個數(shù)可能達到上百萬個。此時讀取每個詞在每個文檔中的位置信息，如果不進行特別處理，則要進行上百萬次的讀盤操作。如果對關鍵詞在文檔中的位置信息進行cache其消耗的內存要比文檔列表大得多。因此，提高計算相對位置的效率也是改善系統(tǒng)整體性能的關鍵。.站點聚類站點聚類不涉

44、及對磁盤的操作，其效率并不會構成系統(tǒng)的瓶頸。但新的系統(tǒng)還是改進了原有的算法，通過先聚類后排序的方式，減少了最終進行排序的文檔量，從時間復雜度上對性能進行了優(yōu)化。在這一章里，我們主要討論的是系統(tǒng)最底層的數(shù)據(jù)組織。這個模塊為上層的模塊提供了一個快速的訪問索引文件的接口，同時它負責對文檔列表和位置列表的cache進行組織。我們將以模塊的接口為主線來分析其數(shù)據(jù)組織。創(chuàng)建索引要訪問索引文件首先必須創(chuàng)建一個索引對象(index),其接口如下：index_t*createindex(constchar*desfile,constchar*idxfile,constchar*datafile,size_tca

45、che_max);前三個參數(shù)分別是描述文件，索引文件和記錄文件的文件名，最后一個參數(shù)cache_max為index對象可用的文檔列表cache最大值，必須根據(jù)硬件條件來確定。在index.c文件中我們可以看到如下的定義：typedefstruct_indexindex_t;struct_indexintdatafd;unsignedintalign_bits;size_tattr_size;size_tterm_cnt;struct_term_entry*term_list;mbuf_t*mbuf;structlist_headdoc_list;size_tcache_max;size_tca

46、che_size;當createindex被調用時，描述文件和索引文件中的內容被一次地讀入內存，索引文件中的索引信息被保存在term_list域中，按照關鍵詞開存排列，在查找時使用二分查找的方式。與原有系統(tǒng)使用散列查找的方法有所不同。原因是，使用散列將引起太多的內存浪費。可以大致的計算一下，假設總的關鍵詞數(shù)為m,散列的空間至少需要3m,則至少浪費2m個指針的空間。而且每個關鍵詞入口還至少需要一個指針來解決散列函數(shù)的沖突，于是總的多余指針開銷達到3m個。假設m等于500萬，則浪費的總字節(jié)數(shù)為3X500萬X系統(tǒng)地址長度，在32位系統(tǒng)下大約為60MB。而由于關鍵詞都已經一次性讀入內存，對關鍵詞的查找

47、所占用的時間幾乎可以乎略不計，在認真考慮之后系統(tǒng)使用了二分的查找方式。關鍵詞列表在內存中的組織如下圖：index圖3.1關鍵詞列表關鍵詞列表是一個指針的數(shù)組，各指針指向的內存塊中保存的關鍵詞信息。但從圖中我們可以看出，這些內存塊的長度并不一樣，這是為了盡量節(jié)省內存的開銷而使用了變長結構，這個結構的定義如下：struct_term_entry(union(struct_doc_list_head*doc_list;unsignedintoffset;unsignedintpos_info_size:8;unsignedintterm_len:8;charterm1;)；最后一個域term為關鍵詞

48、的原文，term_len表示關鍵詞長度。在關鍵詞之后還有一個變長整數(shù)記錄了關鍵詞所對應的文檔列表信息的長度，從結構的定義上看不到。在為每個term_entry分配內存之前都必須精確計算出它所需的字節(jié)數(shù)。如果最后一個域定義為char*term,則平均每個結構會增加3個指針的額外開銷。offset域保存了關鍵詞文檔列表信息在記錄文件中的偏移，這個域與doc_list域共用一個內存單元，如果該關鍵詞的文檔列表在cache中，則doc_list域指向cache中的文檔列表。但我們并沒有看到結構中用來標識文檔列表是否在cache中的域，這是因為這個標志被存放在term_list指針數(shù)組每個指針的最低位。

49、在使用內存分配函數(shù)(如malloc)獲得內存時，得到的內存至少是與計算機系統(tǒng)的字長對齊的，最低兩個位必然是0,這兩個位可以被用來保存一些信息。除了最低位用來標識文檔列表是否被cache,次低位也被利用，它被用來標識pos_info_size域的計數(shù)單位(粒度)。pos_info_size域保存的是關鍵詞所有位置列表信息的總長度，指針次低位用于標識這個長度是以16字節(jié)為單位還是以4K字節(jié)為單位。由于指針中一些位被程序所利用，因此需要一次轉換來獲得實際地址，例如：#defineDOC_LIST_MASK#definePOS_INFO_MASK#defineMASK_ALL#defineTERM_E

50、NTRY(ptr)1UL2UL(DOC_LIST_MASK|POS_INFO_MASK)(struct_term_entry*)(*(unsignedlong*)(ptr)&MASK_ALL)此外為了避免動態(tài)內存管理而引起的平均兩個指針額外內存開銷，在為term_entry分配內存時并不是直接調用malloc函數(shù)，而是通過一個專門設計的類(mbuf)來負責內存分配。該對象可把額外開銷降至幾乎為零，但必須保證后申請的內存先被釋放。使用完index對象，必須調用destroyindex函數(shù)將對象釋放。函數(shù)原型為:voiddestroyindex(index_t*index);3.3獲得文檔

51、列表接口與數(shù)據(jù)組織創(chuàng)建了index對象，要得到關鍵詞對應的文檔列表，首先要獲得文檔列表對象，其調用是：doclist_t*getdoclist(constchar*term,size_tlen,index_t*index);第一參數(shù)term為關鍵詞，根據(jù)索引文件的格式定義可以包含任意字符；len表示關鍵詞的長度；index參數(shù)為createindex函數(shù)生成的索引對象。getdoclist函數(shù)首先從index->term_list找到對應的term_entry,如果該關鍵詞的文檔列表不在cache中，則把它從記錄文件讀到cache,如果cache已經達到最大值還要淘汰掉那些最久沒有被訪問

52、到的文檔列表。下圖是文檔列表在cache中的組織：indexdoclistcache圖3.2文檔列表的cache組織我們看看每個文檔列表cache的結構:struct_doc_list_cache(structlist_headIru;size_tstruct_size;struct_term_entry*entry;unsignedintoffset;chardoc_list1;);所有文本3列表cache通過lru域以鏈表的形式組織，由于這也是一個變長結構，因此我們用struct_size來記錄下結構實際占用的空間，用于統(tǒng)計當前總的cache使用量。entry指回termlist中對應的位

53、置，以便當cache被淘汰時把最低位清0。offset域取自對應的termentry,因為當文檔列表被讀入cache時,termentry中的offset域被doc_list指針所覆蓋，當cache被換出時要把它恢復。這么做的目也是為了節(jié)省內存的占用。doclist對象內有一個指針，當對象被創(chuàng)建時，它指向了cache中的對應文檔列表開始位置。文檔列表的cache使用LRU的淘汰策略，當cache被一個doclist對象引用時，還要把它移到鏈表的最前端。cache中的文檔列表數(shù)據(jù)以壓縮的形式存放。止匕外，在上一節(jié)中我們提到，每個termentry中有一個域用于保存關鍵詞位置信息總長度，并且有16

54、字節(jié)或4K字節(jié)現(xiàn)兩種粒度。當把文檔列表從外存讀到cache中的時候，如果發(fā)現(xiàn)其粒度為16字節(jié)，也就是說位置列表信息的總長度不超16X255字節(jié)，則會把關鍵詞在各文檔中的位置列表信息一起讀入內存(根據(jù)倒排文件的格式，位置信息緊跟著文檔列表信息存放)。這樣當程序需要讀取關鍵詞的在各文檔中的位置列表時，無需再進行磁盤的讀取操作。在獲得文檔列表對象之后，可調用readdoclist函數(shù)讀取到文檔列表中的信息：size_treaddoclist(structdoc_entry*docs,size_tn,doclist_t*doclist);該函數(shù)從doclist對象中讀出n個文檔，并把doclist的內

55、部指針向前移動，這類似于文件系統(tǒng)的read操作。但與文件系統(tǒng)不同，doclist不存在類似lseek的操作，這是因為cache中數(shù)據(jù)都是壓縮的，只能順序訪問。在index.h中有doc_entry結構的定義：structdoc_entry(unsignedintdocid;constchar*attr;unsignedint_offset;unsignedint_len;)；前兩個域分別為文檔號與關鍵詞在文檔中的屬性,調用者可直接使用。_len域記錄了關鍵詞在文檔中位置信息的長度，_offset域是該文檔之前所有文檔_len域的總和。在2.3.3節(jié)中我們提到過，可用于計算位置列表信息在記錄文件

56、中的位置。函數(shù)的調用者并不需要直接訪問這兩個域，但它們在獲取位置列表的時候有作用。使用完doclist對象之后，需調用函數(shù)freedoclist將對象釋放：voidfreedoclist(doclist_t*doclist);3.3.2性能測試卜面我們對cache的性能進行測試。我們選用了天網(wǎng)查詢日志中的20000個查詢記錄，測試的文檔集合約250萬文檔，倒排文件中，attr_size=2我們先看看cache命中率隨著cache大小的變化:T一字節(jié)命中率T一文檔列表命中率可以看出，當cache最大值為500MB時，就有超過85%的字節(jié)命中率，這個數(shù)字似乎很激動人心。但是另一組實驗數(shù)據(jù)卻很出乎意

57、料，下圖是cache大小和查詢響應時間的變化關系(測試中沒有計算關鍵詞在文檔中的相對位置，且所有請求串行發(fā)送)：查詢響應時間(ms)圖3.4cache大小對查詢響應時間的影響可以說這個結果很讓人失望，我們發(fā)現(xiàn)雖然cache命中率越來越高，但對查詢的響應是時間卻沒有什么影響，甚至有變慢的趨勢。分析其原因：操作系統(tǒng)自身有cache機制，操作系統(tǒng)會把當前所有可用的內存用作文件系統(tǒng)cache,以減少對磁盤的真正訪問次數(shù)，提高IO速度。由于文件系統(tǒng)cache的存在，我們對文檔列表cache#用也就很不明顯了。但這似乎還不能說明問題，因為我們根據(jù)自己的需要組織cache,性能應該會比文件系統(tǒng)cache更好

58、一點。于是我們又把cache最大值調到1500MB,發(fā)現(xiàn)系統(tǒng)性能急劇下降。經過分析，認為是索引系統(tǒng)的某些頁面被換出引起。由于文件系統(tǒng)cache的需要，把用戶程序的一些物理內存頁面交換到虛擬內存，當這些頁面再次需要使用時又被換入，使得磁盤IO開銷很大?，F(xiàn)在，我們換一個實驗環(huán)境來試試，我們選用一臺有16GB內存的計算機，以確保無需用到虛擬內存，其結果如下：r查詢響應時間（ms）圖3.5cache大小對查詢響應時間的影響（系統(tǒng)內存16GB）可以看出在這種情況下cache確實起了一定的作用，但由于文件系統(tǒng)同樣有cache的原因，因此效果并不明顯。我們回到那臺2GB內存的機器，并把文件系統(tǒng)cache禁用

59、AndreaArcangeli,2001（在打開文件時使用O_DIRECT標志）,在這種方式下，數(shù)據(jù)通過DMA方式直接從磁盤傳送到用戶空間的內存，無需經過內核空間的交換，減少了內存的重制次數(shù)。再做一次實驗，結果如下：10圖3.6cache大小對查詢響應時間的影響（關閉文件系cache)此時cache的作用就比較明顯了，并且，當cache大小為1GB的時候，響應時間比圖3.4中任何一個都要快。雖然說使用1GB的內存用于文檔列表cache可能不太值得，但至少說明，我們可以通過自己組織cache的方式，繞開文件系統(tǒng)cache來提高檢索的性能。由于在讀取以O_DIRECT方式打開的文件時，緩沖區(qū)內存，傳輸?shù)臄?shù)據(jù)長度和文件偏移量都必須是頁面對齊（Linux內核2.6之后只要求512字節(jié)對齊），導致實際讀取的數(shù)據(jù)要多一點。因此如果要設計一個這種方式的檢索系統(tǒng)，可以考慮記錄文件和cache都以固定大小的塊形式組織