关于后端:一篇文章告诉你什么是BloomFilter

40次阅读

共计 6925 个字符，预计需要花费 18 分钟才能阅读完成。

什么是 BloomFilter

布隆过滤器（英语：Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。次要用于判断一个元素是否在一个汇合中。

通常咱们会遇到很多要判断一个元素是否在某个汇合中的业务场景，个别想到的是将汇合中所有元素保存起来，而后通过比拟确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。然而随着汇合中元素的减少，咱们须要的存储空间也会出现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种构造的检索工夫复杂度别离为 $O(n)$，$O(logn)$，$O(1)$。

这个时候，布隆过滤器（Bloom Filter）就应运而生。

布隆过滤器原理

理解布隆过滤器原理之前，先回顾下 Hash 函数原理。

哈希函数

哈希函数的概念是：将任意大小的输出数据转换成特定大小的输入数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值。上面是一幅示意图：

所有散列函数都有如下根本个性：

  • 如果两个散列值是不雷同的（依据同一函数），那么这两个散列值的原始输出也是不雷同的。这个个性是散列函数具备确定性的后果，具备这种性质的散列函数称为 单向散列函数。
  • 散列函数的输出和输入不是惟一对应关系的，如果两个散列值雷同，两个输出值很可能是雷同的，但也可能不同，这种状况称为“散列碰撞（collision）”。

然而用 hash 表存储大数据量时，空间效率还是很低，当只有一个 hash 函数时，还很容易产生哈希碰撞。

布隆过滤器数据结构

BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数组成的。

在初始状态时，对于长度为 m 的位数组，它的所有位都被置为 0，如下图所示：

当有变量被退出汇合时，通过 K 个映射函数将这个变量映射成位图中的 K 个点，把它们置为 1（假设有两个变量都通过 3 个映射函数）。

查问某个变量的时候咱们只有看看这些点是不是都是 1 就能够大概率晓得汇合中有没有它了

  • 如果这些点有任何一个 0，则被查问变量肯定不在；
  • 如果都是 1，则被查问变量很 可能存在

为什么说是可能存在，而不是肯定存在呢？那是因为映射函数自身就是散列函数，散列函数是会有碰撞的。

误判率

布隆过滤器的误判是指多个输出通过哈希之后在雷同的 bit 地位 1 了，这样就无奈判断到底是哪个输出产生的，因而误判的本源在于雷同的 bit 位被屡次映射且置 1。

这种状况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果咱们间接删除这一位的话，会影响其余的元素。(比方上图中的第 3 位)

个性

  • 一个元素如果判断后果为存在的时候元素不肯定存在，然而判断后果为不存在的时候则肯定不存在。
  • 布隆过滤器能够增加元素，然而不能删除元素。因为删掉元素会导致误判率减少。

增加与查问元素步骤

增加元素

  1. 将要增加的元素给 k 个哈希函数
  2. 失去对应于位数组上的 k 个地位
  3. 将这 k 个地位设为 1

查问元素

  1. 将要查问的元素给 k 个哈希函数
  2. 失去对应于位数组上的 k 个地位
  3. 如果 k 个地位有一个为 0，则必定不在汇合中
  4. 如果 k 个地位全副为 1，则可能在汇合中

长处

相比于其它的数据结构，布隆过滤器在空间和工夫方面都有微小的劣势。布隆过滤器存储空间和插入 / 查问工夫都是常数 $O(K)$，另外，散列函数相互之间没有关系，不便由硬件并行实现。布隆过滤器不须要存储元素自身，在某些对窃密要求十分严格的场合有劣势。

布隆过滤器能够示意选集，其它任何数据结构都不能；

毛病

然而布隆过滤器的毛病和长处一样显著。误算率是其中之一。随着存入的元素数量减少，误算率随之减少。然而如果元素数量太少，则应用散列表足矣。

另外，个别状况下不能从布隆过滤器中删除元素。咱们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就能够了。然而要保障平安地删除元素并非如此简略。首先咱们必须保障删除的元素确实在布隆过滤器外面。这一点单凭这个过滤器是无奈保障的。另外计数器回绕也会造成问题。

在升高误算率方面，有不少工作，使得呈现了很多布隆过滤器的变种。

布隆过滤器应用场景和实例

在程序的世界中，布隆过滤器是程序员的一把利器，利用它能够疾速地解决我的项目中一些比拟辣手的问题。

如网页 URL 去重、垃圾邮件辨认、大汇合中反复元素的判断和缓存穿透等问题。

