文章來自《程序員》
英文原文可以在這里找到http://dev.csdn.net/develop/article/12/12657.shtm

關(guān)鍵字：WWW   搜索引擎   網(wǎng)絡(luò)爬蟲    PageRank     Google

       作為一種功能強(qiáng)大的搜索引擎，Googic的背后似乎隱藏著巨大的奧秘，本文是Googic的兩位創(chuàng)始人在1998年國際互聯(lián)網(wǎng)大會(huì)上發(fā)表的論文，通過對(duì)Google進(jìn)行完整地剖析，幫助讀者理解Google的實(shí)現(xiàn)過程.
1。為什么要用Google
    Web結(jié)構(gòu)的特殊性為信息收集工作帶來了新的挑戰(zhàn)。Web上的信息數(shù)量迅速增長的同時(shí)，對(duì)于Web毫無使用經(jīng)驗(yàn)的新用戶也在與日俱增。使用高質(zhì)量的搜索引擎，無疑可以縮短Web同新用戶之間的距離。大家關(guān)心的問題是，搜索質(zhì)量和效率。

    Yahoo曾一度是用戶的最佳選擇。Yahoo的人工維護(hù)方式可以有效涵蓋最流行的主題。然而，維護(hù)人員的主觀性、高昂的維護(hù)代價(jià)、較慢的更新速度都是Yahoo的缺陷。更重要的事，這種方式并不能覆蓋所有用戶所關(guān)心的話題。所有這些制約了Yahoo的進(jìn)一步發(fā)展。基于關(guān)鍵字的搜索引擎隨之出現(xiàn)，但新的問題接踵而來：搜索引擎制造出的大量“垃圾”結(jié)果遮住了用戶的視線，也考驗(yàn)了更多人的耐心。一些廣告商為了吸引用戶的目光，采用一些手段欺騙搜索引擎，這使事情變得更糟。

    Google為上述問題提供了新的解決方案。首先，Google是基于關(guān)鍵字的，這樣突破了查詢主題的限制；其次，Google利用網(wǎng)頁超級(jí)連接的深度和獨(dú)創(chuàng)的PageRank算法，為網(wǎng)頁賦予了“級(jí)別（Rank）”含義：用戶的檢索結(jié)果，是按照網(wǎng)頁的級(jí)別（Rank）進(jìn)行排序的．級(jí)別高的網(wǎng)頁鏈接排在前面．

　　Google這個(gè)名字的來歷也很有意思：Google的創(chuàng)建者參考了單詞googol（１０１００）的拼寫，也許這和作者要建立大規(guī)模的搜索引擎的目標(biāo)不謀而合．
2．設(shè)計(jì)目標(biāo)
　　正如你想到的，GOOGLE的主要目標(biāo)是提高搜索引擎的搜索質(zhì)量和易用性．１９９７年１１月的一項(xiàng)調(diào)查中，排名前四位的商業(yè)化搜索引擎，在執(zhí)行以它自身的名字作為關(guān)鍵字的查詢時(shí)，僅有一個(gè)搜索引擎在其搜索結(jié)果的前１０條查詢結(jié)果中找到自己．問題已經(jīng)變得很明顯：用戶關(guān)心的不是搜索引擎所能提供的查詢結(jié)果，而是在搜索引擎中所能提供的前數(shù)十條查詢結(jié)果中，能否找到自己的滿意答案．正因?yàn)槿绱耍?dāng)Web文檔成倍增長時(shí)，如何提供一個(gè)既易于操作，又能提供準(zhǔn)確查詢的新的搜索引擎技術(shù)．這成為了關(guān)注的焦點(diǎn)．

　　近幾年的一些相關(guān)研究為Google打開了思路．這些研究的主要方向是：如何從頁面的超鏈接文本中獲取對(duì)開發(fā)人員有用的信息．正是通過對(duì)HTML文檔中超文本鏈接的深度分析，Google為自己的精確度算法提供了理論依據(jù)．

　　Google希望通過自己的努力，把原本只屬于商業(yè)領(lǐng)域的搜索引擎技術(shù)帶到理論研究的范疇，并能讓更多的人參與和完善．Google把自己的系統(tǒng)比喻為一個(gè)大的實(shí)驗(yàn)室環(huán)境，并歡迎其他領(lǐng)域的研究人員參與其中．正是在千千萬萬如Google這樣的組織的帶動(dòng)下，Web獲取了它前所未有的發(fā)展動(dòng)力．

