Roaring Bitmap

定义

Roaring Bitmap 是一种压缩位图数据结构，用来存储 32 位无符号整数的集合。位图（bitmap，又称 bitset 或位向量）用 n 个二进制位表示区间 [0, n) 内的整数集合，第 i 位为 1 就表示整数 i 在集合中，集合的交、并、差可以直接用按位与、或、非运算完成^[1]。Roaring Bitmap 在这些性质的基础上加入分层与自适应选择，使存储更紧凑，同时保留逐值查询的能力^[2]。

按照其格式规范，一个 Roaring Bitmap 由 1 至 65536 个容器（container）组成，最多可容纳 4294967296 个整数，全部容器均非空，且每个容器都记录自身的基数（cardinality），即其中整数的个数^[3]。它就是许多容器的有序集合^[4]。

原理

Roaring Bitmap 把 32 位整数的取值范围按高 16 位切分成若干块，每块最多容纳 2^16 个整数，用一个相应的容器保存这些整数的低 16 位^[5]。容器的 16 位高位值也称作键（key），它作为第一级索引；全部容器按键排序存放在一个动态数组中，因此查找时先对键做二分查找，再进入容器内部定位^[5]。在数据规模为一百万时，这一级索引最多只有 16 个条目，通常可以常驻在处理器缓存中^[5]。

容器分为 3 种类型：数组容器（array container）、位图容器（bitset container）和游程容器（run container）^[3]。当某一块中的整数不超过 4096 个时，采用排好序的 16 位整数数组；超过 4096 个时改用 2^16 位的位图^[5]。这个阈值保证在容器层面每个整数最多占用 16 位：数组容器每个整数占 16 位，位图容器固定为 8 kB，两者在 4096 个整数处空间开销相等^[6]。游程容器则对连续的整数序列做游程编码，序列 11、12、13、14、15 会被压缩为一对数值 11 和 4，表示 11 之后还有 4 个连续递增的值^[3]。

数组容器与位图容器之间的转换由基数阈值触发：添加整数使数组容器超过 4096 个元素时转为位图容器，删除整数使位图容器降到 4096 个元素时转回数组容器，转换时按更新后的数据建立新容器并丢弃旧容器^[5]。此外还可调用优化接口，比较现有容器与等价游程容器的空间开销，若游程编码更省空间就加以转换^[2]。查询某个整数 x 是否存在时，先用二分查找定位 x/2^16 对应的容器；若命中位图容器，直接访问第 x mod 2^16 位；若命中数组容器，则在有序数组中再做一次二分查找^[5]。

两个 Roaring Bitmap 之间的集合运算按第一级索引逐键比较：键相同时对其容器执行第二级运算，键不同时按大小推进游标，求并集时保留较小的键及其容器副本，求交集时某一侧索引耗尽即终止^[5]。容器之间也存在多种组合，例如位图容器与位图容器做并集时可对 1024 个 64 位字逐字做按位或，位图容器与数组容器求交时可遍历数组并逐值在位图中检验^[5]。由于每个容器预先记录基数，整个位图的基数只需累加至多 ⌈n/2^16⌉ 个计数器，rank 与 select 查询也因此更快^[5]。

序列化后的字节数有上界公式，对 [0, x) 区间内的 N 个整数，占用不超过 $8 + 9 \times \lceil x/65536 \rceil + 2N$ 字节，即在值域开销之外每个整数最多 2 字节^[1]。规范采用小端序编码，以 cookie 头标识数据流并给出容器数量，随后是描述各容器键与基数的描述头、可选的偏移头，最后依次存放各容器^[3]。

发展历程

此前主流的压缩位图多由 Oracle 的 BBC 格式衍生而来，依赖游程编码，包括 WAH、Concise、EWAH 等^[5]。这类格式虽然节省空间，但随机访问能力很弱，检查或修改第 i 位需要 O(n) 时间，因为必须从头解压整段数据，两个大集合求交时最坏情况也要完整解压其中一个^[5]。

2014 年 2 月，萨米·尚比（Samy Chambi）、丹尼尔·勒米尔（Daniel Lemire）、欧文·卡瑟（Owen Kaser）与罗伯特·戈丹（Robert Godin）提出 Roaring 压缩位图格式，其思路是不再依赖游程编码，而把取值空间切块并对稠密块与稀疏块采用不同表示^[5]。该工作于 2015 年 4 月 21 日在线发表于《软件：实践与经验》，并于 2016 年 5 月刊出，卷期页码为第 46 卷第 5 期第 709 至 719 页^[7]。论文报告在合成数据与真实数据上，Roaring 位的压缩率常优于 WAH 和 Concise 约 2 倍，交集运算最多快 900 倍，对当时认为游程编码压缩最优的观点提出了挑战^[8]。

