布隆過濾器
布隆過濾器是一個BIT數(shù)組，可以用來判斷一個元素是否在一個集合中已存在。很常用的一個功能是用來去重。例如在爬蟲中，我們要爬取的目標網(wǎng)站 URL 千千萬，怎么判斷某個 URL 爬蟲是否已經(jīng)爬取過？簡單點可以爬蟲每采集過一個 URL，就把這個 URL 存入數(shù)據(jù)庫中，每次一個新的 URL 過來就到數(shù)據(jù)庫查詢下是否訪問過。但是隨著爬蟲爬過的 URL 越來越多，每次請求前都要訪問數(shù)據(jù)庫一次，并且對于這種字符串的 SQL 查詢效率并不高。除了數(shù)據(jù)庫之外，使用 Redis 的 set 結(jié)構(gòu)也可以滿足這個需求，并且性能優(yōu)于數(shù)據(jù)庫。但是 Redis 也存在一個問題：耗費過多的內(nèi)存。相比于數(shù)據(jù)庫和 Redis，使用布隆過濾器可以很好的避免性能和內(nèi)存占用的問題。
實現(xiàn)原理
布隆過濾器實現(xiàn)非常簡單，如下圖所示，在存入元素a、b和c時，分別通過3個hash算法h1()、h2()和h2()計算出相應的hash值，并將BIT數(shù)組對應位置設(shè)為1。之后在判斷新元素是否已存在時，也只需要使用這3個hash算法h1()、h2()和h2()計算出對應的hash值，然后通過hash值判斷BIT數(shù)組對應位置，如果都為1，這就能夠說明：d可能存在集合中（因為可能出現(xiàn)hash沖突）。如果有一個為0，那么說明：d一定不存在集合中。所以布隆過濾器對于一個元素是否已存在會存在誤判，但如果某個元素經(jīng)過布隆過濾器判斷不存在，那說明這個元素真的不存在，不會發(fā)生誤判。
布隆過濾器非常適合那種不需要 100% 準確的、允許存在小概率誤判的大規(guī)模判重場景。除了爬蟲網(wǎng)頁去重這個例子，還有比如統(tǒng)計一個大型網(wǎng)站的每天的 UV 數(shù)，也就是每天有多少用戶訪問了網(wǎng)站，我們就可以使用布隆過濾器，對重復訪問的用戶進行去重。
Redis 中的布隆過濾器
redis 在 4.0 的版本中加入了 module 功能，布隆過濾器可以通過 module 的形式添加到 redis 中，所以使用 redis 4.0 以上的版本可以通過加載 module來使用 redis 中的布隆過濾器。但是這不是最簡單的方式，使用 docker 可以直接在 redis 中體驗布隆過濾器。
> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
> docker exec -it bloomfilter redis-cli
redis 布隆過濾器主要就兩個命令：
-
bf.add添加元素到布隆過濾器中：bf.add urls https://jaychen.cc。 -
bf.exists判斷某個元素是否在過濾器中：bf.exists urls https://jaychen.cc。