3.技術(shù)分析
　　Google之所以能獲取高效率的查詢結(jié)果，得益于其兩相重要的技術(shù)特性：第一，Google分析整個(gè)Web的鏈接結(jié)構(gòu)，然后計(jì)算出每一個(gè)網(wǎng)頁的級(jí)別，并進(jìn)行綜合評(píng)分，這就是Google所采用的PageRank技術(shù)；第二，Google充分利用鏈接提供的信息以進(jìn)一步改善查詢質(zhì)量．
　3.1 PageRank：頁面的排序技術(shù)
　　Google的核心技術(shù)稱為PageRank，這是Google的創(chuàng)始人Larry Page和Sergey Brin在斯坦福大學(xué)開發(fā)出的一套用于網(wǎng)頁評(píng)級(jí)的系統(tǒng)．作為組織管理工具，PageRank利用了互聯(lián)網(wǎng)獨(dú)特的明主特性及其巨大的鏈接結(jié)構(gòu)．在浩瀚的鏈接資源中，Google提取出上億個(gè)超級(jí)鏈接進(jìn)行分析，制作出一個(gè)巨大的網(wǎng)絡(luò)地圖（Map）．依據(jù)此地圖，PageRank技術(shù)能夠快速的計(jì)算出網(wǎng)頁的級(jí)別（Rank）．這個(gè)級(jí)別的依據(jù)是：當(dāng)從網(wǎng)頁A連接到網(wǎng)頁B時(shí)，Google就認(rèn)為＂網(wǎng)頁A投了網(wǎng)頁B一票＂．Google根據(jù)網(wǎng)頁的得票數(shù)評(píng)定其重要性．然而，除了考慮網(wǎng)頁得票數(shù)（即鏈接）的純數(shù)量之外，Google還要分析投票的網(wǎng)頁。“重要”的網(wǎng)頁所投出的票就會(huì)有更高的權(quán)重，并且有助于提高其他網(wǎng)頁的“重要性”。
    Google以其復(fù)雜而全面自動(dòng)的搜索方法排除了人為因素對(duì)搜索結(jié)果的影響。所以說，PageRank相對(duì)是公平的。在這個(gè)意義上，對(duì)于基于關(guān)鍵字搜索的引擎技術(shù)來說，PageRank無疑是一項(xiàng)優(yōu)秀的技術(shù)，Google可以方便、誠實(shí)、客觀地幫您在網(wǎng)頁上找到任何有價(jià)值的資料。

     3.1.1 PageRank算法描述
     近些年來，大量的學(xué)術(shù)研究成果被應(yīng)用到Web中，主要被用來統(tǒng)計(jì)網(wǎng)頁的引用或返回鏈接。這些數(shù)據(jù)為網(wǎng)頁的重要性和價(jià)值分析提供了粗略的依據(jù)。基于此, PageRank還進(jìn)一步統(tǒng)計(jì)鏈接在所有網(wǎng)頁中出現(xiàn)的次數(shù)。PageRank定義如下所述：

     假定頁面A有很多指向他的鏈接，分別定義為頁面T1...Tn。我們?cè)俣x阻尼系數(shù)d（0〈=d〈=1）。通常指定d=0.85（譯者注：下一節(jié)給出實(shí)例分析）。函數(shù)C（A）表示頁面A中指向其他頁面的鏈接的個(gè)數(shù)。那么，頁面A的PageRank（PR（A））可以通過下面的公式計(jì)算出：

     PR（A）=（1-d）+d（PR（T1）/C（T1）+...PR（Tn）/c（Tn））

     注意到PageRank的值是通過整個(gè)Web計(jì)算出來的，所以，所有頁面的PageRank值的和必然為1。

     通過簡單的遞歸計(jì)算，并參照Web中規(guī)范型鏈接矩陣的主特征向量，我們就可以計(jì)算出一個(gè)頁面的PageRank（PR（A））。假設(shè)計(jì)算大約26，000，000個(gè)頁面的PageRank，使用一臺(tái)中等規(guī)模的工作站，大約需要數(shù)個(gè)小時(shí)的時(shí)間。具體實(shí)現(xiàn)的細(xì)節(jié)已經(jīng)超出文本的討論范圍，讀者可以參考相關(guān)文檔。

    3.1.2 PageRank模型
    為了更好地理解 PageRank，我們建立以下一個(gè)假想的模型。我們假定有一個(gè)Web用戶正在隨機(jī)瀏覽某個(gè)網(wǎng)頁，隨著興趣的變化，他也可能隨機(jī)點(diǎn)擊頁面中的另一個(gè)鏈接，跳轉(zhuǎn)到其他頁面（暫且假定該用戶沒有使用返回按鈕）。在這個(gè)模型中，吸引用戶點(diǎn)擊指向某個(gè)頁面的鏈接的概率就是頁面的PageRank。而由于某些因素導(dǎo)致用戶選擇了其他鏈接的概率就是該頁面的阻尼系數(shù)d。有一些極端的情況，如有些頁面可能很少被人訪問，這些頁面就會(huì)積累起很高的阻尼系數(shù)。所以說，PageRank的技術(shù)可以公平有效到避免有些系統(tǒng)為了獲取較高級(jí)別而采取一些欺騙搜索引擎的行為。

    一般來說。網(wǎng)頁的鏈接指向越多，PageRank的值就會(huì)越高。同樣，被一些“重量級(jí)”的網(wǎng)站（例如yahoo)引用的次數(shù)越多，PageRank的值同樣也會(huì)很高。相反，那些設(shè)計(jì)不佳，或者被鏈接破壞指向的網(wǎng)頁，將逐漸被用戶所遺忘。所有的這些因素都在PageRank技術(shù)的綜合考慮之中。 

  3.2錨文本（anchor text）
    在Google中，鏈接文本（text of link ）被使用一種特殊的方式進(jìn)行處理。大多數(shù)的搜索引擎都是把鏈接文本和它所在的頁面相關(guān)聯(lián)，而Google則把鏈接文本和它指向的文檔聯(lián)系到一起（想想的確應(yīng)該如此）。這樣做的優(yōu)點(diǎn)很多：首先，錨（anchor ）一般都會(huì)提供它所指向的文檔的準(zhǔn)確的描述，而這樣信息，頁面本身往往不能提供；第二，對(duì)于那些不能被基于文本的搜索引擎建立索引的文檔，例如圖象，程序以及數(shù)據(jù)庫等，指向它們的鏈接卻可能存在，這樣就使得那些不能被引擎取回分析的文檔也能作為查詢結(jié)果返回。但是，這樣做也可能會(huì)引起一些問題，因?yàn)檫@些文檔在返回給用戶之前并未經(jīng)過搜索引擎的有效性檢查。在這種情況下，搜索引擎就可以簡單地返回查詢結(jié)果，甚至不用考慮頁面是否存在，而只管是否有指向它們的超級(jí)鏈接存在。也許你會(huì)問，這合適嗎？不用擔(dān)心，由于查詢結(jié)果是經(jīng)過級(jí)別排序輸出的，這種特殊的情況也許根本看不到。

    其實(shí)，這種使用錨文本技術(shù)的思想更早可以追溯到World Wide Web Worm搜索引擎。它使得WWWW可以檢索到非文本信息，甚至擴(kuò)展到一些可以下載的文檔，Google繼承了這種思路，因?yàn)樗梢詭椭峁└玫乃阉鹘Y(jié)果。然而，使用這種技術(shù)需要克服很多的技術(shù)難題，首當(dāng)其沖的就是如何處理如此龐大的數(shù)據(jù)量。我們來看看一組數(shù)據(jù)，在Google爬蟲取回的24，000，000個(gè)網(wǎng)頁數(shù)據(jù)中，需要處理的鏈接數(shù)高達(dá)259，000，000之多。

  3.3其它功能
    除了PageRank和錨文本技術(shù)之外，Google還有一些其它的技術(shù)。首先，對(duì)于所有命中（hits),Google都記錄了單詞在文檔中的位置信息，這些信息在最終的查詢中可以被用來進(jìn)行單詞的相似度分析。第二，Google還記錄了頁面中的字體大小、大小寫等視覺信息。有的時(shí)候，大號(hào)字體和粗體的設(shè)置可以用來表示一些重要的信息。第三，在repository數(shù)據(jù)庫中保存所有頁面的HTML代碼。
    (譯注：命中(hit)是Google定義的一個(gè)數(shù)據(jù)結(jié)構(gòu)，有關(guān)命中和相似度的描述，詳見下文。)

