一、引言

相信大家對(duì)網(wǎng)頁爬蟲一定不陌生，爬蟲的工作原理是：

• 爬理：通過解析已經(jīng)爬取頁面中的網(wǎng)頁鏈接，然后再爬取這些鏈接對(duì)應(yīng)的網(wǎng)頁。

但是重點(diǎn)是，同一個(gè)網(wǎng)頁鏈接有可能被包含在多個(gè)頁面中，這就會(huì)導(dǎo)致爬蟲在爬取的過程中，重復(fù)爬取相同的網(wǎng)頁。

• 那么如何避免這些重復(fù)的爬取呢？

1. Record已經(jīng)爬取的網(wǎng)頁鏈接（ URL）；
2. 在爬取一個(gè)新的網(wǎng)頁之前，拿新的網(wǎng)頁的鏈接，在已經(jīng)爬取的網(wǎng)頁鏈接列表中搜索；
3. 如果存在，那就說明這個(gè)網(wǎng)頁已經(jīng)被爬取過了；
4. 如果不存在，那就說明這個(gè)網(wǎng)頁還沒有被爬取過，可以繼續(xù)去爬??；
5. 等爬取到這個(gè)網(wǎng)頁之后，我們將這個(gè)網(wǎng)頁的鏈接add到已經(jīng)爬取的網(wǎng)頁鏈接列表了。

二、怎么爬取網(wǎng)頁鏈接？

2.1 對(duì)URL要進(jìn)行的操作有哪些？

這個(gè)problem要處理的對(duì)象是網(wǎng)頁鏈接，需要support的操作有兩個(gè)：

• 添加一個(gè)URL
• 查詢一個(gè)URL

In the meantime，在非功能性方面，

• 執(zhí)行效率盡可能高
• 存儲(chǔ)效率盡可能高

2.2 哪些數(shù)據(jù)結(jié)構(gòu)可以滿足上述要求？

首先我們need想想，

• 滿足要求的數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)是什么？

快速地插入、查找數(shù)據(jù)

• 那么哪些數(shù)據(jù)結(jié)構(gòu)有這種特點(diǎn)？

散列表、紅黑樹、跳表這些動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)

但是需要注意的是，我們對(duì)內(nèi)存也有要求。For example，我們用散列表來爬取10億個(gè)web pages，

• 將10億web pages存儲(chǔ)到散列表中，大約需要多少內(nèi)存？

假設(shè)一個(gè) URL 的平均長度是 64 字節(jié)，那單純存儲(chǔ)這 10 億個(gè) URL，
需要大約 60GB 的內(nèi)存空間。

因?yàn)樯⒘斜肀仨毦S持較小的裝載因子，才能保證不會(huì)出現(xiàn)過多的散列沖突，導(dǎo)致操作的性能下降。
而且，用鏈表法解決沖突的散列表，還會(huì)存儲(chǔ)鏈表指針。

所以，如果將這 10 億個(gè) URL 構(gòu)建成散列表，那需要的內(nèi)存空間會(huì)遠(yuǎn)大于 60GB，有可能會(huì)超過 100GB。

Of course，對(duì)于一個(gè)Google來說，
即便是 100GB 的內(nèi)存要求，其實(shí)也不高，
我們can采用分治的思想，用多臺(tái)機(jī)器（比如 20 臺(tái)內(nèi)存是 8GB 的機(jī)器）來存儲(chǔ)這 10 億網(wǎng)頁鏈接。

時(shí)間復(fù)雜度只是表示執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模的變化趨勢(shì)，并不能度量在特定的數(shù)據(jù)規(guī)模下，代碼執(zhí)行時(shí)間的多少。

2.3 如何優(yōu)化DS？

如果時(shí)間復(fù)雜度中原來的系數(shù)是 10，現(xiàn)在能夠通過優(yōu)化，將系數(shù)降為 1，
那在時(shí)間復(fù)雜度沒有變化的情況下，執(zhí)行效率就提高了 10 倍。

如果我們用基于鏈表的方法解決沖突問題，散列表中存儲(chǔ)的是 URL，那當(dāng)查詢的時(shí)候，通過哈希函數(shù)定位到某個(gè)鏈表之后，我們還需要依次比對(duì)每個(gè)鏈表中的 URL。

