Nakama 依赖中的 Roaring Bitmap：Go 高性能压缩位图库原理与实战指南

本文聚焦当前仓库（GitHub_Trending/na/nakama）vendor 目录中随附的开源依赖 vendor/github.com/RoaringBitmap/roaring/README.md 所讲解的核心主题——Go 语言版的 Roaring Bitmap（咆哮位图）数据结构。Roaring Bitmap 是一种专为整数集合设计的压缩位图结构，在数据库索引、搜索引擎倒排索引、分析引擎等场景中广泛使用。读完本文，你将掌握：何时该用位图/压缩位图、Roaring 相比 WAH/EWAH/Concise 等传统压缩位图格式的优势、它在 Go 中的安装与 API 用法、三种内部容器（Array / Bitmap / Run）的切换原理、32 位与 64 位版本的差异，以及序列化、并发安全、测试与模糊测试等工程实践。

一、仓库中随附的 Roaring 依赖

当前 Nakama 仓库将 github.com/RoaringBitmap/roaring 以 v1.9.4 版本随附在 vendor 目录中（见 go.mod 中的 github.com/RoaringBitmap/roaring v1.9.4 // indirect 声明及 vendor/modules.txt 的模块清单），其完整源码位于 vendor/github.com/RoaringBitmap/roaring/，核心文档即 vendor/github.com/RoaringBitmap/roaring/README.md。

从代码引用关系看，Nakama 并不直接调用 Roaring，而是通过 Bluge/Bleve 生态的倒排索引组件间接使用：vendor/github.com/blugelabs/ice/posting.go、vendor/github.com/blugelabs/bluge/index/segment.go 等文件都导入了 github.com/RoaringBitmap/roaring，用于存储和合并倒排文档列表（postings）。这正是 Roaring 的典型应用场景——用整数集合表示"哪些文档/行满足某个属性"，并快速执行交集、并集、差集运算。

二、何时应该使用位图：从位向量说起

集合是软件中的基础抽象，可被实现为哈希表、树等多种形态。在数据库和搜索引擎中，集合常常是索引的核心组成部分。例如，我们需要维护"满足某个属性的全部文档或行（用数值型标识符表示）"这样的集合，并且除了增删元素之外，还需要快速地计算交集、并集、差集等集合运算。

实现整数集合时，位图（bitmap，也称 bitset 或位向量）是一种特别有吸引力的方案：使用 n 个比特位，即可表示范围 [0, n) 内的任意整数集合——第 i 位为 1 表示整数 i 在集合中。通用处理器以 W=32 或 W=64 位的字为单位工作，通过组合大量这样的字即可支持很大的 n 值。于是交集、并集、差集可以分别实现为按位 AND、OR 和 ANDNOT 运算，更复杂的集合函数同样可以转化为位运算。

当位图方案适用时，它可能比其他集合实现（例如哈希表）快数个数量级，同时内存占用少好几倍。

位图不适用的情况：稀疏场景

然而，位图（即便是压缩位图）并非总是适用。README 明确指出两个典型反例：

1. 小宇宙（universe）场景：如果集合表示的是 [0, n) 且 n 很小（如 n=64 或 n=128），用普通未压缩 BitSet 即可，内存不会爆炸，压缩反而多此一举。此时 BitSet 的速度优势非常显著。
2. 稀疏随机数据场景：如果只有 1000 个看起来随机的整数，简单数组（sorted array）可能是最佳表示。随机数据通常不可压缩——例如少量 32 位随机整数，数学上每个整数不可能远少于 32 比特，尝试压缩反而适得其反。

未压缩位图的内存问题

未压缩的 BitSet 可能消耗大量内存：如果你在一个 BitSet 中把位置 1,000,000 的位设为 true，就需要超过 100KB——只为存储一个 1 的位置。这即使不考虑内存也是浪费：假设要计算这个 BitSet 与另一个在位置 1,000,001 置位的 BitSet 的交集，无论你愿不愿意，都必须遍历所有这些 0 位，代价非常高昂。

三、Roaring 与替代方案：为什么比 WAH/EWAH/Concise 更好

传统压缩位图大多属于"游程编码位图"（run-length-encoded bitmaps）家族：识别长串的 1 或 0，用标记字（marker word）表示它们；局部 1 和 0 混合时则使用未压缩的字。这个家族包括：

格式	特点
Oracle BBC	已过时的格式，压缩率虽好，但因过多的分支判断通常比现代方案慢得多
WAH	BBC 的专利变体，性能更好
Concise	WAH 的专利变体，某些情况下压缩率可比 WAH 好 2 倍，但通常更慢
EWAH	无专利负担，比上述所有格式都快，但压缩率略逊；它允许某种"跳过"未压缩字的能力，因此在随机访问方面优于其他同类

