Roaring Bitmap：互联网如何管理亿级用户标签？

引言：亿级用户标签的挑战​

在互联网产品的精准营销场景中，用户标签系统是核心基础设施。一个典型的互联网平台往往拥有数亿甚至十亿级别的用户，而每个用户身上又可能挂载几十到上百个标签。这些标签通常包括年龄区间、性别、地域、兴趣偏好、消费能力、活跃度、设备类型、会员等级等维度。当运营方需要筛选出「居住在北京、年龄在 25 到 35 岁之间、最近 30 天有活跃行为、且对数码产品感兴趣」的用户群体推送营销活动时，底层系统需要在亿级用户规模上高效完成多个标签集合的组合运算。

传统方案存在明显的瓶颈：

• 关系型数据库方案：为每个标签建立字段或关联表，通过 SQL 的 WHERE 子句过滤。小规模数据下可行，但亿级用户、数百标签的场景下，多条件组合查询延迟极高，存储成本也难以承受。
• 倒排索引方案：为每个标签维护一个命中用户的有序列表，查询时对多个列表求交集。当列表长度达到千万甚至亿级时，归并求交的运算开销会成为性能瓶颈。

朴素位图（Bitmap）是一种直观的替代方案：为每个标签维护一个长度等于用户 ID 空间的比特数组，第 i 位为 1 表示用户 i 拥有该标签，0 表示没有。标签组合查询可以直接转化为位图的按位与（AND）运算，现代 CPU 的 SIMD 指令可以一次处理数十到数百个比特，运算效率极高。但朴素位图存在严重的存储浪费问题：如果用户 ID 是 32 位无符号整数（取值范围 0~40 亿），单个标签的位图需要 40 亿比特 ≈ 512 MB 存储空间；如果有 1000 个标签，总存储将达到 512 GB，完全不具备工程可行性。

Roaring Bitmap 正是为了解决「位图的高效运算能力」与「稀疏场景下的存储浪费」之间的矛盾而设计的压缩位图数据结构。它在保留位图快速集合运算特性的同时，大幅降低了存储空间，能够适配多种数据分布特征。本文将围绕用户标签系统的实际场景，详细介绍 Roaring Bitmap 的核心设计、三种容器类型、标签组合查询的实现逻辑，以及其在精准营销中的实际应用案例。

朴素位图的局限与 Roaring Bitmap 的核心设计​

朴素位图的优缺点分析​

朴素位图的核心逻辑非常简单：用连续的比特数组映射整数集合，比特下标对应元素值，比特值表示元素是否存在。对于取值空间为 N 的整数集合，朴素位图仅需 N 个比特的存储空间，其核心优势包括：

1. 集合运算效率极高：交集、并集、差集可以直接通过按位与、按位或、按位异或指令实现，配合 SIMD 加速可以进一步提升吞吐量。
2. 单元素查询时间复杂度 O(1)：判断某个用户是否存在于标签集合中，仅需访问对应下标的比特位，无需遍历。
3. 稠密场景下存储紧凑：当集合中元素占比很高时，位图比存储原始整数列表更节省空间。

但朴素位图的缺陷同样突出：

1. 稀疏场景下存储浪费严重：无论集合中有多少元素，位图大小固定为整个取值空间的大小。如果用户 ID 是 uint32，即使一个标签仅命中 1000 个用户，仍需占用 512 MB 空间。
2. 无法利用稀疏性加速运算：求交集时，即使一个位图非常稀疏，另一个位图相对稠密，朴素位图仍需逐块扫描整个比特数组，无法跳过全 0 的空区域。

Roaring Bitmap 的分治思路​

Roaring Bitmap 的核心设计思想是分治：将 32 位整数空间拆分为「高 16 位相同的桶」和「桶内的低 16 位元素」两层结构，具体规则如下：

• 对于任意 32 位无符号整数 x，其高 16 位 x >> 16（即 x / 65536）决定它所属的桶编号，低 16 位 x & 0xFFFF（即 x % 65536）决定它在桶内的位置。
• 整个 32 位整数空间被划分为 65536 个可能的桶，每个桶对应一个唯一的高 16 位值。Roaring Bitmap 仅为非空桶创建存储结构，空桶不占用任何空间。

桶的索引通常采用按高 16 位排序的有序数组管理，查找某个桶时可以通过二分查找实现 O(log M) 的时间复杂度，其中 M 是非空桶的数量。这种分治结构从根源上解决了稀疏场景的存储浪费问题：如果一个标签仅命中少量用户，且这些用户分布在少数几个桶中，Roaring Bitmap 仅需存储这几个桶的结构即可。

三种自适应容器​

