在互联网中，我们经常遇到需要在大量数据中判断目标数据是否存在的情况。例如，在网络爬虫中，我们需要判断某个网址是否已经被访问过。为了实现这一功能，通常需要使用一个容器来存储已访问过的网址。如果将这些数据直接存储在磁盘中，每次判断都要进行磁盘查询，这将导致大量的IO操作，效率较低。因此，我们希望将这些数据保存在内存中。在数据量较小的情况下，可以使用Redis来存储这些数据。但是，当数据量超过上千万时，将会消耗几GB甚至几十GB的内存空间。然而，对于仅需要记录数据是否存在的情况而言，这样使用大量内存显然是浪费的。为了解决这个问题，我们可以使用布隆过滤器(Bloom Filter)。布隆过滤器是一种占用空间少且时间效率高的工具。
布隆过滤器（Bloom Filter）是1970年由布隆提出的，它实质上是一个很长的二进制向量和一系列随机映射函数 (Hash函数)。
作用：它是一个空间效率高的概率型数据结构，用来告诉你:一个元素一定不存在或者可能存在。
布隆过滤器实现原理就是一个超大位数的数组和多个不同Hash算法函数。假设位数组的长度为 m，哈希函数的个数为 k。如下图，一个长度16位的数组，3个不同Hash算法函数，数组里面存储的是 bit 位，只放 0 和 1，初始为 0。
不同Hash算法函数
guava是谷歌开源工具类，其中就有能直接实现布隆过滤器的方法，不需要重复造轮子。
方法名 | 功能 | 参数 | 返回值 |
put | 添加元素 | put(T object) | boolean |
mightContain | 检查元素是否存在 | mightContain(T object) | boolean |
copy | 根据此实例创建一个新的BloomFilte | copy() | BloomFilter |
approximateElementCount | 已添加到Bloom过滤器的元素的数量 | approximateElementCount() | long |
expectedFpp | 返回元素存在的错误概率 | expectedFpp() | double |
isCompatible | 确定给定的Bloom筛选器是否与此Bloom筛选器兼容 | isCompatible(BloomFilterthat) | boolean |
putAll | 通过执行的逐位OR将此Bloom过滤器与另一个Bloom过滤器组合 | putAll(BloomFilterthat) | void |
引入依赖
<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>23.0</version></dependency>测试代码
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());}Redisson方法
方法名 | 功能 | 参数 | 返回值 |
add | 添加元素 | add(T object) | boolean |
contains | 检查元素是否存在 | contains(T object) | boolean |
count | 已添加到Bloom过滤器的元素的数量 | count() | long |
getExpectedInsertions | 返回的预期插入元素的个数 | getExpectedInsertions() | long |
getFalseProbability | 返回元素存在的错误概率 | getFalseProbability() | double |
getHashIterations | 返回每个元素使用的哈希迭代次数 | getHashIterations() | int |
getSize | 返回此实例所需Redis内存的位数 | getSize() | long |
tryInit | 初始化Bloom筛选器参数 | tryInit(long expectedInsertions, double falseProbability) | boolean |
delete | 删除对象 | delete() | boolean |
引入依赖
<dependency> <groupId>org.redisson</groupId> <artifactId>redisson</artifactId> <version>3.22.1</version></dependency>测试代码
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());}基础命令
命令 | 功能 | 参数 |
BF.RESERVE | 创建一个大小为capacity，错误率为error_rate的空的Bloom | BF.RESERVE {key} {error_rate} {capacity} [EXPANSION {expansion}] [NONSCALING] |
BF.ADD | 向key指定的Bloom中添加一个元素itom | BF.ADD {key} {item} |
BF.MADD | 向key指定的Bloom中添加多个元案 | BF.MADD {key} {item ...} |
BF.INSERT | 向key指定的Bloom中添加多个元素，添加时可以指定大小和错误率，且可以控制在Bloom不存在的时候是否自动创建 | BF.INSERT {key} [CAPACITY {cap}] [ERROR {error}] [EXPANSION {expansion}] [NOCREATE] [NONSCALING] ITEMS {item ...} |
BF.EXISTS | 检查一个元秦是否可能存在于key指定的Bloom中 | BF.EXISTS {key} {item} |
BF.MEXISTS | 同时检查多个元素是否可能存在于key指定的Bloom中 | BF.MEXISTS {key} {item ...} |
BF.SCANDUMP | 对Bloom进行增量持久化操作 | BF.SCANDUMP {key} {iter} |
BF.LOADCHUNK | 加载SCANDUMP持久化的Bloom数据 | BF.LOADCHUNK {key} {iter} {data} |
BF.INFO | 查询key指定的Bloom的信息 | BF.INFO {key} |
BF.DEBUG | 查看BloomFilter的内部详细信息(如每层的元素个数，错误率等) | BF.DEBUG (key} |
引入依赖
<dependency> <groupId>redis.clients</groupId> <artifactId>jedis</artifactId> <version>4.2.0</version> </dependency>测试代码
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}自定义方法
方法名 | 功能 | 参数 | 返回值 |
add | 添加元素 | add(String key, String element, int expireSec) | boolean |
contains | 检查元素是否存在 | contains(String key, String element) | boolean |
getExpectedInsertions | 返回的预期插入元素的个数 | getExpectedInsertions() | long |
getFalseProbability | 返回元素存在的错误概率 | getFalseProbability() | double |
getNumHashFunctions | 返回每个元素使用的哈希迭代次数 | getNumHashFunctions() | int |
getBitmapLength | 返回Bitmap长度 | getBitmapLength() | long |
BloomFilterUtils | 创建Bloom对象 | BloomFilterUtils(long expectedInsertions, double falseProbability) | BloomFilterUtils |
测试代码
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(); } }}在C1看视频得曝光活动项目中，为了在个人中心页为拥有在架商品的用户展示活动入口，需要高效地判断用户是否有在架商品。目前存在上亿存量用户和上百万的在架商品用户。每次用户进入个人中心页时，需要查询用户是否有在架商品，以确定是否展示活动入口。然而，直接查询商品服务会导致大量的重复查询和增加服务耗时。可以使用布隆过滤器来优化此过程，它只需要几十MB内存，相比于使用Redis存储每日在架商品用户需要几GB内存，更加高效节省内存消耗。
实现方式 | 储存位置 | 适用场景 | 备注 |
Guava | 机器 | 单机 | 只需要机器内存不需要其他资源 |
Redisson | redis | 分布式 | 连接Redis即可使用 |
Redis插件 | redis | 分布式 | 需要对redis集群进行设置支持布隆过滤器插件 |
Redis的bitMap | redis | 分布式 | 需要自己实现添加和查询 |
对于分布式服务环境，Guava方式不适合使用，而Redis插件需要复杂的配置和高成本支持。相比之下，Redisson连接Redis并进行插入和查询的方式更适合当前场景，因此最终选择了Redisson方式。
1、内存占用情况
- 上线初期，我们将符合条件的用户存入Codis缓存中。这使得内存从1.98GB增长到9.52GB，此次数据量占用了7.54GB的内存。
- 随后，为进一步优化，我们成功将用户量缩小了25倍。这使得内存占用降至308.8MB。
- 最终，我们切换到了Redisson方式使用布隆过滤器。这次Redis内存从2.7172GB增长到2.7566GB，而数据量仅占用39.4MB的内存。
使用Codis内存占用情况
插入数据前：
插入数据后：
使用布隆过滤器内存占用情况
插入数据前：
插入数据后：
2、通过使用布隆过滤器减少对商品服务的查询，从而提升服务性能。之前需要查询商品服务来判断用户商品状态，但使用布隆过滤器后，减少了这部分服务间的调用耗时，整体流程的耗时减少了大约5ms。
作者介绍
李帅齐，转转商业后端开发工程师，目前负责商业C端相关业务系统开发(广告检索、计费以及特征工程系统等)。
本文链接：http://www.28at.com/showinfo-26-81233-0.html布隆过滤器：提高效率与降低成本的秘密
声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com
Copyright © 2016-2023 天津谷骐科技有限公司 版权所有 sitemap.xml
违法及侵权请联系：2376512515@qq.com 津ICP备18001702号
津公网安备 12010102000574号
