布隆過濾器
是一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都比一般的算法要好的多，缺點是有一定的誤識別率和刪除困難。但是布隆過濾器可以控制錯誤率。
具體的布隆過濾器相關的內容可查找相關資料，非常詳細，其優勢就是佔用內存比hash表要小得多，非常適合用於做過濾的場景
Guava中的布隆過濾器
Guava是google開發的java基礎庫，其中提供了布隆過濾器的實現，即名為BloomFilter的類，其使用方式類似如下：
使用Redis實現布隆過濾器
當布隆過濾器也需要使用大量內存，並要求在多臺機器之間共享時，Guava提供的BloomFilter就難以滿足需求了。BloomFilter在數據存在上，實際上可以認為是一個非常大了位圖，而redis支持bitmap數據結構，正好可以用於實現布隆過濾器。
然而，我們如何實現BloomFilter呢，我們可以先看看guava中的BloomFilter的實現方式：
BloomFilter.put()方法中，直接調用了strategy.put()，我們可以繼續進入到這個Strategy中：
可以看到，Strategy是BloomFilter類中的內部接口，是用於當布隆過濾器存儲的對象轉換成bits，guava中提供的實現是一個enum：
我們繼續看看其put方法的實現：
其中，除了hash以外，就是對LockFreeBitArray的操作，因此，如果我們能通過redis實現一個新的LockFreeBitArray，那我們就能實現一個基於redis的布隆過濾器了，但是很可惜，LockFreeBitArray是final的類，且是包訪問權限，我們無法從LockFreeBitArray類做擴展。
那麼我們只有使用兩種方式：
1. 自己從頭開始實現BloomFilter
2. 拿來主義，都是開源的了，抄代碼吧，把BloomFilter相關的代碼copy出來，替換掉LockFreeBitArray
我這裡使得了第二種方式，將guava中的BloomFilter複製一份，並加上JedisPool參數用於訪問redis，然後基於redis實現一個LockFreeBitArray，其中基於redis的LockFreeBitArray的實現如下：
可以看到，本質上就是通過一個key創建出一個bitmap，代碼本身只是將原來guava的LockFreeBitArray中的byte數據替換成了redis和bitmap
整個BloomFilterStrategies的重新實現如下：
最後是與Guava的BloomFilter幾乎一樣的RedisBloomFilter
待優化點
目前的環境中使得的redis是單機的，所以這樣使用是沒問題的，但是對於使用redis集群而言，這樣做就不太好了，因為整個BloomFilter只關聯了一個key，無法分散到redis集群中的各臺機器上，因此可以針對集群做一個優化，一種可行的思路就是將一個BloomFilter拆分成多個BloomFilter，生成不同的key，將BloomFilter的數據分散到redis集群中不同的redis機器上，這樣可充分發揮出redis集群的性能和緩存的容量
閱讀更多 無醉 的文章
