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

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

2、能問題進(jìn)行了研究，討論了影響檢索性能的幾個(gè)因素，并分別提出改進(jìn)的方法和途徑。這些方法包括設(shè)計(jì)出結(jié)構(gòu)更加良好的倒排文件結(jié)構(gòu)，改進(jìn)整數(shù)壓縮編碼，引入倒排文件cache,預(yù)先計(jì)算關(guān)鍵詞與文檔相關(guān)度，減少關(guān)鍵詞相對(duì)位置計(jì)算開銷，改進(jìn)站點(diǎn)聚類算法等。另外，論文還闡述了系統(tǒng)中使用的新的相關(guān)度計(jì)算方法，這個(gè)算法使得在最終的結(jié)果排序上比原有系統(tǒng)有了一些改進(jìn)。論文的組織形式以實(shí)際系統(tǒng)中各模塊為主線，這些模塊包括倒排文件結(jié)構(gòu)，底層數(shù)據(jù)接口，查詢，計(jì)分和站點(diǎn)聚類等。在論文最后給出了系統(tǒng)的綜合測(cè)試結(jié)果，指出系統(tǒng)中還存在的不足，并對(duì)后續(xù)工作提出了一些建議。關(guān)鍵詞：搜索引擎，檢索系統(tǒng)，倒排文件，檢索效率，相關(guān)度計(jì)算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)分布式結(jié)構(gòu).4.1.4 現(xiàn)有系統(tǒng)的不足與本文的主要貢獻(xiàn)5第2章倒排文件設(shè)計(jì) 基本原則 整數(shù)壓縮編碼方法 系統(tǒng)使用的倒排文件結(jié)構(gòu)定義81 描述文件8.1 索引文件101 記錄文件10第3章底層數(shù)據(jù)組織131.1.< 影響檢索效率的主要因素1.31.2.< 創(chuàng)建索引1.51.3.< 獲得文檔列表18< 接口與數(shù)據(jù)組織1.8< 性能測(cè)試201.4.< 獲得位置列表231.5.< 模塊的一些不足26第4章查詢過程274.2 文檔列表求交274.3 相關(guān)度計(jì)算284.3.1 關(guān)鍵詞與文檔相關(guān)度284.3.2 相對(duì)位置得

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24、7,對(duì)于小整數(shù)占多數(shù)的倒排文件來說，壓縮率比較高，可以為每個(gè)從64至127的整數(shù)節(jié)省去一個(gè)字節(jié)的空間。但當(dāng)整數(shù)的范圍從221到222-1時(shí)，則會(huì)多占用一個(gè)字節(jié)。ByteCodeEx可擴(kuò)展到無限大的正整數(shù)。以下是為2576933個(gè)文檔建立倒排索引，對(duì)整數(shù)的使用情況統(tǒng)計(jì)：表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有不小的提高。對(duì)于LittleEndian的計(jì)算機(jī)系統(tǒng)，編碼方式略有不同，表示壓縮整數(shù)長(zhǎng)度的位從第一個(gè)字節(jié)的最低位開始，并且也先存放低字節(jié)。這樣做是為了提高編碼和解碼的效率。系統(tǒng)使用的倒排文件結(jié)構(gòu)定義新系統(tǒng)的倒排文件由描述文件，索引文件和記錄文件組成，下面分別對(duì)它們進(jìn)行定義。描述文件描述文件記錄了倒排文件自身的屬性信息。可用BNF表示如下:des-file=(attributeCRLF)*CRLFattribute=namevaluename=1*<anyCHARexceptCT

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

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

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

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

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

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

