One Hash Bloom Filter

# One Hash Bloom Filters - Jim Calabro 来源：https://calabro.io/ohbf *注：一如既往，我所有公开文章都是我亲手撰写的。* #### 概述 布隆过滤器（https://en.wikipedia.org/wiki/Bloom_filter）是一种概率型数据结构，能够以快速且低成本的方式回答"**某个键 X 是否在这个集合中？**"这个问题，答案是"**肯定不在**"或"**可能在**"之一。 你可以根据工作负载和硬件条件选择一个可接受的误报率，将键添加到集合中，之后再检查它们是否存在。 布隆过滤器使用的内存量相对于集合基数来说非常小，且计算开销极低。因此，它们在高性能数据系统中被广泛使用。 例如，数据库可能在内存中维护一个布隆过滤器，在查找行时先检查它，再决定是否访问磁盘。这可以节省大量非常缓慢的磁盘 I/O。 我们在 Bluesky（https://bsky.app/）后端的各个地方都使用了布隆过滤器。在查询屏蔽、静音、标签等信息时，它们使我们每秒减少了**数百万次**对 Scylla 数据库的查询。比如，我们经常可以直接回答"**用户 X 是否屏蔽了用户 Y？**"这个问题，而完全不需要访问数据库。 以下是最近几天我们部分布隆过滤器的正命中率：  上面的黄色曲线正命中率大约为 1%，这意味着 99% 的情况下我们可以完全跳过数据库查询。这对我们的网站扩展能力和低成本运维至关重要。 #### 传统布隆过滤器 布隆过滤器是一个位数组和 *k* 个哈希函数。你需要提前选择数组大小和 *k* 的值，并根据工作负载调整到合适的规模，以达到特定的误报率。 要将一个键添加到集合中，用 *k* 个哈希函数处理它，并将每个哈希结果对应位置的位设置为 1。 要检查一个键是否在集合中，将它哈希 *k* 次，检查位数组中每个结果位置。如果任意一个位为 0，则该键从未被添加过。如果所有位都为 1，则它可能在集合中。 这是一个可能的正例：  以及一个确定的负例：  很简单吧！ #### 双重哈希 虽然比访问磁盘**便宜得多**，但对每个键计算 *k* 个独立哈希对于超高性能系统来说仍然有些昂贵。 2008 年，Kirsch 和 Mitzenmacher 发表了一篇论文（https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf），证明了两个哈希就可以达到相同的效果。其中的数学远超我的理解能力，但如果你将第 *i* 个位置推导为 `\(hash_1 + i \* hash_2\) % n`，那么误报率实际上与使用 *k* 个独立哈希相同。太好了！ 由 Daniel Lemire（https://lemire.me/blog/）维护的 bits-and-blooms/bloom（https://github.com/bits-and-blooms/bloom）是一个非常优秀的 Go 语言双重哈希布隆过滤器实现。Daniel 是我非常敬仰的人，你应该买他的书（https://www.amazon.com/dp/B0HF4JT75J）。它对 128 位 murmur3 运行两次，得到四个 64 位值，然后组合生成所有 *k* 个位位置。我们在 Bluesky 的生产环境中使用了很长时间。 在 Bluesky 后端，每当某个进程启动时，我们基本上会执行一次 `SELECT * FROM blocks`、mutes、list items 等查询，然后将所有项目添加到布隆过滤器中。同时还有一个实时的 atproto（https://atproto.com/）firestream 消费者在向布隆过滤器中插入数据（即使在进程启动期间也是如此），因此如果不小心的话就会出现竞态条件。 `bits-and-blooms` 库的问题在于它内部不是线程安全的，所以我们需要用互斥锁（https://pkg.go.dev/sync）包装所有布隆过滤器访问操作，否则就会发生数据竞争。pprof（https://pkg.go.dev/net/http/pprof）显示互斥锁争用实际上是进程启动的瓶颈。曾经一次部署需要 90 分钟才能完全完成！ 所以我的同事 Jasmine（https://jazco.dev/）fork 了这个库并创建了 atomic-bloom（https://github.com/jazware/atomic-bloom），它使用原子（https://pkg.go.dev/sync/atomic）CPU 指令来执行相同的逻辑，但安全且不需要互斥锁。这大大减少了争用，速度比基于互斥锁的方式快得多。我们的部署时间从 90 分钟降到了大约 15 分钟，使我们能够更快、更有信心地发布。太棒了！ #### 单哈希 我们能再进一步吗？ 对于 Bluesky，答案是**不能**。争用是我们最初的问题，而不是哈希函数数量或其他因素，因此根据 Amdahl 定律（https://en.wikipedia.org/wiki/Amdahl%27s_law），我们不会从减少哈希函数数量中获得明显的额外加速。不过，深入探索和学习新知识仍然很有趣！ 在研究布隆过滤器技术的过程中，我们遇到了 Lu 等人的这篇论文（https://yangtonghome.github.io/uploads/One_Hashing.pdf），他们使用**更多数学**证明了如何仅使用单个哈希来实现布隆过滤器。 以下是其工作原理的概述： - 不使用一个大的位数组，而是将其拆分为 *k* 个固定大小的数组分区 - 每个分区的大小不同，且所有大小两两互素（https://en.wikipedia.org/wiki/Coprime_integers），意味着没有任何两个大小除了 1 之外有公共因子 - 你对给定的键哈希一次得到 *hash* - 分区 *p* 中的位位置为 `hash % size_p`（即分区的大小） - 由于你有 *k* 个分区，从单个哈希中你得到 *k* 个位位置 - 你可以像使用其他布隆过滤器类型一样使用这 *k* 个位位置！ 有了这项技术，我编写了 jcalabro/gloom（https://github.com/jcalabro/gloom），一个 Go 语言的单哈希布隆过滤器（OHBF）实现。它已经在 Bluesky 后端运行了 9 个月，表现相当不错。它也被用于我们的高性能同步服务 jetstream（https://github.com/bluesky-social/jetstream）中。 以下是使用示例： ```` package main import ( "fmt" "sync" "github.com/jcalabro/gloom" ) func main() { // 创建一个线程安全的原子布隆过滤器： // - 预期容量为 100 万条目 // - 近似误报率为 1% f := gloom.NewAtomic(1_000_000, 0.01) var wg sync.WaitGroup defer wg.Wait() for i := range 8 { wg.Go(func() { for j := range 100000 { str := fmt.Sprintf("key-%d-%d", i, j) if f.TestString(str) { // 由于该键不在集合中，这总是一个误报 fmt.Printf("found a false positive: %s\n", str) } f.AddString(str) } }) } } ```` 接下来，让我们更详细地了解它在底层是如何工作的。以下是一些 Go 示例代码，展示了我们如何为要检查的给定键选择块索引和 `h`： ```` hash := xxh3.Hash128(key) // 计算 128 位哈希 block := hash.Hi % numBlocks // 高 64 位选择块 h := hash.Lo // 低 64 位是我们要检查的哈希值 ```` 然后，布隆过滤器的检查过程如下：  除了使用单个哈希之外，它还使用了一些有趣的性能优化技巧。 首先，我们将布隆过滤器拆分为许多 64 字节的块，以匹配常见的 CPU 缓存行大小。其次，由于 Go 的分配器不保证这些块的分配是缓存对齐的（https://learn.arm.com/learning-paths/cross-platform/memory-latency/latency-and-cache-alignment/），我们稍微多分配了一些空间，并使用 unsafe（https://pkg.go.dev/unsafe）来确保对齐。实现代码请见这里（https://github.com/jcalabro/gloom/blob/41399c29b47251fe3822e64cbb934c609f7b29c8/bloom.go#L90-L99）。 这两种技术的结合保证了在最坏情况下，一次布隆过滤器查找只会产生一次缓存未命中。很不错！ 还有一个来自 Daniel Lemire 的有趣的优化（https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/），它允许你使用单条 `MUL` 指令（而非需要昂贵除法指令的取模运算）来选择要检查的块。 我要讨论的最后一个有趣优化是 ShardedAtomicFilter（https://github.com/jcalabro/gloom/tree/bf26d4b6e5e9e0a86e48ad444dd4e85740a90ceb#high-throughput-concurrent-writes）。在 Bluesky，我管理着一大群高端裸金属服务器集群。为了从这些系统中榨取最大性能，最好避免多个核心争用同一份数据。`ShardedAtomicFilter` 将写入操作分散到多个底层过滤器分片上，从而降低了争用的可能性。 #### 结语 布隆过滤器（以及 Roaring 位图（https://lemire.me/en/publication/spe2016roaring/））推动了世界的运转（https://bsky.app/profile/jaz.sh/post/3mizi7ns23s2u）。 希望这是一次关于布隆过滤器工作原理的有趣探索。如果你对底层工程细节感兴趣，欢迎在 Bluesky（https://bsky.app/profile/calabro.io/）上关注我，或通过 atproto、RSS 等方式订阅本博客。 另外值得一提的是，我一直在开发一套推动技术前沿的全新可观测性工具。请在 GitHub 上给它加星（https://github.com/microscope-dev/microscope），近期还会有更多讨论，敬请关注！