4.系統(tǒng)剖析
    從上文中，我們已經(jīng)了解Google的一些工作原理。在這一章節(jié)中，我們將一起深入探討Google的體系框架，然后具體介紹Google用到的一些數(shù)據(jù)結(jié)構(gòu)。最后，我們?cè)僖黄鸱治鯣oogle用到的三個(gè)關(guān)鍵技術(shù)：網(wǎng)頁抓取(crawling)、索引(indexing)以及基于關(guān)鍵字的搜索(searching)。

  4.1 Google體系框架
    本節(jié)中，我們共同探討Google體系框架的運(yùn)行流程，如圖1所示。下面的幾個(gè)章節(jié)將詳細(xì)的介紹所用到的技術(shù)和數(shù)據(jù)結(jié)構(gòu)。考慮到執(zhí)行效率，Google 中的大部分代碼都是用C/C++語言實(shí)現(xiàn)的，并且可以同時(shí)運(yùn)行在Solaris和Linux系統(tǒng)中。

圖1

    在Google的體系框架中，網(wǎng)頁爬行技術(shù)(Crawling，指網(wǎng)頁的下載過程)是由若干個(gè)分布式的網(wǎng)絡(luò)爬蟲(Crawler)軟件實(shí)現(xiàn)的。其中，一個(gè)叫做URL Server的服務(wù)器負(fù)責(zé)把需要分析的URL地址列表分派給這些網(wǎng)絡(luò)爬蟲進(jìn)行處理。網(wǎng)頁數(shù)據(jù)如果被取回，將立即被送到Store Server中。Store Server對(duì)網(wǎng)頁數(shù)據(jù)進(jìn)行壓縮，然后保存到Repository數(shù)據(jù)庫中。每一個(gè)文檔都擁有一個(gè)與之相關(guān)的唯一的ID編號(hào)，Google稱它為docID。每當(dāng)有一個(gè)新的鏈接從頁面中被解析(parse)出來，它所指向的文檔就將自動(dòng)獲得一個(gè)docID。建立索引的任務(wù)則交給索引器(Indexer)和排序器(Sorter)來完成。Indexer依次從Repository中取出文檔，對(duì)文檔解壓縮，然后對(duì)文檔進(jìn)行解析。隨后文檔被解析為一組命中。在Google中，命中(hit)是一種數(shù)據(jù)結(jié)構(gòu)，用來記錄單詞在文中每一次出現(xiàn)的信息。在命中結(jié)構(gòu)中，記錄了每個(gè)詞(word)、詞在頁面中的位置、大小寫、字體相對(duì)大小等信息。這樣，每個(gè)詞都有很多不同的命中，這些命中的組合又稱為該詞的命中列表(hit list)。索引器把這些命中再寫入到一組桶(barrel) 中，并建立一個(gè)部分排序的前敘索引(foward index)。索引器還同時(shí)把網(wǎng)頁中所有的鏈接的重要信息解析出來，并記錄到一個(gè)叫做Anchors的文件中。該文件包含了足夠多的信息，從中可以查詢出每一個(gè)鏈接的來源、指向以及該鏈接的文本。

    （譯注：索引器還把解析出的詞寫入到一個(gè)詞典(Lexicon中，這將在下文中提到。）

     URL Resolver服務(wù)器負(fù)責(zé)從 Anchors文件中讀取這些鏈接，把相對(duì)路徑改為絕對(duì)路徑，再轉(zhuǎn)換為相應(yīng)的 docID。通過docID的關(guān)聯(lián)，錨文本的信息也被加入到前序索引的anchor hit結(jié)構(gòu)中。URL Resolver同時(shí)創(chuàng)建了一個(gè)Links數(shù)據(jù)庫，用來存放兩兩對(duì)應(yīng)的docID。Links數(shù)據(jù)庫被用來計(jì)算所有文檔的PagePank 。

     接著排序器接管過這些桶。如前所述，這些桶已經(jīng)按照 docID進(jìn)行了排序。排序器的主要任務(wù)是按照WordID重新進(jìn)行排序，從而為這些桶生成一個(gè)倒排索引(inverted index)。這個(gè)操作是在每個(gè)桶中執(zhí)行的，所以只需要用到很少的臨時(shí)空間。排序器還建立了一個(gè)WordID列表，列表中同時(shí)記錄了該WordID在倒排索引中的偏移量大小。有一個(gè)叫做DumpLexicon的工具，用來把wordID和上文中提到的由索引器產(chǎn)生的詞典（Lexicon）相結(jié)合，并產(chǎn)生一個(gè)新的詞典。這個(gè)新的詞典被用在最終的搜索程序中，連同PageRank和倒排序索引一起，為用戶提供查詢服務(wù)。

  4.2 數(shù)據(jù)結(jié)構(gòu)
    Google對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行了很多優(yōu)化，其目的主要是為了有效的減少在處理大文檔的抓取、索引以及查詢時(shí)所需要耗費(fèi)的成本。雖然這些年來計(jì)算機(jī)的性能得到了很大的改善，但對(duì)于磁盤的檢索仍然需要大約10ms的時(shí)間來完成。基于性能的考慮，Google盡可能地避免使用磁盤操作，而這個(gè)想法也很大的影響了數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)思路。
   
    4.2.1 巨型文件（BigFile）
    巨型文件（BigFile）被設(shè)計(jì)成為跨越多文件系統(tǒng)地、64位地址空間的虛擬文件，并能夠在多文件系統(tǒng)中自動(dòng)進(jìn)行文件分配。因?yàn)椴僮飨到y(tǒng)不能為我們提供有用的支持，巨型文件包（BigFile package）被設(shè)計(jì)用來負(fù)責(zé)操作文件描述符的創(chuàng)建和銷毀。另外，巨型文件也支持一些初步的壓縮喧響。
   
    4.2.2 數(shù)據(jù)倉庫（Repository）
    數(shù)據(jù)倉庫（Repository）中保存了每一個(gè)網(wǎng)頁完整的HTML代碼。為了節(jié)省空間，頁面在存儲(chǔ)前使用zlib技術(shù)進(jìn)行了壓縮。壓縮技術(shù)的選擇綜合考慮了速度和壓縮比的因素。盡管bzip技術(shù)在壓縮比方面技高一籌（壓縮比達(dá)到了4：1），Google還是基于速度的考慮最終選擇了zlib（壓縮比只有3：1）。文檔記錄在數(shù)據(jù)倉庫中順序排列，并以docID、length、URL等作為文檔記錄的前綴，如圖2所示。數(shù)據(jù)倉庫的訪問不需要使用任何其他的數(shù)據(jù)結(jié)構(gòu)，這樣有助于保持?jǐn)?shù)據(jù)的完整性，并且使得開發(fā)變得更為容易。

    4.2.3  文檔索引（Document Index）
    文檔索引（Document Index）用來跟蹤每一個(gè)文檔的信息。它是一種定寬的ISAM（Index sequential access mode）類型的索引，并按照文檔的docID進(jìn)行了排序。索引中的每一項(xiàng)存儲(chǔ)了當(dāng)前文檔的狀態(tài)、指向數(shù)據(jù)倉庫的指針、文檔校驗(yàn)和，以及一些統(tǒng)計(jì)信息。如果文檔被爬蟲取回，則該索引項(xiàng)還將包含一個(gè)指向docinfo文件的指針。docinfo文件包含該文檔的URL和標(biāo)題；否則，這個(gè)指針就被指向一個(gè)僅包含一種比較緊湊的數(shù)據(jù)結(jié)構(gòu)，以及在一次搜索操作中查找一條磁盤記錄的執(zhí)行效率。

   另外，在轉(zhuǎn)換URLs到docIDs時(shí)需要用到一個(gè)文件。這個(gè)文件其實(shí)是一個(gè)包含URL校驗(yàn)和（checksum）和與它對(duì)應(yīng)的docID的列表，并且按照checksum進(jìn)行排序。通常，我們需要根據(jù)URL來查找文檔的docID。這時(shí)，首先計(jì)算出該URL的校驗(yàn)和（checksum）進(jìn)行二進(jìn)制的檢索，然后根據(jù)檢索結(jié)果找到其所對(duì)應(yīng)的docID。其實(shí)，URL Resolver正是使用這個(gè)辦法把URL轉(zhuǎn)換為docID的。在這里使用批處理模式很有必要，否則對(duì)于包含322,000,000各鏈接的數(shù)據(jù)集來說，要檢索所有的鏈接至少得耗費(fèi)數(shù)月之久。

    4.2.4 詞典 （Lexicon）
