概述：
- scrapy_redis去重使用的是redis集合猖吴，是將請求數(shù)據(jù)以sha1加密之后的加密值存入redis集合，通過redis集合來實現(xiàn)去重讼积，去重數(shù)據(jù)量可以在千萬級別以上，至于具體的數(shù)值就看硬件了。但是對現(xiàn)在的各家大數(shù)據(jù)公司而言钞螟，數(shù)據(jù)需求往往不是1兩個G能解決的，在數(shù)據(jù)量太大之后谎碍，redis的去重壓力會很大鳞滨，甚至會掛掉。為了提高去重上限蟆淀，滿足我們爬蟲的需求實現(xiàn)基于scrapy_redis構建以布隆過濾器為核心的去重拯啦。
下面先來段科普(關于布隆過濾器)：
布隆過濾器［1］（Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出的熔任。它實際上是由一個很長的二進制向量和一系列隨機映射函數(shù)組成褒链，布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都遠遠超過一般的算法疑苔，缺點是有一定的誤識別率（假正例False positives甫匹，即Bloom Filter報告某一元素存在于某集合中，但是實際上該元素并不在集合中）和刪除困難惦费，但是沒有識別錯誤的情形（即假反例False negatives赛惩，如果某個元素確實沒有在該集合中，那么Bloom Filter 是不會報告該元素存在于集合中的趁餐，所以不會漏報）喷兼。
在日常生活中，包括在設計計算機軟件時后雷，我們經(jīng)常要判斷一個元素是否在一個集合中季惯。比如在字處理軟件中吠各，需要檢查一個英語單詞是否拼寫正確（也就是要判斷 它是否在已知的字典中）；在 FBI勉抓，一個嫌疑人的名字是否已經(jīng)在嫌疑名單上贾漏；在網(wǎng)絡爬蟲里，一個網(wǎng)址是否被訪問過等等藕筋。最直接的方法就是將集合中全部的元素存在計算機中纵散，遇到一個新 元素時，將它和集合中的元素直接比較即可隐圾。一般來講伍掀，計算機中的集合是用哈希表（hash table）來存儲的。它的好處是快速準確暇藏，缺點是費存儲空間蜜笤。當集合比較小時，這個問題不顯著盐碱，但是當集合巨大時把兔，哈希表存儲效率低的問題就顯現(xiàn)出來 了。比如說瓮顽，一個象 Yahoo,Hotmail 和 Gmai 那樣的公眾電子郵件（email）提供商县好，總是需要過濾來自發(fā)送垃圾郵件的人（spamer）的垃圾郵件。一個辦法就是記錄下那些發(fā)垃圾郵件的 email 地址暖混。由于那些發(fā)送者不停地在注冊新的地址缕贡，全世界少說也有幾十億個發(fā)垃圾郵件的地址，將他們都存起來則需要大量的網(wǎng)絡服務器儒恋。如果用哈希表，每存儲一億 個 email 地址黔漂， 就需要 1.6GB 的內存（用哈希表實現(xiàn)的具體辦法是將每一個 email 地址對應成一個八字節(jié)的信息指紋（詳見：googlechinablog.com/2006/08/blog-post.html）诫尽， 然后將這些信息指紋存入哈希表，由于哈希表的存儲效率一般只有 50%炬守，因此一個 email 地址需要占用十六個字節(jié)牧嫉。一億個地址大約要 1.6GB， 即十六億字節(jié)的內存）。因此存貯幾十億個郵件地址可能需要上百 GB 的內存。除非是超級計算機打却，一般服務器是無法存儲的［2］久脯。（該段引用谷歌數(shù)學之美：http://www.google.com.hk/ggblog/googlechinablog/2007/07/bloom-filter_7469.html）
我的認識跟理解
算法：
1. 首先需要k個hash函數(shù)，每個函數(shù)可以把key散列成為1個整數(shù)
2. 初始化時族淮，需要一個長度為n比特的數(shù)組，每個比特位初始化為0
3. 某個key加入集合時，用k個hash函數(shù)計算出k個散列值怕轿，并把數(shù)組中對應的比特位置為1
4. 判斷某個key是否在集合時偷崩，用k個hash函數(shù)計算出k個散列值，并查詢數(shù)組中對應的比特位撞羽，如果所有的比特位都是1阐斜，認為在集合中。優(yōu)點：不需要存儲key诀紊，節(jié)省空間
缺點：
1. 算法判斷key在集合中時谒出，有一定的概率key其實不在集合中
2. 無法刪除誤報：
布隆過濾器會：這個url肯定存在，或者這個url肯定不存在邻奠，或者這個url可能存在笤喳。會出現(xiàn)誤報，但是不會報錯惕澎，針對不同的應用場景莉测，這有可能會是一個巨大的缺陷，亦或是無關緊要的問題唧喉。如果在檢索元素是否存在時不介意引入誤報情況捣卤，那么你就應當考慮用布隆過濾器。-
簡單實現(xiàn)(在我的github的bloomfilter_demo.py)：
image2.png
在scrapy_redis的布隆過濾基本實現(xiàn)流程介紹
- 布隆過濾器封裝在py_bloomfilter.py中八孝，基于redis.第三方依賴：mmh3--下載命令: pip install mmh3(用來實現(xiàn)hash的函數(shù)類庫).
- bloom_dupefilter.py 來重寫scrapy_redis的去重策略.
- settings.py配置修改董朝，如下圖，跟scrapy_redis的配置格式基本相同干跛，不過需要把去重的類改成我們自己重寫的DUPEFILTER_CLASS.
- 使用爬蟲流程跟scrapy_redis的操作相同子姜，去重數(shù)據(jù)會在我們的布隆過濾器交互的redis里。
- 我的py_bloomfilter.py跟bloom_dupefilter.py路徑放置如下圖：