這個(gè)操作是比較耗時(shí)的，主要有兩點(diǎn)原因。

• 一方面，鏈表中的結(jié)點(diǎn)在內(nèi)存中不是連續(xù)存儲(chǔ)的，所以不能一下子加載到 CPU 緩存中，沒法很好地利用到 CPU 高速緩存，所以數(shù)據(jù)訪問性能方面會(huì)打折扣。
• 另一方面，鏈表中的每個(gè)數(shù)據(jù)都是 URL，而 URL 不是簡單的數(shù)字，是平均長度為 64 字節(jié)的字符串。
  • 也就是說，我們要讓待判重的 URL，跟鏈表中的每個(gè) URL，做字符串匹配。顯然，這樣一個(gè)字符串匹配操作，比起單純的數(shù)字比對(duì)，要慢很多。

所以，基于這兩點(diǎn)，執(zhí)行效率方面肯定是有優(yōu)化空間的。

In actually，如果要想內(nèi)存方面有優(yōu)化，那就得換一種存儲(chǔ)結(jié)構(gòu)，布隆過濾器（Bloom Filter）。

在講布隆過濾器前，我要先講一下另一種存儲(chǔ)結(jié)構(gòu)，位圖（BitMap）。因?yàn)?，布隆過濾器本身就是基于位圖的，是對(duì)位圖的一種改進(jìn)。

• Q: 有 1 千萬個(gè)整數(shù)，整數(shù)的范圍在 1 到 1 億之間。如何快速查找某個(gè)整數(shù)是否在這 1 千萬個(gè)整數(shù)中呢？當(dāng)然，這個(gè)問題還是可以用散列表來解決。不過，我們可以使用一種比較“特殊”的散列表，那就是位圖。

• 我們申請(qǐng)一個(gè)大小為 1 億、數(shù)據(jù)類型為布爾類型（true 或者 false）的數(shù)組。將這 1 千萬個(gè)整數(shù)作為數(shù)組下標(biāo)，將對(duì)應(yīng)的數(shù)組值設(shè)置成 true。
  • 比如，整數(shù) 5 對(duì)應(yīng)下標(biāo)為 5 的數(shù)組值設(shè)置為 true，也就是 array[5]=true。
  • 當(dāng)查詢某個(gè)整數(shù) K 是否在這 1 千萬個(gè)整數(shù)中的時(shí)候，只需要將對(duì)應(yīng)的數(shù)組值 array[K] 取出來，看是否等于 true。
    • 如果等于 true，那說明 1 千萬整數(shù)中包含這個(gè)整數(shù) K；相反，就表示不包含這個(gè)整數(shù) K。

2.4 位圖&布隆過濾器

實(shí)際上，表示 true 和 false 兩個(gè)值，我們只需要用一個(gè)二進(jìn)制位（bit）就行。

• 那如何通過編程語言，來表示一個(gè)二進(jìn)制位呢？

這里就要用到位運(yùn)算了?？梢越柚幊陶Z言中提供的數(shù)據(jù)類型，比如 int、long、char 等類型，通過位運(yùn)算，用其中的某個(gè)位表示某個(gè)數(shù)字。

• 位圖通過數(shù)組下標(biāo)來定位數(shù)據(jù)，
  • 所以，訪問效率非常高。
  • 而且，每個(gè)數(shù)字用一個(gè)二進(jìn)制位來表示，在數(shù)字范圍不大的情況下，所需要的內(nèi)存空間非常節(jié)省。

比如just的例子，如果用散列表存儲(chǔ)這 1 千萬的數(shù)據(jù)，數(shù)據(jù)是 32 位的整型數(shù)，也就是需要 4 個(gè)字節(jié)的存儲(chǔ)空間，那總共至少需要 40MB 的存儲(chǔ)空間。

如果我們通過位圖的話，數(shù)字范圍在 1 到 1 億之間，只需要 1 億個(gè)二進(jìn)制位，也就是 12MB 左右的存儲(chǔ)空間就夠了。

但是，