Roaring Bitmap 的核心特性是：每个桶的内部存储结构不是固定的，而是根据桶内元素的数量和分布特征，自动选择最合适的容器类型。Roaring Bitmap 共支持三种容器类型，分别是数组容器（Array Container）、位图容器（Bitmap Container）和运行容器（Run Container）。系统会在元素插入、删除后自动判断是否需要切换容器类型，始终保证当前桶的存储和运算效率最优。

三种容器详解​

三种容器的设计目标、适用场景和性能特征各有不同，下面逐一展开说明，并结合用户标签系统的实际场景解释其价值。

数组容器（Array Container）​

结构与存储​

数组容器使用有序的 uint16 数组存储桶内的低 16 位元素。由于低 16 位的取值范围是 0~65535，每个元素恰好占用 2 字节，数组按升序排列以支持二分查找和高效归并运算。

适用场景​

数组容器适用于桶内元素数量较少的场景。Roaring Bitmap 的默认实现中，当桶内元素数量 ≤ 4096 时，优先使用数组容器。这个阈值的设计依据是存储成本的平衡点：

• 位图容器固定占用 65536 比特 = 8192 字节（8 KB）。
• 数组容器的存储开销为 2 * 元素数量 字节。
• 当元素数量为 4096 时，数组容器开销为 2 * 4096 = 8192 字节，与位图容器持平；当元素数量小于 4096 时，数组容器比位图容器更节省空间。

优缺点​

优点：

• 稀疏场景下存储极其紧凑，无额外空间浪费。
• 支持二分查找，单元素查询时间复杂度为 O(log N)，N 为桶内元素数。
• 有序数组结构便于与其他有序容器做归并运算，求交、求并效率高。

缺点：

• 插入、删除元素时需要移动数组中的其他元素，时间复杂度为 O(N)。
• 当元素数量接近阈值时，存储和运算效率会下降。

用户标签场景示例​

例如「居住在南极洲」这类极低频标签，可能仅命中几百个用户，且这些用户的 ID 高 16 位仅分布在 1~2 个桶中，每个桶内仅几十个元素。此时使用数组容器存储，每个桶仅需几十到几百字节，完全避免了朴素位图的 512 MB 浪费。

位图容器（Bitmap Container）​

结构与存储​

位图容器使用固定长度为 65536 比特的比特数组存储桶内的低 16 位元素，固定占用 8192 字节（8 KB）。比特数组的第 i 位为 1 表示低 16 位值为 i 的元素存在于集合中，0 表示不存在。

适用场景​

位图容器适用于桶内元素数量较多的场景，即元素数量 > 4096 时。此时固定 8 KB 的存储开销比数组容器更低，且位运算的特性可以大幅提升集合运算效率。

优缺点​

优点：

• 存储开销固定，元素越多单位成本越低。
• 单元素查询时间复杂度为 O(1)，仅需访问对应比特位。
• 集合运算（与、或、异或）可以通过位运算直接实现，非常适合 SIMD 指令加速，运算吞吐量极高。

缺点：

• 元素数量较少时存在空间浪费，因此需要数组容器作为补充。
• 遍历所有元素需要扫描整个 8 KB 比特数组，稀疏场景下遍历效率低。

用户标签场景示例​

例如「最近 30 天有活跃行为」这类高频标签，假设平台总用户数为 10 亿，活跃用户为 5 亿，平均每个桶内包含约 7600 个用户，远超 4096 的阈值，适合使用位图容器。此时每个桶固定占用 8 KB，存储成本可控，且求交集时可以通过 SIMD 指令快速完成按位与运算。

运行容器（Run Container）​

结构与存储​

运行容器采用**游程编码（Run-Length Encoding, RLE）**的方式存储连续的元素区间。它内部维护一个 uint16 对的数组，每对包含一个区间的起始值 start 和长度减一 length-1，表示从 start 开始连续 length 个值都在集合中。

例如，桶内的元素是 {100, 101, 102, 103, 200, 201, 202}，运行容器会存储为 [(100, 3), (200, 2)]，表示 100103 共 4 个连续值，200202 共 3 个连续值。注意长度字段存储的是 length-1，因此 3 对应 4 个连续元素，2 对应 3 个连续元素。

适用场景​

运行容器适用于桶内元素呈现大段连续分布的场景。在用户标签系统中，这种情况并不罕见：如果用户 ID 是连续分配的，且某个标签命中的用户恰好是一段连续的 ID 区间，运行容器可以用极少的存储表示大量元素。

运行容器的存储优势在极端场景下非常明显：如果桶内 65536 个值全部存在，位图容器需要 8 KB，而运行容器仅需存储一个区间 (0, 65535)，即 4 字节，压缩比达到 2048:1。

优缺点​

优点：

• 连续分布的数据下存储极其紧凑，压缩比极高。
• 部分集合运算可以利用区间特性加速，例如判断某个区间是否完全包含于另一个容器。

缺点：