这些格式有一个可能造成严重损害的致命缺陷：没有随机访问能力。要检查某个值是否在集合中，必须从头开始"解压"整个集合。这意味着即使只是把一个小集合与大集合做交集，最坏情况下仍要解压整个大集合。

Roaring 解决了这个问题。它的工作方式如下：

1. 把数据划分为大小为 2¹⁶（65536）个整数的块（chunk），例如 [0, 2¹⁶)、[2¹⁶, 2×2¹⁶)、……；
2. 每个块内部可以使用未压缩位图、简单整数列表或游程列表（runs）三种表示之一；
3. 无论采用哪种表示，都支持快速检查任意值是否存在（例如借助二分查找）。

净效果是：Roaring 能以比 WAH、EWAH、Concise 等游程编码格式快得多的速度执行大量运算；并且出人意料的是，它通常还能提供更好的压缩率。

README 引用的业界结论（Wang et al., SIGMOD 2017）："只要有可能，就使用 Roaring 做位图压缩，不要使用其他位图压缩方法。"

源码证据：三种容器与 4096 阈值

仓库源码印证了上述设计。roaringarray.go 中定义了统一的 container 接口（含 and、or、andNot、xor、rank、selectInt、intersects 等集合运算与 iadd/iremove 原地操作），底层则由三个具体实现承担：

