一、布隆過濾器
1.1 原理
1.1.1 布隆過濾器基礎(chǔ)版
原理就是一個對一個key進行k個hash算法獲取k個值，在比特數(shù)組中將這k個值散列后設定為1，然后查的時候如果特定的這幾個位置都為1，那么布隆過濾器判斷該key存在。
布隆過濾器可能會誤判，如果它說不存在那肯定不存在，如果它說存在，那數(shù)據(jù)有可能實際不存在；
Redis的bitmap只支持2^32大小，對應到內(nèi)存也就是512MB，誤判率萬分之一，可以放下2億左右的數(shù)據(jù)，性能高，空間占用率及小，省去了大量無效的數(shù)據(jù)庫連接。
存入過程： 通過三個hash函數(shù)計算出三個哈希值，然后將三個值映射到數(shù)組中將0改成1。
查詢過程：通過三個hash函數(shù)計算出查詢數(shù)據(jù)的哈希值，然后檢查布隆過濾器對應位置上的值是否為1，如果有一個不為1表示該值不存在，如果都為1表示該值可能存在。（查詢時間復雜度為O(k)，k為哈希函數(shù)個數(shù)）
刪除過程：不能進行刪除，因為會刪除掉其他數(shù)據(jù)。
更新過程：也不能進行更新。
1.1.2 布隆過濾器增強版
為了解決上面布隆過濾器的問題,出現(xiàn)了一個增強版的布隆過濾器(Counting Bloom Filter),這個過濾器的思路是將布隆過濾器的bitmap更換成數(shù)組,當數(shù)組某位置被映射一次時就+1,當刪除時就-1,這樣就避免了普通布隆過濾器刪除數(shù)據(jù)后需要重新計算其余數(shù)據(jù)包Hash的問題,但是依舊沒法避免誤判。
1.2 應用
redis緩存穿透（大量查詢不存在于數(shù)據(jù)庫中的數(shù)據(jù)）：使用布隆過濾器進行過濾，如果不存在直接跳過查詢數(shù)據(jù)庫，返回結(jié)果。
新聞客戶端的推送去重功能，當推薦系統(tǒng)推薦新聞時會從每個用戶的歷史記錄里進行篩選，過濾掉那些已經(jīng)存在的記錄。它在起到去重的同時，在空間上還能節(jié)省 90% 以上，只是稍微有那么點不精確，也就是有一定的誤判概率。
黑白名單
塊索引是HBase固有的一個特性，因為HBase的底層數(shù)據(jù)是存儲在HFile中的，而每個HFile中存儲的是有序的<key, value>鍵值對，HFile文件內(nèi)部由連續(xù)的塊組成，每個塊中存儲的第一行數(shù)據(jù)的行鍵組成了這個文件的塊索引，這些塊索引信息存儲在文件尾部。當HBase打開一個HFile時，塊索引信息會優(yōu)先加載到內(nèi)存；HBase首先在內(nèi)存的塊索引中進行二分查找，確定可能包含給定鍵的塊，然后讀取磁盤塊找到實際想要的鍵。
但實際應用中，僅僅只有塊索引滿足不了需求，這是因為，塊索引能幫助我們更快地在一個文件中找到想要的數(shù)據(jù)，但是我們可能依然需要掃描很多文件。而布隆過濾器就是為解決這個問題而生。因為布隆過濾器的作用是，用戶可以立即判斷一個文件是否包含特定的行鍵，從而幫我們過濾掉一些不需要掃描的文件。
1.3 代碼實現(xiàn)
1.3.1 實現(xiàn)一(Guava)
調(diào)用谷歌的guava包的api就可以。
缺點：guava版實現(xiàn)主要問題在于無法支持集群環(huán)境. 為了支持集群環(huán)境主要考慮通過redis setbit來實現(xiàn)BloomFilter。
創(chuàng)建布隆過濾器對象：
// 參數(shù)Funnels.integerFunnel()是默認參數(shù)，size是預計存入的數(shù)據(jù)量，fpp是設置的誤判率
public static <T> BloomFilter<T> create(
Funnel<? super T> funnel, int expectedInsertions, double fpp) {
return create(funnel, (long) expectedInsertions, fpp);
}
誤判率越低，哈希函數(shù)個數(shù)和布隆過濾器數(shù)組長度越大，運算效率越低。
放入數(shù)據(jù)：
@CanIgnoreReturnValue
public boolean put(T object) {
return strategy.put(object, funnel, numHashFunctions, bits);
}
判斷是否存在：
public boolean mightContain(T object) {
return strategy.mightContain(object, funnel, numHashFunctions, bits);
}
1.3.2 實現(xiàn)二(Redisson)
使用redis實現(xiàn)
依賴
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson</artifactId>
<version>3.6.5</version>
</dependency>
代碼
public class RedissonBloomFilter {
public static void main(String[] args) {
Config config = new Config();
config.useSingleServer().setAddress("redis://192.168.32.128:6379");
// config.useSingleServer().setPassword("");
// 構(gòu)造Redisson
RedissonClient redissonClient = Redisson.create(config);
// 初始化布隆過濾器：預計元素為100000000L個，誤差率為3%
RBloomFilter<Object> bloomFilter = redissonClient.getBloomFilter("phoneList");
bloomFilter.tryInit(100000000L, 0.03);
// 將號碼插入到布隆過濾器中
bloomFilter.add("10086");
// 判斷下面的號碼是否在布隆過濾器中
System.out.println(bloomFilter.contains("10000"));
System.out.println(bloomFilter.contains("10086"));
}
}
1.4 布隆過濾器的缺點
- 不支持刪除元素：一旦對位數(shù)組進行了賦值，無法將其刪除?？梢酝ㄟ^增加每個數(shù)組元素大小使用增強版過濾器實現(xiàn)刪除功能。
- 查詢性能弱：布隆過濾器使用多個hash函數(shù)計算位圖多個不同位點，由于多個位點在內(nèi)存中不連續(xù)，CPU尋址花銷較大。
- 空間利用率低。
二、布谷鳥過濾器
2.1 原理
布谷鳥哈希結(jié)構(gòu)：布谷鳥過濾器由一個數(shù)組組成，數(shù)組中元素大小為4個字節(jié)，可以存儲4個指紋，每個指紋占一個字節(jié)(128種)。同一個數(shù)組元素 上的多個座位在內(nèi)存空間上是連續(xù)的，可以有效利用 CPU 高速緩存。
type bucket [4]byte // 一個桶，4個座位
type cuckoo_filter struct {
buckets [size]bucket // 一維數(shù)組
nums int // 容納的元素個數(shù)
kick_max // 最大擠兌次數(shù)
}
插入：首先計算數(shù)據(jù)的指紋和哈希值，并通過指紋和哈希值計算另一個哈希值，兩個哈希值映射到兩個位置(因為計算得到兩個位置，每個位置存儲4個指紋，所以相同對象最多存儲8個)。接下來進行插入，會嘗試插入兩個位置，如果都失敗，隨機擠走一個指紋，并重新為該指紋尋找新的位置(超過最大擠兌次數(shù)后擴容)。
擴容：如果數(shù)組過小，會發(fā)生循環(huán)擠兌的情況，就可以設置最大擠兌次數(shù)，如果超過該次數(shù)，進行擴容，重新計算每個指紋的位置。
查找：通過計算哈希值得到兩個元素，對兩個元素中的8個位置進行指紋對比，如果對比成功則表示數(shù)據(jù)存在。如果哈希值和指紋相同時會發(fā)生誤判(小概率)。
刪除：因為每個對象的指紋會存儲到一個位置中，所以可以通過刪除這個指紋來刪除數(shù)據(jù)。刪除功能無法使用的情況：如果相同對象存儲超過8個，就無法使用刪除功能；如果倆數(shù)據(jù)的哈希值和指紋相同時，會出現(xiàn)誤刪除情況。
更新：即刪除后再添加新指紋。
2.2 應用
同布隆過濾器。
2.3 代碼實現(xiàn)
貌似目前沒有現(xiàn)成的java實現(xiàn)。
可以參考如下項目：
通過redis中強有力的第三方擴展module, 讓redis支持sql及布谷鳥過濾器。
https://github.com/RedBeardLab/rediSQL
2.4 布谷鳥過濾器的優(yōu)缺點
對比布隆過濾器：
布谷鳥過濾器在錯誤率小于3%的時候空間性能是優(yōu)于布隆過濾器的，而這個條件在實際應用中常常滿足，所以一般來說它的空間性能是要優(yōu)于布隆過濾器的。布谷鳥過濾器按照普通設計，只有兩個Hash表，在查找的時候可以確保兩次訪存就可以做完，相比于布隆過濾器的K個Hash函數(shù)K次訪存，在數(shù)據(jù)量很大不能全部裝載在內(nèi)存中的情況下，多次訪問內(nèi)存性能較差。
當然，布谷過濾器也有其相應的缺點，當裝填數(shù)據(jù)過多的時候，容易出現(xiàn)循環(huán)的問題，即插入失敗的情況。另外，它還跟布隆過濾器共有的一個缺點，就是訪問空間地址不連續(xù)，內(nèi)存尋址消耗大。
優(yōu)點：
- 訪問內(nèi)存次數(shù)低
- Hash函數(shù)計算簡單
- 存在刪除操作。如果相同數(shù)據(jù)個數(shù)不超過8個，那么刪除操作可用；但是因為存儲的是計算后的指紋信息，存在誤刪除的可能，所以不好用。
缺點：
- 內(nèi)存空間不聯(lián)系，CPU消耗大。
- 容易出現(xiàn)裝填循環(huán)問題：Hash沖突踢出原數(shù)據(jù)，原數(shù)據(jù)還是存在沖突。
- 刪除數(shù)據(jù)時，Hash沖突會引起誤刪：查詢有誤判，那么刪除也會有誤刪。
