
Go 语言中的概率数据结构:第二部分
来源标题:Probabilistic data structures in Go, part 2
文章介绍 Go 语言中的概率数据结构,可在牺牲精确度的前提下大幅节省内存。本篇对比介绍了 binary fuse filter、UltraLogLog、log-linear histogram 和 MinHash 四种新结构,并说明其原理与保证,示例均基于 Go 包 unsure。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
概率数据结构针对其处理的数据给出近似的答案。集合中是否包含某个元素?集合中有多少个不重复的元素?一连串数字中的第99百分位数是多少?两个集合有多相似?与确定性结构不同,这些答案可能并不精确,但作为交换,你可以节省大量内存。
之前,我们介绍过以下数据结构:Bloom filter(用于检查元素是否在集合中)、Count-min sketch(用于计数)、HyperLogLog(用于统计不重复元素)、T-digest(用于求分位数)以及 Top-k(用于找出出现频率最高的元素)。
在这篇文章中,我们将讨论其他概率数据结构,并将它们与已经介绍过的结构进行比较。我们会了解它们的工作原理以及它们提供何种保证。
所有示例均使用 unsure —— 一个在 Go 中实现这些结构的包。
Binary fuse filter • UltraLogLog • Log-linear histogram • MinHash
binary fuse filter 是一种用确定性换取空间的集合,类似 Bloom filter¹。它可以告诉你某个元素肯定不在集合中,或者可能在集合中(这可能是误报)。该过滤器不存储元素本身,因此比常规集合紧凑得多。
与 Bloom filter 不同,binary fuse filter 是静态的:你从所有元素一次性构建它,之后无法再添加。作为交换,在相同误报率下,它比 Bloom filter 使用更少的内存。例如,针对 1,000,000 个元素、误报率为 0.39% 的 fuse filter 占用 1.13 MB(每元素 9 bit),而 Bloom filter 占用 1.51 MB(每元素 12 bit)。
这使得 binary fuse filter 非常适合一次写入、多次读取的数据,比如数据库中不可变文件的键集合(用于跳过不包含该键的文件),或者已知不良元素的列表,例如泄露的密码或恶意 URL。
items := [][]byte{[]byte("alice"), []byte("bob")} // An 8-bit filter: 0.39% false positive rate. filter := fuse.New[uint8](slices.Values(items), len(items)) filter.Contains([]byte("alice")) // true filter.Contains([]byte("carol")) // false (or, rarely, true)
指纹类型(New[T] 中的 T)决定了误报率和内存占用:
构造函数接收一个待加入过滤器的元素迭代器,以及预期元素数量(未知时填 0)。该数字仅用于预分配内存,因此良好的估计能让构建更快。
你可以检查某个元素是否在过滤器中,但不能添加或删除元素、统计元素数量或遍历它们。
过滤器² 是一个由 b 位指纹组成的数组(例如 b = 8 对应 uint8)。每个元素被哈希为 64 位值 h,由此得到该元素的指纹 f(从 h 计算出的 b 位)以及数组中的三个位置(单元)。数组的填充方式使得对于每个元素,其三个单元的 XOR 等于 f。
┌──────┐ ┌──► f (b bits) item ──►│ hash │──► h ─────────┤ └──────┘ └──► i0, i1, i2 i0 i1 i2 ┌───┬───┬──▼──┬───┬───┬──▼──┬───┬──▼──┬───┐ │ │ │ F0 │ │ │ F1 │ │ F2 │ │ F0 ^ F1 ^ F2 == f └───┴───┴─────┴───┴───┴─────┴───┴─────┴───┘
要检查某个元素,你计算 h,查找它的三个单元,并将它们的 XOR 与 f 比较。对于集合中的元素,它们总是匹配。对于任何其他元素,XOR 是一个随机的 b 位值,以 2^-b 的概率与 f 匹配。
每次检查读取三个单元,因此对于大型过滤器来说就是三次缓存未命中,而分块 Bloom filter 只需一次。不过,由于这些读取是相互独立的,CPU 可以并发执行,因此检查速度与 Bloom filter 大致相当。
该过滤器使用本地的 wyhash³ 实现进行哈希。它的性能与 xxh34 大致相同,但实现简单得多,不涉及 SIMD 或汇编。
以下是完整基准测试⁵ 的摘录,比较了 unsure 与 xorfilter⁶(论文作者实现的 binary fuse)以及 bloom(unsure 自带的 Bloom filter),均使用 8 位指纹(ns/op,越低越好):
Unsure 与 xorfilter 大小相同(布局一致),检查速度最多快 25%。与 Bloom filter 相比,它最多节省 36% 的内存,检查速度相当或更快,但构建速度最多慢 2.5 倍。
Bloom filter 概述及其工作原理。 ↩︎
Binary Fuse Filters 论文,作者 Thomas Mueller Graf 和 Daniel Lemire,2022 年。 ↩︎
wyhash 参考实现,作者 Wang Yi。 ↩︎
xxHash 参考实现,作者 Yann Collet。 ↩︎
FastFilter/xorfilter,作者 Daniel Lemire。 ↩︎
UltraLogLog 是一种不重复元素计数器,用精度换取空间,类似 HyperLogLog⁷。它告诉你它大致见过多少个不重复元素,无论每个元素出现了多少次。UltraLogLog 不存储元素,因此比常规集合紧凑得多。
UltraLogLog 是一种较新的设计(Otmar Ertl,2024 年),空间利用更高效:在相同误差下,它比 HyperLogLog 少用约 43% 的内存。例如,标准误差为 0.81% 的 HyperLogLog sketch 占用 16 KB,而误差为 0.86% 的 UltraLogLog sketch 仅占用 8 KB。不过,添加、计数和合并操作比 HyperLogLog 慢。
UltraLogLog 的适用场景与 HyperLogLog 相同:统计独立访客、独立搜索查询或数据库列中的不重复值,可能跨多台机器或分片进行。
// Standard error about 0.9% of the true count. sketch := ull.New() sketch.Add([]byte("alice")) sketch.Add([]byte("bob")) sketch.Add([]byte("alice")) sketch.Add([]byte("carol")) sketch.Count() // 3 (approximately)
你可以合并多个 sketch,得到所有 sketch 中不重复元素的总数,而不会重复计算共享的元素。
home := ull.New() // visitors to the home page docs := ull.New() // visitors to the docs // ... home.Merge(docs) home.Count() // visitors to either page
该 sketch 只有一个设置:精度 p,它对应的相对标准误差为 0.782/√(2^p)。默认值为 p=13,在 8 KB 内存下误差为 0.86%,接近常见的 HyperLogLog 默认值(16 KB 下 0.81%)。
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。