　　詞典有好幾種不同的格式．隨著內(nèi)存成本的下降，現(xiàn)在可以實(shí)現(xiàn)把詞典嵌入到內(nèi)存中運(yùn)行，這將可以大大提高運(yùn)行的效率．在一個(gè)256M電腦的內(nèi)存中，可以運(yùn)行一個(gè)包含14，000，000個(gè)詞匯的詞典。詞典由兩部分來實(shí)現(xiàn)：一個(gè)詞列表（彼此之間以Null分隔)和一個(gè)包含指針的哈希表.

    4.2.5 命中列表（Hit Lists）
    命中列表（hit list）對(duì)應(yīng)于某個(gè)特定的詞在某個(gè)特定的文檔中一次或多次的出現(xiàn)，它主要用來記錄詞在文中出現(xiàn)的位置、字體、大小寫等信息。命中列表在前序索引和倒排索引中都占據(jù)了絕大部分的空間。因此，命中列表需要盡可能地以一種高效率的方式來實(shí)現(xiàn)。有幾個(gè)可以用來參考的編碼方案：一個(gè)是簡單編碼方式（三位整數(shù)法），第二是壓縮編碼方式（對(duì)位的分配進(jìn)行手工優(yōu)化），最后一種是有名的霍夫曼編碼方式。Google在權(quán)衡了空間的占用量以及對(duì)于位操作的復(fù)雜性之后，選擇了第二種壓縮編碼方案。命中的實(shí)現(xiàn)細(xì)節(jié)，參見圖3

