手把手教你寫網路爬蟲（7） 作者：拓海 摘要：從零開始寫爬蟲，初學者的速成指南！ 封面： 本期我們來聊聊URL去重那些事兒。以前我們曾使用Python的字典來保存抓取過的URL，目的是將重覆抓取的URL去除，避免多次抓取同一網頁。爬蟲會將待抓取的URL放在todo隊列中，從抓取到的網頁中提取到新的U ...
手把手教你寫網路爬蟲（7）
作者：拓海
摘要：從零開始寫爬蟲，初學者的速成指南！
封面：
本期我們來聊聊URL去重那些事兒。以前我們曾使用Python的字典來保存抓取過的URL，目的是將重覆抓取的URL去除，避免多次抓取同一網頁。爬蟲會將待抓取的URL放在todo隊列中，從抓取到的網頁中提取到新的URL，在它們被放入隊列之前，首先要確定這些新的URL是否被抓取過，如果之前已經抓取過了，就不再放入隊列。
有別於單機系統，在分散式系統中，這些URL應該存放在公共緩存中，才能讓多個爬蟲實例共用，我們繼續使用Redis緩存這些數據。URL既可以存儲在Redis的Set數據結構中，也可以將URL作為Key存儲為Redis的String類型。至於這兩種方案各有什麼優缺點，就留給讀者自己去思考了。
直接存儲URL
將URL以字元串的形式直接存儲到記憶體中。保守估計一下URL的平均長度是100位元組，那麼1億個URL所占的記憶體是: 100000000 * 0.0001MB = 10000MB，約等於10G。這也不是不能用，占用的空間再大都能通過擴容來解決。
問題是，如果一個伺服器存不下這麼多URL該怎麼辦呢？其實也簡單，明確每台伺服器的分工，也就是說得到一個URL就知道要交給哪台伺服器存儲，每台伺服器只存儲一類URL，比較簡單的實現方式就是對URL先哈希再取模。雖然能用，但還是有很大優化空間的。
存儲消息摘要
MD5是一個消息摘要演算法，它的用途很廣泛，我們這裡用它來壓縮URL。
消息摘要演算法的特點：
- 無論輸入的消息有多長，計算出來的消息摘要的長度總是固定的。
- 只要輸入的消息不同，對其進行摘要以後產生的摘要消息也必不相同；但相同的輸入必會產生相同的輸出。
- 消息摘要是單向、不可逆的。只能進行正向的信息摘要，而無法從摘要中恢復出任何的原始消息。
以上特點說明我們可以通過存儲URL的MD5來實現去重功能，因為不同的URL，MD5不同，相同的URL，MD5相同嘛。
對應的MD5值是這樣的：d552b0b40e21d06d73a1a0938635eb1a
怎麼樣？省了不少空間吧？
有人說，拓海你不要騙我，這個演算法的輸入是個無窮集合，而輸出是一個有限集合，必然會存在碰撞的，也就是存在不同的URL算出相同的MD5。這會導致去重時誤判，少抓數據！
好吧，從理論上來說，必然會出現這種情況。可是出現這種情況的概率是多少呢？下麵就算算兩個不同URL產生相同消息摘要的概率。
以下是三種常見的消息摘要演算法，分別是32、64、128位元組，每個位元組是十六進位數字的字元，它們的可能值數量分別是：
md5: 16^32 = 2^128 = 3.4 * 10^38
sha256: 16^64 = 2^256 = 1.2 × 10^77
sha512: 16^128 = 2^512 = 1.3 × 10^154
你可能會說，我是數字盲，我不知道這個數大不大。好吧，我為你找到了兩個直觀的參照物：
IPv6編碼地址數：2^128（約3.4×10^38）
IPv6是IETF設計的用於替代現行版本IP協議（IPv4）的下一代IP協議，號稱可以為全世界的每一粒沙子編上一個網址。
可觀測宇宙中的原子總數：10^80
上圖是哈勃望遠鏡對準天球上一個特定的區域（相當於整個天球面積的1/12700000）進行長時間的圖像拍攝，最後在這個區域裡面找到了約有10000個星系。這樣可以合理的推測，目前我們能用天文望遠鏡觀測到的宇宙範圍內有1.27x10^11個星系。
一個星系的恆星數(行星忽略不計了)目前普遍接受的一個數量級是4x10^11個。
像太陽這樣的恆星的質量是1.96x10^30kg。
這就可以算出宇宙的總質量為9.96x10^55kg。
一個氫原子的質量是1.66x10^-24g。
用宇宙質量除以一個氫原子的質量就得出了目前可觀測宇宙中的近似原子個數是10^80個。
可見，不同URL產生相同消息摘要的可能性非常小，簡直像大海撈針。。。不是，簡直像宇宙中撈原子一樣難，所以就放心使用吧。
消息摘要實現了對URL的壓縮，但壓縮後的大小還是和原來在一個數量級，空間效率並沒有質的提升。有沒有辦法只用幾個bit來唯一標識一個URL呢？有！布隆過濾器就是專門解決這類問題的。
布隆過濾器
Bloom Filter是一種空間效率很高的隨機數據結構，它利用bit數組很簡潔地表示一個集合，並能判斷一個元素是否屬於這個集合。Bloom Filter的這種高效是有一定代價的：在判斷一個元素是否屬於某個集合時，有可能會把不屬於這個集合的元素誤認為屬於這個集合（false positive）。因此，Bloom Filter不適合那些“零錯誤”的應用場合。而在能容忍低錯誤率的應用場合下，Bloom Filter通過極少的錯誤換取了存儲空間的極大節省。
它的原理很簡單，首先需要準bit數組（所有位初始化為0）和k個獨立hash函數。將hash函數對應的值的位數組置1，查找時如果發現所有hash函數對應位都是1說明存在，否則不存在。很明顯這個過程並不保證查找的結果是100%正確的。
如何根據輸入元素個數n，確定bit數組m的大小及hash函數個數呢？當hash函數個數k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大於E的情況下，m至少要等於n*lg(1/E)才能表示任意n個元素的集合。但m還應該更大些，因為還要保證bit數組裡至少一半為0，則m應該>=nlg(1/E)*lge ，大概就是nlg(1/E)的1.44倍。假設錯誤率為0.01，則此時m應是n的13倍。這樣k大概是8個。
Google的Guava基礎庫里有布隆過濾器的實現，非常的簡潔和有深度，我們一起來學習一下這段java代碼。
1 public <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits) { 2 long bitSize = bits.bitSize(); 3 long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong(); 4 int hash1 = (int) hash64; 5 int hash2 = (int) (hash64 >>> 32); 6 7 boolean bitsChanged = false; 8 for (int i = 1; i <= numHashFunctions; i++) { 9 int combinedHash = hash1 + (i * hash2); 10 // Flip all the bits if it's negative (guaranteed positive number) 11 if (combinedHash < 0) { 12 combinedHash = ~combinedHash; 13 } 14 bitsChanged |= bits.set(combinedHash % bitSize); 15 } 16 return bitsChanged; 17 }
01 函數的功能是把一條數據hash後保存到BitArray中，如果BitArray有變化則返回true，否則返回false。參數是數據、hash函數個數、BitArray地址。
03 使用murmur3 hash出一個long型的值。為什麼是一個，不應該是numHashFunctions個嗎？請往下看。
04 05 把hash64切成兩半，變成hash1和hash2。
08 09 重點來了，numHashFunctions個hash函數原來是這麼來的：hash1+(i*hash2)。Excuse me? 這種操作太隨意了吧？不用擔心，請看《Less Hashing, Same Performance: Building a Better Bloom Filter》，裡面論述了這種操作不會影響布隆過濾器的性能：A standard technique from the hashing literature is to use two hash functions h1(x) and h2(x) to simulate additional hash functions of the form gi(x) = h1(x) + ih2(x). We demonstrate that this technique can be usefully applied to Bloom filters and related data structures. Specifically, only two hash functions are necessary to effectively implement a Bloom filter without any loss in the asymptotic false positive probability.這個優化非常有用，畢竟hash的代價還是很大的。
11 12 是負的就取反（這裡的操作都很粗暴）。
14 設置BitArray里對應的bit，下麵進入set()里看看。
1 boolean set(long index) { 2 if (!get(index)) { 3 data[(int) (index >>> 6)] |= (1L << index); 4 bitCount++; 5 return true; 6 } 7 return false; 8 } 9 10 boolean get(long index) { 11 return (data[(int) (index >>> 6)] & (1L << index)) != 0; 12 }
02 先get()一下，看看是不是已經置為1。
03 index右移6位就是除以64，說明data是long型的數組，除以64就定位到了bit所在的數組下標。1L左移index位，定位到了bit在long中的位置。
下一步
以上就是URL去重的一點思路，希望對大家有幫助。下期打算為大家介紹下字元編解碼，以及亂碼的完美解決方案。再見！
