Posted by on | Featured

Bloom过滤器带来了一种仿佛充满魔力的功能：它只需使用几千字节的内存，就能判断某个元素是否存在于由数十亿个元素组成的集合中。而且无论存储了多少数据，它回答这个问题的速度依然非常快。

这听起来似乎是不可能的。普通的集合结构必须记住所有的元素，因此其内存占用会随着数据量的增加而增长。但Bloom过滤器几乎不对这些元素本身进行任何存储，却仍然能够判断某个元素是否属于该集合。关键在于，它允许自己在某个特定且可控制的范围内出现错误。

其实这并不是魔法，当你自己动手构建一个Bloom过滤器时，就会发现其中的原理其实很简单，你也就能清楚地了解它的局限性和能力范围了。

在本教程中，我们将使用Python从零开始构建一个功能完备的Bloom过滤器，整个过程只需要使用位数组和几个哈希函数而已。通过学习这个教程，你将理解什么是位数组、为什么需要使用多个哈希函数、什么是误报现象、Bloom过滤器有哪些必然遵守的原则，以及如何根据目标错误率来调整过滤器的规模。

目录

Bloom过滤器的真正含义

Bloom过滤器是一种概率数据结构。它的唯一用途就是回答一个问题：“这个元素是否存在于该集合中？”而它只会给出两个答案之一：

  • 肯定不在该集合中。这个答案总是正确的。

  • 可能在这个集合中。这个答案通常也是正确的，但偶尔也会出现错误。

    • 令人惊讶的是，Bloom过滤器在根本不需要存储任何元素信息的情况下就能完成这种判断。普通的集合结构，比如Python中的set或哈希表，都会保存所有存储的元素，因此它们的内存占用会随着元素数量的增加而增长。

    而Bloom过滤器只保留一段固定的位数组。无论你存储的是短字符串、长URL还是整个文件，它的规模都是事先确定好的，并且永远不会改变。

    因此，布隆过滤器其实并不是一种用于存储数据的容器。它更像是一组数据的“指纹”。你无法让它列出其中包含的元素，也无法让它将某个元素退还出来。你只能问它“这个元素是否可能存在于这组数据中？”而对于它的回答“不”，你可以完全信任。

    可以这样简单理解：与其维护一份客人名单，不如用一排电灯开关来代替。当有客人到来时，就根据他们的名字去按下其中几个开关。要确认某人是否真的来了，只需查看这些开关的状态——如果其中有任何一个是关闭的，那就说明那个人肯定没有来；如果所有的开关都是打开的，那么这个人很可能来了，不过也有可能是其他人的名字导致了这些开关被按下。

    这个比喻也能解释为什么人们会选择使用 Bloom 过滤器而不是普通的集合结构。对于一百万个平均长度为50字节的URL来说，普通的集合结构需要占用数十兆字节的内存空间，并且随着URL长度的增加，所需内存也会进一步增加。而同样的数据量使用Bloom过滤器，在1%的错误率下，只需要大约1.2兆字节的内存即可完成存储任务，而且这个成本是固定的，与URL的长度无关。

    当数据量非常大，需要在每台机器上都将其存储在内存中，或者需要存储一些体积较大的数据时，这种节省空间所带来的优势就变得至关重要了。虽然Bloom过滤器会偶尔产生误报，但通常情况下，这种误报带来的损失远小于因此而避免的昂贵查询操作所带来的好处。因为“否定”的结果可以直接跳过耗时的查询过程，而“肯定”的结果也只是触发本来就需要进行的、速度较慢的精确检查而已。

    一个简单的判断标准是：如果你需要得到准确的答案、执行删除操作，或者需要列出存储在其中的所有数据，那就应该使用普通的集合结构；而如果你只需要一个快速、高效的机制来决定是否可以跳过某些耗时的操作，并且这个机制能够可靠地告诉你何时可以这样做，那么Bloom过滤器就是你的最佳选择。

    简史

    这种数据结构是以伯顿·霍华德·布卢姆的名字命名的。他在1970年发表在《ACM通讯》上的一篇论文中首次描述了这一概念，这篇论文的标题是“允许出错的哈希编码中的空间/时间权衡”。

    他举的那个例子非常普通：一个需要将文本进行连字符连接并进行拼写检查的程序，必须会在字典中查找相关的单词，但在1970年那个时候，要在如此有限的内存空间里存储整个字典显然是不现实的。布卢姆的想法就是，通过允许一定数量的错误发生，来换取大幅节省内存空间的好处。正是这种“允许少量错误以节省大量内存”的设计思路，使得这种数据结构在五十多年后的今天，仍然被广泛应用于许多大型系统中。

    Bloom过滤器的应用场景

    如今，你很可能已经使用过基于Bloom过滤器的软件。它们在以下领域发挥着重要作用：

    • 数据库和存储系统： Cassandra、HBase、Bigtable以及许多采用LSM树结构的存储系统，都会为每个磁盘文件配置一个Bloom过滤器。在执行耗时的磁盘读取操作之前，这些系统会先使用过滤器来判断“这个键是否存在于该文件中”；如果结果是“否”，就可以直接跳过这个文件，从而避免进行大量的不必要的读取操作。

    • 安全浏览：早期版本的Google Chrome会将每个URL与一个包含已知危险网站的本地Bloom过滤器进行匹配检查。如果结果为“否”，则表示该网站是安全的，系统就不会发起任何网络请求；而只有当结果为“是”时，才会触发针对完整列表的详细验证。

    • 缓存和内容分发网络：一种常见的做法是，只有在一个资源被请求了至少两次之后，才将其添加到缓存中。Bloom过滤器可以低成本地帮助系统判断“我之前是否已经访问过这个资源”，从而过滤掉那些仅被请求一次的资源请求。

    • 推荐系统：Medium平台就曾使用Bloom过滤器来避免向用户推荐他们已经读过的文章。

    • 网络技术和加密领域：路由器利用Bloom过滤器来识别重复的数据包；而早期的比特币轻量级客户端也使用这种技术来请求相关交易信息，而不需要暴露具体的地址信息。

    其结构始终是相同的。Bloom过滤器会被用来替代那些耗时较长的操作（比如磁盘读写、网络请求或数据库查询），通过这种机制，大部分耗时的检查过程都可以被简化为几次快速的数组读取操作。现在我们就来构建一个Bloom过滤器，看看它是如何工作的。

    核心原理：位数组与哈希函数

    Bloom过滤器的构成分为两部分：

    1. **位数组**：由一系列二进制位组成，所有位的初始值均为0。

    2. **若干个哈希函数**，这些函数能够将任意数据转换为该位数组中的某个具体位置。

    要**添加**一个元素到过滤器中，就需要将该元素通过所有的哈希函数进行处理，从而得到对应的几个位置值，然后将这些位置的位设置为1。

    要**检查**某个元素是否存在于过滤器中，同样需要使用这些哈希函数对该元素进行运算，并查看相应的位置值。如果所有位置的位都是1，那么该元素“很可能”存在于过滤器中；如果哪怕有一个位置的位是0，那么该元素“肯定”不存在于过滤器中。

    其中第二种判断结果才是关键。如果某个位置的位仍然是0，那就说明你从未添加过任何会导致该位置位变为1的元素。因此，Bloom过滤器从不会漏掉那些确实存在于其中的元素。

    以下是用Python实现的完整代码示例：

    import hashlib

