面经策

用 Bitmap 来存储 100 个用户 ID，但是这个 ID 的范围很大，此时会有什么问题？如何解决？ ​

  • 标签：后端、场景题

🏛 业务架构师 ​

Bitmap 存 100 个用户 ID 但 ID 范围很大（比如 64 位ID）的问题很明确：Bitmap 按"最大 ID 值"分配空间，和存了多少个无关——ID 范围到 40 亿，存 100 个也要 500MB，空间利用率 0.0000025%，纯粹为 100 个值付了 40 亿的成本。

问题本质：Bitmap 适合值域稠密的场景（连续 ID、全量活跃用户），稀疏值域下它是灾难。

解决方案

方案一：映射压缩（字典编码） 维护"原始 ID → 连续自增序号"的映射（Redis String/INCR 或 DB 自增表），bitmap 存序号。适合 ID 集合相对稳定、多次复用的场景（固定运营名单、圈人包）。代价：多一次映射查询，映射表本身也是存储。

方案二：RoaringBitmap（业界标准答案）

  • 把 32 位空间切成 2^16 个容器（每个管 65536 个值域段）
  • 容器按密度自适应存储：稀疏段用数组（array container），稠密段才用 bitmap，中间态用游程编码
  • 结果：稀疏数据压缩几个数量级，稠密数据保持 bitmap 性能，且支持跨 bitmap 的交并运算（AND/OR），是画像系统、去重统计的事实标准
java
RoaringBitmap bitmap = new RoaringBitmap();
bitmap.add(9_876_54_321L); // 稀疏大ID, 只占几十字节

架构师视角的应用判断

  • 用户标签/人群圈选（存多个亿级集合做交集）：RoaringBitmap 几乎是唯一正解，ClickHouse 也内置支持
  • 值域连续可控（如自增 UID）：普通 bitmap 就够
  • 不需要集合运算、只要"是否存在"：直接 Redis Set 或布隆过滤器，别为了"Bitmap 快"的字面印象付稀疏的代价
  • 选数据结构先看值域分布和操作类型，不是看哪个听起来高级

🏗 系统架构师 ​

问题很直接：Bitmap 按值域定长，ID 范围大就意味着空间爆炸。

问题量化：Bitmap 的下标是 ID 本身，100 个用户但 ID 到 10 亿，就需要 10 亿 bit ≈ 125MB，存 100 个值利用率只有 1/10^7。且 Redis 的 SETBIT 超长偏移会一次性补齐中间的空位，一个误操作就把 Redis 内存打爆（maxmemory 直接 OOM 命令被拒）。

解决方案按场景选：

  1. Roaring Bitmap 压缩位图（首选）：把 32 位空间切成 2^16 个 chunk，每个 chunk 内按密度自适应：稀疏用数组存、中等用位图、连续用 RLE。10 亿值域里的 100 个值只占几百字节。Redis 用 REDIS BIT 模块（RedisBloom 的 CBloom）或 RoaringBitmap 库在应用层维护；大数据组件（Spark/Doris/ClickHouse）都原生支持 Roaring，这是亿级用户标签圈选的标准方案。

  2. ID 映射（重排为稠密序号）：维护 原始ID → 自增序号 的映射表（DB 自增或 Redis INCR 分配），Bitmap 用序号做下标，值域永远稠密（用户数 = bit 数）。代价是每次 set/get 前多一次映射查询，适合用户规模可控的增长型业务。

  3. Hash 分桶：ID 按 hash 分到多个小 Bitmap，单桶值域受限，空间可控，适合分布式分片存储。

我的选型：用户标签/签到类场景直接 Roaring；需要与原始 ID 双向查询、数据需长期精确的就 ID 映射。要点是把"空间 = 值域/8"和"压缩后 ≈ 与基数相关"这笔账当场算出来。

💻 全栈开发专家 ​

问题很明确：Bitmap 按值直接定偏移，稀疏大范围 ID 会浪费海量内存。100 个 ID、最大值 10 亿，就需要 10 亿 bit ≈ 120MB，利用率万分之一。

解决两条路

路一：RoaringBitmap（压缩位图，首选）

把 32 位值按高 16 位分桶，每个桶 65536 个值，桶内按密度自适应容器：

  • 稀疏（< 4096 个）：数组容器排序存储；
  • 稠密：位图容器（8KB 定长）；
  • 连续：游程容器（RLE）。

100 个稀疏 ID 只需几百字节，同时保留位图的交并运算能力。

xml
<dependency>
    <groupId>org.roaringbitmap</groupId>
    <artifactId>RoaringBitmap</artifactId>
</dependency>
java
RoaringBitmap rb = new RoaringBitmap();
rb.add(987_654_321L);
rb.contains(987_654_321L);

Redis 侧也有对应模块 redis-cell 之外的 RedisBloom（CRoaring 内核），BF.ADD/BF.EXISTS。

路二：ID 映射（字典编码）

ID → 自增序号（发号器/映射表），bitmap 只按序号存，100 个 ID 用 128 bit 就够。代价是维护映射与查询时多一次转换，适合 ID 集合相对稳定的场景（如用户分群标签）。

选型 要集合运算（交并、去重统计）→ RoaringBitmap；要极简 + ID 集合固定 → 字典映射；数据量小到没运算需求，直接 HashSet 就够了，别为了炫技上位图。