Roaring Bitmap：原理、实现与性能剖析

一、从问题出发：为什么需要 Roaring Bitmap？

位图（Bitmap）是一种非常经典的数据结构，它用N个比特位来表示一个整数集合——第i个比特位为1，就表示数字i存在于这个集合中。这种结构的优势极其明显：存储1亿个用户ID，传统HashSet需要约1.2GB内存，而位图只需要12MB，压缩比高达32倍。而且位运算（AND、OR、XOR）天然支持高效的集合运算。

然而，传统位图有一个致命缺陷：它要求为整个值域预先分配空间。如果用户ID范围是0到10亿，但每天只有1万个活跃用户，传统位图仍然需要分配10亿个比特位（约119MB），其中99.999%的空间被白白浪费。这个问题在用户画像、广告投放、物联网设备管理等场景中尤为突出。

为了解决稀疏数据的空间浪费问题，学术界先后提出了WAH、Concise、EWAH等基于行程长度编码（Run-Length Encoding，RLE）的压缩位图方案。这些方案通过压缩连续的0或1序列来节省空间。但它们存在一个共同的弱点：为了压缩而牺牲了随机访问性能——检查或修改某个比特位，最坏情况下需要O(n)的时间。

2014年，S. Chambi、D. Lemire等学者在一篇论文中提出了Roaring Bitmap，它采用了一种完全不同的思路：与其试图用一种压缩算法应对所有数据分布，不如将数据分而治之，对不同的数据密度采用不同的存储策略。实验证明，Roaring Bitmap不仅压缩效果更好（有时是WAH的2倍），在交集运算上甚至可以快900倍。

Roaring Bitmap正是为了同时解决传统位图的内存浪费和RLE方案的随机访问性能瓶颈而生的。

二、整体架构：分桶管理与二级索引

Roaring Bitmap采用”分而治之”的思路，构建了一个精巧的两级索引结构来处理32位无符号整数。

2.1 分桶（Bucketing）

将一个32位整数拆分为高16位和低16位：

数字: 0x12345678
├─ 高16位: 0x1234 (桶索引，用于定位容器)
└─ 低16位: 0x5678 (桶内偏移，在容器中查找)

2.2 一级索引（Key）

高16位作为桶的键（Key），所有可能的键（0到65535）被存储在一个有序数组中。这个数组就是一级索引，用于快速定位数据所在的桶。

2.3 二级容器（Container）

每个桶对应一个容器（Container），负责存储该桶内所有元素共同的低16位值。关键设计：只有当桶内至少有一个数据时，对应的容器才会被创建，从根本上避免了为空洞分配内存。

这种设计让访问任意元素都只需要两步：在有序数组中二分查找高16位（O(log n)），再在容器内操作低16位（O(1)或O(log n)），保证了高速随机访问。

三、容器的三种形态与动态转换

这是Roaring Bitmap实现自适应压缩的核心。容器内部会根据数据特征，在三种实现中动态切换，以保证每个桶内部的内存都达到最优。

3.1 数组容器（Array Container）——稀疏数据的轻骑兵

实现：一个有序的uint16_t数组，存储所有元素的低16位。初始容量通常为4，按需动态扩容（扩容系数从2倍逐渐降至1.25倍）。

适用：稀疏数据，即容器内元素数量少于4096个时。

内存：与元素数量c成正比，约2c字节。当c=4096时，占用8KB。

性能：查找使用二分查找，时间复杂度为O(log c)。插入/删除是O(n)（因需移动数组）。

3.2 位图容器（Bitmap Container）——稠密数据的重装旅

实现：固定使用1024个uint64_t的数组，即8KB，来直接表示一个完整的16位位图（65536个比特位）。

适用：稠密数据，即容器内元素数量达到或超过4096个时。

内存：恒定8KB，与元素多少无关。

性能：直接通过下标访问对应比特位，O(1)时间，速度极快。其结构也天然利于SIMD指令集优化。

3.3 行程容器（Run Container）——连续数据的压缩大师

实现：采用行程长度编码（RLE），将连续的数值序列压缩为(起始值, 长度)对。例如：序列11,12,13,14,15可存储为(11, 4)。

适用：存在大量连续数值的场景，如区间数据。

内存：取决于行程（run）的数量r，约4r字节。对连续数据压缩效果惊人，但对离散数据（每个元素都是一个孤立的run）反而会膨胀。

性能：查找与修改需遍历run，时间复杂度O(log r)，通常比数组容器慢。

3.4 容器的动态转换机制

容器并非一成不变，而是在增删操作中动态调整，以始终适应当前数据分布。

阈值为何是4096？
因为当存储4096个元素时，数组容器占用4096 * 2 = 8192字节，恰好等于位图容器的固定大小8KB。超过这个数量，位图容器就更省空间且访问更快。

