F7z28資訊網——每日最新資訊28at.com

一、背景介紹

在互聯網中，我們經常遇到需要在大量數據中判斷目標數據是否存在的情況。例如，在網絡爬蟲中，我們需要判斷某個網址是否已經被訪問過。為了實現這一功能，通常需要使用一個容器來存儲已訪問過的網址。如果將這些數據直接存儲在磁盤中，每次判斷都要進行磁盤查詢，這將導致大量的IO操作，效率較低。因此，我們希望將這些數據保存在內存中。在數據量較小的情況下，可以使用Redis來存儲這些數據。但是，當數據量超過上千萬時，將會消耗幾GB甚至幾十GB的內存空間。然而，對于僅需要記錄數據是否存在的情況而言，這樣使用大量內存顯然是浪費的。為了解決這個問題，我們可以使用布隆過濾器(Bloom Filter)。布隆過濾器是一種占用空間少且時間效率高的工具。F7z28資訊網——每日最新資訊28at.com

二、認識布隆過濾器

2.1 布隆過濾器簡介

布隆過濾器（Bloom Filter）是1970年由布隆提出的，它實質上是一個很長的二進制向量和一系列隨機映射函數 (Hash函數)。F7z28資訊網——每日最新資訊28at.com

作用：它是一個空間效率高的概率型數據結構，用來告訴你:一個元素一定不存在或者可能存在。F7z28資訊網——每日最新資訊28at.com

2.2 優點

• 相比于其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數（即hash函數的個數）。
• Hash 函數相互之間沒有關系，方便由硬件并行實現。
• 布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。
• 布隆過濾器可以表示全集，其它任何數據結構都不能。

2.3 缺點

• 有誤判率存在。
• 不支持刪除。

2.4 適用場景

• 預防緩存穿透：布隆過濾器快速判斷數據是否存在，避免通過查詢數據庫來判斷數據是否存在。
• 網絡爬蟲：布隆過濾器可以用來去重已經爬取過的URL。
• 郵箱的垃圾郵件過濾。
• 黑白名單。

三、 布隆過濾器原理

3.1 結構

布隆過濾器實現原理就是一個超大位數的數組和多個不同Hash算法函數。假設位數組的長度為 m，哈希函數的個數為 k。如下圖，一個長度16位的數組，3個不同Hash算法函數，數組里面存儲的是 bit 位，只放 0 和 1，初始為 0。F7z28資訊網——每日最新資訊28at.com

不同Hash算法函數F7z28資訊網——每日最新資訊28at.com

F7z28資訊網——每日最新資訊28at.com

4.3 誤判率公式

F7z28資訊網——每日最新資訊28at.com

五、實現方式

5.1 Guava實現

guava是谷歌開源工具類，其中就有能直接實現布隆過濾器的方法，不需要重復造輪子。F7z28資訊網——每日最新資訊28at.com

引入依賴F7z28資訊網——每日最新資訊28at.com

<dependency>    <groupId>com.google.guava</groupId>    <artifactId>guava</artifactId>    <version>23.0</version></dependency>

測試代碼F7z28資訊網——每日最新資訊28at.com

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方法F7z28資訊網——每日最新資訊28at.com

引入依賴F7z28資訊網——每日最新資訊28at.com

<dependency>    <groupId>org.redisson</groupId>    <artifactId>redisson</artifactId>    <version>3.22.1</version></dependency>

測試代碼F7z28資訊網——每日最新資訊28at.com

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 官方提供布隆過濾器插件

基礎命令F7z28資訊網——每日最新資訊28at.com

引入依賴F7z28資訊網——每日最新資訊28at.com

<dependency>        <groupId>redis.clients</groupId>        <artifactId>jedis</artifactId>        <version>4.2.0</version>    </dependency>

測試代碼F7z28資訊網——每日最新資訊28at.com

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自己實現

自定義方法F7z28資訊網——每日最新資訊28at.com

測試代碼F7z28資訊網——每日最新資訊28at.com

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內存，更加高效節省內存消耗。F7z28資訊網——每日最新資訊28at.com

6.2 布隆過濾器選擇

對于分布式服務環境，Guava方式不適合使用，而Redis插件需要復雜的配置和高成本支持。相比之下，Redisson連接Redis并進行插入和查詢的方式更適合當前場景，因此最終選擇了Redisson方式。F7z28資訊網——每日最新資訊28at.com

6.3 使用布隆過濾器效果

1、內存占用情況F7z28資訊網——每日最新資訊28at.com

1. 上線初期，我們將符合條件的用戶存入Codis緩存中。這使得內存從1.98GB增長到9.52GB，此次數據量占用了7.54GB的內存。
2. 隨后，為進一步優化，我們成功將用戶量縮小了25倍。這使得內存占用降至308.8MB。
3. 最終，我們切換到了Redisson方式使用布隆過濾器。這次Redis內存從2.7172GB增長到2.7566GB，而數據量僅占用39.4MB的內存。

使用Codis內存占用情況F7z28資訊網——每日最新資訊28at.com

插入數據前：F7z28資訊網——每日最新資訊28at.com

F7z28資訊網——每日最新資訊28at.com

插入數據后：F7z28資訊網——每日最新資訊28at.com

F7z28資訊網——每日最新資訊28at.com

使用布隆過濾器內存占用情況F7z28資訊網——每日最新資訊28at.com

插入數據前：F7z28資訊網——每日最新資訊28at.com

F7z28資訊網——每日最新資訊28at.com

插入數據后：F7z28資訊網——每日最新資訊28at.com

F7z28資訊網——每日最新資訊28at.com

2、通過使用布隆過濾器減少對商品服務的查詢，從而提升服務性能。之前需要查詢商品服務來判斷用戶商品狀態，但使用布隆過濾器后，減少了這部分服務間的調用耗時，整體流程的耗時減少了大約5ms。F7z28資訊網——每日最新資訊28at.com

F7z28資訊網——每日最新資訊28at.com

作者介紹F7z28資訊網——每日最新資訊28at.com

李帥齊，轉轉商業后端開發工程師，目前負責商業C端相關業務系統開發(廣告檢索、計費以及特征工程系統等)。F7z28資訊網——每日最新資訊28at.com

本文鏈接：http://www.www897cc.com/showinfo-26-81233-0.html布隆過濾器：提高效率與降低成本的秘密

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com

上一篇： 廣州輝龍過濾：談液體過濾布從固液分離過濾的多種應用

下一篇： 詳解基于Spring Boot的WebSocket持久化方案