此后，勒米尔等人又提出把未压缩位图、紧凑数组与游程编码段结合的混合方案，以改善那些存在长连续游程的数据的压缩效果；新实现可比 WAH、Concise、EWAH 等传统方案快数倍甚至两个数量级，同时压缩率更好^[9]。相关成果于 2016 年 11 月刊出于《软件：实践与经验》第 46 卷第 11 期第 1547 至 1569 页^[10]。

实现层面出现了多种语言的版本，且跨语言二进制兼容：Java、C、C++ 与 Go 版本可以互相读写对方序列化的位图，互通依赖一份独立的格式规范^[1]。2018 年，勒米尔等人发表关于优化软件库实现的论文，介绍面向单指令多数据（SIMD）指令的向量化算法，用于加速数组之间的交、并、差与对称差运算^[11]。规范后来还补充了 64 位实现的便携序列化扩展，以一套 32 位键与 32 位 Roaring 位图的映射来描述 64 位整数集合，但并非所有 64 位实现都兼容该扩展^[3]。

应用

Roaring Bitmap 的主要用途是数据库与搜索引擎中的位图索引，尤其适合倒排索引里「词项对应文档编号集合」这一类结构，因为这类场景需要频繁计算集合的交集、并集与差集^[12]。其格式规范列举的使用方包括 Apache Lucene 及由其衍生的 Solr、Elasticsearch，Apache Spark、Apache Hive、Apache Tez、eBay 的 Apache Kylin、LinkedIn Pinot、Netflix Atlas、Druid、Pilosa 等系统^[3]。

Lucene 自 5.0 版起采用 Roaring 格式压缩文档标识符，不过 Lucene 使用的是自己独立实现的版本^[7]。YouTube 的 SQL 引擎 Google Procella 也用 Roaring 位图建立索引^[1]。在数据湖与表格式方向，Iceberg 通过 32 位 Roaring 位图数组覆盖 0 到 2^64-1 的取值空间，并采用 Roaring 的便携序列化格式。

除固定实现外，多种语言提供了绑定或移植版本，包括 Python、Rust、Node、Swift 等^[11]。部分数据库进一步把该结构暴露给查询语言，例如以位图列存储整型集合并提供聚合构建函数，可用于人群标签、去重计数等分析场景^[13]。

局限

Roaring Bitmap 的原始格式只面向 32 位无符号整数，更大范围的整数需要额外的 64 位扩展；规范明确指出，目前的标准格式只涉及 32 位整数，64 位版本并无统一的二进制格式，只有 32 位格式在 Java、C++、C、Go 之间保证互通^[3]。因此不同实现之间的 64 位数据互操作需要额外的约定，否则可能出现格式互不兼容的情况^[1]。

压缩并非在所有数据分布下都划算。若值域本身很小，例如集合取自 [0, 64) 或 [0, 128)，未压缩位图不会占用过多内存，压缩带来的收益有限，而未压缩位图速度更好^[1]。若数据稀疏且近似随机，则本质上不可压缩，一小组 32 位随机整数不可能用远低于 32 位每整数的空间表示，此时使用紧凑数组往往比位图更合适^[1]。论文的实测也显示，在平均基数远小于值域规模的数据集上，结构开销会使 Roaring 位图占用约为 Concise 的 4 倍内存^[5]。

面对大量连续 1 的稠密数据，Roaring 位图也可能不如游程编码方案紧凑。论文报告在特定数据集上 Concise 与 WAH 的压缩率可比 Roaring 约好 30%，原因正是数据中存在长串连续位，而早期 Roaring 位图并不压缩这种模式^[5]。后续引入游程容器与混合方案，正是为改善这类情形^[9]。

此外，容器级优化并非自动持续执行：游程优化是一个需要显式调用的常规函数，若调用策略随意或只执行一次，可能达不到优化效果，反而降低性能^[6]。线程安全方面，各实现普遍不为位图内部加同步锁以换取性能，并发修改同一个位图需要调用方自行提供同步^[1]。当位图来自不可信来源时，反序列化后还需做完整性校验，否则可能接受非法内容^[2]。

参见

• 位图 —— Roaring Bitmap 是在其基础上发展出的压缩形式。

• 游程编码 —— 压缩位图的另一条技术路线，也是 Roaring 位图游程容器的实现方式。

• 倒排索引 —— Roaring Bitmap 最主要的应用场景之一。

• Apache Lucene —— 自 5.0 版起采用 Roaring 格式压缩文档标识符。

• Apache Spark —— 采用 Roaring 位图实现相关索引与集合运算。

• 单指令多数据 —— 用于加速 Roaring 位图集合运算的处理器指令技术。