Java的布隆過濾器你瞭解嗎

2022-03-18 16:00:32

BitMap

現代計算機用二進位制（bit，位）作為資訊的基礎單位，1 個位元組等於 8 位，例如big字串是由 3 個位元組組成，但實際在計算機儲存時將其用二進位制表示，big分別對應的 ASCII 碼分別是 98、105、103，對應的二進位制分別是 01100010、01101001 和 01100111。

許多開發語言都提供了操作位的功能，合理地使用位能夠有效地提高記憶體使用率和開發效率。

Bit-map 的基本思想就是用一個 bit 位來標記某個元素對應的 value，而 key 即是該元素。由於採用了 bit 為單位來儲存資料，因此在儲存空間方面，可以大大節省。

在 Java 中，int 佔 4 位元組，1 位元組 = 8位元（1 byte = 8 bit），如果我們用這個 32 個 bit 位的每一位的值來表示一個數的話是不是就可以表示 32 個數位，也就是說 32 個數位只需要一個 int 所佔的空間大小就可以了，那就可以縮小空間 32 倍。

1 Byte = 8 Bit，1 KB = 1024 Byte，1 MB = 1024 KB，1GB = 1024 MB

假設網站有 1 億使用者，每天獨立存取的使用者有 5 千萬，如果每天用集合型別和 BitMap 分別儲存活躍使用者：

1.假如使用者 id 是 int 型，4 位元組，32 位，則集合型別佔據的空間為 50 000 000 * 4/1024/1024 = 200M；

2.如果按位元儲存，5 千萬個數就是 5 千萬位，佔據的空間為 50 000 000/8/1024/1024 = 6M。

那麼如何用 BitMap 來表示一個數呢？

上面說了用 bit 位來標記某個元素對應的 value，而 key 即是該元素，我們可以把 BitMap 想象成一個以位為單位的陣列，陣列的每個單元只能儲存 0 和 1（0 表示這個數不存在，1 表示存在），陣列的下標在 BitMap 中叫做偏移量。比如我們需要表示{1,3,5,7}這四個數，如下：

那如果還存在一個數 65 呢？只需要開int[N/32+1]個 int 陣列就可以儲存完這些資料（其中 N 表示這群資料中的最大值），即：

int[0]：可以表示 0~31

int[1]：可以表示 32~63

int[2]：可以表示 64~95

假設我們要判斷任意整數是否在列表中，則 M/32 就得到下標，M%32就知道它在此下標的哪個位置，如：

65/32 = 2，65%32=1，即 65 在int[2] 中的第 1 位。

布隆過濾器

本質上布隆過濾器是一種資料結構，比較巧妙的概率型資料結構，特點是高效地插入和查詢，可以用來告訴你 “某樣東西一定不存在或者可能存在”。

相比於傳統的 List、Set、Map 等資料結構，它更高效、佔用空間更少，但是缺點是其返回的結果是概率性的，而不是確切的。

實際上，布隆過濾器廣泛應用於網頁黑名單系統、垃圾郵件過濾系統、爬蟲網址判重系統等，Google 著名的分散式資料庫 Bigtable 使用了布隆過濾器來查詢不存在的行或列，以減少磁碟查詢的 IO 次數，Google Chrome 瀏覽器使用了布隆過濾器加速安全瀏覽服務。

在很多 Key-Value 系統中也使用了布隆過濾器來加快查詢過程，如 Hbase，Accumulo，Leveldb，一般而言，Value 儲存在磁碟中，存取磁碟需要花費大量時間，然而使用布隆過濾器可以快速判斷某個 Key 對應的 Value 是否存在，因此可以避免很多不必要的磁碟 IO 操作。

通過一個 Hash 函數將一個元素對映成一個位陣列（Bit Array）中的一個點。這樣一來，我們只要看看這個點是不是 1 就知道可以集合中有沒有它了。這就是布隆過濾器的基本思想。

運用場景

1、目前有 10 億數量的自然數，亂序排列，需要對其排序。限制條件在 32 位機器上面完成，記憶體限制為 2G。如何完成？

2、如何快速在億級黑名單中快速定位 URL 地址是否在黑名單中？(每條 URL 平均 64 位元組)

3、需要進行使用者登陸行為分析，來確定使用者的活躍情況？

4、網路爬蟲-如何判斷 URL 是否被爬過？

5、快速定位使用者屬性（黑名單、白名單等）？

6、資料儲存在磁碟中，如何避免大量的無效 IO？

7、判斷一個元素在億級資料中是否存在？

8、快取穿透。

傳統資料結構的不足

一般來說，將網頁 URL 存入資料庫進行查詢，或者建立一個雜湊表進行查詢就 OK 了。

當資料量小的時候，這麼思考是對的，確實可以將值對映到 HashMap 的 Key，然後可以在 O(1) 的時間複雜度內返回結果，效率奇高。但是 HashMap 的實現也有缺點，例如儲存容量佔比高，考慮到負載因子的存在，通常空間是不能被用滿的，舉個例子如果一個 1000 萬 HashMap，Key=String（長度不超過 16 字元，且重複性極小），Value=Integer，會佔據多少空間呢？1.2 個 G。

實際上用 bitmap，1000 萬個 int 型，只需要 40M（ 10 000 000 * 4/1024/1024 =40M）左右空間，佔比 3%，1000 萬個 Integer，需要 161M 左右空間，佔比 13.3%。

可見一旦你的值很多例如上億的時候，那 HashMap 佔據的記憶體大小就可想而知了。

但如果整個網頁黑名單系統包含 100 億個網頁 URL，在資料庫查詢是很費時的，並且如果每個 URL 空間為 64B，那麼需要記憶體為 640GB，一般的伺服器很難達到這個需求。

