【正文】 服務(wù)器，使用由DumpLexicon所生成的字典，利用上述反向索引以及頁(yè)面等級(jí)PageRank來回答用戶的提問。主要數(shù)據(jù)結(jié)構(gòu)經(jīng)過優(yōu)化的Google數(shù)據(jù)結(jié)構(gòu)，能夠用較小的代價(jià)抓取大量文檔，建立索引和查詢。磁盤尋道仍然需要10ms。這對(duì)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)影響很大。大文件BigFiles是跨越多個(gè)文件系統(tǒng)的虛擬文件，用長(zhǎng)度是64位的整型數(shù)據(jù)尋址。BigFiles包也處理文件描述符的分配。每個(gè)網(wǎng)頁(yè)用zlib（見RFC1950）壓縮。壓縮技術(shù)的選擇既要考慮速度又要考慮壓縮率。知識(shí)庫(kù)用bzip的壓縮率接近4：1?？s率是3：1。訪問知識(shí)庫(kù)不需要其它的數(shù)據(jù)結(jié)構(gòu)。用其它數(shù)據(jù)結(jié)構(gòu)重構(gòu)系統(tǒng)，我們只需要修改知識(shí)庫(kù)和crawler錯(cuò)誤列表文件。文檔索引文檔的索引保持每個(gè)文檔有關(guān)的信息。它是固定的寬度索引。如果一個(gè)文檔已經(jīng)被抓到，指針指向docinfo文件，該文件的寬度可變，包含了URL和標(biāo)題。這種設(shè)計(jì)考慮到簡(jiǎn)潔的數(shù)據(jù)結(jié)構(gòu)，以及在查詢中只需要一個(gè)磁盤尋道時(shí)間就能夠訪問一條記錄。它是URL校驗(yàn)和與相應(yīng)docID的列表，并按照校驗(yàn)排序。通過對(duì)這個(gè)文件進(jìn)行合并，可以把一批URL轉(zhuǎn)換成對(duì)應(yīng)的docID。術(shù)把URL轉(zhuǎn)換成docID。花費(fèi)一個(gè)多月的時(shí)間。辭典詞典有幾種不同的形式。當(dāng)前實(shí)現(xiàn)中，一臺(tái)256M內(nèi)存的機(jī)器就可以把詞典裝入到內(nèi)存中。它執(zhí)行分兩部分—詞匯表（串聯(lián)在一起，但使用空值隔開）和指針的哈希表的列表的實(shí)現(xiàn)。一個(gè)命中列表對(duì)應(yīng)著一個(gè)單詞在一個(gè)文檔中出現(xiàn)的位置、字體和大小寫信息的列表。我們考慮了對(duì)位置，字體和大小寫信息的多種編碼方式——簡(jiǎn)單編碼（3個(gè)整數(shù)），壓縮編碼（手工優(yōu)化分配比特）和霍夫曼編碼（Huffman coding）。圖3.有兩種命中：特殊命中（fancy hit）和普通命中（plain hit）。其他的都是普通命中。字體在文檔中的相對(duì)大小用3個(gè)比特表示（實(shí)際上只用到7個(gè)值，因?yàn)?11標(biāo)示一個(gè)特殊命中）。對(duì)于錨命中，表示位置的8個(gè)比特被分成兩部分，4個(gè)比特表示在錨文本中的位置，4個(gè)比特為錨文本所在docID的哈希（hash）值。我們期望能更新錨命中的存儲(chǔ)方式能讓位置和docID哈希值能有更大的范圍。命中列表的長(zhǎng)度存在命中的前面。這樣就將長(zhǎng)度分別限制在8個(gè)比特和5個(gè)比特（有一些技巧可以從wordID中借用8個(gè)比特）。它被存放在一系列的桶（barrels）里面（我們用了64個(gè)）。如果一個(gè)文檔包含了屬于某個(gè)桶的單詞，它的docID將被記錄在桶里面，后面接著一個(gè)wordID的列表和相應(yīng)的命中列表。更進(jìn)一步，我們并沒有存儲(chǔ)完整的wordID，而是存儲(chǔ)每個(gè)wordID相對(duì)于其對(duì)應(yīng)的桶里面最小wordID的差距。對(duì)每一個(gè)合法的wordID，詞典包含了一個(gè)指向?qū)?yīng)的桶的指針。這個(gè)文檔列表顯示了有這個(gè)單詞出現(xiàn)的所有文檔。一個(gè)重要的事情是如何對(duì)這個(gè)文檔列表排序。在多個(gè)單詞的查詢中，這種方法可以快速地完成兩個(gè)文檔列表的歸并。這種方式使得單個(gè)詞的查詢相當(dāng)簡(jiǎn)單，并且多詞查詢的返回結(jié)果也很可能接近開頭。而且，開發(fā)也會(huì)困難得多，因?yàn)槊看卧u(píng)分函數(shù)變動(dòng)就需要重新建立整個(gè)索引。這樣我們首先檢查第一個(gè)桶集合，如果沒有足夠的匹配再檢查那個(gè)大一點(diǎn)的。運(yùn)行網(wǎng)絡(luò)爬蟲是一項(xiàng)很有挑戰(zhàn)性的任務(wù)。抓取是一個(gè)很脆弱的應(yīng)用，因?yàn)樗枰c成百上千各種各樣的web服務(wù)器和域名服務(wù)器交互，這些都不在系統(tǒng)的控制范圍之內(nèi)。為了抓取幾億網(wǎng)頁(yè)，Google有一個(gè)快速的分布式爬蟲系統(tǒng)。URL服務(wù)器和爬蟲都用Python實(shí)現(xiàn)。這樣才能保證足夠快地抓取速度。這大概有600K每秒的數(shù)據(jù)傳輸。每個(gè)爬蟲都維護(hù)一個(gè)自己的DNS緩存，這樣在它抓取網(wǎng)頁(yè)之前就不再需要每次都做DNS查詢。這些因素使得爬蟲成為系統(tǒng)里一個(gè)復(fù)雜的模塊。因?yàn)楹芏嗳嗽诰W(wǎng)上，他們并不知道爬蟲是什么，因?yàn)檫@是他們第一次見到。而且，由于涉及到大量的數(shù)據(jù)，一些意想不到的事情總會(huì)發(fā)生。這導(dǎo)致了游戲中出現(xiàn)大量的垃圾消息！這個(gè)問題被證實(shí)是很容易解決的。因?yàn)榫W(wǎng)絡(luò)頁(yè)面和服務(wù)器總是在變化中，在爬蟲正式運(yùn)行在大部分的互聯(lián)網(wǎng)站點(diǎn)之前是不可能進(jìn)行測(cè)試的。需要訪問大量互聯(lián)網(wǎng)站點(diǎn)的系統(tǒng)需要設(shè)計(jì)得很健壯并且小心地測(cè)試。從HTML標(biāo)簽里面的錯(cuò)別字到一個(gè)標(biāo)簽里面上千字節(jié)的0，非ASCII字符，嵌套了幾百層的HTML標(biāo)簽，還有大量超乎人想象的錯(cuò)誤和“創(chuàng)意”。開發(fā)這樣一個(gè)解析器需要大量的工作才能保證它的速度和健壯。每一個(gè)單詞被內(nèi)存里的哈希表——詞典轉(zhuǎn)化成一個(gè)wordID。單詞在被轉(zhuǎn)化成我wordID的時(shí)候，他們?cè)诋?dāng)前文檔中的出現(xiàn)會(huì)被翻譯成命中列表，并寫入正排桶(forward barrels)中。我們并沒有共享整個(gè)詞典，而是在內(nèi)存里保存一份基本詞典，固定的1千4百萬(wàn)個(gè)單詞，多余的詞寫入一個(gè)日志文件。排序——為了產(chǎn)生倒排索引，排序器取出各個(gè)正排的桶，然后根據(jù)wordID排序來產(chǎn)生一個(gè)標(biāo)題和錨命中的倒排桶，和一個(gè)全文的倒排桶。而且，我們簡(jiǎn)單地通過用盡可能多的機(jī)器運(yùn)行多個(gè)排序器做到排序的并行化，不同的排序器可以同時(shí)處理不同的桶。接著，排序器將每個(gè)桶載入內(nèi)存，排好序，把內(nèi)容寫入短的倒排桶和完整的倒排桶。很多大型的商業(yè)搜索引擎在效率方面看起來都有很大的進(jìn)步。Google的查詢?cè)u(píng)估流程如圖4。為了限制響應(yīng)時(shí)間，一旦某個(gè)數(shù)量(現(xiàn)在是40,000)的匹配文檔被找到，搜索器自動(dòng)跳到圖4中的第8步。我們現(xiàn)在在研究新的方法來解決這個(gè)問題。，從每個(gè)單詞的全桶(full barrel)文檔列表開始查找，跳到第4步。，然后返回評(píng)分最高的k個(gè)。Google比典型的搜索引擎維護(hù)了根多的web文檔的信息。而且，我們綜合考慮了超鏈接文本命中和頁(yè)面的PageRank值。我們?cè)O(shè)計(jì)了評(píng)分函數(shù)保證沒有一個(gè)因素有太大的影響。為了對(duì)一個(gè)單詞的查詢計(jì)算文檔的分值，Google首先為這個(gè)單詞查看這個(gè)文檔的命中列表。類型權(quán)重值構(gòu)成一個(gè)由類型尋址（indexed）的向量。每個(gè)數(shù)量轉(zhuǎn)化成一個(gè)數(shù)量權(quán)重（countweight）。我們通過數(shù)量權(quán)重向量和類型權(quán)重向量的點(diǎn)乘為一個(gè)文檔算出一個(gè)IR分?jǐn)?shù)?，F(xiàn)在，多個(gè)命中列表必須一次掃描完，這樣一個(gè)文檔中較近的命中才能比相距較遠(yuǎn)的命中有更高的評(píng)分。對(duì)每一個(gè)命中的匹配集(matched set)，會(huì)計(jì)算出一個(gè)接近度。不光要為每一種類型的命中計(jì)數(shù)，還要為每一種類型和接近度都計(jì)數(shù)。數(shù)量被轉(zhuǎn)化成數(shù)量權(quán)重。所有這些數(shù)字和矩陣都會(huì)在特殊的調(diào)試模式下與搜索結(jié)果一起顯示出來。找出這些參數(shù)的權(quán)重值簡(jiǎn)直就跟妖術(shù)一樣。一個(gè)被信任的用戶可以選擇性地評(píng)價(jià)所有的返回結(jié)果。然后在我們改變?cè)u(píng)分系統(tǒng)的時(shí)候，我們能看到修改對(duì)之前評(píng)價(jià)過的搜索結(jié)果的影響。5結(jié)果與表現(xiàn)衡量一個(gè)搜索引擎最重要的標(biāo)準(zhǔn)是其搜索結(jié)果的質(zhì)量。圖表4Google對(duì)于搜索“”的結(jié)果，作為一個(gè)例子可以說明，對(duì)PageRank, anchor text這樣的搜索結(jié)果顯示了Google的特色。這樣的方法當(dāng)在需要對(duì)結(jié)果集篩選時(shí)非常有用。當(dāng)前，更不用說正確的結(jié)果。基于anchor text同樣的，第15號(hào)結(jié)果是一個(gè)電子郵件地址，當(dāng)然這也是基于超鏈接的結(jié)果，而非可抓取得結(jié)果。所有結(jié)果都是合理的高質(zhì)量頁(yè)面，而且最后檢查，沒有壞連接。PageRank的百分比使用紅色條形圖表示?；蛑挥袥]有Bill當(dāng)然對(duì)一個(gè)實(shí)際的對(duì)搜索引擎的質(zhì)量測(cè)試應(yīng)該包括廣泛的對(duì)用戶研究或者對(duì)搜索結(jié)果的分析，但是我們沒有時(shí)間做以上析。除搜索質(zhì)量外，Gooogle被設(shè)計(jì)為能夠消化互聯(lián)網(wǎng)規(guī)模不斷增長(zhǎng)帶來的效能問題。表一是對(duì)Google的統(tǒng)計(jì)與存儲(chǔ)需求的詳細(xì)分類，由于壓縮后的存儲(chǔ)體積為53GB，為源數(shù)據(jù)的三分之一多一點(diǎn)。更重要的是，搜索引擎使用的所有數(shù)據(jù)的總合需要相應(yīng)的存儲(chǔ)大約為55GB。[short inverted index]，在更好的編碼與壓縮文檔索引后，一個(gè)高質(zhì)量的網(wǎng)絡(luò)搜索引擎可能只需要一臺(tái)有7GB存儲(chǔ)空間的新電腦。這樣信息被轉(zhuǎn)化為數(shù)據(jù)的速度以及系統(tǒng)主要部分改變后被測(cè)試的速度都相對(duì)更快。一旦硬盤被填滿、或命名服務(wù)器崩潰，或者其它問題導(dǎo)致系統(tǒng)停止，都很難度量抓取所需要化費(fèi)的時(shí)間。但是如果系統(tǒng)運(yùn)行更為流暢，這個(gè)過程還可以更快，最后的1千1百個(gè)頁(yè)面只使用了63個(gè)小時(shí)，平均4百萬(wàn)每天。優(yōu)化包括對(duì)本地硬盤上的文檔的索引進(jìn)行大規(guī)模的升級(jí)和替換關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)。排序可以完全平行作業(yè)，使用四臺(tái)機(jī)器，整個(gè)處理時(shí)間花費(fèi)近24個(gè)小時(shí)。當(dāng)前版本的Google返回多數(shù)查詢結(jié)果的時(shí)間是1到10秒。的限制。我們傾向于通過分布式，硬件，軟件，和算法的改進(jìn)來提高Google的速度。表2有幾個(gè)現(xiàn)在版本Google響應(yīng)查詢時(shí)間的例子。6結(jié)論Google設(shè)計(jì)成可伸縮的搜索引擎。Google應(yīng)用了一些技術(shù)改進(jìn)搜索質(zhì)量包括PageRank，鏈接描述文字，相鄰信息。未來的工作大我們直接的目標(biāo)是提高搜索效率，覆蓋大約100000000個(gè)網(wǎng)頁(yè)。求緩沖區(qū)，巧妙地分配磁盤空間，子索引。我們必須有一個(gè)巧妙的算法來決定哪些舊網(wǎng)頁(yè)需要重新抓取，哪些新網(wǎng)頁(yè)需要被抓取。個(gè)目標(biāo)已經(jīng)由實(shí)現(xiàn)了。我們計(jì)劃加一些簡(jiǎn)單的已經(jīng)被商業(yè)搜索引擎支持的特征，例如布爾然而另外一些應(yīng)用剛剛開始探索，例如相關(guān)反饋，聚類（Google現(xiàn)在支持簡(jiǎn)單的基于主機(jī)名的聚類）。（象用戶地址），結(jié)果摘要。簡(jiǎn)單的實(shí)驗(yàn)證明，通過增加用戶主頁(yè)的權(quán)重或書簽，PageRank可以個(gè)性化。接文本，我們正在試驗(yàn)用鏈接周圍的文本加入到鏈接文本。如此之多以至于我們不能在此一一列舉，因此在不久的將來，我們希望所做的工作不止本節(jié)提到的。當(dāng)結(jié)果常常是好笑的，并且超出用戶的眼界，他們常?；倚膯蕷饫速M(fèi)了寶貴的時(shí)間。Google的設(shè)計(jì)目標(biāo)是隨著Web的快速發(fā)展提供高質(zhì)量的搜索結(jié)果，容易找到信息。文本。評(píng)價(jià)搜索引擎是困難的，我們主觀地發(fā)現(xiàn)Google的搜索質(zhì)量比當(dāng)今商業(yè)搜索引擎高。用鏈接文本描述鏈接所指向的網(wǎng)頁(yè)有助于搜索引擎返回相關(guān)的結(jié)果（某種程度上提高了質(zhì)量）。除空間和時(shí)間必須高效，處理整個(gè)Web時(shí)固定的幾個(gè)因素非常重要。量、磁盤尋道時(shí)間、磁盤吞吐量、磁盤容量、網(wǎng)絡(luò)IO都是瓶頸。Google的主要數(shù)據(jù)結(jié)構(gòu)能夠有效利用存儲(chǔ)空間。我們希望能在一個(gè)月內(nèi)建立不僅是高質(zhì)量的搜索引擎，它還是研究工具。最近的研究，例如，提出了這說明Google不僅是重要的研究工具，而且必不可少，應(yīng)用廣泛。7致謝Scott Hassan and Alan Steremberg評(píng)價(jià)Google的改進(jìn)。感謝Hector GarciaMolina, Rajeev Motwani, Jeff Ullman, and Terry Winograd和全部WebBase開發(fā)組的支持和富有深刻見解的討論。這里DARPA引用Best of the Web 1994 Navigators Bill Clinton Joke of the Day: April 14, 1997. ~cjburke/clinton/.Bzip2 Homepage Google Search Engine Harvest Mauldin, Michael L. Lycos Design Choices in an Internet Search Service, IEEE Expert Interview The Effect of Cellular Phone Use Upon Driver Attention Search Engine Watch RFC 1950 (zlib) ftp://Robots Exclusion Protocol: Web Growth Summary: Yahoo! [Abiteboul 97] Serge Abiteboul and Victor Vianu, Queries and Computation on the Web. Proceedings of the International Conference on Database Theory.GreeceBrisbane,LawrenceAustralia, April 1418, 1998.[Gravano 94] Luis Gravano, Hector GarciaMolina, and A. Tomasic. The Effectiveness of GlOSS for the TextDatabase Discovery Problem. Proc. of the 1994 ACM SIGMOD International Conference On Management Of Data, 1994.[Kleinberg 98] Jon Kleinberg, Authoritative Sources in a Hyperlinked Environment, Proc. ACMSIAM Symposium on Discrete Algorithms, 1998.[Marchiori 97] Massimo Marchiori. The Quest for Correct Information on the Web: Hyper Search Engines. The Sixth International WWW Conference (WWW 97).USA, April 711, 1997.[McBryan 94] Oliver A. McBryan. GENVL and WWWW: Tools for Taming the Web. First International Conference on the World Wide Web. CERN,(Switzerland), May 252627 1994. [Page 98]Page, Sergey Brin, Rajeev Motwani, Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web. Manuscript in progress. ~backrub/[Pinkerton 94] Brian Pin