快捷導(dǎo)航

Redis BloomFilter實(shí)例講解

更新時(shí)間：2021年09月01日 10:21:45 作者：張鐵牛

這篇文章主要介紹了Redis BloomFilter實(shí)例。BloomFilter不需要存儲(chǔ)key，節(jié)省空間，在某些對(duì)保密要求非常嚴(yán)格的場(chǎng)合有優(yōu)勢(shì)。想要進(jìn)一步了解BloomFilter運(yùn)用實(shí)例的小伙伴可以了解一下這篇文章

1. 簡(jiǎn)介

布隆過(guò)濾器是防止緩存穿透的方案之一。布隆過(guò)濾器主要是解決大規(guī)模數(shù)據(jù)下不需要精確過(guò)濾的業(yè)務(wù)場(chǎng)景，如檢查垃圾郵件地址，爬蟲URL地址去重，解決緩存穿透問(wèn)題等。

布隆過(guò)濾器：在一個(gè)存在一定數(shù)量的集合中過(guò)濾一個(gè)對(duì)應(yīng)的元素，判斷該元素是否一定不在集合中或者可能在集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都比一般的算法要好的多，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。

2. guava 實(shí)現(xiàn)

google的guava工具類已經(jīng)幫我們?cè)旌昧溯喿?，通過(guò)實(shí)例來(lái)感受一下。

2.1 導(dǎo)入依賴

<dependency>
   <groupId>com.google.guava</groupId>
   <artifactId>guava</artifactId>
   <version>30.1.1-jre</version>
</dependency>

2.2 BloomFilterTest

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import lombok.extern.slf4j.Slf4j;

/**
 * 布隆過(guò)濾器簡(jiǎn)單實(shí)現(xiàn)
 * @author ludangxin
 * @date 2021/8/16
 */
@Slf4j
public class BloomFilterTest {
   /**
    * 預(yù)計(jì)要插入元素個(gè)數(shù)
    */
   private static final int SIZE = 1000000;
   /**
    * 誤判率
    */
   private static final double FPP = 0.01;
   /**
    * 布隆過(guò)濾器
    */
   private static final BloomFilter<Integer> BLOOMFILTER = BloomFilter.create(Funnels.integerFunnel(), SIZE, FPP);

   public static void main(String[] args) {
      //插入數(shù)據(jù)
      for (int i = 0; i < 1000000; i++) {
         BLOOMFILTER.put(i);
      }
      int count = 0;
      // 過(guò)濾判斷
      for (int i = 1000000; i < 3000000; i++) {
         if (BLOOMFILTER.mightContain(i)) {
            count++;
            log.info(i + "誤判了");
         }
      }
      log.info("總共的誤判數(shù):" + count);
   }
}

2.3 啟動(dòng)測(cè)試

如上代碼，我們?cè)O(shè)置了0.01的誤差，過(guò)濾判斷時(shí)從1000000到3000000，誤判了2 * 20000000 ≈ 20339 符合預(yù)期。

.....
21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 2999004誤判了
21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 2999045誤判了
21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 2999219誤判了
21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 2999699誤判了
21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 2999753誤判了
21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 2999838誤判了
21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 2999923誤判了
21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 2999928誤判了
21:40:21.529 [main] INFO com.ldx.redisson.controller.BloomFilterTest - 總共的誤判數(shù):20339

2.4 小節(jié)

guava的工具包雖然好用，但是數(shù)據(jù)集是存儲(chǔ)在jvm中的，分布式環(huán)境下依然沒(méi)法使用。

3. redisson 實(shí)現(xiàn)

3.1 導(dǎo)入依賴

<dependency>
   <groupId>org.redisson</groupId>
   <artifactId>redisson-spring-boot-starter</artifactId>
   <version>3.16.1</version>
</dependency>

3.2 BloomFilterWithRedisson

import lombok.RequiredArgsConstructor;
import lombok.extern.slf4j.Slf4j;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

/**
 * redisson 布隆過(guò)濾器實(shí)現(xiàn)
 *
 * @author ludangxin
 * @date 2021/8/16
 */
@Slf4j
@RestController
@RequestMapping("bloomFilter")
@RequiredArgsConstructor
public class BloomFilterWithRedisson {
   private final RedissonClient redissonClient;

   /**
    * 預(yù)計(jì)要插入元素個(gè)數(shù)
    */
   private static final long SIZE = 1000000L;
   /**
    * 誤判率
    */
    private static final double FPP = 0.01;

   /**
    * 自定義布隆過(guò)濾器的 key
    */
   private static final String BLOOM_FILTER_KEY = "bloomFilter";

   /**
    * 向布隆過(guò)濾器中添加數(shù)據(jù), 模擬向布隆過(guò)濾器中添加10億個(gè)數(shù)據(jù)
    */
   @GetMapping
   public void filter() {
     // 獲取布隆過(guò)濾器
      RBloomFilter<Integer> bloomFilter = redissonClient.getBloomFilter(BLOOM_FILTER_KEY);
      // 初始化，容量為100萬(wàn)， 誤判率為0.01
      bloomFilter.tryInit(SIZE, FPP);
      // 模擬向布隆過(guò)濾器中添加100萬(wàn)個(gè)數(shù)據(jù)
      for (int i = 0; i < SIZE; i++) {
          bloomFilter.add(i);
      }
      int count = 0;
      // 過(guò)濾判斷
      for (int i = 1000000; i < 3000000; i++) {
         if (bloomFilter.contains(i)) {
            count++;
            log.info(i + "誤判了");
         }
      }
      log.info("size:" + bloomFilter.getSize());
      log.info("總共的誤判數(shù):" + count);
   }
}