圖3。

    在這種壓縮編碼中，每個(gè)命中占用2個(gè)字節(jié)的空間。命中又可細(xì)分為兩種類型：特殊命中（fancy hit）和普通命中（plain hit）。特殊命中（fancy hit）是指出現(xiàn)在URL、頁面標(biāo)題、錨文本或者meta標(biāo)簽中的命中，除此之外的全部命中都是普通命中（plain hit）。普通命中（plain hit）包含標(biāo)識(shí)大小寫的位（1位）、字體大小位、以及12位的為之心系（如果在文檔中的位置大于4095，則一律以4096表示）。字體大小是字體在文檔中的相對(duì)大小，用3位來表示。字體大小只使用從000到110這七個(gè)數(shù)，111被用來單獨(dú)表示一個(gè)特殊命中（fancy hit）。特殊命中（fancy hit）也包含一個(gè)大小寫的位（1位）、字體大小（設(shè)為7=111）、4位的類型編碼、以及8位的位置信息。對(duì)于出現(xiàn)在錨文本的命中（anchor hit）來說，8位的位置信息又細(xì)分為錨中的位置信息（4位）以及錨所在的文檔docID的hash值（4位）。這樣，在針對(duì)某些特定的詞進(jìn)行查詢時(shí)，如果找不到足夠的鏈接匹配，就可以從這些anchor hit中找一些來補(bǔ)充。以后，考慮到對(duì)于位置信息和docID的哈希值哈還會(huì)有更多的解決方案，anchor hit的存儲(chǔ)方式將會(huì)有所改變。另外，Google之所以使用字體的相對(duì)大小，主要是考慮到在對(duì)文檔計(jì)算級(jí)別時(shí)，我們不能僅僅因?yàn)锳文檔使用了較大的字體就說A文檔比B文檔級(jí)別高。
  
    命中列表的長度保存在命中列表的前面。為了節(jié)省空間，采用了一些特殊的技巧，從前序索引的worldID自段和后排索引的docID字段中分別壓縮出8位和5位空間，用來存儲(chǔ)該長度值。如果長度值出現(xiàn)溢出，這些位將使用一個(gè)溢出符表示，并在緊接著的下兩個(gè)字節(jié)中包含實(shí)際的長度值。
 
    4.2.6 前序索引 （Forward index）
    前序索引實(shí)際已經(jīng)經(jīng)過部分排序。它由許多個(gè)桶組成，每個(gè)桶中保存一定范圍的wordID。如果某篇文檔中詞對(duì)應(yīng)到某個(gè)桶中的wordID，該文檔的wordID也會(huì)被記錄到該桶中。每個(gè)docID后面緊跟著一個(gè)屬于它的wordID列表，而這些列表中每個(gè)wordID的后面又緊跟著該word的命中列表。

    因?yàn)榇罅恐貜?fù)docID的存在，這種存儲(chǔ)方案也許會(huì)帶來更大的空間需求。但是由于索引被分散在許多個(gè)桶中，而且這種設(shè)計(jì)在最后由排序器執(zhí)行的短語索引操作中可以合理地節(jié)省時(shí)間上的開銷，并降低了編程的復(fù)雜度，所以，空間上的這點(diǎn)浪費(fèi)是完全可以容忍的。而且，wordID中存儲(chǔ)的實(shí)際上是WordID與其所在的桶中的WordID最小值之間計(jì)算出來的相對(duì)差。這樣，WordID就只需要24位來存儲(chǔ)，余下的8位恰好可以被用來存儲(chǔ)命中列表中的長度（參見上文）。

   4.2.7倒排索引（Inverted Index)
   和前序索引一樣，到排索引也是由同一組桶所組成，只是這些桶經(jīng)過了排序器的進(jìn)一步處理。對(duì)于每一個(gè)有效的WordID，詞典中都會(huì)有一個(gè)指向包含該WordID的桶的指針。這個(gè)指針指向一個(gè)docID的列表（doclist),列表中的每一項(xiàng)都由docID和該WordID的命中列表組成。該WordID所在的所有的文檔的docID都包含在該doclist中.

   一個(gè)重要的問題是，doclit列表中的docID應(yīng)該如何排序？一個(gè)比較簡單的解決方案是直接根據(jù)docID排序。這種方案在對(duì)多字詞的復(fù)合查詢時(shí)，可以實(shí)現(xiàn)多個(gè)doclist之間的快速歸并（merge)操作。另外一個(gè)復(fù)雜一點(diǎn)的方案，是按照word在每篇文擋中出現(xiàn)的級(jí)別進(jìn)行排序。