如果數(shù)字的范圍很大，比如剛剛那個(gè)問題，數(shù)字范圍不是 1 到 1 億，而是 1 到 10 億，那位圖的大小是多少？

答案就是 10 億個(gè)二進(jìn)制位，也就是 120MB 的大小，消耗的內(nèi)存空間，不降反增。這個(gè)時(shí)候，布隆過濾器就要出場了。

Suppose剛剛的例子，數(shù)據(jù)個(gè)數(shù)是 1 千萬，數(shù)據(jù)的范圍是 1 到 10 億。

• 布隆過濾器的做法是，仍然使用一個(gè) 1 億個(gè)二進(jìn)制大小的位圖，然后通過哈希函數(shù)，對(duì)數(shù)字進(jìn)行處理，讓它落在這 1 到 1 億范圍內(nèi)。
  比如我們把哈希函數(shù)設(shè)計(jì)成 f(x)=x%n。其中，x 表示數(shù)字，n 表示位圖的大?。? 億），也就是，對(duì)數(shù)字跟位圖的大小進(jìn)行取模求余。

不過，哈希函數(shù)會(huì)存在沖突的問題，一億零一和 1 兩個(gè)數(shù)字，經(jīng)過剛剛那個(gè)取模求余的哈希函數(shù)處理之后，最后的結(jié)果都是 1。

這樣就無法區(qū)分，位圖存儲(chǔ)的是 1 還是一億零一了。

• 為了降低這種沖突概率，當(dāng)然我們可以設(shè)計(jì)一個(gè)復(fù)雜點(diǎn)、隨機(jī)點(diǎn)的哈希函數(shù)。

除此之外，還有其他方法嗎？我們來看布隆過濾器的處理方法。既然一個(gè)哈希函數(shù)可能會(huì)存在沖突，那用多個(gè)哈希函數(shù)一塊兒定位一個(gè)數(shù)據(jù)，是否能降低沖突的概率呢？

2.5 布隆過濾器是怎么做的？

• 使用 K 個(gè)哈希函數(shù)，對(duì)同一個(gè)數(shù)字進(jìn)行求哈希值，那會(huì)得到 K 個(gè)不同的哈希值，
  • 分別記作 X1?，X2?，X3?，…，XK?。

• 把這 K 個(gè)數(shù)字作為位圖中的下標(biāo)，將對(duì)應(yīng)的 BitMap[X1?]，BitMap[X2?]，BitMap[X3?]，…，BitMap[XK?] 都設(shè)置成 true，i.e.，用 K 個(gè)二進(jìn)制位，來表示一個(gè)數(shù)字的存在。

• when要查詢某個(gè)數(shù)字是否存在的時(shí)候，用同樣的 K 個(gè)哈希函數(shù)，對(duì)這個(gè)數(shù)字求哈希值，分別得到 Y1?，Y2?，Y3?，…，YK?。
  • We看這 K 個(gè)哈希值，對(duì)應(yīng)位圖中的數(shù)值是否都為 true，如果都是 true，則說明，這個(gè)數(shù)字存在，如果有其中任意一個(gè)不為 true，那就說明這個(gè)數(shù)字不存在。
    
    布隆過濾器是怎么做的

對(duì)于兩個(gè)不同的數(shù)字來說，經(jīng)過一個(gè)哈希函數(shù)處理之后，可能會(huì)產(chǎn)生相同的哈希值。但是經(jīng)過 K 個(gè)哈希函數(shù)處理之后，K 個(gè)哈希值都相同的概率就非常低了。

盡管采用 K 個(gè)哈希函數(shù)之后，兩個(gè)數(shù)字哈希沖突的概率降低了，但是，這種處理方式又帶來了新的問題，那就是容易誤判?？纯聪旅孢@個(gè)例子——

K個(gè)哈希函數(shù)的缺點(diǎn)——容易誤判

三、布隆過濾器的騷操作

3.1 布隆過濾器會(huì)誤判？

是的，布隆過濾器會(huì)誤判。

• 布隆過濾器的誤判的特點(diǎn)是什么？

它只會(huì)對(duì)存在的情況有誤判。