• arrayContainer（arraycontainer.go）：内部即 content <a href="https://link.gitcode.com/i/1c6303b932d4af1eb58a875b66bf9453" target="_blank">]uint16 有序数组，字节占用为 cardinality * 2（[arraycontainer.go），适合稀疏块；
• bitmapContainer（bitmapcontainer.go）：内部为 bitmap []uint64，每个块固定 1024 个 uint64 字（即 65536 位 ≈ 8KB），适合稠密块；
• runContainer16（runcontainer.go）：内部为排序、不重叠、不相邻的闭区间 interval16{start, length}，对长连续游程场景压缩效果极佳。

块内表示的选择依据是基数阈值：util.go 定义 arrayDefaultMaxSize = 4096，即容器内整数 ≤ 4096 个时使用 array 容器，超过则升级为 bitmap 容器；而在 roaringarray.go 的 runOptimize 注释中说明了 RunOptimize() 只改变表示形式、不改变逻辑内容，可将元素容器替换为空间最优版本。

四、安装与快速上手

安装

go get -t github.com/RoaringBitmap/roaring

依赖会自动拉取，包括 github.com/bits-and-blooms/bitset、github.com/mschoch/smat（注意 smat 库要求 Go 1.6 及以上）、github.com/glycerine/go-unsnap-stream、github.com/philhofer/fwd、github.com/jtolds/gls 等。

完整示例

README 给出了一个简化但完整的示例，涵盖创建、基数、包含判断、And/Or、并行聚合、迭代与序列化：

package main

import (
    "fmt"
    "github.com/RoaringBitmap/roaring"
    "bytes"
)

func main() {
    // example inspired by https://github.com/fzandona/goroar
    fmt.Println("==roaring==")
    rb1 := roaring.BitmapOf(1, 2, 3, 4, 5, 100, 1000)
    fmt.Println(rb1.String())

    rb2 := roaring.BitmapOf(3, 4, 1000)
    fmt.Println(rb2.String())

    rb3 := roaring.New()
    fmt.Println(rb3.String())

    fmt.Println("Cardinality: ", rb1.GetCardinality())

    fmt.Println("Contains 3? ", rb1.Contains(3))

    rb1.And(rb2)

    rb3.Add(1)
    rb3.Add(5)

    rb3.Or(rb1)

    // computes union of the three bitmaps in parallel using 4 workers
    roaring.ParOr(4, rb1, rb2, rb3)
    // computes intersection of the three bitmaps in parallel using 4 workers
    roaring.ParAnd(4, rb1, rb2, rb3)

    // prints 1, 3, 4, 5, 1000
    i := rb3.Iterator()
    for i.HasNext() {
        fmt.Println(i.Next())
    }
    fmt.Println()

    // next we include an example of serialization
    buf := new(bytes.Buffer)
    rb1.WriteTo(buf) // we omit error handling
    newrb := roaring.New()
    newrb.ReadFrom(buf)
    if rb1.Equals(newrb) {
        fmt.Println("I wrote the content to a byte stream and read it back.")
    }
    // you can iterate over bitmaps using ReverseIterator(), Iterator, ManyIterator()
}

要点说明：

• BitmapOf(...) 直接由整数列表构造位图；New() 创建空位图；
• GetCardinality() 返回元素个数，Contains(x) 判断成员资格；
• And / Or 是原地修改的集合运算；ParOr / ParAnd 提供并行版本，第一参数为工作协程数；
• Iterator() 升序遍历，另有 ReverseIterator()（降序）与 ManyIterator()（批量）可选用。

源码层面，位图的核心结构定义在 roaring.go：

// Bitmap represents a compressed bitmap where you can add integers.
type Bitmap struct {
    highlowcontainer roaringArray
}

roaringArray（roaringarray.go）由平行的 keys []uint16（高 16 位键）与 containers []container（低 16 位容器）构成，键与容器按高 16 位有序排列，从而支持通过二分定位 key 快速访问任意整数。

迭代式使用（gore）

README 还推荐使用 gore 做交互式探索：

go get -u github.com/motemen/gore
# 确保 $GOPATH/bin 在 $PATH 中
go get github.com/RoaringBitmap/roaring

$ gore
gore version 0.2.6  :help for help
gore> :import github.com/RoaringBitmap/roaring
gore> x:=roaring.New()
gore> x.Add(1)
gore> x.String()
"{1}"

五、序列化：跨语言二进制兼容与大小上界

序列化是 Roaring 的杀手级特性之一。Java、C、C++ 与 Go 四个版本实现了二进制兼容：例如可以在 Java 程序中保存位图，再在 Go 中加载回来，反之亦然，其格式规范由 RoaringFormatSpec 项目维护。

Go 侧入口在 roaring.go（WriteTo 将序列化版本写入 io.Writer）与 ReadFrom（从流读回）。此外还提供了便捷封装 ToBytes / FromBytes、ToBase64 / FromBase64（roaring.go）。

需要处理错误时，可采用如下写法：

rb := BitmapOf(1, 2, 3, 4, 5, 100, 1000)
buf := new(bytes.Buffer)
size, err := rb.WriteTo(buf)
if err != nil {
    t.Errorf("Failed writing")
}
newrb := New()
size, err = newrb.ReadFrom(buf)
if err != nil {
    t.Errorf("Failed reading")
}
if !rb.Equals(newrb) {
    t.Errorf("Cannot retrieve serialized version")
}

序列化大小上界

README 给出了一个严谨的存储上界：给定 [0, x) 内的 N 个整数，Roaring 位图的序列化字节数不会超过：

8 + 9 * ((long)x + 65535) / 65536 + 2 * N

也就是说，给定宇宙大小 x 的固定开销后，Roaring 每个整数最多占用 2 字节。若需要更精确的估算，可调用 BoundSerializedSizeInBytes。

这一上界在源码中也有印证：array 容器每个元素固定占 2 字节（uint16），即 arraycontainer.go 中的 cardinality * 2。

六、64 位版本 roaring64

默认情况下 roaring 存储无符号 32 位整数。仓库同时提供了面向 64 位整数的扩展包 github.com/RoaringBitmap/roaring/roaring64，支持大致相同的函数：

package main

import (
    "fmt"
    "github.com/RoaringBitmap/roaring/roaring64"
    "bytes"
)

func main() {
    // example inspired by https://github.com/fzandona/goroar
    fmt.Println("==roaring64==")
    rb1 := roaring64.BitmapOf(1, 2, 3, 4, 5, 100, 1000)
    fmt.Println(rb1.String())

    rb2 := roaring64.BitmapOf(3, 4, 1000)
    fmt.Println(rb2.String())

    rb3 := roaring64.New()
    fmt.Println(rb3.String())

    fmt.Println("Cardinality: ", rb1.GetCardinality())

    fmt.Println("Contains 3? ", rb1.Contains(3))

    rb1.And(rb2)

    rb3.Add(1)
    rb3.Add(5)

    rb3.Or(rb1)

    // prints 1, 3, 4, 5, 1000
    i := rb3.Iterator()
    for i.HasNext() {
        fmt.Println(i.Next())
    }
    fmt.Println()

    // next we include an example of serialization
    buf := new(bytes.Buffer)
    rb1.WriteTo(buf) // we omit error handling
    newrb := roaring64.New()
    newrb.ReadFrom(buf)
    if rb1.Equals(newrb) {
        fmt.Println("I wrote the content to a byte stream and read it back.")
    }
}

重要限制：只有 32 位 roaring 格式是标准化的，并且能在 Java、C++、C 与 Go 之间互操作；64 位版本之间不保证兼容。

七、工程实践：并发安全、测试、基准与模糊测试

Goroutine 安全

一般情况下，不应认为同一位图可被不同 goroutine 安全访问——为了性能，库有意不做同步。如果确实需要从多个 goroutine 访问同一个 Bitmap，需要自行提供同步，惯用做法有两种：

• 通过 channel 传递 *Bitmap（Go 风格：保证任意时刻只有一个所有者）；
• 使用 sync.Mutex 串行化对位图的操作。

单元测试与覆盖率

go test -v

项目维护了完整的测试套件，README 指向独立的覆盖率报告服务。仓库内 vendor/github.com/RoaringBitmap/roaring/ 目录下即有 smat.go 与 serializationfuzz.go 等测试辅助源码。

基准测试

运行基准测试：

go test -bench Benchmark -run -

如需在真实 Roaring 数据集（Real Roaring Datasets）上运行基准：

go get github.com/RoaringBitmap/real-roaring-datasets
BENCH_REAL_DATA=1 go test -bench BenchmarkRealData -run -

模糊测试

README 提供了基于 go-fuzz 的模糊测试流程，帮助社区持续验证库的健壮性：

go get github.com/dvyukov/go-fuzz/go-fuzz
go get github.com/dvyukov/go-fuzz/go-fuzz-build
go test -tags=gofuzz -run=TestGenerateSmatCorpus
go-fuzz-build github.com/RoaringBitmap/roaring
go-fuzz -bin=./roaring-fuzz.zip -workdir=workdir/ -timeout=200 -func FuzzSmat

让模糊测试持续运行，如果 crashers 数量 > 0，可在 workdir 中查看报告并找到 panic 的 goroutine 栈轨迹。-func 参数还可替换为 FuzzSerializationBuffer 或 FuzzSerializationStream，分别覆盖缓冲区与流式序列化路径。

八、在 Nakama 中的间接应用：倒排索引的整数集合

虽然 Nakama 游戏服务器代码本身不直接 import roaring，但作为其全文/文档检索依赖链的一部分，Roaring 承担了倒排索引 postings 列表的压缩存储工作：

• vendor/github.com/blugelabs/ice/posting.go：Bluge 生态的 segment 格式（源自 Bleve 的 scorch/ice）用 roaring 位图表示"包含某词的文档 ID 集合"；
• vendor/github.com/blugelabs/bluge/index/merge.go 等索引合并、优化流程会直接对 roaring 位图执行并集/交集运算。

这与 README 描述的核心场景完全一致——用数值标识符集合维护"满足某属性的文档"，并依赖 AND/OR 快速完成查询求值。Roaring 在每个 2¹⁶ 块内支持快速随机访问的特性，正是它在数据库与搜索引擎索引中优于传统游程编码位图的原因。

九、Go 生态中的替代实现

README 介绍了两个值得注意的替代方案：

• gocroaring：Go 语言包装 C/C++ 版本（CRoaring）的实现，通过 cgo 绑定获得 C 版本的能力；
• goroar：Go 原生独立实现，与本库（RoaringBitmap/roaring）相互独立编写。

读者可根据是否接受 cgo、性能诉求与维护偏好在这三者间选择。

十、社区、许可与参考资料

• 本代码以 Apache License, Version 2.0（ASL2.0）授权（见 vendor/github.com/RoaringBitmap/roaring/LICENSE），版权归作者所有（Copyright 2016-...）；
• 该库已投入生产并被多家系统采用，同时被收录进 Awesome Go 集合；README 所列的采用者包括 InfluxDB、Bleve、Weaviate、lindb、SourceGraph、M3、FrostDB 等；
• 仓库内还提供了 Java 版与 C/C++ 版实现，四个版本二进制格式兼容，格式规范由 RoaringFormatSpec 维护。

参考论文（详见 README）

• Daniel Lemire 等，《Roaring Bitmaps: Implementation of an Optimized Software Library》，Software: Practice and Experience 48(4), 2018（arXiv:1709.07821）；
• Samy Chambi 等，《Better bitmap performance with Roaring bitmaps》，Software: Practice and Experience 46(5), 2016（arXiv:1402.6407）；
• Daniel Lemire 等，《Consistently faster and smaller compressed bitmaps with Roaring》，Software: Practice and Experience 46(11), 2016（arXiv:1603.06549）。

小结

Roaring Bitmap 通过"2¹⁶ 分块 + 三种容器自适应 + 随机访问"的设计，在压缩率与运算速度之间取得了优于传统 RLE 位图的平衡。对 Nakama 这类依赖 Bluge/Bleve 检索链路的 Go 服务而言，它是倒排索引 postings 存储的幕后功臣；而对其 README 与源码的研读，也为你在自己的 Go 项目中自行引入和使用 roaring 提供了完整依据——从安装、核心 API、序列化上界，到并发注意事项与测试基准手段，皆可在此仓库内找到一手证据。