SpringBoot+Redis實現布隆過濾器的範例程式碼

2022-03-17 13:00:49

簡述

關於布隆過濾器的詳細介紹，我在這裡就不再贅述一遍了

我們首先知道：BloomFilter使用長度為m bit的位元組陣列，使用k個hash函數，增加一個元素: 通過k次hash將元素對映到位元組陣列中k個位置中，並設定對應位置的位元組為1。查詢元素是否存在: 將元素k次hash得到k個位置，如果對應k個位置的bit是1則認為存在，反之則認為不存在。

Guava 中已經有具體的實現，而在我們實際生產環境中，原生的儲存往往無法滿足我們實際的需求。所以在這時候，就需要我們使用 redis 了。

Redis 安裝 Bloom Filter

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

vi redis.conf
## 增加設定
loadmodule /usr/local/web/redis/RedisBloom-1.1.1/rebloom.so

##redis 重啟
#關閉
./redis-cli -h 127.0.0.1 -p 6379 shutdown
#啟動
./redis-server ../redis.conf &

基本指令

#建立布隆過濾器，並設定一個期望的錯誤率和初始大小
bf.reserve userid 0.01 100000
#往過濾器中新增元素
bf.add userid 'sbc@163.com'
#判斷指定key的value是否在bloomfilter裡存在，存在：返回1，不存在：返回0
bf.exists userid 'sbc@163.com'

結合 SpingBoot

搭建一個簡單的 springboot 框架

方式一

設定

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
        xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>
    <groupId>com.bloom</groupId>
    <artifactId>test-bloomfilter</artifactId>
    <version>1.0-SNAPSHOT</version>
    <parent>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-parent</artifactId>
        <version>1.5.8.RELEASE</version>
        <relativePath/> <!-- lookup parent from repository -->
    </parent>
    <dependencies>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter</artifactId>
        </dependency>
        <dependency>
            <groupId>org.apache.commons</groupId>
            <artifactId>commons-lang3</artifactId>
            <version>3.0.1</version>
        </dependency>
    </dependencies>
</project>

redis本身對布隆過濾器就有一個很好地實現，在 java 端，我們直接匯入 redisson 的 jar包即可

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

將 Redisson範例注入 SpringIOC 容器中

@Configuration
public class RedissonConfig {

    @Value("${redisson.redis.address}")
    private String address;

    @Value("${redisson.redis.password}")
    private String password;

    @Bean
    public Config redissionConfig() {
        Config config = new Config();
        SingleServerConfig singleServerConfig = config.useSingleServer();
        singleServerConfig.setAddress(address);
        if (StringUtils.isNotEmpty(password)) {
            singleServerConfig.setPassword(password);
        }

        return config;
    }

    @Bean
    public RedissonClient redissonClient() {
        return Redisson.create(redissionConfig());
    }
}

組態檔

redisson.redis.address=redis://127.0.0.1:6379
redisson.redis.password=

最後測試我們的布隆過濾器

@SpringBootApplication
public class BloomApplication {
    public static void main(String[] args) {
        ConfigurableApplicationContext context = SpringApplication.run(BloomApplication.class, args);
        RedissonClient redisson = context.getBean(RedissonClient.class);
        RBloomFilter bf = redisson.getBloomFilter("test-bloom-filter");
        bf.tryInit(100000L, 0.03);
        Set<String> set = new HashSet<String>(1000);
        List<String> list = new ArrayList<String>(1000);
      //向布隆過濾器中填充資料，為了測試真實，我們記錄了 1000 個 uuid，另外 9000個作為干擾資料
        for (int i = 0; i < 10000; i++) {
           String uuid = UUID.randomUUID().toString();
          if(i<1000){
            set.add(uuid);
            list.add(uuid);
          }
          
           bf.add(uuid);
        }

        int wrong = 0; // 布隆過濾器誤判的次數
        int right = 0;// 布隆過濾器正確次數
        for (int i = 0; i < 10000; i++) {
            String str = i % 10 == 0 ? list.get(i / 10) : UUID.randomUUID().toString();
            if (bf.contains(str)) {
                if (set.contains(str)) {
                    right++;
                } else {
                    wrong++;
                }
            }
        }

        //right 為1000
        System.out.println("right:" + right);
        //因為誤差率為3%，所以一萬條資料wrong的值在30左右
        System.out.println("wrong:" + wrong);
          //過濾器剩餘空間大小
        System.out.println(bf.count());
    }
}

