一、 什么是布隆过滤器

介绍布隆过滤器之前，先介绍一下哈希函数，我们在Java中的HashMap，HashSet也接触过hashcode()这个函数。

哈希函数指将哈希表中元素的关键键值通过一定的函数关系映射为元素存储位置的函数。

哈希函数的特点：

• 如果根据同一个哈希函数得到的哈希值不同，那么这两个哈希值的原始输入值肯定不同
• 如果根据同一个哈希函数得到的两个哈希值相等，两个哈希值的原始输入值有可能相等，有可能不相等

布隆过滤器实际上是一个非常长的二进制向量(bitmap)和一系列随机哈希函数。

布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
Bloom Filter（BF）是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。
它是一个判断元素是否存在集合的快速的概率算法。Bloom Filter有可能会出现错误判断，但不会漏掉判断。也就是Bloom Filter判断元素不再集合，那肯定不在。如果判断元素存在集合中，有一定的概率判断错误。因此，Bloom Filter”不适合那些“零错误的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter比其他常见的算法（如hash，折半查找）极大节省了空间。

优点：

• 布隆过滤器存储空间和插入/查询时间都是常数
• Hash函数相互之间没有关系，方便由硬件并行实现
• 布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势
• 布隆过滤器可以表示全集，其它任何数据结构都不能

缺点：

• 有一定的误判率

常见的补救办法是建立一个小的白名单，存储那些可能被误判的元素。但是如果元素数量太少，使用散列表足矣。

• 一般情况下不能从布隆过滤器中删除元素。

我们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加1， 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面，这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

二、布隆过滤器的作用

布隆过滤器可以用于检索一个元素是否在一个集合中，常用于解决如下问题

• 解决Redis缓存穿透
• 邮件过滤，使用布隆过滤器来做邮件黑名单过滤
• 解决视频推荐过的不再推荐

三、布隆过滤器的基本原理

布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。

检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。

Bloom Filter跟单哈希函数Bit-Map不同之处在于：Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应。从而降低了冲突的概率。

步骤：

• 首先，建立一个二进制向量，并将所有位设置为0。
• 然后，选定K个散列函数，用于对元素进行K次散列，计算向量的位下标。
• 添加元素：当添加一个元素到集合中时，通过K个散列函数分别作用于元素，生成K个值作为下标，并将向量的相应位设置为1。
• 检查元素：如果要检查一个元素是否存在集合中，用同样的散列方法，生成K个下标，并检查向量的相应位是否全部是1。如果全为1，则该元素很可能在集合中；否则（只要有1个或以上的位为0），该元素肯定不在集合中。

四、在Spring Boot中集成Redisson实现布隆过滤器

4.1 添加maven依赖

不再需要spring-boot-starter-data-redis依赖，但是都添加也不会报错

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

4.2 配置yml

https://www.jianshu.com/p/00ddb0187468

4.3 配置RedissonConfig

https://www.jianshu.com/p/00ddb0187468

4.4 工具类BloomFilterUtil

import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.stereotype.Component;

import javax.annotation.Resource;

/**
 * @Author: huangyibo
 * @Date: 2022/7/25 17:21
 * @Description:
 */

@Component
public class BloomFilterUtil {

    @Resource
    private RedissonClient redissonClient;

    /**
     * 创建布隆过滤器
     *
     * @param filterName         过滤器名称
     * @param expectedInsertions 预测插入数量
     * @param falsePositiveRate  误判率
     */
    public <T> RBloomFilter<T> create(String filterName, long expectedInsertions, double falsePositiveRate) {
        RBloomFilter<T> bloomFilter = redissonClient.getBloomFilter(filterName);
        bloomFilter.tryInit(expectedInsertions, falsePositiveRate);
        return bloomFilter;
    }
}

4.5 编写service实现层

其它层正常编写即可，与之前并无差别，此处不再展示

import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.cache.annotation.CacheEvict;
import org.springframework.cache.annotation.CachePut;
import org.springframework.cache.annotation.Cacheable;
import org.springframework.stereotype.Service;

import javax.annotation.PostConstruct;
import javax.annotation.Resource;
import java.util.List;
import java.util.concurrent.TimeUnit;

/**
 * @Author: huangyibo
 * @Date: 2022/7/25 18:44
 * @Description:
 */

@Service
public class UserServiceImpl {

    // 预期插入数量
    static long expectedInsertions = 200L;
    // 误判率
    static double falseProbability = 0.01;

    // 非法请求所返回的JSON
    static String illegalJson = "[\"com.company.springboot.entity.User\",{\"id\":null,\"userName\":\"null\",\"sex\":null,\"age\":null}]";

    private RBloomFilter<Long> bloomFilter = null;

    @Resource
    private BloomFilterUtil bloomFilterUtil;

    @Resource
    private RedissonClient redissonClient;

    @Resource
    private UserMapper userMapper;