這種放案對(duì)于單字詞的查詢作用不大，但對(duì)于多字詞的查詢，可以實(shí)現(xiàn)把最近的查詢結(jié)果排到前面。兩種方案各有自己的不足。首先，歸并操作具有一定的難度；而級(jí)別計(jì)算函數(shù)的每一次改變都可能需要對(duì)索引進(jìn)行重建，著無疑會(huì)給開發(fā)工作增加新的難度。所以，有必要采取一種折中的方案。在這個(gè)方案中，保持兩組排序的桶，其中一組用來包含在標(biāo)題或錨文本中出現(xiàn)的命中列表，另一組則包含所有的命中列表。首先，查詢第一組桶（short barrel)中進(jìn)行；如果找不到足夠的匹配，則轉(zhuǎn)到另一組桶（full barrel)中繼續(xù)查找。

  4.3 Web爬行技術(shù)（Crawling the Web)
　　事實(shí)上，在Web上運(yùn)行一個(gè)網(wǎng)絡(luò)爬蟲（crawler)的工作頗具挑戰(zhàn)性。這不僅兼顧棘手的性能和可靠性因素之外，更重要的，還需要考慮一些社會(huì)因素。由于需要實(shí)時(shí)的和成千上萬臺(tái)狀態(tài)不可控的Web服務(wù)器進(jìn)行交互，Web爬行技術(shù)也極容易崩潰。

    為了更好的適應(yīng)Web上數(shù)以千億的網(wǎng)頁數(shù)量，Google采用了一種分布式的Web爬行系統(tǒng)，由于URL server負(fù)責(zé)把URL需求提交給若干個(gè)爬蟲軟件進(jìn)行處理。需要說明的是，URLServer以及爬蟲都是用Python語言實(shí)現(xiàn)的。每個(gè)爬蟲一次可以同時(shí)打開大約300個(gè)連接線程，這樣，網(wǎng)頁爬行足以保持一個(gè)足夠快的進(jìn)度。假如使用4個(gè)crawler，系統(tǒng)就可以實(shí)現(xiàn)最快每秒抓取超過100個(gè)頁面，也就是大約600k/秒的數(shù)據(jù)流。性能上的影響主要來自對(duì)于DNS（域名服務(wù)）的查詢，因此，每個(gè)爬蟲都配有一個(gè)單獨(dú)的DNS高速cache，這樣可以有效的避免影響效率的DNS查詢。爬蟲擁有的線程分為下列幾種狀態(tài)：DNS查詢階段，正在連接主機(jī)，發(fā)送請(qǐng)求階段，以及處理服務(wù)器響應(yīng)過程。依據(jù)狀態(tài)的不同，線程被分別放在不同的隊(duì)列中。當(dāng)線程的狀態(tài)發(fā)生改變時(shí)，異步IO的方式被用來發(fā)出事件通知，同時(shí)線程被轉(zhuǎn)移到另一個(gè)相關(guān)隊(duì)列中。

   事實(shí)上，由于面對(duì)如此巨大的數(shù)據(jù)處理，總會(huì)有一些難以預(yù)料的事情發(fā)生。舉個(gè)例子來說，如果爬蟲試圖處理的鏈接是一個(gè)在線游戲，那會(huì)出現(xiàn)什么情況？情況的確很糟，自作聰明的爬蟲將取回大量的垃圾頁面，而當(dāng)你發(fā)現(xiàn)問題并試圖處理時(shí)，你將面對(duì)的是數(shù)以千萬計(jì)的已經(jīng)被下載的網(wǎng)頁。看來，有些導(dǎo)致錯(cuò)誤的因素也許根本是無法預(yù)測的。系統(tǒng)必須經(jīng)過認(rèn)真的測試。然而，Internet如此之大，測試工作從何開始？這個(gè)時(shí)候，合理處理用戶的反饋信息顯得尤為重要。

  4.4 Web索引技術(shù)（Indexing the Web)
       解析技術(shù)（Parsing)--任何一種為Web設(shè)計(jì)的解析技術(shù)必須能夠有效處理各種各樣可能出現(xiàn)的錯(cuò)誤，包括HTML標(biāo)簽的拼寫錯(cuò)誤，標(biāo)簽定義中缺少的空格，非ASCII字符，錯(cuò)誤嵌套的HTML標(biāo)簽以及形形色色的其它錯(cuò)誤類型。這些錯(cuò)誤都在挑戰(zhàn)著設(shè)計(jì)者的想象力，促使他們拿出創(chuàng)造性的設(shè)計(jì)方案。考慮到速度的最大化，Google沒有采用由YACC來產(chǎn)生CFG解析器的做法，而使用Flex（一種快速的詞典分析器制作工具）設(shè)計(jì)了一個(gè)具有自己堆棧的詞典分析器。當(dāng)然，分析器必須同時(shí)實(shí)現(xiàn)穩(wěn)定性和高速度的要求。

      文檔的哈希索引（Indexing Documents into Barrels)--文檔被解析之后，就會(huì)被編碼并放入有許多桶組成的哈希表中。文檔中的每一個(gè)詞，通過檢索在內(nèi)存中運(yùn)行的詞典哈希表，被映射成其所對(duì)應(yīng)的WordID。詞典中沒有的詞被紀(jì)錄到一個(gè)日志文件中。當(dāng)一個(gè)word被映射成WordID時(shí)，它在當(dāng)前文檔中的出現(xiàn)信息將被同時(shí)構(gòu)造成相應(yīng)的命中列表，然后命中列表被紀(jì)錄到前序索引相對(duì)應(yīng)的桶中。在這個(gè)過程中，詞典必須被共享，所以如何解決索引階段的并發(fā)操作問題成為一個(gè)難題。有一個(gè)方案，可以避免詞典的共享。在這個(gè)方案中，使用一個(gè)基詞典，其中固定使用大約14，000，000個(gè)詞。擴(kuò)增的詞都寫入到日志中。這樣，多感索引器就可以并發(fā)的執(zhí)行，而把這個(gè)包含擴(kuò)增詞匯的日志文件交給最后剩下的一個(gè)索引器處理就夠了。

      排序技術(shù)（Sorting)--為了建立倒排索引，排序排序器接管過前敘索引中的桶，并按照WordID進(jìn)行重新排序，從而產(chǎn)生了兩組倒排序的桶：一組是對(duì)于標(biāo)題和錨命中的倒排序索引（short barrle),一組是對(duì)于所有命中列表的倒排序索引（full barrle)。由于排序的過程每次僅再一個(gè)桶中進(jìn)行，所以只需要很少的臨時(shí)空間。另外，排序的階段被盡可能多的分派到多臺(tái)計(jì)算機(jī)上運(yùn)行，這樣，多個(gè)排序器就可以并行處理多個(gè)不同的bucket。因?yàn)橥辈贿m合被放入內(nèi)存中運(yùn)行，排序器便把它細(xì)分為一系列適合放進(jìn)內(nèi)存中的bucket，這些bucket是基于WordID和docID的。然后，排序器把每一個(gè)bucket加載到內(nèi)存中，并執(zhí)行排序，最后把它的內(nèi)容分別寫入到short barrle和full barrle這兩組倒排的桶中。

  4.5 搜索技術(shù)（Searching)
    能夠高效地提供高質(zhì)量的搜索結(jié)果，是每一個(gè)搜索技術(shù)的最終目標(biāo)。很多大型的商業(yè)化搜索引擎已經(jīng)在執(zhí)行效率方面取得了很大的進(jìn)步。所以Google就把更多的精力投放到搜索結(jié)果的質(zhì)量研究上來。當(dāng)然，Google的執(zhí)行效率同商業(yè)化的搜索引擎相比同樣毫不遜色。