• 数据不连续时，存储效率可能不如数组容器，甚至超过位图容器。
• 插入、删除元素可能需要拆分或合并区间，操作逻辑相对复杂。

容器类型的自动转换​

Roaring Bitmap 不需要用户手动选择容器类型，系统会在元素变更时自动判断并切换最优容器：

1. 数组容器 → 位图容器：当数组容器的元素数量超过 4096 时，自动转换为位图容器。
2. 位图容器 → 数组容器：当位图容器的元素数量减少到 4096 以下时，自动转换为数组容器。
3. 数组/位图容器 → 运行容器：当数据呈现明显连续性，且运行容器的存储开销更低时，转换为运行容器。
4. 运行容器 → 数组/位图容器：当连续性被破坏，运行容器不再具备存储优势时，转换回数组或位图容器。

这种自适应机制让 Roaring Bitmap 可以自动适配各种数据分布，无需业务方感知底层实现细节。

三种容器核心特性对比​

为了更直观地理解三种容器的差异，以下是核心特性对比表：

标签组合查询的实现​

用户标签系统的核心需求是支持多个标签的灵活组合查询，对应到集合运算上就是交集、并集、差集、异或等操作。Roaring Bitmap 天然支持这些运算，且由于分治的桶结构，运算可以逐桶并行执行，效率极高。

问题建模​

在用户标签系统中，每个标签对应一个 Roaring Bitmap 结构的用户 ID 集合。常见的标签组合查询可以建模为以下集合运算：

• 交集（AND）：筛选同时满足多个标签的用户，例如「居住在北京」∩「年龄 25-35」∩「最近 30 天活跃」。
• 并集（OR）：筛选满足任意一个标签的用户，例如「是会员」∪「最近 7 天有购买行为」。
• 差集（ANDNOT）：筛选满足某个标签但不满足另一个标签的用户，例如「高消费能力」-「已购买过该商品」。
• 异或（XOR）：筛选仅满足其中一个标签的用户，例如「渠道 A 来源」⊕「渠道 B 来源」。

交集运算（AND）​

两个 Roaring Bitmap 求交集的执行逻辑分为两步：

1. 桶索引求交：对两个 Bitmap 的高 16 位桶索引数组求交集，得到共同存在的桶编号。由于桶索引是有序数组，可以通过归并算法在 O(M1 + M2) 时间内完成，其中 M1、M2 是两个 Bitmap 的非空桶数量。
2. 容器内求交：对每个共同桶内的两个容器执行交集运算，不同容器类型的组合对应不同的实现逻辑：
   • 数组 ∩ 数组：归并两个有序数组，收集共同元素，时间复杂度 O(N1 + N2)。
   • 位图 ∩ 位图：对两个 8 KB 比特数组执行按位与运算，可配合 SIMD 指令加速，时间复杂度 O(8192/指令位宽)。
   • 数组 ∩ 位图：遍历数组中的每个元素，检查位图中对应位是否为 1，时间复杂度 O(N)，N 为数组长度。
   • 运行容器与其他容器求交：逐区间扫描，判断区间内的元素是否存在于另一个容器中，收集匹配元素。

并集运算（OR）​

并集运算的逻辑与交集类似，但桶的处理方式不同：

1. 桶索引求并：对两个 Bitmap 的桶索引数组求并集，得到所有需要保留的桶编号。同样通过归并算法在 O(M1 + M2) 时间内完成。
2. 容器内求并：
   • 共同桶：对两个容器执行并集运算，若结果元素数超过 4096，自动转换为位图容器。
   • 仅存在于单个 Bitmap 的桶：直接复用该桶的容器，无需额外运算。

差集运算（ANDNOT）​

差集运算 A - B 表示属于 A 但不属于 B 的元素，执行逻辑如下：

1. 遍历 A 的所有桶，对于每个桶：
   • 若桶不存在于 B 中，直接保留 A 的容器。
   • 若桶存在于 B 中，对两个容器执行差集运算，移除 B 中存在的元素。
2. 空容器对应的桶会被自动删除，不占用存储空间。

异或运算（XOR）​

异或运算表示属于 A 或属于 B，但不同时属于两者的元素，执行逻辑：

1. 对桶索引求并集，得到所有相关桶。
2. 共同桶：对两个容器执行异或运算。
3. 仅存在于单个 Bitmap 的桶：直接复用该桶的容器。

运算复杂度分析​

Roaring Bitmap 的集合运算复杂度主要由两个因素决定：非空桶数量、容器类型。假设两个 Bitmap 的非空桶数量为 M1、M2，桶索引归并的时间复杂度为 O(M1 + M2)。对于每个共同桶，容器运算的最坏时间复杂度为 O(65536)（位图容器的按位运算），但由于位运算可以通过 SIMD 加速，实际执行效率极高。

