布隆过滤器原理和使用场景

简介: 布隆过滤器(Bloom Filter)是一种高效的空间节省型数据结构,用于判断元素是否存在于集合中。它通过多个哈希函数将元素映射到位数组,查询时检查对应位是否全为1。优点是空间效率高,缺点是有一定误判率。典型应用场景包括缓存穿透防护、垃圾邮件过滤、黑名单管理及去重等。Java实现中使用BitSet和自定义哈希函数,而Guava和Redis也提供了布隆过滤器的实现。

1.什么是布隆过滤器

Bloom Filter 会使用一个较大的 bit 数组来保存所有的数据,数组中的每个元素都只占用 1 bit ,并且每个元素只能是 0 或者 1(代表 false 或者 true),用于检索元素是否存在于大集合中的数据结构。

缺点是:有一定的错误识别率

2.原理介绍

核心原理:

  • 数据结构:二进制数组+多个哈希函数组成
  • 添加元素:通过多个哈希函数计算得到多个位数组位置,将这些位置设为1
  • 查询元素:进行相同的哈希计算,判断数组中每个位置的元素是否都为1,如果都为1,则可能存在,如果有一个值不为1,则一定不存在。

布隆过滤器原理.png

不同的字符串可能哈希出来的位置相同,这种情况我们可以适当增加位数组大小或者调整我们的哈希函数。

综上,我们可以得出:布隆过滤器说某个元素存在,小概率会误判。布隆过滤器说某个元素不在,那么这个元素一定不在。

3.使用场景

主要是两种场景:

  • 判断给定数据是否存在
    • 缓存穿透防护(拦截不存在的数据请求,避免频繁查询数据库)
    • 邮箱垃圾邮件过滤(判断一个邮件地址是否在垃圾邮件列表中)
    • 黑名单功能(判断一个IP或者手机号等是否在黑名单中)
  • 去重
    • 爬虫URL去重(爬给定网址时对已爬过的URL去重)
    • 对巨量QQ号、订单号去重
    • 抖音推荐功能,推荐的视频不重复

4.具体实现(java手写)

了解了布隆过滤器的原理,可以手动实现一个,关键步骤有:

  • 一个合适大小的位数组
  • 几个不同的哈希函数
  • 添加元素到位数组的方法实现
  • 查询方法,即判断元素是否在位数组的方法实现

直接贴一个代码案例:

import java.util.BitSet;

public class MyBloomFilter {
   

    /**
     * 位数组的大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;
    /**
     * 通过这个数组可以创建 6 个不同的哈希函数
     */
    private static final int[] SEEDS = new int[]{
   3, 13, 46, 71, 91, 134};

    /**
     * 位数组。数组中的元素只能是 0 或者 1
     */
    private BitSet bits = new BitSet(DEFAULT_SIZE);

    /**
     * 存放包含 hash 函数的类的数组
     */
    private SimpleHash[] func = new SimpleHash[SEEDS.length];