布隆过滤器的典型利用有：

  • 数据库避免穿库。Google Bigtable，HBase 和 Cassandra 以及 Postgresql 应用 BloomFilter 来缩小不存在的行或列的磁盘查找。防止代价昂扬的磁盘查找会大大提高数据库查问操作的性能。
  • 业务场景中判断用户是否浏览过某视频或文章，比方抖音或头条，当然会导致肯定的误判，但不会让用户看到反复的内容。
  • 缓存宕机、缓存击穿场景，个别判断用户是否在缓存中，如果在则间接返回后果，不在则查问 db，如果来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时候能够用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查问缓存，如果没查问到，则穿透到 db。如果不在布隆器中，则间接返回。
  • WEB 拦截器，如果雷同申请则拦挡，避免反复被攻打。用户第一次申请，将申请参数放入布隆过滤器中，当第二次申请时，先判断申请参数是否被布隆过滤器命中。能够进步缓存命中率。Squid 网页代理缓存服务器在 cache digests 中就应用了布隆过滤器。Google Chrome 浏览器应用了布隆过滤器减速平安浏览服务
  • Venti 文档存储系统也采纳布隆过滤器来检测先前存储的数据。
  • SPIN 模型检测器也应用布隆过滤器在大规模验证问题时跟踪可达状态空间。

Coding~

晓得了布隆过滤去的原理和应用场景，咱们能够本人实现一个简略的布隆过滤器

自定义的 BloomFilter

public class MyBloomFilter {

    /**
     * 一个长度为 10 亿的比特位
     */
    private static final int DEFAULT_SIZE = 256 << 22;

    /**
     * 为了升高错误率，应用加法 hash 算法，所以定义一个 8 个元素的质数数组
     */
    private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};

    /**
     * 相当于构建 8 个不同的 hash 算法
     */
    private static HashFunction[] functions = new HashFunction[seeds.length];

    /**
     * 初始化布隆过滤器的 bitmap
     */
    private static BitSet bitset = new BitSet(DEFAULT_SIZE);

    /**
     * 增加数据
     *
     * @param value 须要退出的值
     */
    public static void add(String value) {if (value != null) {for (HashFunction f : functions) {
                // 计算 hash 值并批改 bitmap 中相应地位为 true
                bitset.set(f.hash(value), true);
            }
        }
    }

    /**
     * 判断相应元素是否存在
     * @param value 须要判断的元素
     * @return 后果
     */
    public static boolean contains(String value) {if (value == null) {return false;}
        boolean ret = true;
        for (HashFunction f : functions) {ret = bitset.get(f.hash(value));
            // 一个 hash 函数返回 false 则跳出循环
            if (!ret) {break;}
        }
        return ret;
    }

    /**
     * 模仿用户是不是会员，或用户在不在线。。。*/
    public static void main(String[] args) {for (int i = 0; i < seeds.length; i++) {functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);
        }

        // 增加 1 亿数据
        for (int i = 0; i < 100000000; i++) {add(String.valueOf(i));
        }
        String id = "123456789";
        add(id);

        System.out.println(contains(id));   // true
        System.out.println(""+ contains("234567890"));  //false
    }
}

class HashFunction {

    private int size;
    private int seed;

    public HashFunction(int size, int seed) {
        this.size = size;
        this.seed = seed;
    }

    public int hash(String value) {
        int result = 0;
        int len = value.length();
        for (int i = 0; i < len; i++) {result = seed * result + value.charAt(i);
        }
        int r = (size - 1) & result;
        return (size - 1) & result;
    }
}

What？咱们写的这些早有大牛帮咱们实现，还造轮子，真是浪费时间，No，No，No，咱们学习过程中是能够造轮子的，造轮子自身就是咱们本人对设计和实现的具体落地过程，不仅能进步咱们的编程能力，在造轮子的过程中必定会遇到很多咱们没有思考过的问题，成长看的见~~

理论我的项目应用的时候，领导和我说我的项目肯定要稳固运行，没自信的我放弃了本人的轮子。

Guava 中的 BloomFilter

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>23.0</version>
</dependency>
public class GuavaBloomFilterDemo {public static void main(String[] args) {
        // 后边两个参数：预计蕴含的数据量，和容许的误差值
        BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), 100000, 0.01);
        for (int i = 0; i < 100000; i++) {bloomFilter.put(i);
        }
        System.out.println(bloomFilter.mightContain(1));
        System.out.println(bloomFilter.mightContain(2));
        System.out.println(bloomFilter.mightContain(3));
        System.out.println(bloomFilter.mightContain(100001));

        //bloomFilter.writeTo();}
}

分布式环境中，布隆过滤器必定还须要思考是能够共享的资源，这时候咱们会想到 Redis，是的，Redis 也实现了布隆过滤器。