32、了各文檔號(hào)以及關(guān)鍵詞在各文檔中的屬性信息，但不包含關(guān)鍵詞在各文檔中的位置列表信息。對(duì)于單個(gè)關(guān)鍵詞的查詢來說，位置列表信息沒有必要讀取，上面的信息已經(jīng)足夠計(jì)算相關(guān)度了。也就是說，對(duì)于單個(gè)關(guān)鍵詞的查詢，一次讀操作就足夠了。記錄文件記錄文件是整個(gè)倒排文件中最重要，也是最復(fù)雜的部分。用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=<長(zhǎng)度為attr-size字節(jié)的用>由BNFW見，每個(gè)記錄由文檔列表信息（doclist）和在文檔中的位置信息（posinfo）組成，doclist的開始位置用一個(gè)壓縮整數(shù)保存了doclist中文檔的個(gè)數(shù)，也就是詞的文檔頻率（df）,之后連續(xù)保存每個(gè)文檔（doc）的信息，包括文檔號(hào)（docid）,關(guān)鍵詞在文檔中的屬性（attr）和關(guān)鍵詞在本文檔中位置列表的字節(jié)長(zhǎng)度（poslistlen）,docid使用差值存放。posinfo由df個(gè)位置列表（poslist）所組成，依次對(duì)應(yīng)每一個(gè)文檔。每

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

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

36、XXXoffset2=YYYY由此帶來的好處是減少了對(duì)空間的占用，這也就減少了讀取磁盤的開銷，同時(shí)可能減少應(yīng)用程序cache的空間開銷。這個(gè)交換完全是值得的。<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ù)組織影響檢索效率的主要因素首先，我們有必要先了解一下一個(gè)查詢被執(zhí)行的過程。如圖1.2所示，當(dāng)前臺(tái)服務(wù)器通過廣播的方式把

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

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

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

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

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

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

45、che_max);前三個(gè)參數(shù)分別是描述文件，索引文件和記錄文件的文件名，最后一個(gè)參數(shù)cache_max為index對(duì)象可用的文檔列表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;當(dāng)createindex被調(diào)用時(shí)，描述文件和索引文件中的內(nèi)容被一次地讀入內(nèi)存，索引文件中的索引信息被保存在term_list域中，按照關(guān)鍵詞開存排列，在查找時(shí)使用二分查找的方式。與原有系統(tǒng)使用散列查找的方法有所不同。原因是，使用散列將引起太多的內(nèi)存浪費(fèi)。可以大致的計(jì)算一下，假設(shè)總的關(guān)鍵詞數(shù)為m,散列的空間至少需要3m,則至少浪費(fèi)2m個(gè)指針的空間。而且每個(gè)關(guān)鍵詞入口還至少需要一個(gè)指針來解決散列函數(shù)的沖突，于是總的多余指針開銷達(dá)到3m個(gè)。假設(shè)m等于500萬，則浪費(fèi)的總字節(jié)數(shù)為3X500萬X系統(tǒng)地址長(zhǎng)度，在32位系統(tǒng)下大約為60MB。而由于關(guān)鍵詞都已經(jīng)一次性讀入內(nèi)存，對(duì)關(guān)鍵詞的查找

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

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

49、在使用內(nèi)存分配函數(shù)(如malloc)獲得內(nèi)存時(shí)，得到的內(nèi)存至少是與計(jì)算機(jī)系統(tǒng)的字長(zhǎng)對(duì)齊的，最低兩個(gè)位必然是0,這兩個(gè)位可以被用來保存一些信息。除了最低位用來標(biāo)識(shí)文檔列表是否被cache,次低位也被利用，它被用來標(biāo)識(shí)pos_info_size域的計(jì)數(shù)單位(粒度)。pos_info_size域保存的是關(guān)鍵詞所有位置列表信息的總長(zhǎng)度，指針次低位用于標(biāo)識(shí)這個(gè)長(zhǎng)度是以16字節(jié)為單位還是以4K字節(jié)為單位。由于指針中一些位被程序所利用，因此需要一次轉(zhuǎn)換來獲得實(shí)際地址，例如：#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)此外為了避免動(dòng)態(tài)內(nèi)存管理而引起的平均兩個(gè)指針額外內(nèi)存開銷，在為term_entry分配內(nèi)存時(shí)并不是直接調(diào)用malloc函數(shù)，而是通過一個(gè)專門設(shè)計(jì)的類(mbuf)來負(fù)責(zé)內(nèi)存分配。該對(duì)象可把額外開銷降至幾乎為零，但必須保證后申請(qǐng)的內(nèi)存先被釋放。使用完index對(duì)象，必須調(diào)用destroyindex函數(shù)將對(duì)象釋放。函數(shù)原型為:voiddestroyindex(index_t*index);3.3獲得文檔

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

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

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

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

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

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

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

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

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