大規(guī)模超文本網(wǎng)絡(luò)搜索引擎剖析

1、大規(guī)模超文本網(wǎng)絡(luò)搜索引擎剖析SergeyBrinandLarrypage概述在這篇文章中，我們介紹Google,一個大規(guī)模搜索引擎的原型。Google被設(shè)計成未可以進行有效的網(wǎng)絡(luò)抓取和索引并返回比現(xiàn)行系統(tǒng)更加讓人滿意的搜索結(jié)果。我們的這個原型包括索引了2千4百萬頁面的全文本和超鏈接的數(shù)據(jù)庫，你可以通過來進行訪問。對于一個計算機工程師來說，建立一個搜索引擎可以說是一項具有挑戰(zhàn)性的任務(wù)，因為搜索引擎索引成百上千萬頁面的同時也涉及到了相同數(shù)量級別的關(guān)鍵詞(Terms)。并且每天要回答超過1千萬個查詢請求。雖然，在當(dāng)今網(wǎng)絡(luò)中，搜索引擎的重要程度正越來

2、越突出的顯現(xiàn)出來，但是真正學(xué)術(shù)上的相關(guān)研究卻很少。而且，隨著科技的飛速發(fā)展和網(wǎng)絡(luò)規(guī)模的不斷擴大，在今天建立一個搜索已經(jīng)和三年前大不相同了。這篇論文提供了關(guān)于如何創(chuàng)建一個大規(guī)模搜索引擎的深層次描述，這也是到目前為止我們所知道的第一篇在這一領(lǐng)域的論文。除了一些傳統(tǒng)的數(shù)據(jù)級別相同的搜索引擎的技術(shù)，還有一些新的運用在超文本中旨在創(chuàng)建更為優(yōu)化的搜索結(jié)果的技術(shù)。如何建立一個可以深度挖掘利用超文本中信息的大規(guī)模搜索引擎？這是本文提出的一個問題。同時，我們關(guān)注的另外一個問題是：對于那些不受傳統(tǒng)格式限制的超文本，我們?nèi)绾蝸磉M行處理？關(guān)鍵詞：萬維網(wǎng)(WorldWideWeb),搜索引擎(SearchEngines

3、),信息檢索(InformationRetrieval),PageRank,Google1 .介紹網(wǎng)絡(luò)(Web)給信息檢索領(lǐng)域帶來了新的挑戰(zhàn)。就像飛速增長的對Web搜索毫無經(jīng)驗的新用戶一樣，互聯(lián)網(wǎng)上的信息量也在疾速地擴充。人們習(xí)慣于利用網(wǎng)頁上的鏈接結(jié)構(gòu)來進行網(wǎng)上沖浪。通常他們的網(wǎng)上旅程都是從高質(zhì)量的人工維護索引的網(wǎng)站比如說Yahoo或者搜索引擎開始的。人為維護的列表可以有效地包含一些熱點流行的話題但是帶來的問題是：建立和維護這樣一個引用表上的成本過于昂貴和主觀化、難以及時的進行改進、不能包括所有深入的主題。依賴于關(guān)鍵詞匹配的自動化搜索引擎通常會返回一些低質(zhì)量的結(jié)果給用戶。更加惡劣的是，一些廣告

4、商為了吸引用戶的眼球，不惜誤導(dǎo)這些搜索引擎來返回錯誤的結(jié)果給用戶。我們建立了一個能夠解決這些現(xiàn)存系統(tǒng)中問題的大規(guī)模搜索引擎。這套系統(tǒng)能夠利用超文本中的信息來返回高質(zhì)量的搜索結(jié)果給用戶。我們把系統(tǒng)取名為Google,這個名稱來源于Googol,意思是1后面100個0。這個名字能夠更好的反映出我們建立這個系統(tǒng)的目標(biāo)。1.1 .Web搜索引擎：規(guī)模的擴大：1994-2000為了適應(yīng)互聯(lián)網(wǎng)絡(luò)的飛速發(fā)展，搜索引擎技術(shù)這些年來有了質(zhì)的飛躍。在1994年，萬維網(wǎng)蟲(WorldWideWebWorm),作為一個最早期的互聯(lián)網(wǎng)搜索引擎在當(dāng)時索引了11萬個Web頁面和可以訪問的Web文檔。到了1997年的11月，

5、頂級的搜索引擎(WebCrawler)號稱已經(jīng)索引了1億個Web文檔?？梢灶A(yù)見的是，至U2000年，可以索引的Web文檔數(shù)量將會超過10億個。與此同時，搜索引擎所要應(yīng)付的查詢請求也在以難以置信的速度增長。1994年的3,4月間，WorldWideWebWorm每天大概接受1500個請求。在1997年的11月，Altavista聲稱其每天處理約2千萬個請求。隨著互聯(lián)網(wǎng)用戶和自動請求搜索引擎的系統(tǒng)的增加，到2000年底，一些頂尖搜索引擎很有可能達到日處理2千萬個請求的數(shù)量級。我們系統(tǒng)的目標(biāo)是在質(zhì)量和規(guī)模上解決所有由上述趨勢所帶來的問題。1.2 Google抓取網(wǎng)絡(luò)建立一個搜索引擎抓取目前的互聯(lián)網(wǎng)帶

6、來了很多挑戰(zhàn)，為了能夠收集網(wǎng)絡(luò)文檔并保持他們的時效性，一種快速的抓取技術(shù)是必須的。存儲空間必須被合理利用來存儲索引和文檔本身；索引系統(tǒng)必須能夠有效地處理海量數(shù)據(jù)；請求必須能夠以每秒幾百甚至幾千次的速度被快速地處理。這些問題隨著互聯(lián)網(wǎng)規(guī)模的擴大將會變得越來越困難。然而，硬件性能的改進和成本的降低部分地解決了一些困難。但是，這些硬件的發(fā)展也帶來了一定程度的副作用。比如說磁盤定位時間和操作系統(tǒng)的健壯性。在設(shè)計Google的過程中，我們充分考慮到了互聯(lián)網(wǎng)增長的速率和技術(shù)的變化。Google被設(shè)計成可以有效地適應(yīng)海量的數(shù)據(jù)集。Google能夠有效地利用存儲空間來存儲索引。為了快速有效地對其數(shù)據(jù)進行訪問，

