Ristretto z/bbloom 深度解析:Go 语言 bitset 布隆过滤器的实现原理与实战应用
Ristretto z/bbloom 深度解析:Go 语言 bitset 布隆过滤器的实现原理与实战应用
导读
bbloom 是 Ristretto 仓库 z 子包中内置的一个基于真正「位图(bitset)」实现的 Go 布隆过滤器(Bloom Filter),它既是 Ristretto 缓存淘汰策略 TinyLFU 中"doorkeeper"门卫组件的底层支撑,也可以脱离缓存单独使用,用于海量数据的快速判重场景。本文以 z/README.md 为主体,结合 z/bbloom.go 的源码实现与 z/bbloom_test.go 的测试用例,完整讲解它的安装、API 用法、参数计算原理、位运算实现细节,以及它在 policy.go 中的真实调用链,读完即可在自己的 Go 项目中直接落地使用。
bbloom 是什么
bbloom 是一个为 Go 语言设计的快速布隆过滤器。与许多用 []bool 切片模拟位图的实现不同,bbloom 使用真正的 []uint64 位图(bitset),每一位都对应过滤器中的一个哈希位置,因此内存占用极小。
原文档中对该包定位的说明是:
package implements a fast bloom filter with real 'bitset' and JSONMarshal/JSONUnmarshal to store/reload the Bloom filter.
即:提供真实的 bitset 存储,并通过 JSONMarshal / JSONUnmarshal 实现布隆过滤器的持久化保存与恢复。
一个重要的历史背景(继承自原文档):bbloom 最初是为了强化一个网站日志数据库而开发的,并针对如下日志条目格式做过专门测试优化:
2014/%02i/%02i %02i:%02i:%02i /info.html
不过该过滤器对任何形式的条目都同样适用,并非只能处理这种日志格式。最初的哈希函数采用改进的 Berkeley DB sdbm 哈希(为小字符串优化),后来发现 SipHash-2-4(由 Jean-Philippe Aumasson 和 Daniel J. Bernstein 提出的快速短输入伪随机函数,Go 版本由 Dmitry Chestnyk 移植)速度与之相当,因此后续版本以 SipHash 一系哈希作为补充方案。
在 Ristretto 中的定位:TinyLFU 的 doorkeeper
在深入 API 之前,先说明它在当前仓库中的真实身份。在 policy.go 中,tinyLFU 结构体持有两个核心成员:
type tinyLFU struct {
freq *cmSketch
door *z.Bloom
incrs int64
resetAt int64
}
func newTinyLFU(numCounters int64) *tinyLFU {
return &tinyLFU{
freq: newCmSketch(numCounters),
door: z.NewBloomFilter(float64(numCounters), 0.01),
resetAt: numCounters,
}
}
这里 door *z.Bloom 就是 bbloom 的实例,作为 TinyLFU 的 doorkeeper 使用:当一个 key 第一次出现时,先把它写入布隆过滤器(门卫位);只有已经出现在门卫中的 key,其访问频率才会被计入 count-min sketch 计数器(见 policy.go 的 Increment 逻辑)。当 incrs 达到 resetAt 时触发 reset(),此时门卫位图被 Clear() 清零、计数器减半。因此 bbloom 的 AddIfNotHas、Has、Clear 三个方法直接决定了 TinyLFU 频率估计的准确性,进而影响 Ristretto 的命中率与准入/驱逐决策——这正是它在缓存库中的核心价值。
安装与测试
安装
原文档给出的安装方式面向独立使用场景:
go get github.com/AndreasBriese/bbloom
需要说明的是:在当前 Ristretto 仓库中,该实现已经以内嵌形式存在于 z 子包,模块路径为 github.com/dgraph-io/ristretto/v2/z,无需单独安装即可通过 z.NewBloomFilter 使用。若要在自己的项目中引入整个 Ristretto,参考仓库根目录 README.md 的方式执行:
go get github.com/dgraph-io/ristretto/v2
测试
原文档要求进入 bbloom 目录,准备 words.txt 词表文件后运行基准测试:
go test -bench=.
当前仓库对应的测试位于 z/bbloom_test.go,测试用 32 字节随机数据填充 65536(2^16)个条目,TestMain 中会打印:
Benchmarks relate to 2**16 OP. --> output/65536 op/ns
其中三个测试/基准用例分别验证:
TestM_NumberOfWrongs:统计在NewBloomFilter(7*2^16, 7)配置下的误报(false positive)数量;TestM_JSON:先JSONMarshal导出、再JSONUnmarshal恢复后,重新插入 65536 个条目应得到完全一致的计数结果(require.Equal(t, shallBe, cnt2)),验证序列化的无损性;BenchmarkM_New/BenchmarkM_Clear/BenchmarkM_Add/BenchmarkM_Has:分别测量构造、清空、添加、查询的耗时。
在仓库根目录直接运行:
go test -bench=. -run '^$' ./z
即可复现针对 z 包的基准结果。
API 使用详解
原文档中的用法示例基于原始库 bbloom.New(...) 的 API 形态;当前仓库 z/bbloom.go 已将同一实现移植为包内 API,入口函数名为 NewBloomFilter,且 Add / Has 接收的入参是 uint64 哈希值(而不是原始库中的 []byte)。下面给出两者对应的完整用法。
创建布隆过滤器
import (
"github.com/dgraph-io/ristretto/v2/z"
)
// 为 65536 个条目、1% 误报率创建过滤器
bf := z.NewBloomFilter(float64(1<<16), float64(0.01))
// 或者显式指定过滤器大小为 650000 bit、每个哈希使用 7 个位置
bf = z.NewBloomFilter(float64(650000), float64(7))
NewBloomFilter(params ...float64) 接受两个参数,语义由第二个参数的值决定(源码见 z/bbloom.go):
| 第二参数取值 | 含义 | 内部处理 |
|---|---|---|
< 1 |
误报率(false positive rate) | 调用 calcSizeByWrongPositives 反推所需位图大小与哈希位置数 |
>= 1 |
每个条目使用的哈希位置数(locs) | 第一个参数直接作为位图大小(bit 数) |
calcSizeByWrongPositives(z/bbloom.go)使用的正是经典布隆过滤器容量公式:
size := -1 * numEntries * math.Log(wrongs) / math.Pow(0.69314718056, 2)
locs := math.Ceil(0.69314718056 * size / numEntries)
其中 0.69314718056 ≈ ln 2。第一个公式计算在目标误报率下需要的位图总位数,第二个公式计算最优哈希函数个数(每个条目写入的位数量)。
最小过滤器大小:自动对齐为 512 bit
getSize(z/bbloom.go)保证最小哈希集合大小为 512(即 [4]uint64,原文档明确说明该下限会被自动设置):
func getSize(ui64 uint64) (size uint64, exponent uint64) {
if ui64 < uint64(512) {
ui64 = uint64(512)
}
size = uint64(1)
for size < ui64 {
size <<= 1
exponent++
}
return size, exponent
}
也就是说,实际位图大小会被向上取整到 2 的幂,且至少为 512 bit。取整后的大小存入 Bloom 结构体的 size(减 1 后作为位掩码)与 sizeExp(指数),shift 则为 64 - exponent,用于后续把 64 位哈希拆成高、低两半。
添加与查询
当前仓库版本接收的是预先算好的 uint64 哈希值,哈希计算可复用 z.MemHash(即 Go runtime 的 memhash,见 z/rtutil.go,AES 指令可用时等价于 aeshash):
// 添加一个条目
bf.Add(z.MemHash([]byte("butter")))
// 已添加元素个数(注意:ElemNum 不会被包含在 JSON 导出中,以兼容旧版本)
nOfElementsInFilter := bf.ElemNum
// 判断条目是否在过滤器中
isIn := bf.Has(z.MemHash([]byte("butter"))) // 应为 true
isNotIn := bf.Has(z.MemHash([]byte("Butter"))) // 应为 false
// "仅当条目为新元素时才添加":返回是否真正写入
added := bf.AddIfNotHas(z.MemHash([]byte("butter"))) // false:已在集合中
added = bf.AddIfNotHas(z.MemHash([]byte("buTTer"))) // true:新条目
AddIfNotHas 的实现(z/bbloom.go)先调用 Has 检查,命中则返回 false 不再重复写入,否则执行 Add 并返回 true。
线程安全版本:AddTS / HasTS / AddIfNotHasTS
原文档 changelog 记录了 2015 年 11 月新增的线程安全方法 AddTS()、HasTS()、AddIfNotHasTS(),该改进源自 Srdjan Marinovic 的建议(GitHub 用户 @a-little-srdjan),并被其用于编写布隆过滤器缓存。带 TS 后缀的方法适用于多 goroutine 并发场景,例如:
// 并发安全的添加
bf.AddTS(z.MemHash([]byte("peanutbutter")))
// 并发安全的查询
isIn = bf.HasTS(z.MemHash([]byte("peanutbutter"))) // 应为 true
isNotIn = bf.HasTS(z.MemHash([]byte("peanutButter"))) // 应为 false
// 并发安全的"仅添加新元素"
added = bf.AddIfNotHasTS(z.MemHash([]byte("peanutbuTTer"))) // true
JSON 序列化与恢复
布隆过滤器可以整体导出为 JSON 字节流并重新恢复:
// 转换为 JSON ([]byte)
json := bf.JSONMarshal()
// 布隆过滤器的 Mutex 对外暴露,可在 JSON 转换期间手动加锁
bf.Mtx.Lock()
json = bf.JSONMarshal()
bf.Mtx.Unlock()
// 从 JSON 恢复过滤器
bfNew, err := z.JSONUnmarshal(json)
if err != nil {
// 处理反序列化错误
}
isInNew := bfNew.Has(z.MemHash([]byte("butter"))) // 应为 true
isNotInNew := bfNew.Has(z.MemHash([]byte("Butter"))) // 应为 false
序列化的内部结构定义在 z/bbloom.go:
type bloomJSONImExport struct {
FilterSet []byte
SetLocs uint64
}
即只导出位图原始字节(FilterSet)与每个条目的哈希位置数(SetLocs),因此文件非常紧凑。JSONUnmarshal 会先反序列化得到这两个字段,再调用 newWithBoolset 以 len(bs)<<3(字节数 × 8,即 bit 数)重建同尺寸的过滤器,并把字节逐个写回 bitset(见 z/bbloom.go)。
底层实现:unsafe.Pointer 与位操作
bbloom 之所以"快",关键在于读写位图时绕过了切片越界检查与逐位计算的间接层。Set 与 IsSet 的实现(z/bbloom.go)使用 unsafe.Pointer 直接定位到字节:
func (bl *Bloom) Set(idx uint64) {
ptr := unsafe.Pointer(uintptr(unsafe.Pointer(&bl.bitset[idx>>6])) + uintptr((idx%64)>>3))
*(*uint8)(ptr) |= mask[idx%8]
}
func (bl *Bloom) IsSet(idx uint64) bool {
ptr := unsafe.Pointer(uintptr(unsafe.Pointer(&bl.bitset[idx>>6])) + uintptr((idx%64)>>3))
r := ((*(*uint8)(ptr)) >> (idx % 8)) & 1
return r == 1
}
逐位拆解:
idx >> 6:把位索引除以 64,定位到对应的uint64字;(idx % 64) >> 3:在字内再定位到具体字节的偏移;mask[idx%8]:mask = []uint8{1, 2, 4, 8, 16, 32, 64, 128},取出该字节内的目标位掩码。
Add 与 Has 的关键在于如何从单个 64 位哈希派生出多个哈希位置(z/bbloom.go):
func (bl *Bloom) Add(hash uint64) {
h := hash >> bl.shift
l := hash << bl.shift >> bl.shift
for i := uint64(0); i < bl.setLocs; i++ {
bl.Set((h + i*l) & bl.size)
bl.ElemNum++
}
}
先把 64 位哈希拆成高半 h 与低半 l,然后通过线性组合 h + i*l 生成 setLocs 个相互独立的位置,再与 bl.size(2 的幂减 1)做与运算取模。这一技巧只需一次哈希计算即可生成 k 个位置,是保证吞吐的关键。
关于 ElemNum 的语义需要特别注意:源码中 Add 每次循环都会执行 bl.ElemNum++(见 z/bbloom.go),因此它统计的是"位写入次数"而非"条目数";同时原文档明确指出 ElemNum 不会被写入 JSON 导出,以保证与旧版本的兼容性。请勿用它作为精确的条目计数。
TotalSize()(z/bbloom.go)可估算过滤器占用的总内存字节数:len(bl.bitset)*8 + 5*8(5 个 8 字节的结构体成员加上位图切片本身),可用于容量规划。
unsafe 使用提醒
原文档特别提示:bbloom 使用 unsafe.Pointer 设置和读取位图中的位。如果你对使用 unsafe 包感到不适,可以考虑作者的另一套基于 <a href="https://link.gitcode.com/i/231f30a6a22ecae5f2ca45088999fba1" target="_blank">]bool 的布隆过滤器实现(原文档中给出的路径为 github.com/AndreasBriese/bloom)。在原仓库 z 包的上下文中,unsafe 还被用于 memhash 的 linkname 绑定([z/rtutil.go),这与 Go runtime 内部机制直接相关,使用方应注意该实现依赖具体 Go 版本行为。
性能表现:为什么"快"?
原文档给出了一个完整的横向对比表(测试环境为 MBPro15、OSX 10.8.5、i7 4 核 2.4GHz,过滤器大小 524288 bit、7 个哈希位置,65536 条目的 Add/Has 各重复 10 次):
Bloom filter (filter size 524288, 7 hashlocs)
github.com/AndreasBriese/bbloom 'Add' 65536 items (10 repetitions): 6595800 ns (100 ns/op)
github.com/AndreasBriese/bbloom 'Has' 65536 items (10 repetitions): 5986600 ns (91 ns/op)
github.com/AndreasBriese/bloom 'Add' 65536 items (10 repetitions): 6304684 ns (96 ns/op)
github.com/AndreasBriese/bloom 'Has' 65536 items (10 repetitions): 6568663 ns (100 ns/op)
github.com/willf/bloom 'Add' 65536 items (10 repetitions): 24367224 ns (371 ns/op)
github.com/willf/bloom 'Test' 65536 items (10 repetitions): 21881142 ns (333 ns/op)
github.com/dataence/bloom/standard 'Add' 65536 items (10 repetitions): 23041644 ns (351 ns/op)
github.com/dataence/bloom/standard 'Check' 65536 items (10 repetitions): 19153133 ns (292 ns/op)
github.com/cabello/bloom 'Add' 65536 items (10 repetitions): 131921507 ns (2012 ns/op)
github.com/cabello/bloom 'Contains' 65536 items (10 repetitions): 131108962 ns (2000 ns/op)
需要说明:上述数字摘自原文档,属于其开发环境(约 2015 年)的历史测试数据,仅用于说明该设计思路的相对优势,不应视为当前仓库的现测结论。如需当前硬件下的数据,请在仓库内自行运行 go test -bench=. ./z。此外,文档还指出该实现与作者的 []bool 变体速度相当,但内存占用约为后者的 1/8,这正是 bitset 紧凑存储带来的收益。
关于 32 位变体(bloom32),原文档说明其使用改进的 sdbm 哈希,每个字节仅需 2 次位移、1 次异或和 1 次减法完成哈希,速度与 fnv64a 相当但在上述日志数据集上冲突更少;用 New(10*2^16, 7) 配置填充 2^16 个随机条目并对其余数据进行测试,误报率低于 0.05%。
实战要点小结
- 参数选择:推荐使用"条目数 + 误报率"的组合(第二参数 < 1),由公式自动推导最优位图大小与哈希位置数;需要精确控制内存时再改用"位图大小 + 位置数"形式,但要注意位图会被向上取整为 2 的幂且最小 512 bit。
- 哈希配合:当前仓库 API 接收
uint64哈希而非原始字节,与 z/z.go 中的KeyToHash(MemHash/MemHashString配合 xxhash)或z.MemHash搭配使用;注意MemHash的种子随进程变化,不能作为持久化哈希。 - 并发与持久化:多 goroutine 场景使用
TS系列方法;需要落盘/恢复时用JSONMarshal/JSONUnmarshal,必要时配合暴露的Mtx手动加锁。 - 在 Ristretto 中的配置联动:由于 doorkeeper 的位图大小由
NumCounters决定(policy.go),NumCounters的取值直接影响布隆过滤器尺寸与 TinyLFU 的准入精度,按 cache.go 的建议设置为预期缓存条目数的 10 倍左右。
对更多实现细节感兴趣的读者,可以继续阅读 z/bbloom.go 的完整源码、z/bbloom_test.go 的测试与基准用例,以及 policy.go 中 TinyLFU 对它的完整调用逻辑。