布隆过滤器 课程研究报告

导语：这次报告内容为布隆过滤器，对于布隆过滤器进行一个较为全面的介绍，从背景及意义、算法描述、优缺点、应用场景等角度对布隆过滤器进行描述。并且对于分布式布隆过滤器我也想给大家介绍一下

1 布隆过滤器

1.1 什么是布隆过滤器

布隆过滤器是一种节省空间的概率数据结构，可用于各种问题。它们已成功用于web缓存、聚合函数的完全分散计算、高效内存的基因组组装、分布式系统中的集合协调、区块链架构中更高效的块传播以及许多其他方面。它实际上是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中。
尽管布隆过滤器有很多变体，但大多数都有相同的核心思想：布隆过滤器可以快速验证一个项目是否存在于一个空间要求最低的集合中。这是通过牺牲一些精度以获得更少的空间来实现的。例如，当检查布隆过滤器中是否存在元素时，可能会得到一些假阳性匹配，但绝不会得到假阴性匹配。换句话说，布隆过滤器可以证明某个项不在集合中，或者它可能在集合中。

1.2 背景及其意义

在现实业务中，我们会遇到很多判断一个元素是否在某个集合中的业务场景，一般想到的解决方法是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为$O(n)$，$O(logn)$，$O(1)$，这个时候，布隆过滤器（Bloom Filter）就应运而生。
其本质是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

1.3 布隆过滤器算法原理

为了更好地理解这是如何工作的，让我们来了解一下算法：
1、定义了k个独立的哈希函数（其中“k”是使用的哈希函数）
2、定义了一个m位长的零位数组。
3、当向bloom过滤器插入元素时，我们将元素散列k次，如第一步中所定义。每个哈希值用于指向零位数组的索引（在步骤2定义）。然后将这些索引处的位从0切换到1，如图1所示。

1.3.1 插入查找（无误报）

假设我们在bloom过滤器中插入了几个元素，现在我们要检查其中是否有特定元素。为此，我们只需将元素散列k次并查找给定的索引。如果bloom过滤器中k个索引之一的位为零，我们可以得出结论，给定元素从未插入bloom过滤器。换句话说，我们总是可以知道某个元素是否不在集合中，即bloom过滤器中不会出现误报。

1.3.2 检查集合是否存在（可能误报）

当我们想检查集合中是否存在元素时，情况就有点不同了。这是一种可能导致误报的查询为了更好地理解为什么会出现这种情况，让我们看看图2。

我们有元素Y和Z以及三个哈希函数来将值映射到bloom过滤器。让我们假设Y的结果散列为{11，6，1}，Z的结果散列为{5，2，9}。然后，我们将给定索引的所有位切换为一位。如果有人想验证Y或Z是否真的存在于集合中，就会得到一个肯定的结果，这是因为Y和Z的所有索引都是一。然而，这有一个问题。如果有另一个元素，我们称之为X，它碰巧有{1，5，2}作为散列，那么将得到一个误报。{1，5，2}处的位已经是1，但我们从未将X插入bloom过滤器。因此，我们无法知道X是否真的插入到bloom过滤器中。

1.4 优缺点

布隆过滤器具有以下几个优点：由于存储的是二进制数据，所以占用的空间很小；它的插入和查询速度是非常快的，时间复杂度是O（K）；并且保密性很好，因为本身不存储任何原始数据，只有二进制数据。人们可以使用哈希表来实现同样的事情，而不需要bloom过滤器的概率特性，但bloom过滤器提供的最小空间要求使其成为许多问题的有用数据结构。
但是也存在以下一些缺点：由于此为概率型数据结构，可能不准确，只能确定某元素一定不存在或者可能存在，不能确定某元素真的存在删除困难，由于映射的K个点中可能出现多个元素共用的情况，删除的过程中，这几个点的变化可能会涉及其他值的变化，所以不易删除

2 分布式布隆过滤器

2.1 独特的布隆过滤器映射

分布式布隆过滤器是一种概率数据结构，适用于需要以节省空间和时间的方式快速同步的分布式系统。实现这一点的方法非常简单：每个节点在与另一个节点交互时，都会发送一个具有唯一映射的bloom过滤器，而不是向不同的节点发送相同的bloom过滤器。当我们这样做时，一个元素复制到另一个节点的概率略有变化

2.2 分布式结构布隆过滤器缺失元素的概率

现在，我们计算N个节点不区分缺失元素的概率：

N在本例中是正在联系的其他节点的数量。这个小小的变化有一些有趣的含义。我们的bloom过滤器突然被允许有很高的误报率，这意味着相对于集合n的大小，bloom过滤器的大小m要小得多。当我们使用不同映射的bloom过滤器联系其他n个节点时，所有节点对元素的误报命中率随每个添加的节点而降低。

参考文献

[1] Lum Ramabaja,Arber Avdullahu The Distributed Bloom Filter 2019，October
[2] D. Guo, M. Li, Set Reconciliation via Counting Bloom Filters, IEEE Transactions on Knowledge and Data Engineering 25 (2013) 2367–2380.
[3] M. T. Goodrich, M. Mitzenmacher, Invertible Bloom Lookup Tables (2011).