Redis 使用布隆過濾器從海量數據中查詢一個值是否存在

楔子

我們前面介紹過 HyperLogLog 可以用來做基數統計，但它統計的是總數量，而無法判斷某個指定的值是否存在。那我們如果想在海量數據之中檢索某個值存在與否，該怎麼做呢？

因爲是海量數據，所以我們不可能將每個鍵值都存起來，然後再從結果中檢索數據。我們只能依靠專門處理此問題的特殊方法來實現數據的查找，而它就是我們今天的主角：布隆過濾器。

布隆過濾器實現原理

布隆過濾器（Bloom Filter）是 1970 年由布隆提出的，它實際上是一個很長的二進制向量和一系列隨機映射函數，可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都比一般的算法要好的多，缺點是有一定的誤識別率和刪除困難。也就是說布隆過濾器的優點就是計算和查詢速度很快，但是缺點也很明顯，會存在一定的誤差。

假設現在要存儲一個鍵值對，但是布隆過濾器不會真的存儲具體的數據，那樣就太佔空間了。它是利用幾個不同的無偏哈希函數，把此元素的 hash 值均勻地映射在位數組中。

通過哈希函數對 key 進行運算，然後再對數組的長度取模，即可得到一個索引，然後將數組中該索引對應的元素設置爲 1 即可。並且由於存在衝突，比如 key1 和 key2 映射到同一個槽，所以我們會選擇多個哈希函數，畢竟多個哈希函數同時衝突的概率還是很低的。

也就是說，每次添加時會通過幾個無偏哈希函數算出它的一些位置，把這些位置設置成 1 就完成了添加操作。

當判斷元素存在與否時，查詢此元素的幾個哈希位置上的值是否爲 1，如果全部爲 1，則表示此值存在，只要有一個不爲 1，則表示不存在。

比如 key2 在映射的時候，發現第一個哈希槽的元素是 1，而後兩個哈希槽的元素是 0。說明 key2 是不存在的，第一個槽之所以爲 1，是因爲其它的 key 碰巧也映射到了這個槽。所以我們才選擇多個哈希函數（無偏），爲的就是減少哈希的隨機性帶來的誤差，只有全部爲 1，key 才存在，而有一個不是 1，那麼 key 就不存在。

但很明顯，當位數組存儲的值比較稀疏的時候，查詢的準確率會很高；而當位數組存儲的值越來越多時，誤差也會增大。比如某個 key 不存在，但它映射出的多個哈希槽裏面的元素都是 1，這種情況是有可能發生的，而此時也說明布隆過濾器已經存儲了非常多的數據。

因此可以得出結論：布隆過濾器判斷某個 key 存在時，此 key 不一定存在；但判斷某個 key 不存在時，此 key 一定不存在。

所以布隆過濾器和 Redis Hash 類型的實現原理是一樣的，只不過 Redis Hash 的每個哈希槽存的是 *dictEntry，而布隆過濾器的每個哈希槽存的是 1 或 0。以及布隆過濾器在映射的時候會使用多個哈希函數（以減少衝突），而 Hash 類型只用一個哈希函數。

最後還有一個重點，布隆過濾器使用的數組是位數組，也就是說數組裏面的每個元素存的是 bit 位，因爲 1 和 0 只用一個 bit 位就能保存。但現代計算機操作的最小單位是字節，所以在實際使用數組的時候，我們會基於位運算，將裏面的一個元素當成多個元素來用。

比如 int64 類型的數組，裏面有 10 個元素，每個元素 8 字節、也就是 64 個 bit 位，那麼我們會把它看成是一個長度爲 64 * 10 的位數組。如果類型是 int16，那麼就看成是長度爲 16 * 10 的位數組。

假設類型是 int64，哈希映射之後的槽是 60，那麼就將數組中第一個元素的第 61 個位設置爲 1；如果映射之後的槽是 80，就將數組中第二個元素的第 17 個位設置爲 1。

所以布隆過濾器除了用到了哈希表，還用到了位圖。因爲是海量數據，因此數組會很長，並且爲了避免哈希衝突，我們會將數組申請的更長一些。因此爲了減少內存使用，布隆過濾器還使用了位圖的思想。