如果某個(gè)數(shù)字經(jīng)過布隆過濾器判斷不存在，那說明這個(gè)數(shù)字真的不存在，不會(huì)發(fā)生誤判；
如果某個(gè)數(shù)字經(jīng)過布隆過濾器判斷存在，這個(gè)時(shí)候才會(huì)有可能誤判，有可能并不存在。

No more than，只要調(diào)整哈希函數(shù)的個(gè)數(shù)、位圖大小跟要存儲(chǔ)數(shù)字的個(gè)數(shù)之間的比例，那就可以將這種誤判的概率降到非常低。
盡管布隆過濾器會(huì)存在誤判，但是，這并不影響它發(fā)揮大作用。很多場景對(duì)誤判有一定的容忍度。

比如我們今天要解決的爬蟲判重這個(gè)問題，即便一個(gè)沒有被爬取過的網(wǎng)頁，被誤判為已經(jīng)被爬取，對(duì)于搜索引擎來說，也并不是什么大事情，是可以容忍的，畢竟網(wǎng)頁太多了，搜索引擎也不可能 100% 都爬取到。

3.2 回到網(wǎng)頁爬蟲

弄懂了布隆過濾器，我們今天的爬蟲網(wǎng)頁去重的問題，就很簡單了。

我們用布隆過濾器來記錄已經(jīng)爬取過的網(wǎng)頁鏈接，假設(shè)需要判重的網(wǎng)頁有 10 億，那我們可以用一個(gè) 10 倍大小的位圖來存儲(chǔ)，也就是 100 億個(gè)二進(jìn)制位，換算成字節(jié)，那就是大約 1.2GB。

之前我們用散列表判重，需要至少 100GB 的空間。

相比來講，布隆過濾器在存儲(chǔ)空間的消耗上，降低了非常多。

再來看下，

• 利用布隆過濾器，在執(zhí)行效率方面，是否比散列表更加高效呢？

布隆過濾器用多個(gè)哈希函數(shù)對(duì)同一個(gè)網(wǎng)頁鏈接進(jìn)行處理，CPU 只需要將網(wǎng)頁鏈接從內(nèi)存中讀取一次，進(jìn)行多次哈希計(jì)算，理論上講這組操作是 CPU 密集型的。

而在散列表的處理方式中，需要讀取散列沖突拉鏈的多個(gè)網(wǎng)頁鏈接，分別跟待判重的網(wǎng)頁鏈接，進(jìn)行字符串匹配。

這個(gè)操作涉及很多內(nèi)存數(shù)據(jù)的讀取，所以是內(nèi)存密集型的。我們知道 CPU 計(jì)算可能是要比內(nèi)存訪問更快速的，所以，理論上講，布隆過濾器的判重方式，更加快速。

3.3 summary

• 布隆過濾器非常適合這種不需要 100% 準(zhǔn)確的、允許存在小概率誤判的大規(guī)模判重場景。

除了爬蟲網(wǎng)頁去重這個(gè)例子，還有比如統(tǒng)計(jì)一個(gè)大型網(wǎng)站的每天的 UV 數(shù)，也就是每天有多少用戶訪問了網(wǎng)站，可以使用布隆過濾器，對(duì)重復(fù)訪問的用戶，進(jìn)行去重。

前面講到，布隆過濾器的誤判率，主要跟哈希函數(shù)的個(gè)數(shù)、位圖的大小有關(guān)。

當(dāng)We往布隆過濾器中不停地加入數(shù)據(jù)之后，位圖中不是 true 的位置就越來越少了，誤判率就越來越高了。

所以，對(duì)于無法事先知道要判重的數(shù)據(jù)個(gè)數(shù)的情況，我們需要支持自動(dòng)擴(kuò)容的功能。

當(dāng)布隆過濾器中，數(shù)據(jù)個(gè)數(shù)與位圖大小的比例超過某個(gè)閾值的時(shí)候，我們就重新申請(qǐng)一個(gè)新的位圖。后面來的新數(shù)據(jù)，會(huì)被放置到新的位圖中。

但是，如果我們要判斷某個(gè)數(shù)據(jù)是否在布隆過濾器中已經(jīng)存在，我們就需要查看多個(gè)位圖，相應(yīng)的執(zhí)行效率就降低了一些。