7、我們優(yōu)化了它的數(shù)據(jù)結(jié)構(gòu)。除此以外，我們設(shè)想，Google索引和存儲文檔和Html的消耗將最終減少到一個可以接受的數(shù)量級。這將為一個像Google一樣的中心化系統(tǒng)帶來可觀的抓取特性。1.3 設(shè)計目標(biāo)1.3.1 改進的搜索質(zhì)量我們的主要目的是為了改進Web搜索引擎的質(zhì)量。在1994年，一些人相信一個完全索引的搜索引擎將能夠很容易的為我們找到所需要的內(nèi)容。根據(jù)數(shù)據(jù)顯示，1997年的Web已經(jīng)大不相同了。這些年來，任何一個使用了搜索引擎的用戶都可以去測試并感知索引的完整性并不是用來衡量搜索結(jié)果質(zhì)量的唯一因素?！袄Y(jié)果(JunkResults)"常常將一些用戶感興趣的結(jié)果給掩蓋了。事實上，在

8、1997年11月，只有4家頂級的商業(yè)搜索引擎能夠在搜索結(jié)果中找到自己(根據(jù)輸入自己的名稱在自己的搜索結(jié)果的前10條記錄中返回自己)。一個主要原因是索引中文檔的數(shù)量增加了好幾個數(shù)量級的同時用戶閱讀文檔的能力卻沒有相應(yīng)的增加。人們還是希望能在結(jié)果的前面幾十個結(jié)果文檔中就能找到他們所需要的信息。正因為此，隨著集合大小的增加，我們需要一個工具來對結(jié)果進行精準(zhǔn)的定位(將最為相關(guān)的文檔在結(jié)果的前十個中返回)。當(dāng)然，我們希望我們所說的“相關(guān)”是在結(jié)果中僅僅包括從上萬個輕度相關(guān)的文檔中返回最好的文檔。這種高度查準(zhǔn)率(Precision)哪怕是在犧牲查全率(Recall)的條件下都是尤為重要的。最近有很多的利用

9、更多超文本信息的優(yōu)化措施用來幫助改善搜索和其他應(yīng)用程序的。特別的，鏈接結(jié)構(gòu)和鏈接文本為了做出相關(guān)性判斷和質(zhì)量過濾提供了大量有用的信息。Google為了達到目標(biāo)使用了鏈接結(jié)構(gòu)和錨定文本(anchortext)1.3.2 理論搜索引擎研究隨著時間的變遷，互聯(lián)網(wǎng)除了飛速增長之外，也變得越來越商業(yè)化。在1993年，大概1.5%左右的Web服務(wù)器使用的是.Com的域名。這個數(shù)字在1997年的時候增長到了60%。與此同時，搜索引擎也從純粹的理論學(xué)院派研究轉(zhuǎn)移到了商業(yè)應(yīng)用上。到目前為止，多數(shù)搜索引擎的發(fā)展都是由一些公司主導(dǎo)并且很少有相關(guān)技術(shù)細節(jié)的論文發(fā)表。這導(dǎo)致了搜索引擎技術(shù)被大眾認(rèn)為是一種魔法。我們在設(shè)計

10、Google的時候就有一個目標(biāo)，為了給理論中的相關(guān)領(lǐng)域帶來更多的發(fā)展和認(rèn)識。另外一個很重要的設(shè)計目的是為了能夠讓更多的人可以實際使用我們的系統(tǒng)。用戶的使用對于我們來說是非常重要的，因為我們認(rèn)為很多有趣的研究都將涉及如何平衡大量數(shù)據(jù)的使用。例如，每天都有成千上萬的搜索。但是，得到這些搜索日志的數(shù)據(jù)卻是非常困難的因為這些數(shù)據(jù)常常被認(rèn)為是有商業(yè)用途而不會公開的。我們的終極設(shè)計目的是創(chuàng)建一個這樣的架構(gòu)：這個架構(gòu)能夠支持很多涉及大數(shù)據(jù)集的新型研究活動。為了達到這個目的，Google將所有抓取到的文檔都已壓縮的形式存儲了下來。我們設(shè)計Google的一個主要目的是建立一個環(huán)境：研究人員可以迅速的融入進來，處

11、理網(wǎng)絡(luò)的大塊數(shù)據(jù)并且得出在其他的環(huán)境中很難獲得的研究成果。在系統(tǒng)建立的初期，我們已經(jīng)利用Google的數(shù)據(jù)庫發(fā)表了幾篇論文，還有許多論文正在進行中。另外一個我們的目的是建立一個類似宇宙空間實驗室的環(huán)境。在這里，研究員，甚至是學(xué)生都可以在我們提供的大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)集上進行各種各樣的有趣的研究計劃。2 .系統(tǒng)特征Google的兩項重要特性幫助Google返回高查準(zhǔn)率的搜索結(jié)果。第一，Google利用網(wǎng)絡(luò)的鏈接結(jié)構(gòu)來計算每一個Web頁面的排名。這種排名叫做PageRank,有關(guān)這項技術(shù)的細節(jié)可以參考Page98.第二，Google利用鏈接來改進搜索結(jié)果。2.1 PageRank：為網(wǎng)絡(luò)排序網(wǎng)絡(luò)的引用圖

12、是一項非常重要的資源但是卻常常被當(dāng)今的一些搜索引擎忽略了。我們創(chuàng)建了一個包括了5億1千八百萬類似于這樣的超鏈接的地圖。這些地圖使我們可以快速的計算一個Web頁面的PageRank值。PageRank是某個Web頁面引用重要性的客觀量度。這種重要性與人們主觀上關(guān)于重要性認(rèn)識是一致的。正是基于此，PageRank是一種把搜索結(jié)果根據(jù)Web關(guān)鍵詞搜索排序的絕佳途徑。對于眾多熱門的主題，在使用了PageRank對結(jié)果進行了排序以后，一個簡單的對Web頁面標(biāo)題的嚴(yán)格文本匹配搜索就可以獲得絕佳的性能。對于Google系統(tǒng)中的全文搜索而言，PageRank更是起到了重要的作用。2.1.1 PageRank計