class BloomFilter:
    def __init__(self, size, num_hashes):
        self.size = size              # 位数组的长度
        self.num_HASH = num-hash     # 哈希函数的数量
        self_bits = [0] * size        # 所有位的初始值均为0

    将元素转换为位置值

    对于每个要添加的元素，我们需要num-hash个不同的位置值，并且这些位置值需要分布得比较均匀。一种常用的方法是**双重哈希**：首先使用两个不同的哈希函数对元素进行处理，然后将得到的结果相加，从而得到所需的多个位置值。

    def _positions(self, item):
    data = item.encode("utf-8")
    h1 = int.from_bytes(hashlib.sha256(data).digest()[:8], "big")
    h2 = int.from_bytes(hashlib.md5(data).digest()[:8], "big")
    for i in range(self.num_HASH):
        yield (h1 + i * h2) % self.size

    在这个过程中，会发生以下三件事：

    • sha256和md5产生的哈希值都是固定的，对于相同的输入字符串，这两个哈希值的计算结果始终相同；而对于不同的输入字符串，这些哈希值则看起来是随机的。
    • h1 + i * h2这种运算方式会使得每个i对应的最终位置值都不同，因此这些位置值会均匀地分布在位数组中，而不会聚集在一起。
    • % self.size这个操作会将计算得到的结果转换为一个有效的索引值，其范围是从0到size - 1。

    对某个元素应用这种处理方法后，你就能得到num-hash个位置值。这些位置值其实就是该元素在Bloom过滤器中的“指纹”。

    添加与检查元素

    添加元素时，需要将对应位置的位设置为1；而检查元素是否存在时，则需要确认所有这些位置的位是否都为1。

    def add(self, item):
    for idx in self._positions(item):
        self_bits[idx] = 1