以上使我們使用 redisson 的使用方式，下面介紹一種比較原始的方式，使用lua指令碼的方式

方式二

bf_add.lua

local bloomName = KEYS[1]
local value = KEYS[2]
local result = redis.call('BF.ADD',bloomName,value)
return result

bf_exist.lua

local bloomName = KEYS[1]
local value = KEYS[2]
 
local result = redis.call('BF.EXISTS',bloomName,value)
return result

@Service
public class RedisBloomFilterService {

    @Autowired
    private RedisTemplate redisTemplate;

    //我們依舊用剛剛的那個過濾器
    public static final String BLOOMFILTER_NAME = "test-bloom-filter";

    /**
     * 向布隆過濾器新增元素
     * @param str
     * @return
     */
    public Boolean bloomAdd(String str) {
        DefaultRedisScript<Boolean> LuaScript = new DefaultRedisScript<Boolean>();
        LuaScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("bf_add.lua")));
        LuaScript.setResultType(Boolean.class);
        //封裝傳遞指令碼引數
        List<String> params = new ArrayList<String>();
        params.add(BLOOMFILTER_NAME);
        params.add(str);
        return (Boolean) redisTemplate.execute(LuaScript, params);
    }

    /**
     * 檢驗元素是否可能存在於布隆過濾器中 * @param id * @return
     */
    public Boolean bloomExist(String str) {
        DefaultRedisScript<Boolean> LuaScript = new DefaultRedisScript<Boolean>();
        LuaScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("bf_exist.lua")));
        LuaScript.setResultType(Boolean.class);
        //封裝傳遞指令碼引數
        ArrayList<String> params = new ArrayList<String>();
        params.add(BLOOMFILTER_NAME);
        params.add(String.valueOf(str));
        return (Boolean) redisTemplate.execute(LuaScript, params);
    }
}

最後我們還是用上面的啟動器執行測試程式碼

@SpringBootApplication
public class BloomApplication {
    public static void main(String[] args) {
        ConfigurableApplicationContext context = SpringApplication.run(BloomApplication.class, args);
        RedisBloomFilterService filterService = context.getBean(RedisBloomFilterService.class);
        Set<String> set = new HashSet<String>(1000);
        List<String> list = new ArrayList<String>(1000);
        //向布隆過濾器中填充資料，為了測試真實，我們記錄了 1000 個 uuid，另外 9000個作為干擾資料
        for (int i = 0; i < 10000; i++) {
            String uuid = UUID.randomUUID().toString();
            if (i < 1000) {
                set.add(uuid);
                list.add(uuid);
            }

            filterService.bloomAdd(uuid);
        }

        int wrong = 0; // 布隆過濾器誤判的次數
        int right = 0;// 布隆過濾器正確次數
        for (int i = 0; i < 10000; i++) {
            String str = i % 10 == 0 ? list.get(i / 10) : UUID.randomUUID().toString();
            if (filterService.bloomExist(str)) {
                if (set.contains(str)) {
                    right++;
                } else {
                    wrong++;
                }
            }
        }

        //right 為1000
        System.out.println("right:" + right);
        //因為誤差率為3%，所以一萬條資料wrong的值在30左右
        System.out.println("wrong:" + wrong);
    }
}

相比而言，個人比較推薦第一種，實現的原理都是差不多，redis 官方已經為我封裝好了執行指令碼，和相關 api，用官方的會更好一點

到此這篇關於SpringBoot+Redis實現布隆過濾器的範例程式碼的文章就介紹到這了,更多相關SpringBoot Redis布隆過濾器內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

SpringBoot+Redis實現布隆過濾器的範例程式碼

目錄

簡述

Redis 安裝 Bloom Filter

基本指令

結合 SpingBoot

方式一

方式二

熱門文章