13、算描述：學(xué)術(shù)上的引用文獻方法被應(yīng)用到了Web上，很大程度上被用來計算一個給定頁面的被引用的次數(shù)和向后鏈接(backlinks)。這種方法可以給出一個頁面重要程度和質(zhì)量的估計值。PageRank對這種方法進行了延伸：并不是對來自于所有頁面的鏈接進行相等的相加，而是對一個頁面上的鏈接數(shù)進行規(guī)格化。PageRank定義如下：假設(shè)頁面A有頁面T1TN的指向。參數(shù)d作為一個阻尼因子，它的值可以設(shè)定為0到1之間。我們通常設(shè)為0.85。下一節(jié)中我們將有關(guān)于d的更多細節(jié)。C(A)被定義為頁面A指向其他頁面的鏈接個數(shù)。頁面A的PageRank計算如下：PR(A)=(1-d)+d(PR(T1)/C(T1)+.+P

14、R(Tn)/C(Tn)注意到PageRank在Web頁面上組成了一個概率分布。所以我們不難得出所有Web頁面的PageRank和為1PageRank可以通過一個簡單的迭代算法來進行計算，而且這是符合Web鏈接規(guī)格化矩陣的主特征向量的。同樣的，一個關(guān)于2千6百萬Web頁面的PageRank計算可以在一臺中等規(guī)模的工作站上只用幾個小時就計算完成。更多關(guān)于PageRank計算的細節(jié)超出了本文的討論范圍。2.1.2 直覺地判斷PageRank可以被認(rèn)為是用戶習(xí)慣的模型。我們假設(shè)存在一個“隨機沖浪者”，我們隨機給他一個Web頁面，讓他持續(xù)的點擊其中的鏈接，我們的沖量者從來不會返回，但是他最終會感到疲倦然

15、后從另外一個隨機頁面開始新一輪的沖浪。隨機沖浪者訪問一個頁面的概率就是這個頁面的PageRank值。而且阻尼系數(shù)d值是隨機沖浪者在每個頁面上感到厭倦選擇新的隨機頁面的概率。一個重要的變化因素是僅僅為一個單獨的頁面或者一組頁面增加d值。這種方式允許個性化并且使得故意誤導(dǎo)系統(tǒng)使獲得高排名的企圖幾乎不可能實現(xiàn)。我們對于PageRank還有一些其他的擴充，同樣可以參考Page98另外的一種直覺判斷是這樣的，一個頁面如果擁有很高的PageRank那么表明肯定有很多頁面指向它。直觀地，被互聯(lián)網(wǎng)上多處引用的頁面一定是值得訪問的。同樣的，如果一個頁面僅僅被一個頁面引用，但是這個引用頁面是類似于Yahoo首頁這

16、樣的頁面，我們認(rèn)為這樣的頁面同樣是值得去訪問的。如果一個頁面不具有高質(zhì)量或者是一個壞鏈接，通常像Yahoo首頁這樣的頁面是不會有這樣的鏈接的。PageRank通過Web的連接結(jié)構(gòu)遞歸的傳遞權(quán)值來處理上述的兩個問題。2.2 錨定文本鏈接的文本在我們的搜索引擎中被特殊的處理了，大多數(shù)的搜索引擎將鏈接的文本和該頁面聯(lián)系起來。我們除了進行這些處理以外，我們還把這些文本與鏈接指向的頁面聯(lián)系了起來。這樣做有幾個好處。第一，這些文本通常提供了比Web頁面本身更加精準(zhǔn)的對于頁面內(nèi)容的描述性文字。第二，Anchors描述了一些不能被文本搜索引擎索引的文檔，比如說圖片，程序，數(shù)據(jù)庫等等。這些信息將有可能返回沒有被

17、抓取的Web頁面的地址。注意到那些沒有被抓取的頁面可能帶來的問題：因為它們的有效性在返回給用戶之前永遠不可能得到驗證。在這種情況下，搜索引擎很有可能返回一個實際上根本不存在的但卻有超鏈接鏈接到的頁面。然而，通過對結(jié)果的排序，這個問題在實際中很少會發(fā)生。這種通過錨定文本本身對Web頁面進行描述的思想最早在WorldWideWebWorm中得以特別地實現(xiàn)因為它幫助搜索非文本信息并擴展了搜索的覆蓋度，提供了少數(shù)幾種可下載文檔的信息。我們使用這種思想主要是因為AnchorText可以幫助提供更好的搜索質(zhì)量?？紤]到大量必須被處理的數(shù)據(jù)量，有效的利用AnchorText在技術(shù)上是十分困難的。在我們目前抓取

18、的2千4百萬頁面中，我們索引了超過2億5千9百萬的Anchor文本。2.3 其他特征：除了使用PageRank和AnchorText以外，Google還有一些其他的特征。首先，Google紀(jì)錄了頁面中每個元素的位置信息，更增加了對于相似度的搜索。此外，Google可以獲取一些可視化表示的細節(jié)比如說字體大小。大號或者粗體字被賦予更高的權(quán)重。第三，我們將所有的原始Html頁面存儲了下來。3相關(guān)工作互聯(lián)網(wǎng)上的搜索研究歷史短暫而簡明。WWWW是第一代搜索引擎中的一個。緊跟其后的是一些學(xué)院派搜索引擎，很多現(xiàn)在已經(jīng)公司化了。同Web的發(fā)展和搜索引擎的重要性比起來，很少有關(guān)于最近搜索引擎技術(shù)的文檔。然而，還

