返回资讯中心
外部精选
软件工程
#开发者实时流

Go 语言概率数据结构包 unsure 发布,实现布隆过滤器等五种结构

来源标题:Probabilistic Data Structures in Go

开发者发布 Go 包 unsure,用概率数据结构以近似答案换取大幅内存节省。该包实现 Bloom filter、Count-min sketch、HyperLogLog、T-digest 和 Top-k 五种结构,每个核心逻辑约 100–300 行代码,仅依赖标准库且速度通常快于其他实现。以 100 万个 8 字节字符串为例,普通集合约占 64 MB,而布隆过滤器更紧凑。

Hacker News 最新mfrw2026/11/14 · 3 天前30 分钟阅读

以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

概率数据结构能针对其处理的数据给出近似答案。集合中是否包含某个特定元素?集合中有多少个不重复的元素?哪些元素出现得最频繁?与集合和频率表这类确定性结构不同,这些答案可能并不精确,但作为交换,你可以大幅降低内存占用。

本文将讨论什么是概率结构、它们如何工作,以及它们能提供什么样的保证。我还会介绍 unsure —— 一个用 Go 实现这些结构的包。它很简单(每个数据结构的核心逻辑只有 100–300 行代码),很快(通常比其他实现快数倍),并且除了标准库之外没有任何依赖。

  • Bloom filter
  • Count-min sketch
  • HyperLogLog
  • T-digest
  • Top-k

Bloom filter 是一个用确定性换取空间的集合。它可以告诉你某个元素肯定不在集合中,或者可能在(这可能是误报)。该过滤器实际上并不存储元素,因此比普通集合紧凑得多。

例如,一个包含 1,000,000 个不同的 8 字节字符串的普通集合大约占用 64 MB。对于同样的字符串,误报率为 1% 的 Bloom filter 只占用 1.24 MB(每个元素约 10 比特)—— 小了 50 倍。过滤器的大小不依赖于元素的大小,因此字符串越长,差距就越大。

Bloom filter 通常驻留在内存中,有助于尽量减少磁盘读取或网络调用等昂贵的 I/O 操作。你检查某个元素是否在过滤器中,如果答案是「否」,就跳过代价高昂的查找。如果答案是「是」,你仍然必须执行查找,因为它可能是误报。

// 用于 1000 个元素、误报率为 1% 的过滤器。
filter := bloom.New(1000, 0.01)
filter.Add([]byte("alice"))
filter.Add([]byte("bob"))
filter.Contains([]byte("alice")) // true
filter.Contains([]byte("carol")) // false(或者,极少数情况下为 true)

过滤器的大小是根据给定的元素数量和误报率设定的。你可以添加更多元素,但误报率会上升。

你可以向 Bloom filter 添加元素,也可以检查元素是否在过滤器中,但你不能删除元素、统计元素数量或遍历它们。

Bloom filter1 是一个由 m 个比特组成的大数组,初始时全部置零。要添加一个元素,你为它计算 k 个哈希值,并将对应位置的 k 个比特置位:

┌──────┐   ┌───────┐
item ──►│ hash │──► h1, h2, ..., hk ──►│ mod m │──► i1, i2, ..., ik
        └──────┘                        └───────┘
                                   i1  i2            ik
┌───┬───┬─▼─┬───┬───┬─▼─┬───┬───┬───┬───┬─▼─┬───┐
│ 0 │ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │ 1 │ 0 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
  0   1   2                              m-1

要检查某个元素是否在过滤器中,你计算同样的 k 个哈希值,并检查这 k 个比特是否全部置位:

                                   i1  i2            ik
┌───┬───┬─▼─┬───┬───┬─▼─┬───┬───┬───┬───┬─▼─┬───┐
│ 1 │ 0 │ 1 │ 0 │ 0 │ 1 │ 1 │ 0 │ 1 │ 0 │ 1 │ 0 │  全部为 1 → 可能在集合中
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 0 │ 1 │ 0 │ 0 │ 0 │ 1 │ 0 │ 1 │ 0 │ 1 │ 0 │  任意为 0 → 肯定不在
└───┴───┴───┴───┴───┴─▲─┴───┴───┴───┴───┴───┴───┘  集合中
                       (!)

这 k 个比特随机分布在整个数组中。当过滤器大于 CPU 缓存时,每次比特访问都可能导致缓存未命中,因此一次查找可能要等待内存 k 次。

Unsure 使用分块 Bloom filter2。比特数组被划分为 512 比特的块,每块与一个 CPU 缓存行的大小相匹配。当你添加或检查元素时,它只被哈希一次:哈希的一部分用于选择块,其余部分用于在该块内选择 k 个比特。每次添加或检查只访问一个缓存行,因此即使过滤器非常大,也能保持快速。

┌──────┐   ┌──► 高 32 位 ──► 块
item ──►│ hash │──► h ───┤   ┌─────────┐
        └──────┘   └──► 低 32 位 ──►│ × salts │──► i1, i2, ..., ik
                                    └─────────┘
     块
┌───────┬───▼───┬───────┬───────┬───────┬───────┐
│   0   │   1   │   2   │   3   │  ...  │  n-1  │
└───────┴───────┴───────┴───────┴───────┴───────┘
        │       │
        └───────┘───────────────────────────────┐
        │                i1  i2            ik   │
        ├───┬───┬─▼─┬───┬───┬─▼─┬───┬───┬───┬───┬─▼─┬───┤
        │ 0 │ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │ 1 │ 0 │
        └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
          0   1   2                             511

在分块 Bloom filter 中,某些块最终会比其他的承载更多元素,这会提高误报率。为了弥补这一点,过滤器需要稍微大一些。与标准 Bloom filter 相比,在 1% 误报率下它多占用约 3% 的内存,0.1% 时多 8%,0.01% 时多 15%。

过滤器使用本地 wyhash3 实现进行哈希。它的性能与 xxh34 大致相同,但实现要简单得多,没有 SIMD 或汇编。

以下是完整基准测试5的摘录,将 unsure 与 bits-and-blooms6(经典 Bloom filter)和 gloom7(分块版本)进行比较(ns/op,越低越好):

10M 元素时每个元素占用的内存比特数(越低越好):

Unsure 比 bits-and-blooms 快约 4 倍,比 gloom 快 2 倍,内存占用比 bits-and-blooms 多 1–8%,比 gloom 少 4–10%。

Count-min sketch 是一个用准确性换取空间的频率表。它告诉你每个元素大约出现了多少次。估计值永远不会小于实际计数,但可能更高。该 sketch 实际上并不存储元素,因此比存储每个元素计数的普通 map 紧凑得多。

例如,一个统计 1,000,000 个不同的 8 字节字符串的普通 map 大约占用 64 MB。对于同样的字符串,估计值在总计数 0.01% 以内(99% 概率)的 count-min sketch 只占用 0.55 MB —— 小了 116 倍。Sketch 的大小不依赖于不同元素的数量或它们的大小,只取决于你选择的准确性。因此,字符串越多或越长,差距就越大。

(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →