当前位置：首页 > 科技 > 软件

布隆过滤器：提高效率与降低成本的秘密

来源：责编：时间：2024-04-03 17:37:48 227观看

导读一、背景介绍在互联网中，我们经常遇到需要在大量数据中判断目标数据是否存在的情况。例如，在网络爬虫中，我们需要判断某个网址是否已经被访问过。为了实现这一功能，通常需要使用一个容器来存储已访问过的网址。如果将这些

一、背景介绍

在互联网中，我们经常遇到需要在大量数据中判断目标数据是否存在的情况。例如，在网络爬虫中，我们需要判断某个网址是否已经被访问过。为了实现这一功能，通常需要使用一个容器来存储已访问过的网址。如果将这些数据直接存储在磁盘中，每次判断都要进行磁盘查询，这将导致大量的IO操作，效率较低。因此，我们希望将这些数据保存在内存中。在数据量较小的情况下，可以使用Redis来存储这些数据。但是，当数据量超过上千万时，将会消耗几GB甚至几十GB的内存空间。然而，对于仅需要记录数据是否存在的情况而言，这样使用大量内存显然是浪费的。为了解决这个问题，我们可以使用布隆过滤器(Bloom Filter)。布隆过滤器是一种占用空间少且时间效率高的工具。

二、认识布隆过滤器

2.1 布隆过滤器简介

布隆过滤器（Bloom Filter）是1970年由布隆提出的，它实质上是一个很长的二进制向量和一系列随机映射函数 (Hash函数)。

作用：它是一个空间效率高的概率型数据结构，用来告诉你:一个元素一定不存在或者可能存在。

2.2 优点

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

2.3 缺点

有误判率存在。
不支持删除。

2.4 适用场景

预防缓存穿透：布隆过滤器快速判断数据是否存在，避免通过查询数据库来判断数据是否存在。
网络爬虫：布隆过滤器可以用来去重已经爬取过的URL。
邮箱的垃圾邮件过滤。
黑白名单。

三、布隆过滤器原理

3.1 结构

布隆过滤器实现原理就是一个超大位数的数组和多个不同Hash算法函数。假设位数组的长度为 m，哈希函数的个数为 k。如下图，一个长度16位的数组，3个不同Hash算法函数，数组里面存储的是 bit 位，只放 0 和 1，初始为 0。

不同Hash算法函数

4.3 误判率公式

五、实现方式

5.1 Guava实现

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

5.2 Redis实现

开源Redisson(RBloomFilter)。
Redis 4.0 官方提供布隆过滤器插件。
通过Redis提供的bitMap自己实现。

5.2.1 开源Redisson方式

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

5.2.2 Redis 4.0 官方提供布隆过滤器插件

基础命令

命令	功能	参数
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}

5.2.3 通过Redis提供的bitMap自己实现

自定义方法

方法名	功能	参数	返回值
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();        }    }}

六、布隆过滤器商业运用

6.1 业务场景

在C1看视频得曝光活动项目中，为了在个人中心页为拥有在架商品的用户展示活动入口，需要高效地判断用户是否有在架商品。目前存在上亿存量用户和上百万的在架商品用户。每次用户进入个人中心页时，需要查询用户是否有在架商品，以确定是否展示活动入口。然而，直接查询商品服务会导致大量的重复查询和增加服务耗时。可以使用布隆过滤器来优化此过程，它只需要几十MB内存，相比于使用Redis存储每日在架商品用户需要几GB内存，更加高效节省内存消耗。

6.2 布隆过滤器选择

实现方式	储存位置	适用场景	备注
Guava	机器	单机	只需要机器内存不需要其他资源
Redisson	redis	分布式	连接Redis即可使用
Redis插件	redis	分布式	需要对redis集群进行设置支持布隆过滤器插件
Redis的bitMap	redis	分布式	需要自己实现添加和查询

对于分布式服务环境，Guava方式不适合使用，而Redis插件需要复杂的配置和高成本支持。相比之下，Redisson连接Redis并进行插入和查询的方式更适合当前场景，因此最终选择了Redisson方式。

6.3 使用布隆过滤器效果

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

上一篇：广州辉龙过滤：谈液体过滤布从固液分离过滤的多种应用

下一篇：详解基于Spring Boot的WebSocket持久化方案

标签：

热门焦点

量化指标是与非：挽救被量化指标扼杀的技术团队