当然咱们也能够把布隆过滤器通过 bloomFilter.writeTo() 写入一个文件，放入 OSS、S3 这类对象存储中。

Redis 中的 BloomFilter

Redis 提供的 bitMap 能够实现布隆过滤器，然而须要本人设计映射函数和一些细节，这和咱们自定义没啥区别。

Redis 官网提供的布隆过滤器到了 Redis 4.0 提供了插件性能之后才正式退场。布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了弱小的布隆去重性能。

在已装置 Redis 的前提下，装置 RedisBloom，有两种形式

间接编译进行装置

git clone https://github.com/RedisBloom/RedisBloom.git
cd RedisBloom
make     #编译 会生成一个 rebloom.so 文件
redis-server --loadmodule /path/to/rebloom.so   #运行 redis 时加载布隆过滤器模块
redis-cli    # 启动连贯容器中的 redis 客户端验证

应用 Docker 进行装置

docker pull redislabs/rebloom:latest # 拉取镜像
docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest #运行容器
docker exec -it redis-redisbloom bash
redis-cli

应用

布隆过滤器根本指令：

  • bf.add 增加元素到布隆过滤器
  • bf.exists 判断元素是否在布隆过滤器
  • bf.madd 增加多个元素到布隆过滤器，bf.add 只能增加一个
  • bf.mexists 判断多个元素是否在布隆过滤器
127.0.0.1:6379> bf.add user Tom
(integer) 1
127.0.0.1:6379> bf.add user John
(integer) 1
127.0.0.1:6379> bf.exists user Tom
(integer) 1
127.0.0.1:6379> bf.exists user Linda
(integer) 0
127.0.0.1:6379> bf.madd user Barry Jerry Mars
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists user Barry Linda
1) (integer) 1
2) (integer) 0

咱们只有这几个参数，必定不会有误判，当元素逐步增多时，就会有肯定的误判了，这里就不做这个试验了。

下面应用的布隆过滤器只是默认参数的布隆过滤器，它在咱们第一次 add 的时候主动创立。

Redis 还提供了自定义参数的布隆过滤器，bf.reserve 过滤器名 error_rate initial_size

  • error_rate：容许布隆过滤器的错误率，这个值越低过滤器的位数组的大小越大，占用空间也就越大
  • initial_size：布隆过滤器能够贮存的元素个数，当理论存储的元素个数超过这个值之后，过滤器的准确率会降落

然而这个操作须要在 add 之前显式创立。如果对应的 key 曾经存在，bf.reserve 会报错

127.0.0.1:6379> bf.reserve user 0.01 100
(error) ERR item exists
127.0.0.1:6379> bf.reserve topic 0.01 1000
OK

我是一名 Javaer，必定还要用 Java 来实现的，Java 的 Redis 客户端比拟多，有些还没有提供指令扩大机制，笔者已知的 Redisson 和 lettuce 是能够应用布隆过滤器的，咱们这里用 Redisson

public class RedissonBloomFilterDemo {public static void main(String[] args) {Config config = new Config();
        config.useSingleServer().setAddress("redis://127.0.0.1:6379");
        RedissonClient redisson = Redisson.create(config);

        RBloomFilter<String> bloomFilter = redisson.getBloomFilter("user");
        // 初始化布隆过滤器，预计统计元素数量为 55000000，冀望误差率为 0.03
        bloomFilter.tryInit(55000000L, 0.03);
        bloomFilter.add("Tom");
        bloomFilter.add("Jack");
        System.out.println(bloomFilter.count());   //2
        System.out.println(bloomFilter.contains("Tom"));  //true
        System.out.println(bloomFilter.contains("Linda"));  //false
    }
}

扩大

为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器横空出世。论文《Cuckoo Filter：Better Than Bloom》作者将布谷鸟过滤器和布隆过滤器进行了深刻的比照。相比布谷鸟过滤器而言布隆过滤器有以下有余：查问性能弱、空间利用效率低、不反对反向操作（删除）以及不反对计数。

因为应用较少，暂不深刻。

参考与感激

https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

http://www.justdojava.com/2019/10/22/bloomfilter/

https://www.cnblogs.com/cpselvis/p/6265825.html

https://juejin.im/post/5cc5aa7ce51d456e431adac5

本文由 mdnice 多平台公布

正文完
后端
发表至： 后端
2023-06-25
 0
关于后端:复杂环境下落地Service-Mesh的挑战与实践
关于后端:如何生成随机的参数值apipost
关于后端:深入浅出JVM三之HotSpot虚拟机类加载机制
关于后端:分布式锁原理及实现