布隆過濾器：提高效率與降低成本的秘密
一、背景介紹
在互聯網中，我們經常遇到需要在大量數據中判斷目標數據是否存在的情況。例如，在網絡爬蟲中，我們需要判斷某個網址是否已經被訪問過。為了實現這一功能，通常需要使用一個容器來存儲已訪問過的網址。如果將這些數據直接存儲在磁盤中，每次判斷都要進行磁盤查詢，這將導致大量的IO操作，效率較低。因此，我們希望將這些數據保存在內存中。在數據量較小的情況下，可以使用Redis來存儲這些數據。但是，當數據量超過上千萬時，將會消耗幾GB甚至幾十GB的內存空間。然而，對于僅需要記錄數據是否存在的情況而言，這樣使用大量內存顯然是浪費的。為了解決這個問題，我們可以使用布隆過濾器(Bloom Filter)。布隆過濾器是一種占用空間少且時間效率高的工具。
二、認識布隆過濾器
2.1 布隆過濾器簡介
布隆過濾器（Bloom Filter）是1970年由布隆提出的，它實質上是一個很長的二進制向量和一系列隨機映射函數 (Hash函數)。
作用：它是一個空間效率高的概率型數據結構，用來告訴你:一個元素一定不存在或者可能存在。
2.2 優點
- 相比于其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數（即hash函數的個數）。
- Hash 函數相互之間沒有關系，方便由硬件并行實現。
- 布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。
- 布隆過濾器可以表示全集，其它任何數據結構都不能。
2.3 缺點
- 有誤判率存在。
- 不支持刪除。
2.4 適用場景
- 預防緩存穿透：布隆過濾器快速判斷數據是否存在，避免通過查詢數據庫來判斷數據是否存在。
- 網絡爬蟲：布隆過濾器可以用來去重已經爬取過的URL。
- 郵箱的垃圾郵件過濾。
- 黑白名單。
三、 布隆過濾器原理
3.1 結構
布隆過濾器實現原理就是一個超大位數的數組和多個不同Hash算法函數。假設位數組的長度為 m，哈希函數的個數為 k。如下圖，一個長度16位的數組，3個不同Hash算法函數，數組里面存儲的是 bit 位，只放 0 和 1，初始為 0。
不同Hash算法函數
指定長度數組
3.2 添加元素
將要添加的元素分別通過k個哈希函數計算得到k個哈希值，這k個hash值對應位數組上的k個位置，然后將這k個位置設置為1。
我們添加一個data1和data2兩個元素，兩個元素根據三個hash算法函數計算出的值，需要說明一點三個值可能會存在相同的值。
其中data1計算出1、8、13三值，我們把數組中對應的位置設置為1。
Hash1(data1)=1
Hash2(data1)=8
Hash3(data1)=13
如圖：
data2計算出2、5、13三值，我們把數組中對應的位置設置為1
Hash1(data2)=2
Hash2(data2)=5
Hash3(data2)=13
如圖：
我們發現data1和data2經過hash函數后，出現了一個相同值，這種是正常的，也正是因為這種情況的存在，需要多個函數來保證每個元素盡可能對應數組位置的唯一性，可以看下兩個元素在一起的效果。
如圖：
當不同元素在不同或者相同的hash函數計算后，得到同一個值，依舊只需要這個位置保持1即可。
3.3 查詢元素
將要查詢的元素分別通過k個哈希函數計算得到k個哈希值，這k個hash值對應位數組上的k個位置。如果這k個位置中有一個位置為0，則此元素一定不存在集合中。如果這k個位置全部為1，則這個元素可能存在。
我們在剛才添加過data1和data2兩個元素的布隆過濾器查詢以下三種元素，data1已添加到布隆過濾器元素，data3和data4都是未添加到布隆過濾器元素。
查詢data1先根據添加時的三個hash函數計算分別對應值，值分別是1、8、13，然后查詢數組中這三個位置的值是否為1。
Hash1(data1)=1
Hash2(data1)=8
Hash3(data1)=13
如圖：
我們可以看到數組中1、8、13這三個位置都是1，data1可能存在于該布隆過濾器。我們從添加的角度來看，我們知道data1是一定存在于該布隆過濾器的，為什么還要是說可能呢，是因為查詢出來三個位置都為1不能代表這個三個1都是同一個元素添加的，下面我們看下元素data3的查詢。
查詢data3先根據添加時的三個hash函數計算分別對應值，值分別是2、8、13，然后查詢數組中這三個位置的值是否為1。
Hash1(data3)=2
Hash2(data3)=8
Hash3(data3)=13
如圖：
我們已知的該布隆過濾器我們沒有添加給data3，為什么data3查詢出來三個位置的值都為1呢。我們可以看到data3所命中的位置分別是data2添加時把位置2賦值的1，和data1添加時把位置8和位置13賦值的1，都是由其他元素改變的位置對應的值，所以命中位置全部為1。這個元素可能存在。
我們查詢一下data4，看下命中位置不全為0的數據。查詢data4先根據添加時的三個hash函數計算分別對應值，值分別是2、8、13，然后查詢數組中這三個位置的值是否為1。
Hash1(data4)=1
Hash2(data4)=8
Hash3(data4)=12
如圖：
我們可以看到data4元素的hash函數3計算之后的值是12，數組位置12的值是0，沒有元素在位置12賦值過1。如果data4存在于該布隆過濾器，則一定在添加data4時會把位置12賦值1，此時位置12還是0，則說明該布隆過濾器未添加過data4元素，所以位置中有一個位置為0。則此元素一定不存在布隆過濾器中。
四、布隆過濾器誤判率
剛才查詢時我們發現data3沒有添加過到布隆過濾器，卻在布隆過濾器查詢到了，這種情況就是布隆過濾器誤判了。那可以不存在誤判或者減少誤判嗎？事實上誤判是一定存在的，我們可以盡可能減小誤判。下面說下如何得到誤判率。
4.1 參數
m：布隆過濾器的bit長度。
n：插入過濾器的元素個數。
k：哈希函數的個數。
4.2 推導過程
4.3 誤判率公式
五、實現方式
5.1 Guava實現
guava是谷歌開源工具類，其中就有能直接實現布隆過濾器的方法，不需要重復造輪子。
方法名 | 功能 | 參數 | 返回值 |
put | 添加元素 | put(T object) | boolean |
mightContain | 檢查元素是否存在 | mightContain(T object) | boolean |
copy | 根據此實例創建一個新的BloomFilte | copy() | BloomFilter |
approximateElementCount | 已添加到Bloom過濾器的元素的數量 | approximateElementCount() | long |
expectedFpp | 返回元素存在的錯誤概率 | expectedFpp() | double |
isCompatible | 確定給定的Bloom篩選器是否與此Bloom篩選器兼容 | isCompatible(BloomFilterthat) | boolean |
putAll | 通過執行的逐位OR將此Bloom過濾器與另一個Bloom過濾器組合 | putAll(BloomFilterthat) | void |
引入依賴
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>23.0</version>
</dependency>測試代碼
private static void GuavaBloomFilter() {
// 創建布隆過濾器對象
BloomFilter bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()),EXPECTED_INSERTIONS,FALSE_PROBABILITY);
// 向過濾器中添加元素
bloomFilter.put("element001");
bloomFilter.put("element003");
// 判斷元素是否存在
System.out.println(bloomFilter.mightContain("element001"));//true
System.out.println(bloomFilter.mightContain("element002"));//false
// 已添加到Bloom過濾器的元素的數量
System.out.println(bloomFilter.approximateElementCount());// 2
// 返回元素存在的錯誤概率
System.out.println(bloomFilter.expectedFpp());
}5.2 Redis實現
- 開源Redisson(RBloomFilter)。
- Redis 4.0 官方提供布隆過濾器插件。
- 通過Redis提供的bitMap自己實現。
5.2.1 開源Redisson方式
Redisson方法
方法名 | 功能 | 參數 | 返回值 |
add | 添加元素 | add(T object) | boolean |
contains | 檢查元素是否存在 | contains(T object) | boolean |
count | 已添加到Bloom過濾器的元素的數量 | count() | long |
getExpectedInsertions | 返回的預期插入元素的個數 | getExpectedInsertions() | long |
getFalseProbability | 返回元素存在的錯誤概率 | getFalseProbability() | double |
getHashIterations | 返回每個元素使用的哈希迭代次數 | getHashIterations() | int |
getSize | 返回此實例所需Redis內存的位數 | getSize() | long |
tryInit | 初始化Bloom篩選器參數 | tryInit(long expectedInsertions, double falseProbability) | boolean |
delete | 刪除對象 | delete() | boolean |
引入依賴
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson</artifactId>
<version>3.22.1</version>
</dependency>測試代碼
private static void RedissonBloomFilter() {
Config config = new Config();
config.useSingleServer().setAddress("redis://" + REDIS_IP + ":" + REDIS_PORT);
config.useSingleServer().setPassword(REDIS_PASSWORD);
// 獲取客戶端
RedissonClient redissonClient = Redisson.create(config);
RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter(BLOOM_FILTER_NAME);
// 初始化布隆過濾器：預期插入量為100000000L,預期錯誤概率為1%
bloomFilter.tryInit(EXPECTED_INSERTIONS, FALSE_PROBABILITY);
// 插入數據
bloomFilter.add("element001");
bloomFilter.add("element003");
// 判斷下面元素是否在布隆過濾器中
System.out.println(bloomFilter.contains("element002"));//false
System.out.println(bloomFilter.contains("element001"));//true
// 已添加到Bloom過濾器的元素的數量
System.out.println(bloomFilter.count());//2
// 預期插入元素的個數
System.out.println(bloomFilter.getExpectedInsertions());//1000000
// 元素存在的錯誤概率
System.out.println(bloomFilter.getFalseProbability());//0.01
// 每個元素使用的哈希迭代次數
System.out.println(bloomFilter.getHashIterations());
// 實例所需Redis內存的位數
System.out.println(bloomFilter.getSize());
}5.2.2 Redis 4.0 官方提供布隆過濾器插件
基礎命令
命令 | 功能 | 參數 |
BF.RESERVE | 創建一個大小為capacity，錯誤率為error_rate的空的Bloom | BF.RESERVE {key} {error_rate} {capacity} [EXPANSION {expansion}] [NONSCALING] |
BF.ADD | 向key指定的Bloom中添加一個元素itom | BF.ADD {key} {item} |
BF.MADD | 向key指定的Bloom中添加多個元案 | BF.MADD {key} {item ...} |
BF.INSERT | 向key指定的Bloom中添加多個元素，添加時可以指定大小和錯誤率，且可以控制在Bloom不存在的時候是否自動創建 | BF.INSERT {key} [CAPACITY {cap}] [ERROR {error}] [EXPANSION {expansion}] [NOCREATE] [NONSCALING] ITEMS {item ...} |
BF.EXISTS | 檢查一個元秦是否可能存在于key指定的Bloom中 | BF.EXISTS {key} {item} |
BF.MEXISTS | 同時檢查多個元素是否可能存在于key指定的Bloom中 | BF.MEXISTS {key} {item ...} |
BF.SCANDUMP | 對Bloom進行增量持久化操作 | BF.SCANDUMP {key} {iter} |
BF.LOADCHUNK | 加載SCANDUMP持久化的Bloom數據 | BF.LOADCHUNK {key} {iter} {data} |
BF.INFO | 查詢key指定的Bloom的信息 | BF.INFO {key} |
BF.DEBUG | 查看BloomFilter的內部詳細信息(如每層的元素個數，錯誤率等) | BF.DEBUG (key} |
引入依賴
<dependency>
<groupId>redis.clients</groupId>
<artifactId>jedis</artifactId>
<version>4.2.0</version>
</dependency>測試代碼
private static void RedisBloomFilter() {
// 建立連接
BloomFilterCommands bloomFilterCommands = new JedisPooled(REDIS_IP, REDIS_PORT, "", REDIS_PASSWORD);
// 構建布隆過濾器參數
BFReserveParams bfReserveParams = new BFReserveParams();
bfReserveParams.expansion(2);
// 創建一個過濾器
String test = bloomFilterCommands.bfReserve(BLOOM_FILTER_NAME, FALSE_PROBABILITY, EXPECTED_INSERTIONS, bfReserveParams);
// 向過濾器中添加元素
bloomFilterCommands.bfAdd(BLOOM_FILTER_NAME, "element001");
bloomFilterCommands.bfAdd(BLOOM_FILTER_NAME, "element003");
// 判斷元素是否存在
System.out.println(bloomFilterCommands.bfExists(BLOOM_FILTER_NAME, "element001"));//true
System.out.println(bloomFilterCommands.bfExists(BLOOM_FILTER_NAME, "element002"));//false
}5.2.3 通過Redis提供的bitMap自己實現
自定義方法
方法名 | 功能 | 參數 | 返回值 |
add | 添加元素 | add(String key, String element, int expireSec) | boolean |
contains | 檢查元素是否存在 | contains(String key, String element) | boolean |
getExpectedInsertions | 返回的預期插入元素的個數 | getExpectedInsertions() | long |
getFalseProbability | 返回元素存在的錯誤概率 | getFalseProbability() | double |
getNumHashFunctions | 返回每個元素使用的哈希迭代次數 | getNumHashFunctions() | int |
getBitmapLength | 返回Bitmap長度 | getBitmapLength() | long |
BloomFilterUtils | 創建Bloom對象 | BloomFilterUtils(long expectedInsertions, double falseProbability) | BloomFilterUtils |
測試代碼
public class BloomFilterUtils {
private static final String BF_KEY_PREFIX = "bf_";
private long numApproxElements;
private double falseProbability;
// hash個數
private int numHashFunctions;
// 數組長度
private int bitmapLength;
private JedisResourcePool jedisResourcePool;
/**
* 構造布隆過濾器。注意：在同一業務場景下，三個參數務必相同
*
* @param numApproxElements 預估元素數量
* @param fpp 可接受的最大誤差
* @param jedisResourcePool Codis專用的Jedis連接池
*/
public BloomFilterUtils(Long numApproxElements, double fpp, JedisResourcePool jedisResourcePool) {
this.numApproxElements = numApproxElements;
this.falseProbability = fpp;
this.jedisResourcePool = jedisResourcePool;
// 數組長度 m = (n * lnp)/ln2^2
bitmapLength = (int) (-numApproxElements * Math.log(fpp) / (Math.log(2) * Math.log(2)));
// hash個數 k = (n / m ) * ln2
numHashFunctions = Math.max(1, (int) Math.round((double) bitmapLength / numApproxElements * Math.log(2)));
}
/**
* 取得預估元素數量
*/
public long getExpectedInsertions() {
return numApproxElements;
}
/**
* 返回元素存在的錯誤概率
*/
public double getFalseProbability() {
return falseProbability;
}
/**
* 取得自動計算的最優哈希函數個數
*/
public int getNumHashFunctions() {
return numHashFunctions;
}
/**
* 取得自動計算的最優Bitmap長度
*/
public int getBitmapLength() {
return bitmapLength;
}
/**
* 計算一個元素值哈希后映射到Bitmap的哪些bit上
*
* @param element 元素值
* @return bit下標的數組
*/
private long[] getBitIndices(String element) {
long[] indices = new long[numHashFunctions];
// 元素 使用MurMurHash3 128位Hash算法轉換值
byte[] bytes = Hashing.murmur3_128()
.hashObject(element, Funnels.stringFunnel(Charset.forName("UTF-8")))
.asBytes();
// 低8位轉Long值
long hash1 = Longs.fromBytes(
bytes[7], bytes[6], bytes[5], bytes[4], bytes[3], bytes[2], bytes[1], bytes[0]
);
// 高8位轉Long值
long hash2 = Longs.fromBytes(
bytes[15], bytes[14], bytes[13], bytes[12], bytes[11], bytes[10], bytes[9], bytes[8]
);
long combinedHash = hash1;
// 雙重哈希進行散列
for (int i = 0; i < numHashFunctions; i++) {
indices[i] = (combinedHash & Long.MAX_VALUE) % bitmapLength;
combinedHash += hash2;
}
return indices;
}
/**
* 插入元素
*
* @param key 原始Redis鍵，會自動加上'bf_'前綴
* @param element 元素值，字符串類型
* @param expireSec 過期時間（秒）
*/
public void add(String key, String element, int expireSec) {
if (key == null || element == null) {
throw new RuntimeException("鍵值均不能為空");
}
String actualKey = BF_KEY_PREFIX.concat(key);
try (Jedis jedis = jedisResourcePool.getResource()) {
try (Pipeline pipeline = jedis.pipelined()) {
// 遍歷元素所有hash結果的bit位置
for (long index : getBitIndices(element)) {
pipeline.setbit(actualKey, index, true);
}
pipeline.syncAndReturnAll();
}
jedis.expire(actualKey, expireSec);
}
}
/**
* 檢查元素在集合中是否（可能）存在
*
* @param key 原始Redis鍵，會自動加上'bf_'前綴
* @param element 元素值，字符串類型
*/
public boolean contains(String key, String element) {
if (key == null || element == null) {
throw new RuntimeException("鍵值均不能為空");
}
String actualKey = BF_KEY_PREFIX.concat(key);
boolean result = false;
try (Jedis jedis = jedisResourcePool.getResource()) {
// 遍歷元素所有hash結果的bit位置
try (Pipeline pipeline = jedis.pipelined()) {
for (long index : getBitIndices(element)) {
pipeline.getbit(actualKey, index);
}
result = !pipeline.syncAndReturnAll().contains(false);
}
}
return result;
}
public static void main(String[] args) {
String path = Path.getCurrentPath() + "/config/zzjodis.properties";
ConfigReadUtil configReadUtil = new ConfigReadUtil(path);
try {
JedisResourcePool jedisResourcePool = RoundRobinJedisPool.
create()
.curatorClient(configReadUtil.getString("jodisZkStr"), 5000)
.zkProxyDir(configReadUtil.getString("zkProxyDir"))
.team(configReadUtil.getString("team"))
.connectionTimeoutMs(configReadUtil.getInt("connectionTimeoutMs"))
.soTimeoutMs(configReadUtil.getInt("soTimeoutMs"))
.appKey(configReadUtil.getString("appKey"))
.password("".equals(configReadUtil.getString("password")) ? null : configReadUtil.getString("password"))
.build();
BloomFilterUtils bloomFilterUtils = new BloomFilterUtils(10000, 0.01, jedisResourcePool);
bloomFilterUtils.add("filter01", "element001", 30 * 60);
System.out.println(bloomFilterUtils.contains("filter01", "element001")); // true
System.out.println(bloomFilterUtils.contains("filter01", "element002")); // false
} catch (Exception e) {
e.printStackTrace();
}
}
}六、布隆過濾器商業運用
6.1 業務場景
在C1看視頻得曝光活動項目中，為了在個人中心頁為擁有在架商品的用戶展示活動入口，需要高效地判斷用戶是否有在架商品。目前存在上億存量用戶和上百萬的在架商品用戶。每次用戶進入個人中心頁時，需要查詢用戶是否有在架商品，以確定是否展示活動入口。然而，直接查詢商品服務會導致大量的重復查詢和增加服務耗時。可以使用布隆過濾器來優化此過程，它只需要幾十MB內存，相比于使用Redis存儲每日在架商品用戶需要幾GB內存，更加高效節省內存消耗。
6.2 布隆過濾器選擇
實現方式 | 儲存位置 | 適用場景 | 備注 |
Guava | 機器 | 單機 | 只需要機器內存不需要其他資源 |
Redisson | redis | 分布式 | 連接Redis即可使用 |
Redis插件 | redis | 分布式 | 需要對redis集群進行設置支持布隆過濾器插件 |
Redis的bitMap | redis | 分布式 | 需要自己實現添加和查詢 |
對于分布式服務環境，Guava方式不適合使用，而Redis插件需要復雜的配置和高成本支持。相比之下，Redisson連接Redis并進行插入和查詢的方式更適合當前場景，因此最終選擇了Redisson方式。
6.3 使用布隆過濾器效果
1、內存占用情況
- 上線初期，我們將符合條件的用戶存入Codis緩存中。這使得內存從1.98GB增長到9.52GB，此次數據量占用了7.54GB的內存。
- 隨后，為進一步優化，我們成功將用戶量縮小了25倍。這使得內存占用降至308.8MB。
- 最終，我們切換到了Redisson方式使用布隆過濾器。這次Redis內存從2.7172GB增長到2.7566GB，而數據量僅占用39.4MB的內存。
使用Codis內存占用情況
插入數據前：
插入數據后：
使用布隆過濾器內存占用情況
插入數據前：
插入數據后：
2、通過使用布隆過濾器減少對商品服務的查詢，從而提升服務性能。之前需要查詢商品服務來判斷用戶商品狀態，但使用布隆過濾器后，減少了這部分服務間的調用耗時，整體流程的耗時減少了大約5ms。
作者介紹
李帥齊，轉轉商業后端開發工程師，目前負責商業C端相關業務系統開發(廣告檢索、計費以及特征工程系統等)。