转换流程：

  • 创建：往一个空桶插入单个元素时，默认创建数组容器。插入一个连续区间时，会直接比较数组容器和行程容器谁更省空间，择优创建。
  • Array → Bitmap：当数组容器的元素数量超过4096，在插入时会被自动转换为位图容器。
  • Bitmap → Array：当位图容器因删除操作导致元素数量降至4096或以下，会被转换回数组容器。
  • 主动优化为Run：调用runOptimize()方法，Roaring Bitmap会遍历所有容器，尝试将其转换为行程容器，并选择三者中内存占用最小的方案。需注意，这是一个需手动触发的、可能较重的计算过程，不适合高频调用。

四、性能优势与工程实现

正是这种”分桶索引”+”自适应容器”的组合，赋予了Roaring Bitmap全面的性能优势：

  • 卓越的压缩率：通过动态选择容器，在稀疏、稠密和连续数据上都能保持高效的内存使用。
  • 极致的运算速度：一级索引确保快速定位；位图容器支持O(1)访问和SIMD加速的集合运算（AND/OR/XOR），而数组容器间的二分查找在操作小规模数据时也足够高效。

4.1 与WAH/Concise的对比

WAH和Concise等基于RLE的压缩位图，虽然也能节省空间，但它们牺牲了随机访问能力——要检查某个特定位置的值，可能需要遍历大量RLE编码数据。而Roaring Bitmap的分桶结构确保了任何元素查找都只需要两步：二分查找定位桶（O(log n)），然后在容器内查找（O(log n)或O(1)）。

论文实验表明，在多种数据集上，Roaring Bitmap的压缩率优于WAH和Concise，且在交集运算中的速度可达到WAH的数十倍乃至数百倍。

4.2 实际应用场景

Roaring Bitmap目前已被广泛应用于各类大数据平台：

  • 用户画像与精准营销：将用户的标签属性转换为位图进行存储和计算，实现亿级用户的秒级圈选
  • UV统计与留存计算：存储用户的访问标记，快速计算DAU、MAU、留存率等指标
  • 数据库与搜索引擎：ClickHouse、Apache Doris、StarRocks、Elasticsearch等系统都内置了对Roaring Bitmap的支持

4.3 CRoaring工程实现

在C/C++生态中，官方维护的CRoaring库（BSD许可证）是标准实现。它被ClickHouse、Apache Doris、StarRocks等众多知名系统采用。

CRoaring的核心特性包括：

  • 双语言API：同时提供了纯C（roaring.h）和现代C++（roaring.hh）两套API，方便集成到不同项目中
  • SIMD优化：深度利用AVX2、AVX-512、NEON等指令集优化关键路径，实现极致的数据并行处理
  • Amalgamation支持：可将整个库合并为roaring.c和roaring.h两个文件，方便集成
  • 64位支持：除了处理32位整数的Roaring，还提供了Roaring64Map来处理64位整数
  • 内存管理：提供自定义内存分配器等高级特性，方便集成到各类高性能系统中
  • 跨语言生态：Roaring Bitmap生态已扩展到Java、Python、Rust、Go等多种语言，并且有统一的序列化格式规范（RoaringFormatSpec），确保跨语言数据互通

4.4 内存布局优化

在实现层面，为了优化缓存和内存分配，Roaring Bitmap的内存布局常采用”结构体数组”（SoA）形式，将键（keys）、类型码（typecodes）和容器指针（containers）分开存储，以提升内存连续性。

五、代码示例

下面是一个使用CRoaring库的简单示例：

#include <iostream>
#include "roaring.hh"

int main() {
    // 创建一个 Roaring Bitmap
    roaring::Roaring r1;

    // 添加 100 到 999 这些整数
    for (uint32_t i = 100; i < 1000; i++) {
        r1.add(i);
    }

    // 打印当前集合中的元素个数
    std::cout << "cardinality = " << r1.cardinality() << std::endl;

    // 检查某个元素是否存在
    std::cout << "contains 500? " << r1.contains(500) << std::endl;
    std::cout << "contains 1000? " << r1.contains(1000) << std::endl;

    // 创建另一个位图并执行交集运算
    roaring::Roaring r2;
    for (uint32_t i = 500; i < 1500; i++) {
        r2.add(i);
    }

    roaring::Roaring r3 = r1 & r2;  // 交集
    std::cout << "intersection cardinality = " << r3.cardinality() << std::endl;

    // 手动优化为Run容器
    r1.runOptimize();

    return 0;
}

六、总结

Roaring Bitmap之所以能成为压缩位图领域的”事实标准”，关键在于它放弃了”用一种方式解决所有问题”的思路。通过分桶策略将数据拆解为独立的小块，再根据每个小块的数据密度自适应地选择数组、位图或RLE三种存储方式。这种组合策略让它在内存占用、随机访问速度和集合运算性能三个维度上取得了很好的平衡，在不同数据分布下都能保持优秀的表现。

它的设计哲学值得深思：没有万能的单一数据结构，只有根据不同场景动态组合的智慧系统。这正是Roaring Bitmap能成为经典的根本原因。

作者

老丹

关注我
其他文章