19、是有相當(dāng)一部分關(guān)于搜索引擎某一特性的工作在進行中。特別值得一提的是目前搜索引擎中對搜索結(jié)果進行預(yù)后處理得到最終結(jié)果，或者得到一個小規(guī)模的個性化搜索引擎。最后，還有相當(dāng)多的關(guān)于信息檢索系統(tǒng)領(lǐng)域的研究，特別在受約束集合的范圍下，在下兩個章節(jié)的內(nèi)容中，我們討論如何擴展這些領(lǐng)域的研究成果使它們能夠在Web環(huán)境下工作的更好。4.5 信息檢索信息檢索系統(tǒng)領(lǐng)域中的工作可以回顧到很多年前而且已經(jīng)是發(fā)展得很好的技術(shù)了，然而，所有基于信息檢索系統(tǒng)的研究都是在基于很小范圍內(nèi)的同類型受約束集合中。比如說科學(xué)文獻，關(guān)于某一個話題的新聞故事等等。確實，信息檢索領(lǐng)域的基準(zhǔn)一一文本檢索會議使用的很小一部分這類型的文檔。對比我

20、們抓取的147GB,2千4百萬的Web頁面，“海量文集”基準(zhǔn)只有大概20GB的信息量。很多在TREC上可以獲得很好結(jié)果的方法并不能在Web上得以適用。比如說，標(biāo)準(zhǔn)向量空間模型對文檔和查詢根據(jù)其中單詞的出現(xiàn)來定義其向量。為的是返回與查詢條件最為相近的文檔。在Web上，這種方法通常返回非常短小的文檔，這些文檔通常是查詢的關(guān)鍵字加上少許單詞。比如說，我們曾看到一個主流的搜索引擎在我們輸入“BillClinton”查詢時返回了一個只包含一句"BillClintonSucks”和一張圖片的頁面。一些關(guān)于網(wǎng)絡(luò)上的爭論認(rèn)為，用戶需要輸入更多的關(guān)鍵詞來確定他們需要的結(jié)果。我們強烈不同意這個問題。如果

21、用戶發(fā)起一個"BillClinton”的請求，他們應(yīng)該是得到合理的結(jié)果只要有足夠多的高質(zhì)量關(guān)于這個話題的信息。通過這個例子，我們相信，為了能夠更好的處理網(wǎng)絡(luò)上的信息，傳統(tǒng)的信息檢索工作需要進行擴展。4.6 傳統(tǒng)受約束集合于Web的區(qū)別Web是一個完全不受約束同類文檔的大型集合。Web文檔在文檔結(jié)構(gòu)本身抑或是外部的元數(shù)據(jù)中就存在有很多變化。比如說，文檔本身語言（不論是在自然語言還是程序語言上），詞匯（Email地址，鏈接，壓縮碼，電話號碼，貨物編號），格式類型（文本，HTML,PDF,圖片，聲音）上都有可能不同，此外，很多文檔可能都是機器生成的（日志文件，或者動態(tài)的根據(jù)數(shù)據(jù)庫生成頁面）

22、。另一方面，我們定義外部元數(shù)據(jù)是那些可以推斷文檔的信息，但是這些信息并不包含在文檔當(dāng)中。一些關(guān)于外部元數(shù)據(jù)的例子：來源的可靠性，更新頻率，質(zhì)量，受歡迎程度或者使用程度，還有引用。不僅僅是這些元數(shù)據(jù)的來源可能不同，被度量信息本身可能差別也在幾個數(shù)量級以上。比如說Yahoo目前每天可以有幾千萬次的頁面瀏覽，但可能Web上其他的某些晦澀難懂的歷史文章每10年才會被訪問到一次。顯然，這兩種情況應(yīng)該被搜索引擎區(qū)別來對待。另外一個Web和傳統(tǒng)文檔的不同來自于，通常對于用戶放置于網(wǎng)絡(luò)上的信息沒有一個約束。4系統(tǒng)剖析首先，我們將提供一個總體的架構(gòu)討論，然后，我們將會深入討論一些重要的數(shù)據(jù)結(jié)構(gòu)。最后，主要的應(yīng)用

23、程序：抓取，索引和搜索將被深入的進行探討。Google的架構(gòu)Google的整體架構(gòu)在這一節(jié)，我們將討論如上圖所示的Google的總體架構(gòu)。更多關(guān)于數(shù)據(jù)結(jié)構(gòu)和應(yīng)用程序的討論將在后續(xù)的章節(jié)給出。大部分Google的代碼為了提高工作效率都是使用C或者C+寫成的，這些代碼可以在Solaris或者Linux上面運行。在Google中，Web抓取(WebCrawling)(下載Web頁面)是通過多個分布式的抓取器完成的。URL服務(wù)器(URLServer)發(fā)送待抓取頁面的URL給抓取器。收集到的Web頁面被送到存儲服務(wù)器(storeserver),存儲服務(wù)器(storeserver)壓縮并把Web頁面存放在

24、知識庫(Repository)中。每一個頁面都有一個與之聯(lián)系的ID號叫做DocID。這個ID是在一個頁面中新的URL被解析出來的時候分配的。索引(indexing)的功能由索引器(indexer)和排序器(sorter)完成。索引器讀取知識庫中的頁面，解壓文檔然后對文檔進行解析。每一個文檔都被轉(zhuǎn)換為一組字詞的存在集合我們把這個集合叫做Hits。Hits記錄字詞，文檔中的位置，字體的大小和大小寫。索引器將這些hits分配到一組稱為“桶”的結(jié)構(gòu)中，并由此創(chuàng)建一個部分排序的前向索引(ForwardIndex)。索引器另外一個重要功能是解析每個頁面中的鏈接并把相關(guān)重要的信息存放在錨文件(AnchorF

25、ile)中。這個文件包含足夠的信息來確定每一個鏈接來源與指向以及連接的文本。URL解析器(URLResolver)讀取這些錨文件然后將這些相對URL路徑轉(zhuǎn)換成為絕對路徑并依次分配DocID。URL解析器將AnchorText以及由AnchorText指向的DocID放入前向索引中。同時，URL解析器也產(chǎn)生一個鏈接的數(shù)據(jù)庫，這個數(shù)據(jù)庫中包含有一組組的DocID。連接數(shù)據(jù)庫用來計算所有文檔的PageRank值。排序器(Sorter)使用按照DocID排序的桶來根據(jù)WordID的順序產(chǎn)生倒排索引(InvertedIndex)。一些臨時的存儲空間需要用來進行此項操作。排序器同時也在倒排索引中產(chǎn)生一組W