    @PostConstruct // 项目启动的时候执行该方法，也可以理解为在spring容器初始化的时候执行该方法
    public void init() {
        // 启动项目时初始化bloomFilter
        List<User> userList = this.list();
        bloomFilter = bloomFilterUtil.create("idWhiteList", expectedInsertions, falseProbability);
        for (User user : userList) {
            bloomFilter.add(user.getId());
        }
    }

    @Cacheable(cacheNames = "user", key = "#id", unless = "#result==null")
    public User findById(Long id) {
        // bloomFilter中不存在该key,为非法访问
        if (!bloomFilter.contains(id)) {
            System.out.println("所要查询的数据既不在缓存中，也不在数据库中，为非法key");
            /**
             * 设置unless = "#result==null"并在非法访问的时候返回null的目的是不将该次查询返回的null使用
             * RedissonConfig-->RedisCacheManager-->RedisCacheConfiguration-->entryTtl设置的过期时间存入缓存。
             *
             * 因为那段时间太长了，在那段时间内可能该非法key又添加到bloomFilter，比如之前不存在id为1234567的用户，
             * 在那段时间可能刚好id为1234567的用户完成注册，使该key成为合法key。
             *
             * 所以我们需要在缓存中添加一个可容忍的短期过期的null或者是其它自定义的值,使得短时间内直接读取缓存中的该值。
             *
             * 因为Spring Cache本身无法缓存null，因此选择设置为一个其中所有值均为null的JSON，
             */
            redissonClient.getBucket("user::" + id, new StringCodec()).set(illegalJson, new Random().nextInt(200) + 300, TimeUnit.SECONDS);
            return null;
        }
        // 不是非法访问，可以访问数据库
        System.out.println("数据库中得到数据*****");
        return userMapper.selectById(id);
    }

    // 先执行方法体中的代码，成功执行之后删除缓存
    @CacheEvict(cacheNames = "user", key = "#id")
    public boolean delete(Long id) {
        // 删除数据库中具有的数据,就算此key从此之后不再出现，也不能从布隆过滤器删除
        return userMapper.deleteById(id) == 1;
    }

    // 如果缓存中先前存在，则更新缓存;如果不存在，则将方法的返回值存入缓存
    @CachePut(cacheNames = "user", key = "#user.id")
    public User update(User user) {
        userMapper.updateById(user);
        // 新生成key的加入布隆过滤器，此key从此合法,因为该更新方法并不更新id,所以也不会产生新的合法的key
        bloomFilter.add(user.getId());
        return user;
    }

    @CachePut(cacheNames = "user", key = "#user.id")
    public User insert(User user) {
        userMapper.insert(user);
        // 新生成key的加入布隆过滤器，此key从此合法
        bloomFilter.add(user.getId());
        return user;
    }

}

注意：
redisson利用redis存储，布隆过滤器生成数组，但是长度限制为 4 294 967 296 ，但是根据布隆过滤器的原理来看，生成的数组长度是没有限制的，判断应该是redis String类型最大是512M所导致的限制。

五、在Spring Boot中集成RedisTemplate实现布隆过滤器

首先是pom.xml文件

加入我们这次使用redis & BloomFilter 的核心依赖包

<!--使用Redis-->
<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>

<!--借助guava的布隆过滤器-->
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.1-jre</version>
</dependency>

5.2 配置yml

spring:
  redis:
    database: 3
    host: 127.0.0.1
    port: 6379
    password: 12345
    jedis.pool.max-idle: 100
    jedis.pool.max-wait: -1ms
    jedis.pool.min-idle: 2
    timeout: 2000ms

5.3 RedisConfig.class

如果是一般的使用redis存字符串的话，使用StringRedisTemplate，就不需要配置序列化。

但是咱们这里使用的是RedisTemplate<String, Object> redisTemplate ，存储的是对象，所以为了防止存入的对象值在查看的时候不显示乱码，就需要配置相关的序列化（其实我们存的bit结构数据，布隆过滤器存值分分钟都是百万级别的，会因为数据量太大redis客户端也没办法显示，不过不影响使用）。

import com.fasterxml.jackson.annotation.JsonAutoDetect;
import com.fasterxml.jackson.annotation.PropertyAccessor;
import com.fasterxml.jackson.databind.ObjectMapper;
import com.google.common.base.Charsets;
import com.google.common.hash.Funnel;
import org.springframework.cache.CacheManager;
import org.springframework.cache.annotation.EnableCaching;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.data.redis.cache.RedisCacheManager;
import org.springframework.data.redis.connection.RedisConnectionFactory;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.data.redis.serializer.Jackson2JsonRedisSerializer;

/**
 * @Author: huangyibo
 * @Date: 2022/7/25 19:00
 * @Description:
 */

@Configuration
@EnableCaching
public class RedisConfig {

    @Bean
    public CacheManager cacheManager(RedisConnectionFactory connectionFactory) {

        RedisCacheManager redisCacheManager = RedisCacheManager.create(connectionFactory);

        return redisCacheManager;
    }