安裝布隆過濾器

在 Redis 中不能直接使用布隆過濾器，但我們可以通過 Redis 4.0 版本之後提供的 modules（擴展模塊）方式引入。

1）下載並安裝布隆過濾器；

git clone https://github.com/RedisLabsModules/redisbloom.git
cd redisbloom
make # 編譯redisbloom

編譯完畢之後，會在主目錄生成一個 redisbloom.so 文件。

2）啓動 Redis 服務器；

./redis-server redis.conf --loadmodule redisbloom.so

其中 --loadmodule 爲加載擴展模塊的意思，後面跟的是 redisbloom.so 文件的路徑。

或者更簡便的做法，還可以使用 Docker。

# 拉取鏡像
docker pull redislabs/rebloom  
# 運行容器
docker run -p 6379:6379 redislabs/rebloom

布隆過濾器的使用

布隆過濾器的命令不是很多，主要包含以下幾個：

下面舉例說明。

1）添加元素

127.0.0.1:6379> bf.add user satori
(integer) 1
127.0.0.1:6379> bf.add user koishi
(integer) 1
127.0.0.1:6379> bf.add user marisa
(integer) 1

2）判斷元素是否存在

127.0.0.1:6379> bf.exists user satori
(integer) 1
127.0.0.1:6379> bf.exists user satori1
(integer) 0

3）添加多個元素

127.0.0.1:6379> bf.madd user n1 n2 n3
1) (integer) 1
2) (integer) 1
3) (integer) 1

4）判斷多個元素是否存在

127.0.0.1:6379> bf.mexists user n1 n2 n33
1) (integer) 1
2) (integer) 1
3) (integer) 0

可以看出以上結果沒有任何誤差，然後還有一個布隆過濾器的準確率，不過在介紹它之前，我們先使用 Python 操作一下 Redis 的布隆過濾器。

我們之前使用 Python 操作 Redis 使用第三方模塊也叫 redis，但是對於布隆過濾器來說，這個模塊是不支持的。我們需要使用另一個第三方模塊：redisbloom，直接 pip install redisbloom 安裝即可。

其實 redisbloom 底層還是使用了我們之前的 redis 模塊。

# 我們之前創建連接使用的是 redis.Redis
# 而這個 Client 繼承自 Redis
from redisbloom.client import Client

# 所以我們之前的一些操作，這裏都可以用
client = Client(host="...", 
                decode_responses="utf-8")

# 添加單個元素
client.bfAdd("girl", "satori")

# 添加多個元素
client.bfMAdd("girl", "koishi", "marisa")

# 判斷單個元素是否存在
print(client.bfExists("girl", "satori"))  # 1

# 判斷多個元素是否存在
print(
    client.bfMExists("girl", "satori", "koishi", 
                     "marisa", "xxx")
)  # [1, 1, 1, 0]

最後是設置布隆過濾器的準確率：

# 對於一個已經存在的key，不可以使用bf.reserve
127.0.0.1:6379> bf.reserve user 0.01 200
(error) ERR item exists  
127.0.0.1:6379> bf.reserve user1 0.01 200  
OK

key 後面的兩個值分別表示：error_rate、initial_size。

那麼布隆過濾器一般都用在什麼場景中呢？

布隆過濾器在數據庫領域的使用也比較廣泛，例如：HBase, Cassandra, LevelDB, RocksDB 內部都有使用布隆過濾器。對於布隆過濾器而言，數據量增大到一定程度之後誤差也會隨之增大。

小結

通過本文我們知道可以使用 Redis 4.0 之後提供的 modules 方式來開啓布隆過濾器，並學習了布隆過濾器的幾個重要操作方法。其中比較關鍵的是 bf.reserve，它有 2 個重要的參數：錯誤率和數組大小，錯誤率設置的越低，數組設置的越大，需要存儲的空間就越大，相對來說查詢的錯誤率也越低。具體需要如何設置，需要使用者根據實際情況進行調整。

另外布隆過濾器有一個最大的特點：當它查詢有數據時，此數據不一定真的存在，當它查詢沒有此數據時，此數據一定不存在。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/PuzUckvppuE2hfEoiBWOrQ

猜你喜歡