26、ordID和偏移量。一個叫做DumpLexion的程序?qū)⑦@些鏈表與由索引器產(chǎn)生的詞典關(guān)聯(lián)起來然后產(chǎn)生一個新的詞典供搜索器使用。搜索器在Web服務(wù)器上運行并且利用由DumpLexicon產(chǎn)生的詞典，倒排索引和PageRank來回答查詢。主要數(shù)據(jù)結(jié)構(gòu)優(yōu)化了的Google數(shù)據(jù)結(jié)構(gòu)可以以最小的消耗來處理海量文檔的抓取，索引和搜索。雖然CPU和大數(shù)據(jù)塊的輸入輸出這些年來已經(jīng)有很大改善，磁盤的定位仍然需要大概10MS的時間才能完成。Google被設(shè)計為無論何時總是避免不必要的磁盤定位，這種思想對我們數(shù)據(jù)結(jié)構(gòu)的設(shè)計起了極大的作用。大文件(BigFiles)大文件是由64位整數(shù)設(shè)定地址的虛擬文件，虛擬文件可以

27、生成多文件系統(tǒng)。這種在多文件系統(tǒng)中的分配工作時自動進行的。大文件包(BigFilesPackage)同時也在操作系統(tǒng)沒有足夠的文件描述符時，負(fù)責(zé)文件描述符的分配和回收工作。BigFiles同時也支持原始壓縮選項。知識庫(Repository)Repository:53.5GB=147.8GBuncompressedsynclengtnsynclenqthcomDressqdpqcketcompiessedpacketPacket(storedcompressedinrepository)Idocidecocfelurllenlpaqelerur|paqe知識庫包括了所有頁面的HTML代碼。每一

28、個頁面都使用zlib進行壓縮。選擇的壓縮算法是進行了壓縮比和速度折中的。我們選擇的Zlib在速度上要遠遠優(yōu)于Bzip提供的壓縮算法。對比與Zlib3比1的壓縮比而言，Bzip的壓縮比大約是4比1左右。在知識庫中，文檔順次排列并且以DocID,長度和URL作為前綴。具體結(jié)構(gòu)可以查看圖2。知識庫不需要其他更多的數(shù)據(jù)結(jié)構(gòu)用來訪問。這種結(jié)構(gòu)有利于數(shù)據(jù)的一致性，同時也使得系統(tǒng)的進一步發(fā)展更加容易。我們可以從知識庫和抓取器的錯誤日志中方便的重建其他的所有數(shù)據(jù)結(jié)構(gòu)。文檔索引文檔索引用來保存每一個文檔的信息。這是一個固定寬度按照DocID排序的索引。每一條記錄中存儲的信息包括當(dāng)前文檔的狀態(tài)，指向知識庫的指針，

29、文檔的校驗碼和一些統(tǒng)計數(shù)據(jù)。如果文檔被抓取，記錄中還會包括一個指向叫做Docinfo變長文件的指針。這個變長文件包括文檔的URL和標(biāo)題。如果該頁面還沒有被抓取，則該指針僅僅指向包含URL地址的URLList。這種設(shè)計是希望得到緊湊數(shù)據(jù)結(jié)構(gòu)使得查詢請求可以僅僅在一次磁盤定位時便可以得到相關(guān)記錄。此外，還有一個文件用來處理從URL到DocID的轉(zhuǎn)換。這是一個URL校驗碼的列表包括了每一個URL對應(yīng)的DocID,并且按照校驗碼來進行排序。為了找到特定URL的DocID。我們通過計算URL的校驗碼來對文件進行二叉搜索來找到DocID。同時，我們還能夠通過合并實現(xiàn)批量化的URL,DocID轉(zhuǎn)換。這被UR

30、L解析器用來實現(xiàn)URL到DocID的轉(zhuǎn)換。批量化更新模式非常重要，因為如果不這樣，我們就需要為每一個連接的轉(zhuǎn)換對磁盤進行一次定位。假設(shè)要對3億2千2百萬個連接的數(shù)據(jù)集進行定位，估計要花上1個月的時間。詞典（Lexicon）詞典通常有多種形式。一個與之前系統(tǒng)中詞典最大的不同是我們設(shè)計的詞典可以在地消耗的前提下放入到內(nèi)存中。在目前的實現(xiàn)中，我們可以在一臺256主存的機器上把詞典文件整個的放入到內(nèi)存中去。目前的詞典包含大約1千4萬個關(guān)鍵詞。它的實現(xiàn)分為兩部分。一組關(guān)鍵詞（順序連接但是以NULL作為分割）和一個哈希表。為了應(yīng)付不同的功能，這組詞還包含有一些其他的信息，這些信息超過了本文的討論范圍。Hi

31、t表一個Hit表對應(yīng)到一個特定文檔中某個存在的關(guān)鍵詞的信息。這些信息包括關(guān)鍵詞位置，大小寫信息，字體。Hits表占用了正向索引和倒排索引絕大部分的存儲空間。正因為此，所以如何將這些信息有效的表達出來就顯得尤為重要了。我們考慮了幾種可供選擇對位置，字體和大小寫進行編碼的方案：簡單編碼（三個連續(xù)整數(shù)），緊湊編碼（手工優(yōu)化位處理）和哈夫曼編碼。最后我們選擇一種優(yōu)化的緊湊編碼，因為這種方式可以有效地節(jié)約空間同時也省去了哈夫曼編碼對位的繁瑣處理。Hits的細節(jié)在圖3中標(biāo)明。我們的緊湊編碼使用兩個字節(jié)來處理所有的hit。有兩種形式的hit,一種我們叫做奇異hits,一種普通hits。奇異hits包括出現(xiàn)在

32、URL,標(biāo)題，anchorText或者元標(biāo)簽中的hits。普通Hits包括其余的元素。一個普通的hit包括一位指示大小寫，指示字體大小，12位指示關(guān)鍵詞在文檔中的位置（所有大于4095的位置都被當(dāng)作4096處理），其余的三位用來指定字體的大小。奇異hit包括一位指示大小寫，字體大小為被設(shè)置為7的可以用于判斷是否為奇異hit。4位用來對奇異hit的類別進行編碼，其余八位用來辨明位置。對于anchorhits來說，8位的位置分為4位的位置指示和4位的DocID哈希。只要對于一個特定的關(guān)鍵詞不存在過多的anchor,一些有限的短語搜索是可能的。我們期望對我們的方法進行更新使之能夠?qū)Ω嗟奈恢煤虳oc

