這篇文章中，我們介紹了google，它是一個(gè)大型的搜索引擎(of a large-scale search engine)的原型，搜索引擎在超文本中應(yīng)用廣泛。Google的設(shè)計(jì)能夠高效地抓網(wǎng)頁并建立索引，它的查詢結(jié)果比其它現(xiàn)有系統(tǒng)都高明。這個(gè)原型的全文 和超連接的數(shù)據(jù)庫至少包含24'000'000個(gè)網(wǎng)頁。我們可以從http://google.stanford.edu/ 下載。
設(shè)計(jì)搜索引擎是一項(xiàng)富有挑戰(zhàn)性的工作。搜索引擎為上億個(gè)網(wǎng)頁建立索引，其中包含大量迥然不同的詞匯。而且每天要回答成千上萬個(gè)查詢。在網(wǎng)絡(luò)中，盡管 大型搜索引擎非常重要，但是學(xué)術(shù)界卻很少研究它。此外由于技術(shù)的快速發(fā)展和網(wǎng)頁的大量增加，現(xiàn)在建立一個(gè)搜索引擎和三年前完全不同。
本文詳細(xì)介紹了我們的大型搜索引擎，據(jù)我們所知，在公開發(fā)表的論文中，這是第一篇描述地如此詳細(xì)。除了把傳統(tǒng)數(shù)據(jù)搜索技術(shù)應(yīng)用到如此大量級(jí)網(wǎng)頁中所遇到的問題，還有許多新的技術(shù)挑戰(zhàn)，包括應(yīng)用超文本中的附加信息改進(jìn)搜索結(jié)果。
本文將解決這個(gè)問題，描述如何運(yùn)用超文本中的附加信息，建立一個(gè)大型實(shí)用系統(tǒng)。任何人都可以在網(wǎng)上隨意發(fā)布信息，如何有效地處理這些無組織的超文本集合，也是本文要關(guān)注的問題。
關(guān)鍵詞 World Wide Web，搜索引擎，信息檢索，PageRank, Google
1 緒論
Web給信息檢索帶來了新的挑戰(zhàn)。Web上的信息量快速增長，同時(shí)不斷有毫無經(jīng)驗(yàn)的新用戶來體驗(yàn)Web這門藝術(shù)。人們喜歡用超級(jí)鏈接來網(wǎng)上沖浪，通常都以 象Yahoo這樣重要的網(wǎng)頁或搜索引擎開始。大家認(rèn)為List(目錄)有效地包含了大家感興趣的主題，但是它具有主觀性，建立和維護(hù)的代價(jià)高，升級(jí)慢，不 能包括所有深?yuàn)W的主題。基于關(guān)鍵詞的自動(dòng)搜索引擎通常返回太多的低質(zhì)量的匹配。使問題更遭的是，一些廣告為了贏得人們的關(guān)注想方設(shè)法誤導(dǎo)自動(dòng)搜索引擎。我 們建立了一個(gè)大型搜索引擎解決了現(xiàn)有系統(tǒng)中的很多問題。應(yīng)用超文本結(jié)構(gòu)，大大提高了查詢質(zhì)量。我們的系統(tǒng)命名為google，取名自googol的通俗拼 法，即10的100次方，這和我們的目標(biāo)建立一個(gè)大型搜索引擎不謀而合。
1.1網(wǎng)絡(luò)搜索引擎—升級(jí)換代(scaling up)：
1994-2000 搜索引擎技術(shù)不得不快速升級(jí)(scale dramatically)跟上成倍增長的web數(shù)量。
1994年，第一個(gè)Web搜索引擎，World Wide Web Worm(WWWW)可以檢索到110，000個(gè)網(wǎng)頁和Web的文件。
到1994年11月，頂級(jí)的搜索引擎聲稱可以檢索到2‘000'000(WebCrawler)至100‘000'000個(gè)網(wǎng)絡(luò)文件(來自 Search Engine Watch)。
可以預(yù)見到2000年，可檢索到的網(wǎng)頁將超過1‘000'000‘000。同時(shí)，搜索引擎的訪問量也會(huì)以驚人的速度增長。
在1997年的三四月份，World Wide Web Worm 平均每天收到1500個(gè)查詢。
在1997年11月，Altavista 聲稱它每天要處理大約20'000'000個(gè)查詢。隨著網(wǎng)絡(luò)用戶的增長.
到2000年，自動(dòng)搜索引擎每天將處理上億個(gè)查詢。我們系統(tǒng)的設(shè)計(jì)目標(biāo)要解決許多問題，包括質(zhì)量和可升級(jí)性，引入升級(jí)搜索引擎技術(shù)(scaling search engine technology)，把它升級(jí)到如此大量的數(shù)據(jù)上。
1.2 Google：
跟上Web的步伐(Scaling with the Web)建立一個(gè)能夠和當(dāng)今web規(guī)模相適應(yīng)的搜索引擎會(huì)面臨許多挑戰(zhàn)。抓網(wǎng)頁技術(shù)必須足夠快，才能跟上網(wǎng)頁變化的速度(keep them up to date)。存儲(chǔ)索引和文檔的空間必須足夠大。索引系統(tǒng)必須能夠有效地處理上千億的數(shù)據(jù)。處理查詢必須快，達(dá)到每秒能處理成百上千個(gè)查詢 (hundreds to thousands per second.)。隨著Web的不斷增長，這些任務(wù)變得越來越艱巨。然而硬件的執(zhí)行效率和成本也在快速增長，可以部分抵消這些困難。還有幾個(gè)值得注意的因 素，如磁盤的尋道時(shí)間(disk seek time)，操作系統(tǒng)的效率(operating system robustness)。在設(shè)計(jì)Google的過程中，我們既考慮了Web的增長速度，又考慮了技術(shù)的更新。Google的設(shè)計(jì)能夠很好的升級(jí)處理海量數(shù) 據(jù)集。它能夠有效地利用存儲(chǔ)空間來存儲(chǔ)索引。優(yōu)化的數(shù)據(jù)結(jié)構(gòu)能夠快速有效地存取(參考4.2節(jié))。進(jìn)一步，我們希望，相對(duì)于所抓取的文本文件和HTML網(wǎng) 頁的數(shù)量而言，存儲(chǔ)和建立索引的代價(jià)盡可能的小(參考附錄B)。對(duì)于象Google這樣的集中式系統(tǒng)，采取這些措施得到了令人滿意的系統(tǒng)可升級(jí)性 (scaling properties)。
1. 3設(shè)計(jì)目標(biāo)
1.3.1提高搜索質(zhì)量我們的主要目標(biāo)是提高Web搜索引擎的質(zhì)量。
1994年，有人認(rèn)為建立全搜索索引(a complete search index)可以使查找任何數(shù)據(jù)都變得容易。根據(jù)Best of the Web 1994 -- Navigators ，“最好的導(dǎo)航服務(wù)可以使在Web上搜索任何信息都很容易(當(dāng)時(shí)所有的數(shù)據(jù)都可以被登錄)”。然而1997年的Web就迥然不同。近來搜索引擎的用戶已經(jīng) 證實(shí)索引的完整性不是評(píng)價(jià)搜索質(zhì)量的唯一標(biāo)準(zhǔn)。用戶感興趣的搜索結(jié)果往往湮沒在“垃圾結(jié)果Junk result”中。實(shí)際上，到1997年11月為止，四大商業(yè)搜索引擎中只有一個(gè)能夠找到它自己(搜索自己名字時(shí)返回的前十個(gè)結(jié)果中有它自己)。導(dǎo)致這一 問題的主要原因是文檔的索引數(shù)目增加了好幾個(gè)數(shù)量級(jí)，但是用戶能夠看的文檔數(shù)卻沒有增加。用戶仍然只希望看前面幾十個(gè)搜索結(jié)果。因此，當(dāng)集合增大時(shí)，我們 就需要工具使結(jié)果精確(在返回的前幾十個(gè)結(jié)果中，有關(guān)文檔的數(shù)量)。由于是從成千上萬個(gè)有點(diǎn)相關(guān)的文檔中選出幾十個(gè)，實(shí)際上，相關(guān)的概念就是指最好的文 檔。高精確非常重要，甚至以響應(yīng)(系統(tǒng)能夠返回的有關(guān)文檔的總數(shù))為代價(jià)。令人高興的是利用超文本鏈接提供的信息有助于改進(jìn)搜索和其它應(yīng)用 。尤其是鏈接結(jié)構(gòu)和鏈接文本，為相關(guān)性的判斷和高質(zhì)量的過濾提供了大量的信息。Google既利用了鏈接結(jié)構(gòu)又用到了anchor文本(見2.1和2.2 節(jié))。
1.3.2搜索引擎的學(xué)術(shù)研究隨著時(shí)間的流逝，除了發(fā)展迅速，Web越來越商業(yè)化。
1993年，只有1.5%的Web服務(wù)是來自.com域名。到1997年，超過了60%。同時(shí)，搜索引擎從學(xué)術(shù)領(lǐng)域走進(jìn)商業(yè)。到現(xiàn)在大多數(shù)搜索引擎被公司 所有，很少技公開術(shù)細(xì)節(jié)。這就導(dǎo)致搜索引擎技術(shù)很大程度上仍然是暗箱操作，并傾向做廣告(見附錄A)。Google的主要目標(biāo)是推動(dòng)學(xué)術(shù)領(lǐng)域在此方面的發(fā) 展，和對(duì)它的了解。另一個(gè)設(shè)計(jì)目標(biāo)是給大家一個(gè)實(shí)用的系統(tǒng)。應(yīng)用對(duì)我們來說非常重要，因?yàn)楝F(xiàn)代網(wǎng)絡(luò)系統(tǒng)中存在大量的有用數(shù)據(jù)(us because we think some of the most interesting research will involve leveraging the vast amount of usage data that is available from modern web systems)。例如，每天有幾千萬個(gè)研究。然而，得到這些數(shù)據(jù)卻非常困難，主要因?yàn)樗鼈儧]有商業(yè)價(jià)值。我們最后的設(shè)計(jì)目標(biāo)是建立一個(gè)體系結(jié)構(gòu)能夠支持 新的關(guān)于海量Web數(shù)據(jù)的研究。為了支持新研究，Google以壓縮的形式保存了實(shí)際所抓到的文檔。設(shè)計(jì)google的目標(biāo)之一就是要建立一個(gè)環(huán)境使其他 研究者能夠很快進(jìn)入這個(gè)領(lǐng)域，處理海量Web數(shù)據(jù)，得到滿意的結(jié)果，而通過其它方法卻很難得到結(jié)果。系統(tǒng)在短時(shí)間內(nèi)被建立起來，已經(jīng)有幾篇論文用到了 Google建的數(shù)據(jù)庫，更多的在起步中。我們的另一個(gè)目標(biāo)是建立一個(gè)宇宙空間實(shí)驗(yàn)室似的環(huán)境，在這里研究者甚至學(xué)生都可以對(duì)我們的海量Web數(shù)據(jù)設(shè)計(jì)或 做一些實(shí)驗(yàn)。
2. 系統(tǒng)特點(diǎn)
Google搜索引擎有兩個(gè)重要特點(diǎn)，有助于得到高精度的搜索結(jié)果。
第一點(diǎn)，應(yīng)用Web的鏈接結(jié)構(gòu)計(jì)算每個(gè)網(wǎng)頁的Rank值，稱為PageRank，將在98頁詳細(xì)描述它。
第二點(diǎn)，Google利用超鏈接改進(jìn)搜索結(jié)果。
2.1 PageRank:給網(wǎng)頁排序 Web的引用(鏈接)圖是重要的資源，卻被當(dāng)今的搜索引擎很大程度上忽視了。我們建立了一個(gè)包含518‘000'000個(gè)超鏈接的圖，它是一個(gè)具有重要意 義的樣本。這些圖能夠快速地計(jì)算網(wǎng)頁的PageRank值，它是一個(gè)客觀的標(biāo)準(zhǔn)，較好的符合人們心目中對(duì)一個(gè)網(wǎng)頁重要程度的評(píng)價(jià)，建立的基礎(chǔ)是通過引用判 斷重要性。因此在web中，PageRank能夠優(yōu)化關(guān)鍵詞查詢的結(jié)果。對(duì)于大多數(shù)的主題，在網(wǎng)頁標(biāo)題查詢中用PageRank優(yōu)化簡單文本匹配，我們得 到了令人驚嘆的結(jié)果(從google.stanford.edu可以得到演示)。對(duì)于Google主系統(tǒng)中的全文搜索，PageRank也幫了不少忙。
2.1.1計(jì)算PageRank 文獻(xiàn)檢索中的引用理論用到Web中，引用網(wǎng)頁的鏈接數(shù)，一定程度上反映了該網(wǎng)頁的重要性和質(zhì)量。PageRank發(fā)展了這種思想，網(wǎng)頁間的鏈接是不平等 的。 PageRank定義如下:我們假設(shè)T1…Tn指向網(wǎng)頁A(例如，被引用)。參數(shù)d是制動(dòng)因子，使結(jié)果在0，1之間。通常d等于0.85。在下一節(jié)將詳細(xì) 介紹d。C(A)定義為網(wǎng)頁A指向其它網(wǎng)頁的鏈接數(shù)，網(wǎng)頁A的PageRank值由下式給出： PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) 注意PageRank的形式，分布到各個(gè)網(wǎng)頁中，因此所有網(wǎng)頁的PageRank和是1。 PageRank或PR(A)可以用簡單的迭代算法計(jì)算，相應(yīng)規(guī)格化Web鏈接矩陣的主特征向量。中等規(guī)模的網(wǎng)站計(jì)算26‘000'000網(wǎng)頁的 PageRank值要花費(fèi)幾小時(shí)。還有一些技術(shù)細(xì)節(jié)超出了本文論述的范圍。
2.1.2直覺判斷 PageRank被看作用戶行為的模型。我們假設(shè)網(wǎng)上沖浪是隨機(jī)的，不斷點(diǎn)擊鏈接，從不返回，最終煩了，另外隨機(jī)選一個(gè)網(wǎng)頁重新開始沖浪。隨機(jī)訪問一個(gè)網(wǎng) 頁的可能性就是它的PageRank值。制動(dòng)因子d是隨機(jī)訪問一個(gè)網(wǎng)頁煩了的可能性，隨機(jī)另選一個(gè)網(wǎng)頁。對(duì)單個(gè)網(wǎng)頁或一組網(wǎng)頁，一個(gè)重要的變量加入到制動(dòng) 因子d中。這允許個(gè)人可以故意地誤導(dǎo)系統(tǒng)，以得到較高的PageRank值。我們還有其它的PageRank算法，見98頁。 另外的直覺判斷是一個(gè)網(wǎng)頁有很多網(wǎng)頁指向它，或者一些PageRank值高的網(wǎng)頁指向它，則這個(gè)網(wǎng)頁很重要。直覺地，在Web中，一個(gè)網(wǎng)頁被很多網(wǎng)頁引 用，那么這個(gè)網(wǎng)頁值得一看。一個(gè)網(wǎng)頁被象Yahoo這樣重要的主頁引用即使一次，也值得一看。如果一個(gè)網(wǎng)頁的質(zhì)量不高，或者是死鏈接，象Yahoo這樣的 主頁不會(huì)鏈向它。PageRank處理了這兩方面因素，并通過網(wǎng)絡(luò)鏈接遞歸地傳遞。
2.2鏈接描述文字(Anchor Text)
我們的搜索引擎對(duì)鏈接文本進(jìn)行了特殊的處理。大多數(shù)搜索引擎把鏈接文字和它所鏈向的網(wǎng)頁(the page that the link is on)聯(lián)系起來。另外，把它和鏈接所指向的網(wǎng)頁聯(lián)系起來。這有幾點(diǎn)好處。
第一，通常鏈接描述文字比網(wǎng)頁本身更精確地描述該網(wǎng)頁。
第二，鏈接描述文字可能鏈向的文檔不能被文本搜索引擎檢索到，例如圖像，程序和數(shù)據(jù)庫。有可能使返回的網(wǎng)頁不能被抓到。注意哪些抓不到的網(wǎng)頁將會(huì)帶來一些 問題。在返回給用戶前檢測(cè)不了它們的有效性。這種情況搜索引擎可能返回一個(gè)根本不存在的網(wǎng)頁，但是有超級(jí)鏈接指向它。然而這種結(jié)果可以被挑出來的，所以此 類的問題很少發(fā)生。鏈接描述文字是對(duì)被鏈向網(wǎng)頁的宣傳，這個(gè)思想被用在World Wide Web Worm 中，主要因?yàn)樗兄谒阉鞣俏谋拘畔ⅲ軌蛴蒙倭康囊严螺d文檔擴(kuò)大搜索范圍。我們大量應(yīng)用鏈接描述文字，因?yàn)樗兄谔岣咚阉鹘Y(jié)果的質(zhì)量。有效地利用鏈接 描述文字技術(shù)上存在一些困難，因?yàn)楸仨毺幚泶罅康臄?shù)據(jù)。現(xiàn)在我們能抓到24‘000'000個(gè)網(wǎng)頁，已經(jīng)檢索到259‘000'000多個(gè)鏈接描述文字。
2.3其它特點(diǎn)除了PageRank和應(yīng)用鏈接描述文字外，Google還有一些其它特點(diǎn)。
第一,所有hit都有位置信息，所以它可以在搜索中廣泛應(yīng)用鄰近性(proximity)。
第二，Google跟蹤一些可視化外表細(xì)節(jié)，例如字號(hào)。黑體大號(hào)字比其它文字更重要。
第三，知識(shí)庫存儲(chǔ)了原始的全文html網(wǎng)頁。
3有關(guān)工作 Web檢索研究的歷史簡短。
World Wide Web Worm()是最早的搜索引擎之一。后來出現(xiàn)了一些用于學(xué)術(shù)研究的搜索引擎，現(xiàn)在它們中的大多數(shù)被上市公司擁有。與Web的增長和搜索引擎的重要性相比， 有關(guān)當(dāng)今搜索引擎技術(shù)的優(yōu)秀論文相當(dāng)少。根據(jù)Michael Mauldin(Lycos Inc的首席科學(xué)家)) ，“各種各樣的服務(wù)(包括Lycos)非常關(guān)注這些數(shù)據(jù)庫的細(xì)節(jié)。”雖然在搜索引擎的某些特點(diǎn)上做了大量工作。具有代表性的工作有，對(duì)現(xiàn)有商業(yè)搜索引擎的 結(jié)果進(jìn)行傳遞，或建立小型的個(gè)性化的搜索引擎。最后有關(guān)信息檢索系統(tǒng)的研究很多，尤其在有組織機(jī)構(gòu)集合(well controlled collections)方面。在下面兩節(jié)，我們將討論在信息檢索系統(tǒng)中的哪些領(lǐng)域需要改進(jìn)以便更好的工作在Web上。
3.1信息檢索信息檢索系統(tǒng)誕生在幾年前，并發(fā)展迅速。然而大多數(shù)信息檢索系統(tǒng)研究的對(duì)象是小規(guī)模的單一的有組織結(jié)構(gòu)的集合，例如科學(xué)論文集，或相 關(guān)主題的新聞故事。實(shí)際上，信息檢索的主要基準(zhǔn)，the Text Retrieval Conference()，用小規(guī)模的、有組織結(jié)構(gòu)的集合作為它們的基準(zhǔn)。大型文集基準(zhǔn)只有20GB，相比之下，我們抓到的24000000個(gè)網(wǎng)頁占 147GB。在TREC上工作良好的系統(tǒng)，在Web上卻不一定產(chǎn)生好的結(jié)果。例如，標(biāo)準(zhǔn)向量空間模型企圖返回和查詢請(qǐng)求最相近的文檔，把查詢請(qǐng)求和文檔都 看作由出現(xiàn)在它們中的詞匯組成的向量。在Web環(huán)境下，這種策略常常返回非常短的文檔，這些文檔往往是查詢?cè)~再加幾個(gè)字。例如，查詢“Bill Clinton”，返回的網(wǎng)頁只包含“Bill Clinton Sucks”，這是我們從一個(gè)主要搜索引擎中看到的。網(wǎng)絡(luò)上有些爭議，用戶應(yīng)該更準(zhǔn)確地表達(dá)他們想查詢什么，在他們的查詢請(qǐng)求中用更多的詞。我們強(qiáng)烈反對(duì) 這種觀點(diǎn)。如果用戶提出象“Bill Clinton”這樣的查詢請(qǐng)求，應(yīng)該得到理想的查詢結(jié)果，因?yàn)檫@個(gè)主題有許多高質(zhì)量的信息。象所給的例子，我們認(rèn)為信息檢索標(biāo)準(zhǔn)需要發(fā)展，以便有效地處 理Web數(shù)據(jù)。
3.2有組織結(jié)構(gòu)的集合(Well Controlled Collections)與Web的不同點(diǎn) Web是完全無組織的異構(gòu)的大量文檔的集合。Web中的文檔無論內(nèi)在信息還是隱含信息都存在大量的異構(gòu)性。例如，文檔內(nèi)部就用了不同的語言(既有人類語言 又有程序)，詞匯(email地址，鏈接，郵政編碼，電話號(hào)碼，產(chǎn)品號(hào))，類型(文本，HTML，PDF，圖像，聲音)，有些甚至是機(jī)器創(chuàng)建的文件 (log文件，或數(shù)據(jù)庫的輸出)。可以從文檔中推斷出來，但并不包含在文檔中的信息稱為隱含信息。隱含信息包括來源的信譽(yù)，更新頻率，質(zhì)量，訪問量和引 用。不但隱含信息的可能來源各種各樣，而且被檢測(cè)的信息也大不相同，相差可達(dá)好幾個(gè)數(shù)量級(jí)。例如，一個(gè)重要主頁的使用量，象Yahoo 每天瀏覽數(shù)達(dá)到上百萬次，于此相比無名的歷史文章可能十年才被訪問一次。很明顯，搜索引擎對(duì)這兩類信息的處理是不同的。 Web與有組織結(jié)構(gòu)集合之間的另外一個(gè)明顯區(qū)別是，事實(shí)上，向Web上傳信息沒有任何限制。靈活利用這點(diǎn)可以發(fā)布任何對(duì)搜索引擎影響重大的信息，使路由阻 塞，加上為牟利故意操縱搜索引擎，這些已經(jīng)成為一個(gè)嚴(yán)重的問題。這些問題還沒有被傳統(tǒng)的封閉的信息檢索系統(tǒng)所提出來。它關(guān)心的是元數(shù)據(jù)的努力，這在Web 搜索引擎中卻不適用，因?yàn)榫W(wǎng)頁中的任何文本都不會(huì)向用戶聲稱企圖操縱搜索引擎。甚至有些公司為牟利專門操縱搜索引擎。
4 系統(tǒng)分析(System Anatomy)
首先，我們提供高水平的有關(guān)體系結(jié)構(gòu)的討論。然后，詳細(xì)描述重要的數(shù)據(jù)結(jié)構(gòu)。最后，主要應(yīng)用：抓網(wǎng)頁，索引，搜索將被嚴(yán)格地檢查。
4.1Google體系結(jié)構(gòu)概述
這一節(jié)，我們將看看整個(gè)系統(tǒng)是如何工作的(give a high level)，見圖1。本節(jié)不討論應(yīng)用和數(shù)據(jù)結(jié)構(gòu)，在后幾節(jié)中討論。為了效率大部分Google是用c或c++實(shí)現(xiàn)的，既可以在Solaris也可以在 Linux上運(yùn)行。 Google系統(tǒng)中，抓網(wǎng)頁(下載網(wǎng)頁)是由幾個(gè)分布式crawlers完成的。一個(gè)URL服務(wù)器負(fù)責(zé)向crawlers提供URL列表。抓來的網(wǎng)頁交給 存儲(chǔ)服務(wù)器storeserver。然后，由存儲(chǔ)服務(wù)器壓縮網(wǎng)頁并把它們存到知識(shí)庫repository中。每個(gè)網(wǎng)頁都有一個(gè)ID，稱作docID，當(dāng)新 URL從網(wǎng)頁中分析出時(shí)，就被分配一個(gè)docID。由索引器和排序器負(fù)責(zé)建立索引index function。索引器從知識(shí)庫中讀取文檔，對(duì)其解壓縮和分析。每個(gè)文檔被轉(zhuǎn)換成一組詞的出現(xiàn)情況，稱作命中hits。Hits紀(jì)錄了詞，詞在文檔中的 位置，最接近的字號(hào)，大小寫。索引器把這些hits分配到一組桶barrel中，產(chǎn)生經(jīng)過部分排序后的索引。索引器的另一個(gè)重要功能是分析網(wǎng)頁中所有的鏈 接，將有關(guān)的重要信息存在鏈接描述anchors文件中。該文件包含了足夠的信息，可以用來判斷每個(gè)鏈接鏈出鏈入節(jié)點(diǎn)的信息，和鏈接文本。 URL分解器resolver閱讀鏈接描述anchors文件，并把相對(duì)URL轉(zhuǎn)換成絕對(duì)URL，再轉(zhuǎn)換成docID。為鏈接描述文本編制索引，并與它所 指向的docID關(guān)聯(lián)起來。同時(shí)建立由docID對(duì)組成的鏈接數(shù)據(jù)庫。用于計(jì)算所有文檔的PageRank值。用docID分類后的barrels，送給 排序器sorter，再根據(jù)wordID進(jìn)行分類，建立反向索引inverted index。這個(gè)操作要恰到好處，以便幾乎不需要暫存空間。排序器還給出docID和偏移量列表，建立反向索引。一個(gè)叫DumpLexicon的程序把這 個(gè)列表和由索引器產(chǎn)生的字典結(jié)合在一起，建立一個(gè)新的字典，供搜索器使用。這個(gè)搜索器就是利用一個(gè)Web服務(wù)器，使用由DumpLexicon所生成的字 典，利用上述反向索引以及頁面等級(jí)PageRank來回答用戶的提問。
4.2主要數(shù)據(jù)結(jié)構(gòu)經(jīng)過優(yōu)化的Google數(shù)據(jù)結(jié)構(gòu)，能夠用較小的代價(jià)抓取大量文檔，建立索引和查詢。
雖然近幾年CPU和輸入輸出速率迅速提高。磁盤尋道仍然需要10ms。任何時(shí)候Google系統(tǒng)的設(shè)計(jì)都盡可能地避免磁盤尋道。這對(duì)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)影響很大。
4.2.1
大文件大文件BigFiles是指虛擬文件生成的多文件系統(tǒng)，用長度是64位的整型數(shù)據(jù)尋址。多文件系統(tǒng)之間的空間分配是自動(dòng)完成的。BigFiles包也處理已分配和未分配文件描述符。由于操縱系統(tǒng)不能滿足我們的需要，BigFiles也支持基本的壓縮選項(xiàng)。
4.2.2知識(shí)庫 知識(shí)庫包含每個(gè)網(wǎng)頁的全部HTML。每個(gè)網(wǎng)頁用zlib(見RFC1950)壓縮。壓縮技術(shù)的選擇既要考慮速度又要考慮壓縮率。我們選擇zlib的速度而 不是壓縮率很高的bzip。知識(shí)庫用bzip的壓縮率接近4：1。而用zlib的壓縮率是3：1。文檔一個(gè)挨著一個(gè)的存儲(chǔ)在知識(shí)庫中，前綴是docID， 長度，URL，見圖2。訪問知識(shí)庫不需要其它的數(shù)據(jù)結(jié)構(gòu)。這有助于數(shù)據(jù)一致性和升級(jí)。用其它數(shù)據(jù)結(jié)構(gòu)重構(gòu)系統(tǒng)，我們只需要修改知識(shí)庫和crawler錯(cuò)誤 列表文件。
4.2.3文件索引
文件索引保存了有關(guān)文檔的一些信息。索引以docID的順序排列，定寬ISAM(Index sequential access mode)。每條記錄包括當(dāng)前文件狀態(tài)，一個(gè)指向知識(shí)庫的指針，文件校驗(yàn)和，各種統(tǒng)計(jì)表。如果一個(gè)文檔已經(jīng)被抓到，指針指向docinfo文件，該文件的 寬度可變，包含了URL和標(biāo)題。否則指針指向包含這個(gè)URL的URL列表。這種設(shè)計(jì)考慮到簡潔的數(shù)據(jù)結(jié)構(gòu)，以及在查詢中只需要一個(gè)磁盤尋道時(shí)間就能夠訪問 一條記錄。還有一個(gè)文件用于把URL轉(zhuǎn)換成docID。它是URL校驗(yàn)和與相應(yīng)docID的列表，按校驗(yàn)和排序。要想知道某個(gè)URL的docID，需要計(jì) 算URL的校驗(yàn)和，然后在校驗(yàn)和文件中執(zhí)行二進(jìn)制查找，找到它的docID。通過對(duì)這個(gè)文件進(jìn)行合并，可以把一批URL轉(zhuǎn)換成對(duì)應(yīng)的docID。URL分 析器用這項(xiàng)技術(shù)把URL轉(zhuǎn)換成docID。這種成批更新的模式是至關(guān)重要的，否則每個(gè)鏈接都需要一次查詢，假如用一塊磁盤，322‘000'000個(gè)鏈接 的數(shù)據(jù)集合將花費(fèi)一個(gè)多月的時(shí)間。
4.2.4詞典
詞典有幾種不同的形式。和以前系統(tǒng)的重要不同是，詞典對(duì)內(nèi)存的要求可以在合理的價(jià)格內(nèi)。現(xiàn)在實(shí)現(xiàn)的系統(tǒng)，一臺(tái)256M內(nèi)存的機(jī)器就可以把詞典裝入到內(nèi)存 中。現(xiàn)在的詞典包含14000000詞匯(雖然一些很少用的詞匯沒有加入到詞典中)。它執(zhí)行分兩部分—詞匯表(用null分隔的連續(xù)串)和指針的哈希表。 不同的函數(shù)，詞匯表有一些輔助信息，這超出了本文論述的范圍。
4.2.5 hit list
hit list是一篇文檔中所出現(xiàn)的詞的列表，包括位置，字號(hào)，大小寫。Hit list占很大空間，用在正向和反向索引中。因此，它的表示形式越有效越好。我們考慮了幾種方案來編碼位置，字號(hào)，大小寫—簡單編碼(3個(gè)整型數(shù))，緊湊 編碼(支持優(yōu)化分配比特位)，哈夫曼編碼。Hit的詳細(xì)信息見圖3。我們的緊湊編碼每個(gè)hit用2字節(jié)。有兩種類型hit，特殊hit和普通hit。特殊 hit包含URL，標(biāo)題，鏈接描述文字，meta tag。普通hit包含其它每件事。它包括大小寫特征位，字號(hào)，12比特用于描述詞在文檔中的位置(所有超過4095的位置標(biāo)記為4096)。字號(hào)采用相 對(duì)于文檔的其它部分的相對(duì)大小表示，占3比特(實(shí)際只用7個(gè)值，因?yàn)?11標(biāo)志是特殊hit)。特殊hit由大小寫特征位，字號(hào)位為7表示它是特殊 hit，用4比特表示特殊hit的類型，8比特表示位置。對(duì)于anchor hit八比特位置位分出4比特用來表示在anchor中的位置，4比特用于表明anchor出現(xiàn)的哈希表hash of the docID。短語查詢是有限的，對(duì)某些詞沒有足夠多的anchor。我們希望更新anchor hit的存儲(chǔ)方式，以便解決地址位和docIDhash域位數(shù)不足的問題。
因?yàn)樗阉鲿r(shí)，你不會(huì)因?yàn)槲臋n的字號(hào)比別的文檔大而特殊對(duì)待它，所以采用相對(duì)字號(hào)。 hit表的長度存儲(chǔ)在hit前。為節(jié)省空間hit表長度，在正向索引中和wordID結(jié)合在一起，在反向索引中和docID結(jié)合存儲(chǔ)。這就限制它相應(yīng)地只 占8到5比特(用些技巧，可以從wordID中借8bit)如果大于這些比特所能表示的長度，用溢出碼填充，其后兩字節(jié)是真正的長度。
4.2.6正向索引實(shí)際上，正向索引已經(jīng)部分排序。它被存在一定數(shù)量的barrel中(我們用64個(gè)barrels)。每個(gè)barrel裝著一定范 圍的wordID。如果一篇文檔中的詞落到某個(gè)barrel，它的docID將被記錄到這個(gè)barrel中，緊跟著那些詞(文檔中所有的詞匯，還是落入該 barrel中的詞匯)對(duì)應(yīng)的hitlist。這種模式需要稍多些的存儲(chǔ)空間，因?yàn)橐粋€(gè)docID被用多次，但是它節(jié)省了桶數(shù)和時(shí)間，最后排序器進(jìn)行索引 時(shí)降低編碼的復(fù)雜度。更進(jìn)一步的措施是，我們不是存儲(chǔ)docID本身，而是存儲(chǔ)相對(duì)于該桶最小的docID的差。用這種方法，未排序的barrel的 docID只需24位，省下8位記錄hitlist長。
4.2.7反向索引除了反向索引由sorter加工處理之外，它和正向索引包含相同的桶。對(duì)每個(gè)有效的docID，字典包含一個(gè)指向該詞所在桶的指 針。它指向由docID和它的相應(yīng)hitlist組成的doclish，這個(gè)doclist代表了所有包含該詞的文檔。 doclist中docID的順序是一個(gè)重要的問題。最簡單的解決辦法是用doclish排序。這種方法合并多個(gè)詞時(shí)很快。另一個(gè)可選方案是用文檔中該詞 出現(xiàn)的次數(shù)排序。這種方法回答單詞查詢，所用時(shí)間微不足道。當(dāng)多詞查詢時(shí)幾乎是從頭開始。并且當(dāng)用其它Rank算法改進(jìn)索引時(shí)，非常困難。我們綜合了這兩 種方法，建立兩組反向索引barrel，一組barrels的hitlist只包含標(biāo)題和anchor hit，另一組barrel包含全部的hitlist。我們首先查第一組索引桶，看有沒有匹配的項(xiàng)，然后查較大的那組桶。
4.3抓網(wǎng)頁
運(yùn)行網(wǎng)絡(luò)爬行機(jī)器人是一項(xiàng)具有挑戰(zhàn)性的任務(wù)。執(zhí)行的性能和可靠性甚至更重要，還有一些社會(huì)焦點(diǎn)。網(wǎng)絡(luò)爬行是一項(xiàng)非常薄弱的應(yīng)用，它需要成百上千的web服 務(wù)器和各種域名服務(wù)器的參與，這些服務(wù)器不是我們系統(tǒng)所能控制的。為了覆蓋幾十億的網(wǎng)頁，Google擁有快速的分布式網(wǎng)絡(luò)爬行系統(tǒng)。一個(gè)URL服務(wù)器給 若干個(gè)網(wǎng)絡(luò)爬行機(jī)器人(我們采用3個(gè))提供URL列表。URL服務(wù)器和網(wǎng)絡(luò)爬行機(jī)器人都是用Python實(shí)現(xiàn)的。每個(gè)網(wǎng)絡(luò)爬行機(jī)器人可以同時(shí)打開300個(gè) 鏈接。抓取網(wǎng)頁必須足夠快。最快時(shí)，用4個(gè)網(wǎng)絡(luò)爬行機(jī)器人每秒可以爬行100個(gè)網(wǎng)頁。速率達(dá)每秒600K。執(zhí)行的重點(diǎn)是找DNS。每個(gè)網(wǎng)絡(luò)爬行機(jī)器人有它 自己的DNS cache，所以它不必每個(gè)網(wǎng)頁都查DNS。每一百個(gè)連接都有幾種不同的狀態(tài)：查DNS，連接主機(jī)，發(fā)送請(qǐng)求，接收回答。這些因素使網(wǎng)絡(luò)爬行機(jī)器人成為系 統(tǒng)比較復(fù)雜的部分。它用異步IO處理事件，若干請(qǐng)求隊(duì)列從一個(gè)網(wǎng)站到另一個(gè)網(wǎng)站不停的抓取網(wǎng)頁。運(yùn)行一個(gè)鏈接到500多萬臺(tái)服務(wù)器的網(wǎng)頁爬行機(jī)器人，產(chǎn)生 1千多萬登陸口，導(dǎo)致了大量的Email和電話。因?yàn)榫W(wǎng)民眾多，總有些人不知道網(wǎng)絡(luò)爬行機(jī)器人是何物，這是他們看到的第一個(gè)網(wǎng)絡(luò)爬行機(jī)器人。幾乎每天我們 都會(huì)收到這樣的Email“哦，你從我們的網(wǎng)站看了太多的網(wǎng)頁，你想干什么?”還有一些人不知道網(wǎng)絡(luò)搜索機(jī)器人避免協(xié)議(the robots exclusion protocol)，以為他們的網(wǎng)頁上寫著“版權(quán)所有，勿被索引”的字樣就會(huì)被保護(hù)不被索引，不必說，這樣的話很難被web crawler理解。因?yàn)閿?shù)據(jù)量如此之大，還會(huì)遇到一些意想不到的事情。例如，我們的系統(tǒng)曾經(jīng)企圖抓一個(gè)在線游戲，結(jié)果抓到了游戲中的大量垃圾信息。解決 這個(gè)問題很簡單。但是我們下載了幾千萬網(wǎng)頁后才發(fā)現(xiàn)了這個(gè)問題。因?yàn)榫W(wǎng)頁和服務(wù)器的種類繁多，實(shí)際上不在大部分Internet上運(yùn)行它就測(cè)試一個(gè)網(wǎng)頁爬 行機(jī)器人是不可能。總是有幾百個(gè)隱含的問題發(fā)生在整個(gè)web的一個(gè)網(wǎng)頁上，導(dǎo)致網(wǎng)絡(luò)爬行機(jī)器人崩潰，或者更糟，導(dǎo)致不可預(yù)測(cè)的不正確的行為。能夠訪問大部 分Internet的系統(tǒng)必須精力充沛并精心測(cè)試過。由于象crawler這樣大型復(fù)雜的系統(tǒng)總是產(chǎn)生這樣那樣的問題，因此花費(fèi)一些資源讀這些 Email，當(dāng)問題發(fā)生時(shí)解決它，是有必要的。
4.4Web索引分析
任何運(yùn)行在整個(gè)Web上的分析器必須能夠處理可能包含錯(cuò)誤的大型集合。范圍從HTML標(biāo)記到標(biāo)記之間幾K字節(jié)的0，非ASCII字符，幾百層HTML標(biāo)記 的嵌套，各種各樣令人難以想象的錯(cuò)誤。為了獲得最大的速度，我們沒有采用YACC產(chǎn)生上下文無關(guān)文法CFG分析器，而是采用靈活的方式產(chǎn)生詞匯分析器，它 自己配有堆棧。分析器的改進(jìn)大大提高了運(yùn)行速度，它的精力如此充沛完成了大量工作。把文檔裝入barrel建立索引—分析完一篇文檔，之后把該文檔裝入 barrel中，用內(nèi)存中的hash表—字典，每個(gè)詞匯被轉(zhuǎn)換成一個(gè)wordID。當(dāng)hash表字典中加入新的項(xiàng)時(shí)，笨拙地存入文件。一旦詞匯被轉(zhuǎn)換成 wordID，它們?cè)诋?dāng)前文檔的出現(xiàn)就轉(zhuǎn)換成hitlist，被寫進(jìn)正向barrel。索引階段并行的主要困難是字典需要共享。
我們采用的方法是，基本字典中有140萬個(gè)固定詞匯，不在基本字典中的詞匯寫入日志，而不是共享字典。這種方法多個(gè)索引器可以并行工作，最后一個(gè)索引器只 需處理一個(gè)較小的額外詞匯日志。排序—為了建立反向索引，排序器讀取每個(gè)正向barrel，以wordID排序，建立只有標(biāo)題anchor hi t的反向索引barrel和全文反向索引barrel。這個(gè)過程一次只處理一個(gè)barrel，所以只需要少量暫存空間。排序階段也是并行的，我們簡單地同 時(shí)運(yùn)行盡可能多的排序器，不同的排序器處理不同的桶。由于barrel不適合裝入主存，排序器進(jìn)一步依據(jù)wordID和docID把它分成若干籃子，以便 適合裝入主存。然后排序器把每個(gè)籃子裝入主存進(jìn)行排序，并把它的內(nèi)容寫回到短反向barrel和全文反向barrel。
4.5搜索搜索的目標(biāo)是提供有效的高質(zhì)量的搜索結(jié)果。多數(shù)大型商業(yè)搜索引擎好像在效率方面花費(fèi)了很大力氣。因此我們的研究以搜索質(zhì)量為重點(diǎn)，相信我們的解決方案也可以用到那些商業(yè)系統(tǒng)中。
Google查詢?cè)u(píng)價(jià)過程見圖4。
1. 分析查詢。
2. 把詞匯轉(zhuǎn)換成wordID。
3. 在短barrel中查找每個(gè)詞匯doclist的開頭。
4. 掃描doclist直到找到一篇匹配所有關(guān)鍵詞的文檔
5. 計(jì)算該文檔的rank
6. 如果我們?cè)诙蘠arrel，并且在所有doclist的末尾，開始從全文barrel的doclist的開頭查找每個(gè)詞，goto 第四步
7. 如果不在任何doclist的結(jié)尾，返回第四步。
8. 根據(jù)rank排序匹配文檔，返回前k個(gè)。圖4 Google查詢?cè)u(píng)價(jià)在有限的響應(yīng)時(shí)間內(nèi)，一旦找到一定數(shù)量的匹配文檔，搜索引擎自動(dòng)執(zhí)行步驟8。這意味著，返回的結(jié)果是子優(yōu)化的。我們現(xiàn)在研究其它方法 來解決這個(gè)問題。過去根據(jù)PageRank排序hit，看來能夠改進(jìn)這種狀況。
4.5.1 Ranking系統(tǒng) Google比典型搜索引擎保存了更多的web信息。每個(gè)hitlish包括位置，字號(hào)，大小寫。另外，我們還考慮了鏈接描述文字。Rank綜合所有這些 信息是困難的。ranking函數(shù)設(shè)計(jì)依據(jù)是沒有某個(gè)因素對(duì)rank影響重大。首先，考慮最簡單的情況—單個(gè)詞查詢。為了單個(gè)詞查詢中一個(gè)文檔的 rank，Goole在文檔的hitlist中查找該詞。Google認(rèn)為每個(gè)hit是幾種不同類型(標(biāo)題，鏈接描述文字anchor，URL，普通大字 號(hào)文本，普通小字號(hào)文本，……)之一，每種有它自己的類型權(quán)重。類型權(quán)重建立了一個(gè)類型索引向量。Google計(jì)算hitlist中每種hit的數(shù)量。然 后每個(gè)hit數(shù)轉(zhuǎn)換成count-weight。Count-weight開始隨hit數(shù)線性增加，很快逐漸停止，以至于hit數(shù)與此不相關(guān)。我們計(jì)算 count-weight向量和type-weight向量的標(biāo)量積作為文檔的IR值。最后IR值結(jié)合PageRank作為文檔的最后rank 對(duì)于多詞查詢，更復(fù)雜些。現(xiàn)在，多詞hitlist必須同時(shí)掃描，以便關(guān)鍵詞出現(xiàn)在同一文檔中的權(quán)重比分別出現(xiàn)時(shí)高。相鄰詞的hit一起匹配。對(duì)每個(gè)匹配 hit 的集合計(jì)算相鄰度。相鄰度基于hit在文檔中的距離，分成10個(gè)不同的bin值，范圍從短語匹配到根本不相關(guān)。不僅計(jì)算每類hit數(shù)，而且要計(jì)算每種類型 的相鄰度，每個(gè)類型相似度對(duì)，有一個(gè)類型相鄰度權(quán)type-prox-weight。Count轉(zhuǎn)換成count-weight，計(jì)算count- weight type-proc-weight的標(biāo)量積作為IR值。應(yīng)用某種debug mode所有這些數(shù)和矩陣與查詢結(jié)果一起顯示出來。這些顯示有助于改進(jìn)rank系統(tǒng)。
4.5.2反饋
rank函數(shù)有很多參數(shù)象type-weight和type-prox-weight。指明這些參數(shù)的正確值有點(diǎn)黑色藝術(shù)black art。為此，我們的搜索引擎有一個(gè)用戶反饋機(jī)制。值得信任的用戶可以隨意地評(píng)價(jià)返回的結(jié)果。保存反饋。然后，當(dāng)修改rank函數(shù)時(shí)，對(duì)比以前搜索的 rank，我們可以看到修改帶來的的影響。雖然不是十全十美，但是它給出了一些思路，當(dāng)rank函數(shù)改變時(shí)對(duì)搜索結(jié)果的影響。
5執(zhí)行和結(jié)果搜索結(jié)果的質(zhì)量是搜索引擎最重要的度量標(biāo)準(zhǔn)。完全用戶評(píng)價(jià)體系超出了本文的論述范圍，對(duì)于大多數(shù)搜索，我們的經(jīng)驗(yàn)說明Google的搜索結(jié)果 比那些主要的商業(yè)搜索引擎好。作為一個(gè)應(yīng)用PageRank，鏈接描述文字，相鄰度的例子，圖4給出了Google搜索bill Clinton的結(jié)果。它說明了Google的一些特點(diǎn)。服務(wù)器對(duì)結(jié)果進(jìn)行聚類。這對(duì)過濾結(jié)果集合相當(dāng)有幫助。這個(gè)查詢，相當(dāng)一部分結(jié)果來自 whitehouse.gov域，這正是我們所需要的。現(xiàn)在大多數(shù)商業(yè)搜索引擎不會(huì)返回任何來自whitehouse.gov的結(jié)果，這是相當(dāng)不對(duì)的。注 意第一個(gè)搜索結(jié)果沒有標(biāo)題。因?yàn)樗皇潜蛔サ降摹oogle是根據(jù)鏈接描述文字決定它是一個(gè)好的查詢結(jié)果。同樣地，第五個(gè)結(jié)果是一個(gè)Email地址，當(dāng) 然是不可能抓到的。也是鏈接描述文字的結(jié)果。所有這些結(jié)果質(zhì)量都很高，最后檢查沒有死鏈接。因?yàn)樗鼈冎械拇蟛糠諴ageRank值較高。PageRank 百分比用紅色線條表示。沒有結(jié)果只含Bill沒有Clinton或只含Clinton沒有Bill。因?yàn)樵~出現(xiàn)的相近性非常重要。當(dāng)然搜索引擎質(zhì)量的真實(shí) 測(cè)試包含廣泛的用戶學(xué)習(xí)或結(jié)果分析，此處篇幅有限，請(qǐng)讀者自己去體驗(yàn)Google，http://google.stanford.edu/。
5.1
存儲(chǔ)需求除了搜索質(zhì)量，Google的設(shè)計(jì)可以隨著Web規(guī)模的增大而有效地增大成本。一方面有效地利用存儲(chǔ)空間。表1列出了一些統(tǒng)計(jì)數(shù)字的明細(xì)表和 Google存儲(chǔ)的需求。由于壓縮技術(shù)的應(yīng)用知識(shí)庫只需53GB的存儲(chǔ)空間。是所有要存儲(chǔ)數(shù)據(jù)的三分之一。按當(dāng)今磁盤價(jià)格，知識(shí)庫相對(duì)于有用的數(shù)據(jù)來說比 較便宜。搜索引擎需要的所有數(shù)據(jù)的存儲(chǔ)空間大約55GB。大多數(shù)查詢請(qǐng)求只需要短反向索引。文件索引應(yīng)用先進(jìn)的編碼和壓縮技術(shù)，一個(gè)高質(zhì)量的搜索引擎可以 運(yùn)行在7GB的新PC。
5.2系統(tǒng)執(zhí)行搜索引擎抓網(wǎng)頁和建立索引的效率非常重要。Google的主要操作是抓網(wǎng)頁，索引，排序。很難測(cè)試抓全部網(wǎng)頁需要多少時(shí)間，因?yàn)榇疟P 滿了，域名服務(wù)器崩潰，或者其它問題導(dǎo)致系統(tǒng)停止。總的來說，大約需要9天時(shí)間下載26000000網(wǎng)頁(包括錯(cuò)誤)。然而，一旦系統(tǒng)運(yùn)行順利，速度非常 快，下載最后11000000網(wǎng)頁只需要63小時(shí)，平均每天4000000網(wǎng)頁，每秒48.5個(gè)網(wǎng)頁。索引器和網(wǎng)絡(luò)爬行機(jī)器人同步運(yùn)行。索引器比網(wǎng)絡(luò)爬行 機(jī)器人快。因?yàn)槲覀兓ㄙM(fèi)了大量時(shí)間優(yōu)化索引器，使它不是瓶頸。這些優(yōu)化包括批量更新文檔索引，本地磁盤數(shù)據(jù)結(jié)構(gòu)的安排。索引器每秒處理54個(gè)網(wǎng)頁。排序器 完全并行，用4臺(tái)機(jī)器，排序的整個(gè)過程大概需要24小時(shí)。
5.3搜索執(zhí)行改進(jìn)搜索執(zhí)行不是我們研究的重點(diǎn)。
當(dāng)前版本的Google可以在1到10秒間回答查詢請(qǐng)求。時(shí)間大部分花費(fèi)在NFS磁盤IO上(由于磁盤普遍比機(jī)器慢)。進(jìn)一步說，Google沒有做任何 優(yōu)化，例如查詢緩沖區(qū)，常用詞匯子索引，和其它常用的優(yōu)化技術(shù)。我們傾向于通過分布式，硬件，軟件，和算法的改進(jìn)來提高Google的速度。我們的目標(biāo)是 每秒能處理幾百個(gè)請(qǐng)求。表2有幾個(gè)現(xiàn)在版本Google響應(yīng)查詢時(shí)間的例子。它們說明IO緩沖區(qū)對(duì)再次搜索速度的影響。 6結(jié)論 Google設(shè)計(jì)成可伸縮的搜索引擎。主要目標(biāo)是在快速發(fā)展的World Wide Web上提供高質(zhì)量的搜索結(jié)果。Google應(yīng)用了一些技術(shù)改進(jìn)搜索質(zhì)量包括PageRank，鏈接描述文字，相鄰信息。進(jìn)一步說，Google是一個(gè)收 集網(wǎng)頁，建立索引，執(zhí)行搜索請(qǐng)求的完整的體系結(jié)構(gòu)。
6.1未來的工作大型Web搜索引擎是個(gè)復(fù)雜的系統(tǒng)，還有很多事情要做。
我們直接的目標(biāo)是提高搜索效率，覆蓋大約100000000個(gè)網(wǎng)頁。一些簡單的改進(jìn)提高了效率包括請(qǐng)求緩沖區(qū)，巧妙地分配磁盤空間，子索引。另一個(gè)需要研 究的領(lǐng)域是更新。我們必須有一個(gè)巧妙的算法來決定哪些舊網(wǎng)頁需要重新抓取，哪些新網(wǎng)頁需要被抓取。這個(gè)目標(biāo)已經(jīng)由實(shí)現(xiàn)了。受需求驅(qū)動(dòng)，用代理cache創(chuàng) 建搜索數(shù)據(jù)庫是一個(gè)有前途的研究領(lǐng)域。我們計(jì)劃加一些簡單的已經(jīng)被商業(yè)搜索引擎支持的特征，例如布爾算術(shù)符號(hào)，否定，填充。然而另外一些應(yīng)用剛剛開始探 索，例如相關(guān)反饋，聚類(Google現(xiàn)在支持簡單的基于主機(jī)名的聚類)。我們還計(jì)劃支持用戶上下文(象用戶地址)，結(jié)果摘要。我們正在擴(kuò)大鏈接結(jié)構(gòu)和鏈 接文本的應(yīng)用。簡單的實(shí)驗(yàn)證明，通過增加用戶主頁的權(quán)重或書簽，PageRank可以個(gè)性化。對(duì)于鏈接文本，我們正在試驗(yàn)用鏈接周圍的文本加入到鏈接文 本。Web搜索引擎提供了豐富的研究課題。如此之多以至于我們不能在此一一列舉，因此在不久的將來，我們希望所做的工作不止本節(jié)提到的。
6.2高質(zhì)量搜索當(dāng)今Web搜索引擎用戶所面臨的最大問題是搜索結(jié)果的質(zhì)量。
結(jié)果常常是好笑的，并且超出用戶的眼界，他們常常灰心喪氣浪費(fèi)了寶貴的時(shí)間。例如，一個(gè)最流行的商業(yè)搜索引擎搜索“Bill Clillton”的結(jié)果是the Bill Clinton Joke of the Day: April 14, 1997。Google的 設(shè)計(jì)目標(biāo)是隨著Web的快速發(fā)展提供高質(zhì)量的搜索結(jié)果，容易找到信息。為此，Google大量應(yīng)用超文本信息包括鏈接結(jié)構(gòu)和鏈接文本。Google還用到 了相鄰性和字號(hào)信息。評(píng)價(jià)搜索引擎是困難的，我們主觀地發(fā)現(xiàn)Google的搜索質(zhì)量比當(dāng)今商業(yè)搜索引擎高。通過PageRank分析鏈接結(jié)構(gòu)使 Google能夠評(píng)價(jià)網(wǎng)頁的質(zhì)量。用鏈接文本描述鏈接所指向的網(wǎng)頁有助于搜索引擎返回相關(guān)的結(jié)果(某種程度上提高了質(zhì)量)。最后，利用相鄰性信息大大提高 了很多搜索的相關(guān)性。
6.3可升級(jí)的體系結(jié)構(gòu)除了搜索質(zhì)量，Google設(shè)計(jì)成可升級(jí)的。
空間和時(shí)間必須高效，處理整個(gè)Web時(shí)固定的幾個(gè)因素非常重要。實(shí)現(xiàn)Google系統(tǒng)，CPU、訪存、內(nèi)存容量、磁盤尋道時(shí)間、磁盤吞吐量、磁盤容量、網(wǎng) 絡(luò)IO都是瓶頸。在一些操作中，已經(jīng)改進(jìn)的Google克服了一些瓶頸。Google的主要數(shù)據(jù)結(jié)構(gòu)能夠有效利用存儲(chǔ)空間。進(jìn)一步，網(wǎng)頁爬行，索引，排序 已經(jīng)足夠建立大部分web索引，共24000000個(gè)網(wǎng)頁，用時(shí)不到一星期。我們希望能在一個(gè)月內(nèi)建立100000000網(wǎng)頁的索引。
6.4研究工具
Google不僅是高質(zhì)量的搜索引擎，它還是研究工具。Google搜集的數(shù)據(jù)已經(jīng)用在許多其它論文中，提交給學(xué)術(shù)會(huì)議和許多其它方式。最近的研究，例 如，提出了Web查詢的局限性，不需要網(wǎng)絡(luò)就可以回答。這說明Google不僅是重要的研究工具，而且必不可少，應(yīng)用廣泛。我們希望Google是全世界 研究者的資源，帶動(dòng)搜索引擎技術(shù)的更新?lián)Q代。 7致謝 Scott Hassan and Alan Steremberg評(píng)價(jià)了Google的改進(jìn)。他們的才智無可替代，作者由衷地感謝他們。感謝Hector Garcia-Molina, Rajeev Motwani, Jeff Ullman, and Terry Winograd和全部WebBase開發(fā)組的支持和富有深刻見解的討論。最后感謝IBM，Intel，Sun和投資者的慷慨支持，為我們提供設(shè)備。這里 所描述的研究是Stanford綜合數(shù)字圖書館計(jì)劃的一部分，由國家科學(xué)自然基金支持，合作協(xié)議號(hào)IRI-9411306。DARPA ，NASA，Interva研究，Stanford數(shù)字圖書館計(jì)劃的工業(yè)合作伙伴也為這項(xiàng)合作協(xié)議提供了資金。參考文獻(xiàn) ?
Google的設(shè)計(jì)目標(biāo)是可升級(jí)到10億網(wǎng)頁。我們的磁盤和機(jī)器大概能處理這么多網(wǎng)頁。系統(tǒng)各個(gè)部分耗費(fèi)的總時(shí)間是并行的和線性的。包括網(wǎng)頁爬行機(jī)器人， 索引器和排序器。擴(kuò)展后我們認(rèn)為大多數(shù)數(shù)據(jù)結(jié)構(gòu)運(yùn)行良好。然而10億網(wǎng)頁接近所有常用操作系統(tǒng)的極限(我們目前運(yùn)行在Solaris和Linux上)。包 括主存地址，開放文件描述符的數(shù)量，網(wǎng)絡(luò)socket和帶寬，以及其它因素。我們認(rèn)為當(dāng)網(wǎng)頁數(shù)量大大超過10億網(wǎng)頁時(shí)，會(huì)大大增加系統(tǒng)復(fù)雜性。 9.2集中式索引體系的可升級(jí)性隨著計(jì)算機(jī)性能的提高，海量文本索引的成本比較公平。當(dāng)然帶寬需求高的其它應(yīng)用如視頻，越來越普遍。但是，與多媒體例如視 頻相比，文本產(chǎn)品的成本低，因此文本仍然普遍。
圖2 Google系統(tǒng)的工作流程圖
(注：原圖來自Sergey Brin and Lawrence Page, The Anatomy of a Large-Scale Hypertextual. Web Search Engine, 1998.http://www-db.stanford.edu/%7Ebackrub/Google.html)
①Google使用高速的分布式爬行器(Crawler)系統(tǒng)中的漫游遍歷器(Googlebot)定時(shí)地遍歷網(wǎng)頁，將遍歷到的網(wǎng)頁送到存儲(chǔ)服務(wù)器(Store Server)中。
②存儲(chǔ)服務(wù)器使用zlib格式壓縮軟件將這些網(wǎng)頁進(jìn)行無損壓縮處理后存入數(shù)據(jù)庫Repository中。Repository獲得了每個(gè)網(wǎng)頁的完全 Html代碼后，對(duì)其壓縮后的網(wǎng)頁及URL進(jìn)行分析，記錄下網(wǎng)頁長度、URL、URL長度和網(wǎng)頁內(nèi)容，并賦予每個(gè)網(wǎng)頁一個(gè)文檔號(hào)(docID)，以便當(dāng)系 統(tǒng)出現(xiàn)故障的時(shí)候，可以及時(shí)完整地進(jìn)行網(wǎng)頁的數(shù)據(jù)恢復(fù)。
③索引器(Indexer)從Repository中讀取數(shù)據(jù)，以后做以下四步工作：
④(a)將讀取的數(shù)據(jù)解壓縮后進(jìn)行分析，它將網(wǎng)頁中每個(gè)有意義的詞進(jìn)行統(tǒng)計(jì)后，轉(zhuǎn)化為關(guān)鍵詞(wordID)的若干索引項(xiàng)(Hits)，生成索引項(xiàng)列表， 該列表包括關(guān)鍵詞、關(guān)鍵詞的位置、關(guān)鍵詞的大小和大小寫狀態(tài)等。索引項(xiàng)列表被存入到數(shù)據(jù)桶(Barrels)中，并生成以文檔號(hào)(docID)部分排序的 順排檔索引。
索引項(xiàng)根據(jù)其重要程度分為兩種：當(dāng)索引項(xiàng)中的關(guān)鍵詞出現(xiàn)在URL、標(biāo)題、錨文本(Anchor Text)和標(biāo)簽中時(shí)，表示該索引項(xiàng)比較重要，稱為特殊索引項(xiàng)(Fancy Hits);其余情況則稱為普通索引項(xiàng)(Plain Hits)。在系統(tǒng)中每個(gè)Hit用兩個(gè)字節(jié)(byte)存儲(chǔ)結(jié)構(gòu)表示：特殊索引項(xiàng)用1位(bit)表示大小寫，用二進(jìn)制代碼111(占3位)表示是特殊索 引項(xiàng)，其余12位有4位表示特殊索引項(xiàng)的類型(即hit是出現(xiàn)在URL、標(biāo)題、鏈接結(jié)點(diǎn)還是標(biāo)簽中)，剩下8位表示hit在網(wǎng)頁中的具體位置;普通索引項(xiàng) 是用1位表示大小寫，3位表示字體大小，其余12位表示在網(wǎng)頁中的具體位置。
順排檔索引和Hit的存儲(chǔ)結(jié)構(gòu)如圖3所示。
圖3 順排檔索引和Hit的存儲(chǔ)結(jié)構(gòu)
值得注意的是，當(dāng)特殊索引項(xiàng)來自Anchor Text時(shí)，特殊索引項(xiàng)用來表示位置的信息(8位)將分為兩部分：4位表示Anchor Text出現(xiàn)的具體位置，另4位則用來與表示Anchor Text所鏈接網(wǎng)頁的docID相連接，這個(gè)docID是由URL Resolver經(jīng)過轉(zhuǎn)化存入順排檔索引的。
(b)索引器除了對(duì)網(wǎng)頁中有意義的詞進(jìn)行分析外，還分析網(wǎng)頁的所有超文本鏈接，將其Anchor Text、URL指向等關(guān)鍵信息存入到Anchor文檔庫中。
(c)索引器生成一個(gè)索引詞表(Lexicon)，它包括兩個(gè)部分：關(guān)鍵詞的列表和指針列表，用于倒排檔文檔相連接(如圖3所示)。
(d)索引器還將分析過的網(wǎng)頁編排成一個(gè)與Repository相連接的文檔索引(Document Index)，并記錄下網(wǎng)頁的URL和標(biāo)題，以便可以準(zhǔn)確查找出在Repository中存儲(chǔ)的原網(wǎng)頁內(nèi)容。而且把沒有分析的網(wǎng)頁傳給URL Server，以便在下一次工作流程中進(jìn)行索引分析。
⑤URL分析器(URL Resolver)讀取Anchor文檔中的信息，然后做⑥中的工作。
⑥(a)將其錨文本(Anchor Text)所指向的URL轉(zhuǎn)換成網(wǎng)頁的docID;(b)將該docID與原網(wǎng)頁的docID形成“鏈接對(duì)”，存入Link數(shù)據(jù)庫中;(c)將 Anchor Text指向的網(wǎng)頁的docID與順排檔特殊索引項(xiàng)Anchor Hits相連接。
⑦數(shù)據(jù)庫Link記錄了網(wǎng)頁的鏈接關(guān)系，用來計(jì)算網(wǎng)頁的PageRank值。
⑧文檔索引(Document Index)把沒有進(jìn)行索引分析的網(wǎng)頁傳遞給URL Server，URL Server則向Crawler提供待遍歷的URL，這樣，這些未被索引的網(wǎng)頁在下一次工作流程中將被索引分析。
⑨排序器(Sorter)對(duì)數(shù)據(jù)桶(Barrels)的順排檔索引重新進(jìn)行排序，生成以關(guān)鍵詞(wordID)為索引的倒排檔索引。倒排檔索引結(jié)構(gòu)如圖4所示：
圖4 倒排檔索引結(jié)構(gòu)
⑩將生成的倒排檔索引與先前由索引器產(chǎn)生的索引詞表(Lexicon)相連接產(chǎn)生一個(gè)新的索引詞表供搜索器(Searcher)使用。搜索器的功能是由網(wǎng) 頁服務(wù)器實(shí)現(xiàn)的，根據(jù)新產(chǎn)生的索引詞表結(jié)合上述的文檔索引(Document Index)和Link數(shù)據(jù)庫計(jì)算的網(wǎng)頁P(yáng)ageRank值來匹配檢索。
在執(zhí)行檢索時(shí)，Google通常遵循以下步驟(以下所指的是單個(gè)檢索詞的情況)：
(1)將檢索詞轉(zhuǎn)化成相應(yīng)的wordID;
(2)利用Lexicon，檢索出包含該wordID的網(wǎng)頁的docID;
(3)根據(jù)與Lexicon相連的倒排檔索引，分析各網(wǎng)頁中的相關(guān)索引項(xiàng)的情況，計(jì)算各網(wǎng)頁和檢索詞的匹配程度，必要時(shí)調(diào)用順排檔索引;
(4)根據(jù)各網(wǎng)頁的匹配程度，結(jié)合根據(jù)Link產(chǎn)生的相應(yīng)網(wǎng)頁的PageRank情況，對(duì)檢索結(jié)果進(jìn)行排序;
(5)調(diào)用Document Index中的docID及其相應(yīng)的URL，將排序結(jié)果生成檢索結(jié)果的最終列表，提供給檢索用戶。
用戶檢索包含多個(gè)檢索詞的情況與以上單個(gè)檢索詞的情況類似：先做單個(gè)檢索詞的檢索，然后根據(jù)檢索式中檢索符號(hào)的要求進(jìn)行必要的布爾操作或其他操作。
Google向網(wǎng)站管理員提供的信息
遵循以下指南將有助于 Google 查找、檢索您的網(wǎng)站并對(duì)其進(jìn)行排名，這是確保在 Google 搜索結(jié)果中列出您的網(wǎng)址的最佳途徑。即使您選擇不采納這些建議，我們也強(qiáng)烈建議您密切關(guān)注" 質(zhì)量指南 "，該指南對(duì)可導(dǎo)致網(wǎng)站從 Google 索引中徹底刪除的一些違禁行為做了簡要說明。一旦網(wǎng)站刪除之后，Google.com 或 Google 所有合作伙伴網(wǎng)站的搜索結(jié)果中都不會(huì)再顯示該網(wǎng)站。
網(wǎng)站設(shè)計(jì)與內(nèi)容指南：
網(wǎng)站應(yīng)具有清晰的層次結(jié)構(gòu)和文本鏈接。每個(gè)網(wǎng)頁應(yīng)至少可以通過一個(gè)靜態(tài)文本鏈接打開。
為用戶提供一個(gè)網(wǎng)站地圖，并列出指向網(wǎng)站重要位置的鏈接。如果網(wǎng)站地圖上的鏈接超過大約 100 個(gè)，則最好將網(wǎng)站地圖拆成多個(gè)網(wǎng)頁。
網(wǎng)站應(yīng)具有實(shí)用性且信息豐富，網(wǎng)頁文字應(yīng)清晰、準(zhǔn)確地表述要傳達(dá)的內(nèi)容。
要考慮到用戶會(huì)使用哪些關(guān)鍵詞來查找您的網(wǎng)頁，確保網(wǎng)站上包含了這些文字。
盡量使用文字而不是圖像來顯示重要的名稱、內(nèi)容或鏈接。因?yàn)?Google Crawler 無法識(shí)別圖像中所包含的文字。
確保 TITLE 和 ALT 標(biāo)記文字簡單明了并與網(wǎng)頁內(nèi)容相關(guān)。
檢查鏈接是否損壞，HTML 格式是否正確。
如果采用動(dòng)態(tài)網(wǎng)頁(即網(wǎng)址中包含"?"字符)，請(qǐng)注意并非每一個(gè)搜索引擎 Spider 收錄動(dòng)態(tài)網(wǎng)頁都能像收錄靜態(tài)網(wǎng)頁一樣容易。縮短參數(shù)的長度并減少參數(shù)數(shù)目將有助于收錄動(dòng)態(tài)網(wǎng)頁。
將每一網(wǎng)頁上的鏈接數(shù)量限制在合理的范圍內(nèi)(少于 100)。
技術(shù)指南：
由于大部分搜索引擎 Spider 查看網(wǎng)站的方式與文本瀏覽器一樣，所以可使用諸如 Lynx 的文本瀏覽器來檢查您的網(wǎng)站。如果因采用了 Javascript、Cookie、Session ID's、frames (框架)、DHTML 或 Flash 等復(fù)雜技術(shù)，而導(dǎo)致在文本瀏覽器中無法看到網(wǎng)站的所有網(wǎng)頁，則搜索引擎 Spider 在收錄您的網(wǎng)站時(shí)可能會(huì)遇到麻煩。
允許搜索漫游器 (search bots) 收錄您的網(wǎng)站，同時(shí)不采用 Session ID 或其它參數(shù)來追蹤它的瀏覽路徑。這些跟蹤技術(shù)對(duì)了解個(gè)別用戶的行為很有用，但由于漫游器的訪問模式完全不同，采用這些技術(shù)則可能會(huì)導(dǎo)致對(duì)網(wǎng)站的檢索不完 整，因?yàn)槁纹骺赡軣o法排除那些看上去不同但實(shí)際卻指向同一個(gè)網(wǎng)頁的網(wǎng)址。
確保您的網(wǎng)絡(luò)服務(wù)器支持 If-Modified-Since HTTP 標(biāo)題。通過該功能 Google 可以知道自上次收錄以來您的網(wǎng)站內(nèi)容是否有變化，這樣可以節(jié)省您的帶寬和開銷。
使用網(wǎng)絡(luò)服務(wù)器上的 robots.txt 文件。該文件會(huì)告訴 Crawler 可以收取哪些目錄。請(qǐng)確保該文件內(nèi)容的更新，以免 Googlebot Crawler 的收錄意外中斷。有關(guān)來訪漫游器和如何控制它們的常見問題解答，請(qǐng)?jiān)L問 http://www.robotstxt.org/wc/faq.html 。
如果貴公司購買了內(nèi)容管理系統(tǒng)，請(qǐng)確保該系統(tǒng)能導(dǎo)出您的內(nèi)容，以便搜索引擎 Spider 可以收錄您的網(wǎng)站。
當(dāng)您的網(wǎng)站一切準(zhǔn)備就緒時(shí)：
一旦您的網(wǎng)站在線后，請(qǐng)將其提交給 Google，具體網(wǎng)址為： http://www.google.com/addurl.html 。
確保應(yīng)了解您網(wǎng)頁的所有網(wǎng)站都知道您的網(wǎng)站已處于在線狀態(tài)。
將您的網(wǎng)站提交給相關(guān)的目錄，例如，Open Directory Project 和 Yahoo!。
有關(guān)詳細(xì)信息，請(qǐng)定期查閱 Google 的網(wǎng)站管理員部分。
質(zhì)量指南 - 基本原則：
網(wǎng)頁應(yīng)面向用戶，而不是面向搜索引擎。對(duì)用戶應(yīng)保持誠實(shí)無欺的態(tài)度，提交給搜索引擎的內(nèi)容應(yīng)與顯示給用戶的內(nèi)容一致。
請(qǐng)不要為了提高搜索引擎排名而弄虛作假。根據(jù)我們的經(jīng)驗(yàn)，一個(gè)比較好的評(píng)定方法是：您是否可以坦然地向競爭對(duì)手解釋您對(duì)網(wǎng)站所做的一切。另一個(gè)有用的測(cè)試方法則是捫心自問："我這樣做能否幫助我的用戶?如果不存在搜索引擎，我是否還會(huì)這樣做?"
請(qǐng)不要采用旨在提高您的網(wǎng)站排名或 PageRank(網(wǎng)頁評(píng)級(jí))的鏈接手段。尤其要避免鏈接到垃圾/作弊網(wǎng)站或"網(wǎng)上惡鄰"，因?yàn)槟陨淼呐琶墒艿竭@些鏈接的負(fù)面影響。
請(qǐng)不要用未授權(quán)的計(jì)算機(jī)程序提交網(wǎng)頁、檢查排名等。這些程序會(huì)耗用計(jì)算機(jī)資源并違反我們的服務(wù)條款。Google 不建議使用 WebPosition Gold? 這類產(chǎn)品向 Google 發(fā)送自動(dòng)或用程序編寫的查詢。
質(zhì)量指南 - 具體建議：
請(qǐng)不要使用隱藏文本或隱藏鏈接。
請(qǐng)不要采用隱藏真實(shí)內(nèi)容或欺騙性重定向的手段。
請(qǐng)不要向 Google 發(fā)送自動(dòng)查詢。
請(qǐng)不要大量使用與網(wǎng)頁內(nèi)容無關(guān)的關(guān)鍵詞。
請(qǐng)不要?jiǎng)?chuàng)建包含大量重復(fù)內(nèi)容的多個(gè)網(wǎng)頁、子域或域。
請(qǐng)不要采用專門針對(duì)搜索引擎制作的"橋頁 (doorway page)"，也不要采用如聯(lián)屬計(jì)劃 (affliate programs) 這類原創(chuàng)內(nèi)容很少或幾乎沒有原創(chuàng)內(nèi)容的"餅干模子 (cookie cutter)"方式。
上述質(zhì)量指南涵蓋了最常見的作弊形式或操縱行為，對(duì)于此處未列出的其他誤導(dǎo)行為(例如，通過注冊(cè)知名網(wǎng)站的錯(cuò)誤拼寫形式來欺騙用戶)，Google 仍可予以拒絕。不要抱有僥幸心理，認(rèn)為某種欺騙手段未在本頁中列出，Google 就會(huì)認(rèn)可該手段。作為網(wǎng)站管理員，與其花費(fèi)大量時(shí)間尋找漏洞加以利用，不如盡其所能維護(hù)上述基本精神，以便為用戶帶來更好的體驗(yàn)，從而使網(wǎng)站獲得更高的排 名。
如果您認(rèn)為有網(wǎng)站違背了 Google 質(zhì)量指南，請(qǐng)告訴我們，網(wǎng)址為： http://www.google.com/contact/spamreport.html 。對(duì)于網(wǎng)絡(luò)作弊行為，Google 希望能開發(fā)出易于推廣的自動(dòng)解決方案，而盡量減少人為的干預(yù)。我們將利用收到的作弊行為報(bào)告來創(chuàng)建廣泛適用的算法，從而識(shí)別并阻止未來的作弊行為。
文章來自: 站長網(wǎng)(www.admin5.com) 詳文參考：http://www.admin5.com/article/20071225/66563.shtml