注意：一如既往，我所有的公开写作都是我手动撰写的。 概述 布隆过滤器是一种概率数据结构，它允许你快速且低成本地回答“键 X 是否在这个集合中？”的问题，回答可以是“绝对不是”或“可能是”。你选择一个适合你的工作负载和硬件的假阳性率，将键添加到集合中，然后后续检查它们的存在。布隆过滤器相比于集合的基数使用了少量的内存，并且计算成本非常低。正因为如此，它们常常被用在高性能的数据系统中。例如，数据库可能会保持一个内存中的布隆过滤器，并在实际查找行之前先检查它。这可以节省大量非常缓慢的磁盘 I/O。当我们在 Bluesky 后端中使用布隆过滤器时，这也帮助我们在查询我们 Scylla 数据库时节省了每秒数百万个查询，用于查找区块、静音、标签等。例如，我们可以经常在不访问数据库的情况下回答“用户 X 是否屏蔽用户 Y”的问题。以下是我们布隆过滤器正面命中的最近几天数据：上面的黄色线大约有 1% 的正面命中率，这意味着在 99% 的情况下，我们可以完全跳过对数据库的查询。这对我们扩展网站和以低成本运营网站的能力至关重要。 传统的布隆过滤器 布隆过滤器是一个比特数组和 k 个哈希函数。你在预先选择数组的大小和 k，并希望根据你的工作负载正确调整它，以达到特定的假阳性率。要将一个键添加到集合中，通过 k 个哈希函数运行它，并在每个位置设置比特。要检查一个键是否在集合中，对它进行 k 次哈希并检查位数组中每个结果位置。如果任何比特为零，该键从未添加过。如果所有比特都设置为一，它可能在集合中。这是一个潜在正面的例子：和一个绝对负面的例子：相当简单！ 双哈希 虽然比访问磁盘便宜得多，但对每个键计算 k 个独立哈希仍然对非常高性能的系统来说有点昂贵。2008年，Kirsch 和 Mitzenmacher 写了一篇论文，证明两个哈希可以得到相同的输出。数学超出了我的理解，但如果你将 i-th 位置导出为 (hash_1 + i*hash_2) % n，那么假阳性率实际上与使用 k 个独立哈希相同。呼！bits-and-blooms/bloom 由 Daniel Lemire 维护（他是我一个巨大的灵感来源，你应该买他的书）是一个用 Go 语言编写的出色的双哈希布隆过滤器实现。它运行 128 位的 murmur3 两次以获得四个 64 位值，然后组合它们以生成所有 k 位的位置。我们在 Bluesky 的生产环境中使用这个方案已经很长时间了。对于 Bluesky 后端，每次其中一个进程启动时，我们实际上都会执行 SELECT * FROM blocks, mutes, list items 等操作，并将所有项目添加到布隆过滤器中。实时的 atproto firehose 消费者还在将项目插入到布隆过滤器中（甚至是在进程启动期间），因此如果你不小心，会出现竞争条件。bits-and-blooms 库的问题在于它在内部不是线程安全的，因此我们需要将所有布隆过滤器的访问封装在一个互斥锁中，免得我们遭受数据竞争。pprof 显示，互斥锁争用实际上是启动进程的瓶颈。由于这个原因，单次部署曾经需要 90 分钟才能完全推出！于是我的同事 Jasmine fork 了这个库，并创建了 atomic-bloom，它使用原子 CPU 指令来执行相同的逻辑，但安全且没有互斥锁。这减少了争用，速度比基于互斥锁的方法快得多。我们的部署时间从 90 分钟缩短到约 15 分钟，使我们能够更快地发布并充满信心。太棒了！ 单哈希 我们能否走得更远？对于 Bluesky，答案是否定的。争用是我们最初的问题，而不是哈希函数的数量或其他因素，因此根据阿姆达尔定律，我们没有获得任何进一步的速度提升，导致明显的影响。然而，深入研究并学习新东西仍然很有趣！作为我们对布隆过滤器技术研究的一部分，我们发现了 Lu 等人的这篇论文，使用更多数学来展示如何仅使用单个哈希来实现布隆过滤器。以下是其工作原理的概述： 而不是一个大的比特数组，将其分割为 k 个固定大小的数组分区 每个分区的大小不同，且所有大小都是互质的，这意味着没有两个大小共享一个共同因子 你对给定键进行一次哈希以获得哈希 分区 p 中的比特位置为 hash%size_p（该分区的大小） 由于你有 k 个分区，因此可以从该单个哈希中获取 k 个比特位置 你可以像使用其他布隆过滤器类型一样使用这些 k 个比特位置！ 掌握了这项技术后，我制作了 jcalabro/gloom，这是一个用 Go 语言实现的单哈希布隆过滤器 (OHBF)。在过去的九个月里，它已经在 Bluesky 后端运行了。