    /**
     * 初始化多个包含 hash 函数的类的数组,每个类中的 hash 函数都不一样
     */
    public MyBloomFilter() {
   
        // 初始化多个不同的 Hash 函数
        for (int i = 0; i < SEEDS.length; i++) {
   
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    /**
     * 添加元素到位数组
     */
    public void add(Object value) {
   
        for (SimpleHash f : func) {
   
            bits.set(f.hash(value), true);
        }
    }

    /**
     * 判断指定元素是否存在于位数组
     */
    public boolean contains(Object value) {
   
        boolean ret = true;
        for (SimpleHash f : func) {
   
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    /**
     * 静态内部类。用于 hash 操作!
     */
    public static class SimpleHash {
   

        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
   
            this.cap = cap;
            this.seed = seed;
        }

        /**
         * 计算 hash 值
         */
        public int hash(Object value) {
   
            int h;
            return (value == null) ? 0 : Math.abs((cap - 1) & seed * ((h = value.hashCode()) ^ (h >>> 16)));
        }

    }
}

5.中间件实现

Guava实现的布隆过滤器

Guava 中布隆过滤器的实现算是比较权威的,缺陷是只能单机使用。要想在分布式场景使用,需要用redis的布隆过滤器。

具体代码实现可以自行搜索

Redis的布隆过滤器

Redis官网推荐了一个 RedisBloom 作为 Redis 布隆过滤器的 Module,地址:https://github.com/RedisBloom/RedisBloom

除此之外,还有其他模块的布隆过滤器。

基础操作命令

命令 作用 示例
BF.ADD 向布隆过滤器添加单个元素,若key不存在则自动创建(默认参数:error_rate=0.01, capacity=100)。 BF.ADD user_filter "user:1001"
BF.MADD 批量添加多个元素到布隆过滤器。 BF.MADD user_filter "user:1002" "user:1003"
BF.EXISTS 判断单个元素是否可能存在于过滤器中(返回1可能存在,0一定不存在)。 BF.EXISTS user_filter "user:1001"
BF.MEXISTS 批量判断多个元素是否存在。 BF.MEXISTS user_filter "user:1001" "invalid_user"

实际使用:

127.0.0.1:6379> BF.ADD myFilter java
(integer) 1
127.0.0.1:6379> BF.ADD myFilter javag
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter java
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter javag
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter github
(integer) 0
相关文章
|
监控 JavaScript 前端开发
|
数据采集 存储 缓存
SpringBoot与布隆过滤器的完美邂逅:高效防护大规模数据的奇妙结合【实战】
SpringBoot与布隆过滤器的完美邂逅:高效防护大规模数据的奇妙结合【实战】
844 0
|
存储 缓存 NoSQL
在Java中实现redis缓存中的布隆过滤器
在Java中实现redis缓存中的布隆过滤器
657 0
|
8月前
|
数据采集 JSON 网络协议
淘宝评论api调用常见问题以及解决方案?
淘宝评论 API(核心为taobao.item.reviews.get)调用常见问题集中在权限、签名、限流、参数、数据、网络、解析、合规八大类,以下按问题类型逐一说明现象、原因、解决方案与最佳实践,附错误码速查。
|
负载均衡 Kubernetes 网络协议
注册中心如何选型?Eureka、Zookeeper、Nacos怎么选
这是小卷对分布式系统架构学习的第9篇文章,继续探讨注册中心的原理及选型。文章详细介绍了Eureka、Nacos的工作机制与特点,并对比了Eureka、Nacos、Consul和Zookeeper在一致性协议、健康检查、负载均衡等方面的差异。最后根据不同的应用场景给出了注册中心的选型建议,帮助读者理解如何选择最适合的注册中心。
1678 100
|
存储 缓存 负载均衡
如何设计一个注册中心?以Zookeeper为例
本文介绍了分布式系统中注册中心的设计与工作原理,重点讲解了Zookeeper作为注册中心的实现。注册中心需具备服务注册、注销、心跳检测、服务查询等功能,确保高可用性。Zookeeper通过层次命名空间和znode存储数据,支持服务注册与发现,并采用发布-订阅模式通知消费者服务变更。然而,Zookeeper存在选举期间不可用的问题,不太适合作为注册中心,因其CP模型优先保证一致性而非可用性。
895 78
|
消息中间件 中间件 Kafka
分布式事务最全详解 ,看这篇就够了!
本文详解分布式事务的一致性及实战解决方案,包括CAP理论、BASE理论及2PC、TCC、消息队列等常见方案,助你深入理解分布式系统的核心技术。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
分布式事务最全详解 ,看这篇就够了!
|
消息中间件 负载均衡 Java
如何设计一个分布式配置中心?
这篇文章介绍了分布式配置中心的概念、实现原理及其在实际应用中的重要性。首先通过一个面试场景引出配置中心的设计问题,接着详细解释了为什么需要分布式配置中心,尤其是在分布式系统中统一管理配置文件的必要性。文章重点分析了Apollo这一开源配置管理中心的工作原理,包括其基础模型、架构模块以及配置发布后实时生效的设计。此外,还介绍了客户端与服务端之间的交互机制,如长轮询(Http Long Polling)和定时拉取配置的fallback机制。最后,结合实际工作经验,分享了配置中心在解决多台服务器配置同步问题上的优势,帮助读者更好地理解其应用场景和价值。
1079 18
|
监控 搜索推荐 Java
Java 多线程最新实操技术与应用场景全解析:从基础到进阶
本文深入探讨了Java多线程的现代并发编程技术,涵盖Java 8+新特性,如CompletableFuture异步处理、Stream并行流操作,以及Reactive编程中的Reactor框架。通过具体代码示例,讲解了异步任务组合、并行流优化及响应式编程的核心概念(Flux与Mono)。同时对比了同步、CompletableFuture和Reactor三种实现方式的性能,并总结了最佳实践,帮助开发者构建高效、扩展性强的应用。资源地址:[点击下载](https://pan.quark.cn/s/14fcf913bae6)。
763 3
|
消息中间件 算法 调度
分布式系统学习10:分布式事务
本文是小卷关于分布式系统架构学习系列的第13篇,重点探讨了分布式事务的相关知识。随着业务增长,单体架构拆分为微服务后,传统的本地事务无法满足需求,因此需要引入分布式事务来保证数据一致性。文中详细介绍了分布式事务的必要性、实现方案及其优缺点,包括刚性事务(如2PC、3PC)和柔性事务(如TCC、Saga、本地消息表、MQ事务、最大努力通知)。同时,还介绍了Seata框架作为开源的分布式事务解决方案,提供了多种事务模式,简化了分布式事务的实现。
1040 5