    @Bean
    public RedisTemplate<String, Object> redisTemplate(RedisConnectionFactory factory) {
        RedisTemplate<String, Object> redisTemplate = new RedisTemplate<String, Object>();
        redisTemplate.setConnectionFactory(factory);

        Jackson2JsonRedisSerializer jackson2JsonRedisSerializer = new
                Jackson2JsonRedisSerializer(Object.class);
        ObjectMapper om = new ObjectMapper();
        om.setVisibility(PropertyAccessor.ALL, JsonAutoDetect.Visibility.ANY);
        om.enableDefaultTyping(ObjectMapper.DefaultTyping.NON_FINAL);
        jackson2JsonRedisSerializer.setObjectMapper(om);
        //序列化设置 ，这样计算是正常显示的数据，也能正常存储和获取
        redisTemplate.setKeySerializer(jackson2JsonRedisSerializer);
        redisTemplate.setValueSerializer(jackson2JsonRedisSerializer);
        redisTemplate.setHashKeySerializer(jackson2JsonRedisSerializer);
        redisTemplate.setHashValueSerializer(jackson2JsonRedisSerializer);

        return redisTemplate;
    }

    @Bean
    public StringRedisTemplate stringRedisTemplate(RedisConnectionFactory factory) {
        StringRedisTemplate stringRedisTemplate = new StringRedisTemplate();
        stringRedisTemplate.setConnectionFactory(factory);
        return stringRedisTemplate;
    }


    //初始化布隆过滤器，放入到spring容器里面
    @Bean
    public BloomFilterHelper<String> initBloomFilterHelper() {
        return new BloomFilterHelper<>((Funnel<String>) (from, into) -> into.putString(from, Charsets.UTF_8).putString(from, Charsets.UTF_8), 1000000, 0.01);
    }

}

5.4 BloomFilterHelper .calss：

import com.google.common.base.Preconditions;
import com.google.common.hash.Funnel;
import com.google.common.hash.Hashing;

/**
 * @Author: huangyibo
 * @Date: 2022/7/25 18:59
 * @Description:
 */

public class BloomFilterHelper<T> {

    private int numHashFunctions;

    private int bitSize;

    private Funnel<T> funnel;

    public BloomFilterHelper(Funnel<T> funnel, int expectedInsertions, double fpp) {
        Preconditions.checkArgument(funnel != null, "funnel不能为空");
        this.funnel = funnel;
        // 计算bit数组长度
        bitSize = optimalNumOfBits(expectedInsertions, fpp);
        // 计算hash方法执行次数
        numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
    }

    public int[] murmurHashOffset(T value) {
        int[] offset = new int[numHashFunctions];

        long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();
        int hash1 = (int) hash64;
        int hash2 = (int) (hash64 >>> 32);
        for (int i = 1; i <= numHashFunctions; i++) {
            int nextHash = hash1 + i * hash2;
            if (nextHash < 0) {
                nextHash = ~nextHash;
            }
            offset[i - 1] = nextHash % bitSize;
        }

        return offset;
    }

    /**
     * 计算bit数组长度
     */
    private int optimalNumOfBits(long n, double p) {
        if (p == 0) {
            // 设定最小期望长度
            p = Double.MIN_VALUE;
        }
        int sizeOfBitArray = (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
        return sizeOfBitArray;
    }

    /**
     * 计算hash方法执行次数
     */
    private int optimalNumOfHashFunctions(long n, long m) {
        int countOfHash = Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
        return countOfHash;
    }
}

5.5 RedisBloomFilter.class

然后是具体的布隆过滤器配合redis使用的 方法类

import com.google.common.base.Preconditions;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.stereotype.Component;

/**
 * @Author: huangyibo
 * @Date: 2022/7/25 19:02
 * @Description:
 */

@Component
public class RedisBloomFilter<T> {

    @Autowired
    private RedisTemplate<String, T> redisTemplate;

    /**
     * 根据给定的布隆过滤器添加值
     */
    public <T> void addByBloomFilter(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
        Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");
        int[] offset = bloomFilterHelper.murmurHashOffset(value);
        for (int i : offset) {
            System.out.println("key : " + key + " " + "value : " + i);
            redisTemplate.opsForValue().setBit(key, i, true);
        }
    }

    /**
     * 根据给定的布隆过滤器判断值是否存在
     */
    public <T> boolean includeByBloomFilter(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
        Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");
        int[] offset = bloomFilterHelper.murmurHashOffset(value);
        for (int i : offset) {
            System.out.println("key : " + key + " " + "value : " + i);
            if (!redisTemplate.opsForValue().getBit(key, i)) {
                return false;
            }
        }
        return true;
    }

}

六、在Spring Boot中使用lua脚本的集成RedisTemplate实现布隆过滤器

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);
    }
}

参考：
https://blog.csdn.net/dreaming9420/article/details/124153422

https://developer.aliyun.com/article/951745

https://www.cnblogs.com/woshixiangshang/p/11412474.html

https://blog.csdn.net/wuliang20/article/details/122874716

https://blog.csdn.net/qq_14855971/article/details/123650368