33、ID進行編碼。我們在hit中使用字體大小因為我們不想對僅僅只是字體大小不同而內(nèi)容一致的文檔排序。Hit標(biāo)的長度存儲在hits的最前面。為了節(jié)省空間，hit表的在正向索引中與wordID合并在了一起，在倒排索引中則和DocID合并。在兩種索引中的長度分別為8位和5位。如果長度超過了本身可以表示的范圍，一個叫做Escape的碼值將被設(shè)定，在接下來的兩個字節(jié)中將會包含Hit的實際長度。正向索引（ForwardIndex）正向索引實際已經(jīng)部分的被排序了。正向索引被存儲在一系列的桶中（在我們的系統(tǒng)中，桶的個數(shù)為64）.。每一個桶保存一個WordID的范圍值。如果一個文檔包含包括的某個關(guān)鍵詞的wordID

34、正好符合某個特定桶wordID和hits表。的范圍，這個文檔的DocID將會被記錄在桶中。后面是該文檔中對應(yīng)到該桶的關(guān)鍵詞的這種模式因為重復(fù)的DocID要求比實際值更多的存儲空間。但是由于桶的數(shù)量比較合理這種存儲上的差別不會很大，同時也節(jié)省了相當(dāng)多的時間開銷和在后期索引階段排序時編碼的復(fù)雜度。此外，我們對每個WordID求出對每個桶最小ID的相對值而不是使用WordID的絕對值。這樣一來，我們可以只使用24位來記錄在桶中的wordID,剩余的8位留名了hits。Hit:2bytesplain:fancy:anchor:cap;1imp:3position;12cap:1imp=7type:4p

35、osition:8cap:1imp=7type:4hash:4pos:4ForwardBarrels:total43GBIdocidwordid:24nhits:8hithithithitwordid:24nhits:8hithithithitnullwordiddocidwordid:24nhits:8wordid:24nhits:8lithithithitlithithithitwordid:24nhits:8hithithithitnullwordidLexicon:293MBInvertedBarrels:41GBwordidndocs"woF9iUTiroes-wordiU

36、ndocsdocid:27do甄27docid:27docid727n曄;5nhits:5n.ts:5nHts:5nithithithitnithithithithithithitnithit倒排索引(InvertedIndex)WordID,倒排索引除了是由排序器來進行處理以外，桶的結(jié)構(gòu)和正向索引是相同的。對于每一個有效的詞典包含一個指向包含WordID的桶的指針。這個指針指向一個包括對應(yīng)hit表白DDocID的鏈表。這個文檔鏈表表示所有包含該關(guān)鍵詞的文檔集合。一個重要的問題是，在文檔鏈表中，DocID究竟應(yīng)以一種什么樣的順序進行存儲？一個簡單的解決方案是按照DocID的順序進行排序。這在多

37、關(guān)鍵詞進行求交集的時候有利于對文檔鏈表快速地合并。另外一個選擇是根據(jù)該關(guān)鍵詞在每個文檔中的排名來進行排序。這種方法對于處理單關(guān)鍵詞查詢時顯得非常有用但是在多關(guān)鍵詞的文檔鏈表的合并過程中就顯得異常困難。同樣，這種排序方式使系統(tǒng)的進一步發(fā)展變得更加困難。因為一旦我們對排序的算法進行修改，我們就必須得重新生成整個倒排索引。我們在這兩種方法中作了一個折中：對每一個關(guān)鍵詞的文檔鏈表保留兩個倒排桶：一個集合中的DocID是那些保存有奇異Hits的集合，另外一個是全部的集合。通過這種方式，我們首先在第一個集合中搜索結(jié)果，如果第一個集合中的結(jié)果不夠再對第二個集合進行搜索。抓取網(wǎng)絡(luò)運行一個網(wǎng)絡(luò)抓取器是一項頗具挑

38、戰(zhàn)性的任務(wù)。網(wǎng)絡(luò)抓取涉及的問題包括網(wǎng)絡(luò)作弊和可靠性問題，更加重要的是，可能會涉及到一些社會問題。抓取一個十分脆弱的部分因為這一部分要和成千上萬的Web服務(wù)器和各種不同類型的服務(wù)器打交道，這些服務(wù)器都遠遠超過了系統(tǒng)的控制范圍。為了能夠抓取上千萬數(shù)量級的Web頁面，Google使用了一個快速的分布式抓取系統(tǒng)。一個單獨的URL服務(wù)器為多個抓取器（在我們的系統(tǒng)中這個值是3）提供待抓取的URL列表。URL服務(wù)器和抓取器都是使用Python語言實現(xiàn)的。為了保證Web頁面的抓取保持在一個較高的速度上，每一個抓取器每個時刻都保持有近300個連接。在速度最快時，使用4個抓取器的系統(tǒng)可以每秒抓取超過100個頁面差

39、不多600K的數(shù)據(jù)量。一個主要的性能瓶頸在于DNS查找。每一個抓取器都各自維護一個DNS緩存，所以，抓取器不必在每次抓取頁面時都進行DNS查找了。這些連接可能存在眾多不同的狀態(tài)：查找DNS,連接服務(wù)器，發(fā)送請求，接受響應(yīng)。這些狀態(tài)使得抓取器成為系統(tǒng)中一個異常復(fù)雜的模塊。它使用異步的IO來進行事件處理。然后眾多的隊列用來進行頁面不同狀態(tài)的轉(zhuǎn)移。事實證明，抓取器連接成千上萬個服務(wù)器產(chǎn)生的數(shù)以萬計的日志給我?guī)砹撕Ａ康腅mail和電話訪問。因為在這些為數(shù)眾多的上網(wǎng)者中總是有很大一部分人并不知道Crawler為何物。很有可能這是他們第一次見識到Crawler。幾乎每天我們都可以收到這樣的電子郵件：“喔