Google的搜索過程如下。
 
    1.解析查詢字符串；
    2.把word映射成wordID；
    3.對(duì)每一個(gè)word，首先從short barrel中doclist的開頭進(jìn)行檢索；
    4.遍歷整個(gè)doclist直到發(fā)現(xiàn)有一個(gè)文檔能夠匹配所有的搜索項(xiàng)目；  
    5.為此查詢計(jì)算文檔的級(jí)別；
    6.如果到了short barrel中doclist的結(jié)尾，則從full barrel中doclist的開頭繼續(xù)進(jìn)行檢索，并跳轉(zhuǎn)到步驟4；
    7.如果沒有到達(dá)doclist的結(jié)尾，跳轉(zhuǎn)到步驟4；
    8.對(duì)所有通過rank匹配的文檔進(jìn)行排序，并返回前K個(gè)查詢結(jié)果。

    為了控制響應(yīng)時(shí)間，一旦匹配的文檔數(shù)目達(dá)到某個(gè)指定的值（例如40，000），如圖4所示，搜索器就直接跳轉(zhuǎn)到第8步。這就意味著可能有一些沒有完全優(yōu)化的查詢結(jié)果被返回。盡管如此，PageRank技術(shù)的存在有效地改善了這種狀況。

    4.5.1級(jí)別審定系統(tǒng)(The Panking System)
    與其它的搜索引擎相比，Google利用了更多的Web文檔所提供的信息。每一個(gè)命中列表紀(jì)錄了詞的位置、字體、大小寫等信息。另外,包含在錨文本中的命中和文黨的PageRank一樣被Google所關(guān)注。要把所有這些信息都綜合起來給出一個(gè)頁面的級(jí)別有點(diǎn)難度，級(jí)別判定功能必定被設(shè)計(jì)成不會(huì)受到任何個(gè)別因素的影響。

    首先考慮一種最簡單的情況--單詞查詢。為了在單詞匯查詢中計(jì)算出一個(gè)文檔的級(jí)別，Google首先分析該詞匯在這個(gè)文檔中的命中列表。Google為每一個(gè)命中定義了以下幾種不同的類型：標(biāo)題、錨、URL、普通的大字體文本、普通的小字體文本 ，每一種類型都有自己的類型權(quán)重（type-weight).Google把命中的類型權(quán)重組合到一起形成一個(gè)以類型為索引的向量，接著統(tǒng)計(jì)出命中列表中每一種類型的命中所占的數(shù)量。每一個(gè)計(jì)數(shù)值又被轉(zhuǎn)換為一個(gè)計(jì)數(shù)權(quán)重（count-weight)，計(jì)數(shù)權(quán)重隨計(jì)數(shù)值呈線性增長，到達(dá)某個(gè)計(jì)數(shù)值之后就會(huì)趨于停止。最后，把類型權(quán)重組成向量和計(jì)數(shù)權(quán)重組成的向量進(jìn)行點(diǎn)乘得到的矢量積作為該文檔的IR分值。IR分值和PageRank再進(jìn)行組合從而得出文檔最終的級(jí)別。

   對(duì)于多詞匯的查詢，情況變得更加復(fù)雜。多個(gè)命中列表需要被同步分析，在文檔中出現(xiàn)位置比較靠近的命中就會(huì)比位置離的教遠(yuǎn)的命中具有較高的權(quán)重。多個(gè)命中列表中的命中被綜合到一起一使得鄰近的命中最終被分配到一起。對(duì)于每一組經(jīng)過匹配的命中，他們之間的相似度（proximity)接著被計(jì)算出來。相似度基于命中的文檔（或錨）中距離的遠(yuǎn)近，并且被劃分為10個(gè)不同的值“bins”，這些bins的范圍被定義為從短語匹配（phrase match)到根本不匹配（not even close).除了對(duì)每一種類型的命中進(jìn)行計(jì)數(shù)之外，同時(shí)也對(duì)每一種類型和相似度進(jìn)行計(jì)數(shù)。每一對(duì)類型和相似度的組合稱作一個(gè)類型相似度權(quán)重（type-prox-weight),命中的計(jì)數(shù)則被轉(zhuǎn)換為計(jì)數(shù)權(quán)重。最后，把計(jì)數(shù)權(quán)重組成的向量和類型相似度權(quán)重組成的向量進(jìn)行點(diǎn)乘也得到一個(gè)IR分值。在Google的一種特殊的調(diào)試模式中，這些數(shù)字和矩陣可以隨查詢結(jié)果一同顯示，這將為級(jí)別審定系統(tǒng)的開發(fā)工作帶來很大的幫助。