Google布隆过滤器与Redis布隆过滤器

一、什么是布隆过滤器？ 布隆过滤器可以用来判断一个元素是否在一个集合中。它的优势是只需要占用很小的内存空间以及有着高效的查询效率

对于布隆过滤器而言，它的本质是一个位数组：位数组就是数组的每个元素都只占用1bit ，并且每个元素只能是0或者1

布隆过滤器除了一个位数组，还有K个哈希函数。当一个元素加入布隆过滤器中的时候，会进行如下操作：

使用K个哈希函数对元素值进行K次计算，得到K个哈希值 根据得到的哈希值，在位数组中把对应下标的值置为1 下图表示有三个hash函数，比如一个集合中有x、y、z三个元素，分别用三个hash函数映射到二进制序列的某些位上，假设我们判断w是否在集合中，同样用三个hash函数来映射，结果发现取得的结果不全为1，则表示w不在集合里面

数组的容量即使再大，也是有限的。那么随着元素的增加，插入的元素就会越多，位数组中被置为1的位置因此也越多，这就会造成一种情况：当一个不在布隆过滤器中的元素，经过同样规则的哈希计算之后，得到的值在位数组中查询，有可能这些位置因为之前其它元素的操作先被置为1了

所以，有可能一个不存在布隆过滤器中的会被误判成在布隆过滤器中。这就是布隆过滤器的一个缺陷。但是，如果布隆过滤器判断某个元素不在布隆过滤器中，那么这个值就一定不在布隆过滤器中。总结就是：

布隆过滤器说某个元素不在，那么一定不在 布隆过滤器说某个元素在，可能会被误判

总结 布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在。

布隆过滤器使用场景: 1 学习Redis时，在某种情况下，可能会出现缓存雪崩和缓存穿透。 缓存穿透：大量请求访问时，Redis没有命中数据，导致请求绕过了Redis缓存，直接去访问数据库了。数据库难以承受大量的请求。 此时便可以使用布隆过滤器来解决。 请求到来时，先用布隆过滤器判断数据是否有效，布隆过滤器可以判断元素一定不存在和可能存在，对于一定不存在的数据，则可以直接丢弃请求。对可能存在的请求，再去访问Redis获取数据，Redis没有时，再去访问数据库。 2 邮箱的垃圾邮件过滤、黑名单等。 3 去重，：比如爬给定网址的时候对已经爬取过的 URL 去重。

二、Google布隆过滤器基本使用

1）、引入依赖

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

2）、BloomFilterService

@Service public class BloomFilterService { @Autowired private UserMapper userMapper; private BloomFilter<Integer> bf; /** * 创建布隆过滤器 * * @PostConstruct：程序启动时候加载此方法 */ @PostConstruct public void initBloomFilter() { List<User> userList = userMapper.selectAllUser(); if (CollectionUtils.isEmpty(userList)) { return; } //创建布隆过滤器(默认3%误差) bf = BloomFilter.create(Funnels.integerFunnel(), userList.size()); for (User user : userList) { bf.put(user.getId()); } } /** * 判断id可能存在于布隆过滤器里面 * * @param id * @return */ public boolean userIdExists(int id) { return bf.mightContain(id); } }

3）、BloomFilterController

@RestController public class BloomFilterController { @Autowired private BloomFilterService bloomFilterService; @RequestMapping("/bloom/idExists") public boolean ifExists(int id) { return bloomFilterService.userIdExists(id); } }

三、Google布隆过滤器与Redis布隆过滤器对比

1）、Google布隆过滤器的缺点

基于JVM内存的一种布隆过滤器 重启即失效 本地内存无法用在分布式场景 不支持大数据量存储 2）、Redis布隆过滤器

可扩展性Bloom过滤器：一旦Bloom过滤器达到容量，就会在其上创建一个新的过滤器 不存在重启即失效或者定时任务维护的成本：基于Google实现的布隆过滤器需要启动之后初始化布隆过滤器 缺点：需要网络IO，性能比Google布隆过滤器低

参考博客：https://blog.csdn.net/qq_40378034/article/details/93774490

redis 布隆过滤器： https://blog.csdn.net/Carty090616/article/details/89086650

简单实现：

import com.google.common.base.Charsets; import com.google.common.hash.Funnel; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.context.annotation.Bean; import org.springframework.context.annotation.Configuration; import org.springframework.data.redis.core.RedisTemplate; import org.springframework.data.redis.serializer.GenericJackson2JsonRedisSerializer; import org.springframework.data.redis.serializer.StringRedisSerializer; /** * 〈Redis配置〉 * * @create 2019/1/22 * @since 1.0.0 */ @Configuration public class RedisConfig { @Autowired private RedisTemplate redisTemplate; @Bean public RedisTemplate redisTemplateInit() { //设置序列化Key的实例化对象 redisTemplate.setKeySerializer(new StringRedisSerializer()); //设置序列化Value的实例化对象 redisTemplate.setValueSerializer(new GenericJackson2JsonRedisSerializer()); redisTemplate.setHashKeySerializer(new StringRedisSerializer()); redisTemplate.setHashValueSerializer(new StringRedisSerializer()); return redisTemplate; } /** * <注册BloomFilterHelper> * * @param * @return com.zy.crawler.config.redis.BloomFilterHelper<java.lang.String> * @author Lifeifei * @date 2019/4/8 13:18 */ @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); } } import com.zy.crawler.config.redis.BloomFilterHelper; import com.zy.crawler.mapper.WbUserMapper; import com.zy.crawler.model.weibo.WbUser; import com.zy.crawler.service.redis.RedisService; import lombok.extern.slf4j.Slf4j; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.boot.CommandLineRunner; import org.springframework.stereotype.Component; import java.util.List; /** * 〈RedisRunner-用于在项目启动时加载需要的redis相关内容〉 * * @create 2019/1/22 * @since 1.0.0 */ @Slf4j @Component public class RedisRunner implements CommandLineRunner { @Autowired private RedisService redisService; @Autowired private WbUserMapper wbUserMapper; @Autowired private BloomFilterHelper bloomFilterHelper; @Override public void run(String... args) throws Exception { log.info("**** RedisRunner ****"); List<WbUser> wbUsers = wbUserMapper.selectListForBloom(); // 初始化布隆过滤器内容 for (WbUser user : wbUsers) { redisService.addByBloomFilter(bloomFilterHelper, "bloom", user.getName()); } } } import com.google.common.base.Preconditions; import com.google.common.hash.Funnel; import com.google.common.hash.Hashing; /** * <布隆过滤器> * * 算法过程： * 1. 首先需要k个hash函数，每个函数可以把key散列成为1个整数 * 2. 初始化时，需要一个长度为n比特的数组，每个比特位初始化为0 * 3. 某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1 * 4. 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。 * * @author Lifeifei * @create 2019/4/4 * @since 1.0.0 */ 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; } } import com.google.common.base.Preconditions; import com.zy.crawler.config.redis.BloomFilterHelper; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.data.redis.core.*; import org.springframework.stereotype.Service; import java.io.Serializable; import java.util.List; import java.util.Set; import java.util.concurrent.TimeUnit; /** * 〈Redis-操作工具类〉 * * @create 2019/1/22 * @since 1.0.0 */ @Service public class RedisService { @Autowired private RedisTemplate 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; } }