40、，你在我的站點上看了不少頁面哦，感覺怎樣？”。同樣也有些人并不了解RobotExclusionProtocol,并且認(rèn)為她們的頁面應(yīng)該免于被索引，在他們的頁面上常?？梢钥吹竭@樣的句子“這個頁面是受版權(quán)保護的，請勿索引”。這些文字對于抓取器來說無疑是無從知曉的。同樣，因為對大量數(shù)據(jù)的收集，常常會有一些意想不到的結(jié)果。比如說，我們的系統(tǒng)曾經(jīng)試圖抓取一個在線游戲的頁面。結(jié)果導(dǎo)致大量游戲中的垃圾信息被收集起來。由于Web的各種頁面或者服務(wù)器上的變化。不可避免會有成千上萬個問題隱藏在某個頁面中最后導(dǎo)致抓取器的崩潰。更糟糕的是，可能導(dǎo)致抓取器的不可預(yù)知和錯誤的活動。像這些訪問大部分互聯(lián)網(wǎng)的系統(tǒng)一定要設(shè)計得

41、更加強壯同時也要細心的進行測試。索引網(wǎng)絡(luò)解析（parsing）-任意一個用來解析互聯(lián)網(wǎng)絡(luò)的解析器必須能夠應(yīng)付大量可能存在的錯誤。這些錯誤可能是在Html標(biāo)簽中使用打字稿，可能是在標(biāo)簽的中間包含有上千字節(jié)的空字符，可能涉及到非AscII碼等等，還有更多的錯誤在挑戰(zhàn)人們的想象力去解決。為了提高速度，我們使用Flex來產(chǎn)生詞法分析器而摒棄了YACC來產(chǎn)生CFG解析器。開發(fā)這樣一個能夠高速運行并且高度強壯的解析器需要投入巨大的精力。索引文檔入桶一文檔解析完成以后，被編碼進入不同的桶中。每一個詞都通過駐留內(nèi)存的詞典的哈希表被轉(zhuǎn)換為一個WordID。新增的詞典哈希項被記錄到相關(guān)文件上。Word轉(zhuǎn)換為Wor

42、dID以后，他們在每個文檔中的值被轉(zhuǎn)換成為響應(yīng)的Hits表，被寫入到正向索引中。同步索引狀態(tài)的主要難題在于詞典文件需要共享。我們通過采用為所有的不在詞典中的關(guān)鍵詞寫入日志到日志文件中來代替詞典的共享。這樣一來，多個索引器可以并行工作，小的日志文件可以在最后階段被索引器合并成一個大的索引文件。排序-為了產(chǎn)生倒排索引，排序器將所有的正向桶按照WordID進行排序來為標(biāo)題和AnchorHits和全部文檔創(chuàng)建倒排桶。排序器每次對一個桶進行操作，因此對臨時存儲空間的需求就很少。同時我們使用多個排序器在排序階段并行的工作。這些排序器可以在同一時間對不同的桶進行操作。由于桶的大小不能夠全部載入內(nèi)存，排序器根

43、據(jù)WordID和DocID將其拆分成多個可以載入到內(nèi)存中的籃（Basket）。然后排序器裝載這些籃排序，比逆光把結(jié)果寫入到短的和完整的倒排桶中。搜索(Searching)搜索的目標(biāo)是有效的提供高質(zhì)量的搜索結(jié)果。很多目前大型的商業(yè)搜索引擎看上去在效率上有了不少改進。因此，我們將注意力主要集中在對研究對搜索結(jié)果的改善上。雖然我們相信通過進一步努力，我們的解決方案可以在商業(yè)容量上得以擴展。Google的查詢評價顯示在圖4中。.解析查詢.將關(guān)鍵詞轉(zhuǎn)換成為WordID.找到每個關(guān)鍵詞在短倒排桶的起始位置。.搜索所有的文檔鏈表直到找到所有的符合查詢條件的文檔.計算文檔關(guān)于該查詢的排名.如果我們是在短倒排桶

44、中，定位每個關(guān)鍵詞在完全文檔鏈表中的起始位置返回到步驟4.如果還沒有到達文檔的結(jié)尾。則繼續(xù)步驟4.對于符合要求的文檔進行排序，并返回TopK為了有效地縮短響應(yīng)時間，一旦符合匹配的文檔數(shù)量達到一個既定的數(shù)量(目前是40000)。搜索器自動的跳到圖4的第八步。也就是說可能返回的是一個最優(yōu)化結(jié)果的子集。我們現(xiàn)在正在探索其他更好的方案來解決目前的問題。過去，我們對hits用PageRank進行排序。這種方式看上去改善了不少。排序系統(tǒng)Google維持比傳統(tǒng)搜索引擎更多的Web文檔的信息。每一個Hit表都包括位置，字體和大小寫信息。此外，我們將AnchorText和文檔的PageRank作為因此放入hit

45、s中。將所有這些信息都考慮到排序中是相當(dāng)困難的。我們設(shè)計的排序函數(shù)不會讓某一個特定因子起到太大的影響作用。首先，考慮最簡單的情形-單關(guān)鍵詞的查詢。為了對符合單關(guān)鍵詞的文檔進行排序。Google查詢文檔的該關(guān)鍵詞的hit值。Google把hit分成幾種類型：標(biāo)題，Anchor,URL,純文本大字體等等。每種類型有其獨有的權(quán)重。權(quán)重組成了一個由類型索引的向量。Google計算在hit表中每種類型的德數(shù)量。然后每一個計算結(jié)果都轉(zhuǎn)換成一個計算權(quán)重(Count-weight)o計算權(quán)重一開始隨著計數(shù)的增加而線性的增加但是很快的就會逐漸停止，所以一旦超過了一定數(shù)目就不再會有用了。我們對計數(shù)權(quán)重的向量與類型