實現原理

假設我們有個集合 A，A 中有 n 個元素。利用k個雜湊雜湊函數，將A中的每個元素對映到一個長度為 a 位的陣列 B中的不同位置上，這些位置上的二進位制數均設定為 1。如果待檢查的元素，經過這 k個雜湊雜湊函數的對映後，發現其 k 個位置上的二進位制數全部為 1，這個元素很可能屬於集合A，反之，一定不屬於集合A。

比如我們有 3 個 URL {URL1,URL2,URL3}，通過一個hash 函數把它們對映到一個長度為 16 的陣列上，如下：

若當前雜湊函數為 Hash1()，通過雜湊運算對映到陣列中，假設Hash1(URL1) = 3，Hash1(URL2) = 6，Hash1(URL3) = 6，如下：

因此，如果我們需要判斷URL1是否在這個集合中，則通過Hash(1)計算出其下標，並得到其值若為 1 則說明存在。

由於 Hash 存在雜湊衝突，如上面URL2,URL3都定位到一個位置上，假設 Hash 函數是良好的，如果我們的陣列長度為 m 個點，那麼如果我們想將衝突率降低到例如 1%，這個雜湊表就只能容納 m/100 個元素，顯然空間利用率就變低了，也就是沒法做到空間有效（space-efficient）。

解決方法也簡單，就是使用多個 Hash 演演算法，如果它們有一個說元素不在集合中，那肯定就不在，如下：

Hash1(URL1) = 3,Hash2(URL1) = 5,Hash3(URL1) = 6
Hash1(URL2) = 5,Hash2(URL2) = 8,Hash3(URL2) = 14
Hash1(URL3) = 4,Hash2(URL3) = 7,Hash3(URL3) = 10

以上就是布隆過濾器做法，使用了k個雜湊函數，每個字串跟 k 個 bit 對應，從而降低了衝突的概率。

誤判現象

上面的做法同樣存在問題，因為隨著增加的值越來越多，被置為 1 的 bit 位也會越來越多，這樣某個值即使沒有被儲存過，但是萬一雜湊函數返回的三個 bit 位都被其他值置位了 1 ，那麼程式還是會判斷這個值存在。比如此時來一個不存在的 URL1000，經過雜湊計算後，發現 bit 位為下：

Hash1(URL1000) = 7,Hash2(URL1000) = 8,Hash3(URL1000) = 14

但是上面這些 bit 位已經被URL1,URL2,URL3置為 1 了，此時程式就會判斷 URL1000 值存在。

這就是布隆過濾器的誤判現象，所以，布隆過濾器判斷存在的不一定存在，但是，判斷不存在的一定不存在。

布隆過濾器可精確的代表一個集合，可精確判斷某一元素是否在此集合中，精確程度由使用者的具體設計決定，達到 100% 的正確是不可能的。但是布隆過濾器的優勢在於，利用很少的空間可以達到較高的精確率。

實現

Redis 的 bitmap

基於redis 的 bitmap資料結構的相關指令來執行。

RedisBloom

布隆過濾器可以使用 Redis 中的點陣圖(bitmap)操作實現，直到 Redis4.0 版本提供了外掛功能，Redis 官方提供的布隆過濾器才正式登場，布隆過濾器作為一個外掛載入到 Redis Server 中，官網推薦了一個 RedisBloom 作為 Redis 布隆過濾器的 Module。

詳細安裝、指令操作參考：https://github.com/RedisBloom/RedisBloom

檔案地址：https://oss.redislabs.com/redisbloom/

Guava 的 BloomFilter

Guava 專案發布版本11.0時，新新增的功能之一是BloomFilter類。

Redisson

Redisson 底層基於點陣圖實現了一個布隆過濾器。

public static void main(String[] args) {
    Config config = new Config();
    // 單機環境
    config.useSingleServer().setAddress("redis://192.168.153.128:6379");
    //構造Redisson
    RedissonClient redisson = Redisson.create(config);
    RBloomFilter<String> bloomFilter = redisson.getBloomFilter("nameList");
    //初始化布隆過濾器：預計元素為100000000L,誤差率為3%,根據這兩個引數會計算出底層的 bit 陣列大小
    bloomFilter.tryInit(100000L, 0.03);
    //將 10086 插入到布隆過濾器中
    bloomFilter.add("10086");
    //判斷下面號碼是否在布隆過濾器中
    System.out.println(bloomFilter.contains("10086"));//true
    System.out.println(bloomFilter.contains("10010"));//false
    System.out.println(bloomFilter.contains("10000"));//false
}

解決快取穿透

快取穿透是指查詢一個根本不存在的資料，快取層和儲存層都不會命中，如果從儲存層查不到資料則不寫入快取層。

快取穿透將導致不存在的資料每次請求都要到儲存層去查詢，失去了快取保護後端儲存的意義。快取穿透問題可能會使後端儲存負載加大，由於很多後端儲存不具備高並行性，甚至可能造成後端儲存宕掉。

因此我們可以用布隆過濾器來解決，在存取快取層和儲存層之前，將存在的 key 用布隆過濾器提前儲存起來，做第一層攔截。

例如：一個推薦系統有 4 億個使用者 id，每個小時演演算法工程師會根據每個使用者之前歷史行為計算出推薦資料放到儲存層中，但是最新的使用者由於沒有歷史行為，就會發生快取穿透的行為，為此可以將所有推薦資料的使用者做成布隆過濾器。如果布隆過濾器認為該使用者 id 不存在，那麼就不會存取儲存層，在一定程度保護了儲存層。

注：布隆過濾器可能會誤判，放過部分請求，當不影響整體，所以目前該方案是處理此類問題最佳方案