作者 | 刘新翠整理 | 徐杰承本文整理自快狗打车技术总监刘新翠在WOT2023大会上的主题分享，更多精彩内容及现场PPT，请关注51CTO技术栈公众号，发消息【WOT2023PPT】即可直接领取
多线程开发带来的问题与解决方法

使用多线程主要会带来以下几个问题：（一）线程安全问题　　线程安全问题指的是在某一线程从开始访问到结束访问某一数据期间，该数据被其他的线程所修改，那么对于当前线程而言，该线程
这款新兴工具平台，让你的电脑效率翻倍

随着信息技术的发展,我们获取信息的渠道越来越多,但是处理信息的效率却成为一个瓶颈。于是各种工具应运而生,都在争相解决我们的工作效率问题。今天我要给大家介绍一款效率
腾讯盖楼，字节拆墙

来源 | 光子星球撰文 | 吴坤谚编辑 | 吴先之“想重温暴刷深渊、30+技能搭配暴搓到爽的游戏体验吗？一起上晶核，即刻暴打！”曾凭借直播腾讯旗下代理格斗游戏《DNF》一
“又被陈思诚骗了”

作者｜张思齐出品｜众面（ID：ZhongMian_ZM）如今的国产悬疑电影，成了陈思诚的天下。最近大爆电影《消失的她》票房突破30亿断层夺魁暑期档，陈思诚再度风头无两。你可以说陈思诚的
猿辅导与新东方的两种“归途”

作者｜卓心月出品｜零态LT（ID：LingTai_LT）如何成为一家伟大企业？答案一定是对“势”的把握，这其中最关键的当属对企业战略的制定，且能够站在未来看现在，即使这其中的
华为Mate60系列模具曝光：采用硕大圆形后置相机模组+拼接配色方案

据此前多方爆料，今年华为将开始恢复一年双旗舰战略，除上半年推出的P60系列外，往年下半年的Mate系列也将迎来更新，有望在9-10月份带来全新的华为Mate60
iQOO Neo8 Pro即将开售：到手价3099元起安卓性能最强旗舰

5月23日，iQOO如期举行了新品发布会，全新的iQOO Neo8系列也正式与大家见面，包含iQOO Neo8和iQOO Neo8 Pro两个版本，其中标准版搭载高通骁龙8+，而Pro版更
AI艺术欣赏体验会在上海梅赛德斯奔驰中心音乐俱乐部上演

光影交错的镜像世界，虚实幻化的视觉奇观，虚拟偶像与真人共同主持，这些场景都出现在2019世界人工智能大会的舞台上。8月29日至31日，“AI艺术欣赏体验会”在上海

布隆过滤器：提高效率与降低成本的秘密

一、背景介绍

二、认识布隆过滤器

2.1 布隆过滤器简介

2.2 优点

2.3 缺点

2.4 适用场景

三、布隆过滤器原理

3.1 结构

4.3 误判率公式

五、实现方式

5.1 Guava实现

5.2 Redis实现

5.2.1 开源Redisson方式

5.2.2 Redis 4.0 官方提供布隆过滤器插件

5.2.3 通过Redis提供的bitMap自己实现

六、布隆过滤器商业运用

6.1 业务场景

6.2 布隆过滤器选择

6.3 使用布隆过滤器效果

量化指标是与非：挽救被量化指标扼杀的技术团队

多线程开发带来的问题与解决方法

这款新兴工具平台，让你的电脑效率翻倍

腾讯盖楼，字节拆墙

“又被陈思诚骗了”

猿辅导与新东方的两种“归途”

华为Mate60系列模具曝光：采用硕大圆形后置相机模组+拼接配色方案

iQOO Neo8 Pro即将开售：到手价3099元起安卓性能最强旗舰

AI艺术欣赏体验会在上海梅赛德斯奔驰中心音乐俱乐部上演

最新推荐

猜你喜欢

热门推荐

相关资讯

布隆过滤器：提高效率与降低成本的秘密

一、背景介绍

二、认识布隆过滤器

2.1 布隆过滤器简介

2.2 优点

2.3 缺点

2.4 适用场景

三、 布隆过滤器原理

3.1 结构

4.3 误判率公式

五、实现方式

5.1 Guava实现

5.2 Redis实现

5.2.1 开源Redisson方式

5.2.2 Redis 4.0 官方提供布隆过滤器插件

5.2.3 通过Redis提供的bitMap自己实现

六、布隆过滤器商业运用

6.1 业务场景

6.2 布隆过滤器选择

6.3 使用布隆过滤器效果

最新推荐

猜你喜欢

热门推荐

相关资讯

三、布隆过滤器原理