為什么引入
我們的業(yè)務(wù)中經(jīng)常會(huì)遇到穿庫(kù)的問(wèn)題，通常可以通過(guò)緩存解決。如果數(shù)據(jù)維度比較多，結(jié)果數(shù)據(jù)集合比較大時(shí)，緩存的效果就不明顯了。
因此為了解決穿庫(kù)的問(wèn)題，我們引入Bloom Filter。
適合的場(chǎng)景
- 數(shù)據(jù)庫(kù)防止穿庫(kù) google Bigtable，Apache HBase和Apache Cassandra以及Postgresql 使用BloomFilter來(lái)減少不存在的行或列的磁盤查找。避免代價(jià)高昂的磁盤查找會(huì)大大提高數(shù)據(jù)庫(kù)查詢操作的性能。如同一開(kāi)始的業(yè)務(wù)場(chǎng)景。如果數(shù)據(jù)量較大，不方便放在緩存中。需要對(duì)請(qǐng)求做攔截防止穿庫(kù)。
- 緩存宕機(jī) 緩存宕機(jī)的場(chǎng)景，使用布隆過(guò)濾器會(huì)造成一定程度的誤判。原因是除了Bloom Filter 本身有誤判率，宕機(jī)之前的緩存不一定能覆蓋到所有DB中的數(shù)據(jù)，當(dāng)宕機(jī)后用戶請(qǐng)求了一個(gè)以前從未請(qǐng)求的數(shù)據(jù)，這個(gè)時(shí)候就會(huì)產(chǎn)生誤判。當(dāng)然，緩存宕機(jī)時(shí)使用布隆過(guò)濾器作為應(yīng)急的方式，這種情況應(yīng)該也是可以忍受的。
- WEB攔截器 相同請(qǐng)求攔截防止被攻擊。用戶第一次請(qǐng)求，將請(qǐng)求參數(shù)放入BloomFilter中，當(dāng)?shù)诙握?qǐng)求時(shí)，先判斷請(qǐng)求參數(shù)是否被BloomFilter命中。可以提高緩存命中率
- 惡意地址檢測(cè) chrome 瀏覽器檢查是否是惡意地址。首先針對(duì)本地BloomFilter檢查任何URL，并且僅當(dāng)BloomFilter返回肯定結(jié)果時(shí)才對(duì)所執(zhí)行的URL進(jìn)行全面檢查（并且用戶警告，如果它也返回肯定結(jié)果）。
- 比特幣加速 bitcoin 使用BloomFilter來(lái)加速錢包同步。
開(kāi)源項(xiàng)目地址：
https://github.com/luw2007/bloomfilter
我們先看看一般業(yè)務(wù)緩存流程：
先查詢緩存，緩存不命中再查詢數(shù)據(jù)庫(kù)。然后將查詢結(jié)果放在緩存中即使數(shù)據(jù)不存在，也需要?jiǎng)?chuàng)建一個(gè)緩存，用來(lái)防止穿庫(kù)。
這里需要區(qū)分一下數(shù)據(jù)是否存在。如果數(shù)據(jù)不存在，緩存時(shí)間可以設(shè)置相對(duì)較短，防止因?yàn)橹鲝耐降葐?wèn)題，導(dǎo)致問(wèn)題被放大。
這個(gè)流程中存在薄弱的問(wèn)題是，當(dāng)用戶量太大時(shí)，我們會(huì)緩存大量數(shù)據(jù)空數(shù)據(jù)，并且一旦來(lái)一波冷用戶，會(huì)造成雪崩效應(yīng)。
對(duì)于這種情況，我們產(chǎn)生第二個(gè)版本流程:redis過(guò)濾冷用戶緩存流程
我們將數(shù)據(jù)庫(kù)里面中命中的用戶放在redis的set類型中，設(shè)置不過(guò)期。這樣相當(dāng)把redis當(dāng)作數(shù)據(jù)庫(kù)的索引，只要查詢r(jià)edis，就可以知道是否數(shù)據(jù)存在。
redis中不存在就可以直接返回結(jié)果。如果存在就按照上面提到一般業(yè)務(wù)緩存流程處理。
聰明的你肯定會(huì)想到更多的問(wèn)題：
- redis本身可以做緩存，為什么不直接返回?cái)?shù)據(jù)呢？
- 如果數(shù)據(jù)量比較大，單個(gè)set，會(huì)有性能問(wèn)題？
- 業(yè)務(wù)不重要，將全量數(shù)據(jù)放在redis中，占用服務(wù)器大量?jī)?nèi)存。投入產(chǎn)出不成比例？
問(wèn)題1
需要區(qū)分業(yè)務(wù)場(chǎng)景，結(jié)果數(shù)據(jù)少，我們是可以直接使用redis作為緩存，直接返回?cái)?shù)據(jù)。結(jié)果比較大就不太適合用redis存放了。比如ugc內(nèi)容，一個(gè)評(píng)論里面可能存在上萬(wàn)字，業(yè)務(wù)字段多。
redis使用有很多技巧。bigkey 危害比較大，無(wú)論是擴(kuò)容或縮容帶來(lái)的內(nèi)存申請(qǐng)釋放， 還是查詢命令使用不當(dāng)導(dǎo)致大量數(shù)據(jù)返回，都會(huì)影響redis的穩(wěn)定。這里就不細(xì)談原因及危害了。
解決bigkey 方法很簡(jiǎn)單。我們可以使用hash函數(shù)來(lái)分桶，將數(shù)據(jù)分散到多個(gè)key中。減少單個(gè)key的大小，同時(shí)不影響查詢效率。
問(wèn)題3
是redis存儲(chǔ)占用內(nèi)存太大。因此我們需要減少內(nèi)存使用。重新思考一下引入redis的目的。redis像一個(gè)集合，整個(gè)業(yè)務(wù)就是驗(yàn)證請(qǐng)求的參數(shù)是否在集合中。
這個(gè)結(jié)構(gòu)就像洗澡的時(shí)候用的雙向閥門：左邊熱水，右邊冷水。
大部分的編程語(yǔ)言都內(nèi)置了filter。拿Python舉例，filter函數(shù)用于過(guò)濾序列， 過(guò)濾掉不符合條件的元素，返回由符合條件元素組成的列表。
我們看個(gè)例子：
$ python2
Python 2.7.10 (default, Oct 6 2017, 22:29:07)
[GCC 4.2.1 Compatible Apple LLVM 9.0.0 (clang-900.0.31)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> s = {2, 4}
>>> filter(lambda x:x in s, [0, 1, 2])
[2]
集合s中存在 2，4兩個(gè)數(shù)字，我們需要查詢 0，1，2 那些在集合s中。 lambda x:x in s構(gòu)造一個(gè)匿名函數(shù)，判斷入?yún)是否在集合s中。過(guò)濾器filter依次對(duì)列表中的數(shù)字執(zhí)行匿名函數(shù)。最終返回列表[2]。
redis中實(shí)現(xiàn)set用了兩種結(jié)構(gòu)：intset和hash table。非數(shù)字或者大量數(shù)字時(shí)都會(huì)退化成hash table。那么是否好的算法可以節(jié)省hash table的大小呢？
其實(shí)早在1970年由Burton Howard Bloom提出的布隆過(guò)濾器（英語(yǔ)：Bloom Filter）。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。
它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過(guò)一般的算法， 缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。
BloomFilter原理
我們常見(jiàn)的將業(yè)務(wù)字段拼接之后md5，放在一個(gè)集合中。md5生成一個(gè)固定長(zhǎng)度的128bit的串。如果我們用bitmap來(lái)表示，則需要
2**128 = 340282366920938463463374607431768211456 bit
判斷一個(gè)值在不在，就變成在這個(gè)bitmap中判斷所在位是否為1。但是我們?nèi)澜绲臋C(jī)器存儲(chǔ)空間也無(wú)法存儲(chǔ)下載。因此我們只能分配有限的空間來(lái)存儲(chǔ)。
當(dāng)只有一個(gè)hash函數(shù)時(shí)：很容易發(fā)生沖突。
可以看到上面1和2的hash結(jié)果都是7，發(fā)生沖突。如果增加hash函數(shù)，會(huì)發(fā)生什么情況？
我們使用更多的hash函數(shù)和更大的數(shù)據(jù)集合來(lái)測(cè)試。得到下面這張表
由此可以看到當(dāng)增加hash方法能夠有效的降低碰撞機(jī)率。比較好的數(shù)據(jù)如下：
但是增加了hash方法之后，會(huì)降低空間的使用效率。當(dāng)集合占用總體空間達(dá)到25%的時(shí)候， 增加hash 的效果已經(jīng)不明顯
上面的使用多個(gè)hash方法來(lái)降低碰撞就是BloomFilter的核心思想。
算法優(yōu)點(diǎn)：
- 數(shù)據(jù)空間小，不用存儲(chǔ)數(shù)據(jù)本身。
算法本身缺點(diǎn)：
- 元素可以添加到集合中，但不能被刪除。
- 匹配結(jié)果只能是“絕對(duì)不在集合中”，并不能保證匹配成功的值已經(jīng)在集合中。
- 當(dāng)集合快滿時(shí)，即接近預(yù)估最大容量時(shí)，誤報(bào)的概率會(huì)變大。
- 數(shù)據(jù)占用空間放大。一般來(lái)說(shuō)，對(duì)于1％的誤報(bào)概率，每個(gè)元素少于10比特，與集合中的元素的大小或數(shù)量無(wú)關(guān)。查詢過(guò)程變慢，hash函數(shù)增多，導(dǎo)致每次匹配過(guò)程，需要查找多個(gè)位（hash個(gè)數(shù)）來(lái)確認(rèn)是否存在。
對(duì)于BloomFilter的優(yōu)點(diǎn)來(lái)說(shuō)，缺點(diǎn)都可以忽略。畢竟只需要kN的存儲(chǔ)空間就能存儲(chǔ)N個(gè)元素。空間效率十分優(yōu)秀。
如何使用BloomFilter
BloomFilter 需要一個(gè)大的bitmap來(lái)存儲(chǔ)。鑒于目前公司現(xiàn)狀，最好的存儲(chǔ)容器是redis。從github topics: bloom-filter中經(jīng)過(guò)簡(jiǎn)單的調(diào)研。
redis集成BloomFilter方案：
- 原生python 調(diào)用setbit 構(gòu)造 BloomFilter
- lua腳本
- Rebloom - Bloom Filter Module for Redis (注：redis Module在redis4.0引入)
- 使用hiredis 調(diào)用redis pyreBloom
原生python 方法太慢，lua腳本和module 部署比較麻煩。于是我們推薦使用pyreBloom，底層使用。
pyreBloom:master λ ls
Makefile bloom.h bloom.pxd murmur.c pyreBloom.pyx
bloom.c bloom.o main.c pyreBloom.c
從文件命名上可以看到bloom 使用c編寫。pyreBloom 使用cython編寫。
bloom.h 里面實(shí)現(xiàn)BloomFilter的核心邏輯，完成與redis server的交互；hash函數(shù)；添加，檢查和刪除方法的實(shí)現(xiàn)。
進(jìn)階：計(jì)數(shù)過(guò)濾器(Counting Filter)
提供了一種在BloomFilter上實(shí)現(xiàn)刪除操作的方法，而無(wú)需重新重新創(chuàng)建過(guò)濾器。在計(jì)數(shù)濾波器中，陣列位置（桶）從單個(gè)位擴(kuò)展為n位計(jì)數(shù)器。實(shí)際上，常規(guī)布隆過(guò)濾器可以被視為計(jì)數(shù)過(guò)濾器，其桶大小為一位。
插入操作被擴(kuò)展為遞增桶的值，并且查找操作檢查每個(gè)所需的桶是否為非零。然后，刪除操作包括遞減每個(gè)桶的值。
存儲(chǔ)桶的算術(shù)溢出是一個(gè)問(wèn)題，并且存儲(chǔ)桶應(yīng)該足夠大以使這種情況很少見(jiàn)。如果確實(shí)發(fā)生，則增量和減量操作必須將存儲(chǔ)區(qū)設(shè)置為最大可能值，以便保留BloomFilter的屬性。
計(jì)數(shù)器的大小通常為3或4位。因此，計(jì)算布隆過(guò)濾器的空間比靜態(tài)布隆過(guò)濾器多3到4倍。相比之下， Pagh，Pagh和Rao（2005）以及Fan等人的數(shù)據(jù)結(jié)構(gòu)。（2014）也允許刪除但使用比靜態(tài)BloomFilter更少的空間。
計(jì)數(shù)過(guò)濾器的另一個(gè)問(wèn)題是可擴(kuò)展性有限。由于無(wú)法擴(kuò)展計(jì)數(shù)布隆過(guò)濾器表，因此必須事先知道要同時(shí)存儲(chǔ)在過(guò)濾器中的最大鍵數(shù)。一旦超過(guò)表的設(shè)計(jì)容量，隨著插入更多密鑰，誤報(bào)率將迅速增長(zhǎng)。
Bonomi等人。（2006）引入了一種基于d-left散列的數(shù)據(jù)結(jié)構(gòu)，它在功能上是等效的，但使用的空間大約是計(jì)算BloomFilter的一半。此數(shù)據(jù)結(jié)構(gòu)中不會(huì)出現(xiàn)可伸縮性問(wèn)題。一旦超出設(shè)計(jì)容量，就可以將密鑰重新插入到雙倍大小的新哈希表中。
Putze，Sanders和Singler（2007）的節(jié)省空間的變體也可用于通過(guò)支持插入和刪除來(lái)實(shí)現(xiàn)計(jì)數(shù)過(guò)濾器。
Rottenstreich，Kanizo和Keslassy（2012）引入了一種基于變量增量的新通用方法，該方法顯著提高了計(jì)算布隆過(guò)濾器及其變體的誤報(bào)概率，同時(shí)仍支持刪除。
與計(jì)數(shù)布隆過(guò)濾器不同，在每個(gè)元素插入時(shí)，散列計(jì)數(shù)器以散列變量增量而不是單位增量遞增。要查詢?cè)兀枰紤]計(jì)數(shù)器的確切值，而不僅僅是它們的正面性。如果由計(jì)數(shù)器值表示的總和不能由查詢?cè)氐南鄳?yīng)變量增量組成，則可以將否定答案返回給查詢。