def __contains__(self, item):
    return all(self(bits[idx] for idx in self._positions(item))

    定义__contains__这个方法后，我们就可以使用Python中自然的in语法来检查某个元素是否存在于过滤器中。让我们试一试：

    bf = BloomFilter(size=1000, num_hashes=4)
bf.add("alice")
bf.add("bob")

print("alice" in bf)   # True
print("bob" in bf)     # True
print("carol" in bf)   # 几乎总是 False

    "carol"这个元素从未被添加到过滤器中，因此它的四个位中的至少有一个肯定是0，所以过滤器会判断它不存在。这种情况很常见。但请注意“几乎肯定”这个词——正是这种不确定性构成了下一节讨论的重点。

    误报是正常现象

    由于这些位是共享的，当添加了足够多的元素后，那些原本用于编码"carol"的位可能会被其他元素设置为1，即使"carol"本身从未被添加过。在这种情况下，过滤器会错误地判断该元素“可能存在”，而实际上它并不存在。这就是所谓的误报。

    对于初次接触Bloom过滤器的人来说，他们有时会认为这是一种漏洞。但实际上并非如此。这种现象正是使用如此少的内存所必须付出的代价，而且这个问题也是可以调整的。你可以通过在较小的过滤器中添加大量元素来观察这种现象：

    bf = BloomFilter(size=200, num_hashes=4)
    for i in range(100):
    bf.add(f"user-{i}")

    # 这些元素都没有被添加到过滤器中，但其中一些仍会被错误地判断为“存在”：
    false_hits = sum(f"ghost-{i}" in bf for i in range(1000))
    print(falsehits) # 这个数值不为0，说明误报率确实存在

    不过，过滤器在另一种情况下从不会出错。你添加的每一个user-i都会被正确地判断为“存在”，因为添加一个元素会使得它的所有位都变为1，而这些位永远不会被清零。这就是Bloom过滤器始终能够遵守的承诺：

    • “不存在”这个结论永远是正确的。绝对不会出现误判的情况。

    • “存在”这个结论则有可能出错。确实会出现误报的情况。

    正是这种不对称性使得Bloom过滤器如此有用。网页浏览器可以使用Bloom过滤器来记录已知恶意网址，从而能够立即检查所有链接。如果检测结果为“不存在”，那就说明该链接是安全的，无需进一步处理；而如果检测结果为“存在”，那么就需要进行更繁琐的验证。通过使用Bloom过滤器，大多数查询操作只需要进行几次数组读取操作即可完成。

    根据目标误报率来调整过滤器的参数

    误报率取决于三个数值：位数组的大小m、预期要添加的元素数量n，以及使用的哈希函数的数量k。误报率的计算公式如下：

    p = (1 - e^(-k*n/m)) ** k

    你不必猜测这些数值。只要知道要添加的元素数量n以及期望的误报率p，就可以直接计算出最适合的m和k值。

    import math

def optimal_params(n, p):
    m = math.ceil(-n * math.log(p) / (math.log(2) ** 2))  # 所需的比特数
    k = max(1, round((m / n) * math.log(2)))               # 需要使用的哈希函数数量
    return m, k

print(optimal_params(1_000_000, 0.01))  # 结果约为 (9_585_059, 7)

    请仔细理解这个结果。如果要追踪一百万条数据，并且允许1%的错误率，那么你需要大约960万比特，也就是约1.2兆字节的内存，同时还需要使用7个哈希函数。

    如果真的使用一个包含一百万条字符串的集合，所需的成本会高得多，而且这种成本的增加主要与字符串的长度有关。而Bloom过滤器并不关心这些数据的长度，只关心它们的数量而已。

    它不能做什么：删除

    还有一个需要明确指出的限制：你不能通过清零某个数据的比特来删除它，因为这些比特是被其他数据共享的。如果清零了"alice"对应的比特，那么可能也会影响到"bob"所依赖的比特，从而导致"bob"被错误地判断为“不存在”，从而违背了Bloom过滤器“不会产生虚假否定结果”的设计原则。

    如果确实需要实现删除功能，标准的解决方案是使用计数型Bloom过滤器。在这种模式下，每个存储位置都不是一个单独的比特，而是一个用于记录计数的小数值。添加数据时会增加这些计数器的值，删除数据时会减少它们的值；当某个位置的计数器值为正数时，就表示该数据存在于集合中。不过，这种方式会占用更多的内存空间，这也是这种设计常见的权衡。

    整体总结

    以下是我们构建的这个Bloom过滤器的具体结构及所需成本：

    操作类型 成本复杂度
    添加数据 O(k)
    检查数据是否存在 O(k)
    存储空间需求 对于n条数据，大约需要m比特的存储空间，且这个需求与数据的长度无关

    关键要点如下：

    • Bloom过滤器本质上是由一个比特数组和一些哈希函数组成的。添加数据时，会为这些数据分配k比特；检查数据是否存在时，就是判断这k比特是否都被设置为“1”。

    • Bloom过滤器总是会给出“不存在”的正确结果；而“存在”的结果则有可能是误判，这种误判的概率可以通过调整m和k的值来控制。

    • 由于Bloom过滤器只存储数据的“指纹”信息，而不是数据本身，因此它的体积很小，运行速度也非常快；同时，它也会自动忘记这些数据的具体内容。

    • 如果不使用计数型Bloom过滤器，它是无法实现删除功能的，因为各个比特是共享的。

    下次当系统告诉你“这个数据肯定不在缓存中，可以直接跳过查找”或者“这个数据可能是已知的数据，让我再核实一下”时，你就可以清楚地知道：其背后其实只是通过一系列比特、一些哈希函数，以及一个经过精心设计的容错机制来达到这种判断效果的。

    如果你喜欢通过自己动手构建数据结构来学习它们，而不是死记硬背，那么我开发的IWTLP这个实践平台正是非常适合你的。在这个平台上，Bloom过滤器就是数据工程学习模块中其中一个可供自己动手实现的练习项目。

Tags:
Comments are closed.