在用户标签系统的实际场景中，用户 ID 分布在 0~40 亿区间，非空桶数量最多为 65536，但通常远小于这个值。因此亿级用户的标签组合查询通常可以在毫秒级别完成。

营销案例：精准用户筛选​

下面以电商平台的精准营销活动为例，展示 Roaring Bitmap 在用户标签系统中的实际落地效果。

场景描述​

某电商平台拥有 5 亿注册用户，每个用户分配唯一的 uint32 类型 ID。平台计划向符合以下条件的用户推送新上市智能手表的优惠券：

1. 居住在北京
2. 年龄在 25 到 35 岁之间
3. 最近 30 天有活跃行为
4. 对数码产品感兴趣

平台为每个标签维护一个 Roaring Bitmap 集合，分别为 city_beijing、age_25_35、active_30d、interest_digital。如果使用朴素位图存储，每个标签需要 512 MB，4 个标签总存储为 2 GB；而使用 Roaring Bitmap 可以根据每个标签的命中情况动态选择容器，大幅降低存储成本。

存储成本估算​

假设各标签的命中用户数和分布如下：

• city_beijing：北京用户约 5000 万，分布在约 5000 个桶中，平均每个桶约 10000 个用户（超过 4096 阈值），使用位图容器。总存储：5000 * 8 KB = 40 MB。
• age_25_35：该年龄段用户约 1 亿，分布在约 10000 个桶中，平均每个桶约 10000 个用户，使用位图容器。总存储：10000 * 8 KB = 80 MB。
• active_30d：最近 30 天活跃用户约 3 亿，分布在约 50000 个桶中，平均每个桶约 6000 个用户，使用位图容器。总存储：50000 * 8 KB = 400 MB。
• interest_digital：对数码产品感兴趣的用户约 8000 万，分布在约 8000 个桶中，平均每个桶约 10000 个用户，使用位图容器。总存储：8000 * 8 KB = 64 MB。

4 个标签的总存储约为 40 + 80 + 400 + 64 = 584 MB，仅为朴素位图方案的 28.5%，如果部分标签命中用户更稀疏，存储优势会更加明显。

查询执行流程​

目标用户集合的查询逻辑为四个标签的交集：

target = city_beijing AND age_25_35 AND active_30d AND interest_digital

执行流程分为三步：

1. 对 city_beijing 和 age_25_35 求交集：先对两个 Bitmap 的桶索引求交，得到约几千个共同桶，再对每个共同桶内的位图容器执行按位与运算，得到中间结果 tmp1。
2. 对 tmp1 和 active_30d 求交集：同样先求桶索引交，再逐桶执行按位与，得到中间结果 tmp2。
3. 对 tmp2 和 interest_digital 求交集：得到最终目标用户集合 target。

性能分析​

在上述场景中，每一步交集运算涉及几千到几万个桶的位图按位与操作。现代 CPU 的 AVX2 指令集可以一次处理 256 位（32 字节）数据，一个 8 KB 的位图容器仅需 256 次 SIMD 运算即可完成按位与。假设单步交集有 5000 个共同桶，单步运算需要 5000 * 256 = 128 万次 SIMD 操作，在 GHz 级别的 CPU 上仅需几毫秒即可完成。三步交集运算总耗时通常在 10~30 毫秒级别，完全满足营销活动的实时性要求。

查询优化实践​

在实际落地中，可以通过调整查询顺序进一步提升性能：优先对命中率更低的标签求交集，尽早缩小中间结果集，减少后续运算的数据量。例如上述场景中，city_beijing（5000 万）和 interest_digital（8000 万）的命中率更低，可以先对这两个标签求交集，再与 age_25_35 和 active_30d 求交，减少共同桶的数量，降低运算开销。

总结​

Roaring Bitmap 是一种为大规模整数集合设计的高性能压缩位图数据结构，通过「高 16 位分桶、低 16 位自适应容器」的分治设计，完美平衡了存储效率和运算性能。在用户标签系统的场景中，Roaring Bitmap 能够以远低于朴素位图的存储成本，支持亿级用户的多标签组合查询，毫秒级完成交集、并集等集合运算，是精准营销、用户筛选等场景的理想技术方案。

对于需要管理大规模用户标签的互联网产品，Roaring Bitmap 的核心价值在于：

1. 自适应选择三种容器类型，适配稀疏、稠密、连续等多种数据分布，无需业务方手动优化。
2. 分治的桶结构支持逐桶并行运算，配合 SIMD 加速可以实现极低的查询延迟。
3. 存储成本随数据稀疏度动态变化，避免固定位图的空间浪费。

通过合理设计标签体系、优化查询执行顺序，Roaring Bitmap 可以为业务提供高效、可扩展的用户筛选能力，支撑精准营销等场景的核心需求。