46、權(quán)重向量進行點乘為文檔得到一個IR分?jǐn)?shù)。最后，IR的分?jǐn)?shù)和PageRank分?jǐn)?shù)混合起來給文檔一個最后的排名情況。對于多關(guān)鍵詞查詢而言，情況就要復(fù)雜許多了。多個hit表必須一次性的掃描完畢，和那些再文檔中位置比較遠的hits比起來，我們應(yīng)該對對那些在文檔中位置靠近的hits給出更高的分?jǐn)?shù)。對于每一個符合插敘的hits集合來說，我們要對其接近度進行計算。接近度的計算是根據(jù)hits在文檔中的距離進行，從完全匹配到不相關(guān)，我們將其分成10個不同的值。計數(shù)并不僅僅根據(jù)類別，而且也根據(jù)相近度來計算。每一個類別相近度對有一個類別相近度權(quán)值。我們對計數(shù)和權(quán)值進行點乘來獲得IR分?jǐn)?shù)。所有這些數(shù)字和矩陣可以在調(diào)試

47、模式下伴隨搜索結(jié)果顯示出來，這些數(shù)字和矩陣地顯示對我們的排序系統(tǒng)起到了極大的幫助作用。反饋(Feedback)排序函數(shù)有許多參數(shù)，比如說類型權(quán)值和類型相近度權(quán)值，精確的計算這些權(quán)值的確切值在某種程度上幾乎是不可能的。我們通過在搜索引擎中引入用戶反饋機制來達到這個目標(biāo)。一個值得信賴的用戶可能會對所有返回的結(jié)果進行評價，這種反饋被儲存起來，在我們對排序函數(shù)進行修改的時候，我們可以通過反饋得到一些有關(guān)因子在先前查詢中起到的影響。雖然說這些方式遠非理想，但確實給了我們?nèi)绾胃倪M排序算法可以影響搜索結(jié)果5.結(jié)果和性能Query:billclintonhttp壯wwwwh口1,15B&051100.

48、00%(nodate)(OK)/Office口fthuPrcidunt(Dec231996)(2K)htrp：//WH/EOP/OP/html/OP_Home.htmlWglc口meToThWhiteH口utc(Nov091997)(5K)http:/www:whitehouseTgov/WH/Wekome.htmlG一-dElect。門icMRItoth。P1白sident(Jul141997)(5K)htrp:/www.whitehouseTgov/WH/Mail/html/MaiLPresident.hi

49、mlmNiltcrprTsidEritwhitE99.98%maiko:PosidentwhituhoL*eqov99.2Thu"Unofficial"BillClinton94.06%M(Nov111997)(14K)EillClint0門Meet/Th20hrk)k&(Jun291997)(63K)l-ittp:/zpubJcom/unZun-bc9.htmlP心iden【BillCimmri-TheD日kSide97.27%(Nov101997)(15K)http:/www.佗白kh</clinton.htm$3BillC

50、Jjnnjn9473%(nodate)(4K)http;/Figure4.SampleResultsfromGoogle衡量搜索引擎性能很重要的一個因素是搜索結(jié)果的質(zhì)量。雖然完整的用戶評價已經(jīng)超出了本文的討論范圍，我們自身關(guān)于Google經(jīng)驗表明，Google通?？梢援a(chǎn)生比當(dāng)前大多數(shù)主流商業(yè)搜索引擎更好的搜索結(jié)果。為了闡釋PageRank,AnchorText和相近度的作用，圖4給出了Google的對BillClinton這個查詢條件的搜索結(jié)果。這些結(jié)果顯示了Google的一些特性。這些搜索結(jié)果是由服務(wù)器成群的。這為篩選出合適的結(jié)果集起到了很大幫助。很多結(jié)果是由W這個

51、域名返回的。這通常是我們所期望的搜索站點。當(dāng)前，很多主流商業(yè)搜索引擎通常不會返回站點的任何結(jié)果。注意到第一個結(jié)果中沒有標(biāo)題。這是因為這個頁面沒有被抓取。Google通過AnchorText判斷出這是一個對應(yīng)于查詢條件好的回答。同樣的，第五個結(jié)果是一個Email地址，同樣沒有被抓取，是憑借AnchorText判斷得出的結(jié)果。所有的這些結(jié)果都是高質(zhì)量的頁面，而且經(jīng)過最終檢測，并不存在死鏈接。這主要因為結(jié)果是根據(jù)PageRank排序的。PageRank在這些結(jié)果中的權(quán)重是條形碼中紅色部分的百分比。最后，結(jié)果中并沒有出現(xiàn)只有Bill沒有Clinton或者只有Clinton沒

52、有Bill的結(jié)果。這是因為我們?yōu)殛P(guān)鍵詞存在的相近度給了非常高的權(quán)值。當(dāng)然，一個對搜索引擎的真正測試需要更廣泛用戶的使用和對系統(tǒng)進行測試分析，在這里我們邀請讀者訪問Google的網(wǎng)站：.存儲要求除了搜索質(zhì)量外，Google要求系統(tǒng)能夠?qū)eb的增長在性能消耗上做出適應(yīng)。其中的一方面就是如何有效地使用存儲。表1是一些統(tǒng)計數(shù)據(jù)的細目分類和Google對存儲的要求。由于對文檔進行了壓縮，知識庫的大小已經(jīng)縮減到了53GB。僅僅是全部存儲數(shù)據(jù)的1/3。對目前硬盤的價格而言，對于存儲有用的數(shù)據(jù)而言這已經(jīng)是相當(dāng)便宜的資源了。更加重要的是，搜索引擎所需要總體的數(shù)據(jù)的存儲空間量大概是55GB。此外，許多查詢可以僅僅在查找短倒排索引就找到滿足要求的結(jié)果。通過在文檔索引中使用好的編碼和壓縮技術(shù)，高質(zhì)量的Web搜索引擎可以適應(yīng)一個帶有7GB驅(qū)動器的新型PC中。對于一個搜索引擎來說，有效的抓取和索引是非常重要的。因為這樣一來我們可以保證最新的信息能夠及時地收集到而且系統(tǒng)的主要改動可以相應(yīng)的進行迅速測試。對于Google而言，主要的操作是抓取，索引和排序。很難準(zhǔn)確的測量出進行完整一次抓取需要花費多長時間，因為諸如磁盤裝滿，命名服務(wù)器崩潰，或者其它一些問題都可能使得系統(tǒng)停滯下來?？傮w而言，下載2千6百萬頁面大概需要花