1. Bitmap 简介

在 32 位计算机上，对于一个整型数字，比如 int a = 1 在内存中通常占用 4 个字节（32bit, 1Byte = 8bit），这是为了方便机器的运算。但对于某些应用场景而言，这其实是一种巨大的浪费。

Bitmap 的基本思想就是用一个 bit 位来标记某个元素对应的 value，而 key 即是该元素。由于采用了 bit 为单位来存储数据，因此可以大大节省存储空间。这里依次存入 4、2、1、3 为例进行说明（其实就是在下标对应的位置标记 1），如图所示：

假设有这样一个需求：在 20 亿个随机整数中找出某个数 m 是否存在其中，并假设 32 位操作系统，4G 内存。

1. 在 Java 语言中，int 类型占 4 字节，如果每个数字用 int 存储，那就是 20 亿个 int，占用的空间约为 (2000000000 * 4 / 1024 / 1024 / 1024) ≈ 7.45G
2. 如果按位存储就不一样了，20 亿个数就是 20 亿个 bit，占用空间约为 (2000000000 / 8 / 1024 / 1024 / 1024) ≈ 0.233G

二者相比，高下立判。

Bitmap 节省存储空间的优点很明显，不过它也有缺点：只能保存不重复的数据。此外还有数据稀疏的问题，比如要存储两个数字 1 和 10000000，同样需要 10000000 bit 的空间存储，这是一种巨大的浪费！

如何对这个问题进行优化呢？这就需要 Roaring bitmap 了。

2. Roaring bitmap 简介

Roaring bitmap 是一种高效压缩位图，简称 RBM。RBM 的概念于 2016 年由 S. Chambi、D. Lemire、O. Kaser 等人在论文《Better bitmap performance with Roaring bitmaps》、《Consistently faster and smaller compressed bitmaps with Roaring》中提出，下面对其简单介绍。

• 实现思路

RBM 是由两个长度为 2^16 的数组实现的，二者一一对应，一个是 key 数组，一个是 value 数组（称为 Container，包括 ArrayContainer, BitmapContainer, RunContainer 三种）。结构示意图如下：

在存储和查询数值时，将无符号的 int 类型数据（32 bit）划分为高 16 位和低 16 位。其中高 16 位的值作为索引，低 16 位的值作为数据保存到 Container 中。数据写入过程如图所示：

Container 分为三种，ArrayContainer, BitmapContainer, RunContainer，当 Container 的数据量小于 4096（8K） 时，内部使用 ArrayContainer 来存储，当超过 4096 时使用 BitmapContainer。

至于为什么是 4096，其实这是一个临界值：ArrayContainer 占用空间是线性增长的，而 BitmapContainer 则是常量，二者元素数量和占用内存变化如果所示：

RunContainer 中的 Run 指的是行程长度压缩算法（Run Length Encoding），对连续数据有比较好的压缩效果。

有关 RBM 的介绍就到这里，下面介绍 RBM 在当贝用户分群中的实践。

3. Roaring bitmap 在当贝用户分群中的实践

3.1 背景

想象一下，当你沉浸在当贝投影的精彩内容中时，如果平台能够精准地根据你的个人属性、兴趣偏好和行为习惯，为你推送最符合你口味和需求的内容，那么你将能更加轻松地发现和享受你真正感兴趣的内容，从而大大节省了寻找和筛选的时间。

而这一切美好愿景的背后都离不开一项至关重要的技术支撑：用户画像。它就如同一个精准的指南针，帮助平台指引方向，为用户和商家带来更加个性化和高效的互动体验。

用户画像背后则需要海量数据的支持。以当贝用户分群为例，需要对大量用户数据进行分群，比如按年龄段、按一二三四线城市、按购买次数、消费金额等等进行分群，运营可以根据这些分群数据进行精准营销。

由于分群是每天随时产生的，面对大量的用户，由此产生的分群数据也是非常巨大的，需要耗费大量的计算和存储资源。此前存储使用的是 MySQL 分表存储，在每个分群中，一个用户占用一条记录。可想而知，这样占用的存储空间是非常巨大的，单日的存储空间消耗达到几十 GB，还是非常耗费资源的，而且查询起来也比较耗时。

怎样对此进行优化呢？这就用到前面提及的 Roaring bitmap 了。

3.2 Roaring bitmap 应用

为解决用户分群数据占用大量存储空间，且查询较慢的问题，我们引入了 PostgreSQL + Roaring bitmap 进行优化，PostgreSQL 中使用 Roaring bitmap 的步骤及常见的增删改查举例如下：

• PostgreSQL 安装 Roaring bitmap 依赖库

-- 安装插件
CREATE EXTENSION roaringbitmap;

-- 创建一个名为 user_group_bitmap 的数据类型
begin;
create table user_group_bitmap
(   id            integer not null,
    group_index   integer not null,
    shard_index   integer not null,
    bit_index     roaringbitmap,
    ymd           text    not null,
    primary key (ymd,
                 group_index,
                 shard_index)
) partition by range (ymd);
COMMENT ON TABLE user_group_bitmap IS '用户分群数据';
COMMENT ON column user_group_bitmap.id is 'ID';
COMMENT ON column user_group_bitmap.group_index is '分组';
COMMENT ON column user_group_bitmap.shard_index is '分片';
COMMENT ON column user_group_bitmap.bit_index is '位图';
COMMENT ON column user_group_bitmap.ymd is '日期';
commit;

-- 创建分区
CREATE TABLE IF NOT EXISTS user_group_bitmap_20240101 PARTITION 
OF user_group_bitmap
FOR VALUES FROM ('20240101') to ('20240102');

• 增删改查

-- 写入数据
INSERT INTO user_group_bitmap
(id, group_index, shard_index, bit_index, ymd)
VALUES (1000, 1, 2, RB_BUILD(ARRAY[1000,2000,3000,4000]), '20240101');

-- 更新数据
UPDATE user_group_bitmap
SET bit_index = RB_OR(bit_index, RB_BUILD(ARRAY[40,5466,4545]))
WHERE ymd = '20240101'
  AND id = 1000
  AND group_index = 1
  AND shard_index = 2;

-- 判断用户是否在分群中
select 
-- 还原用户id
RB_ITERATE(RB_AND(bit_index, RB_BUILD(array[2000]))) + (group_index * 1024 * 1024) as user_id,
from user_group_bitmap
where ymd = '20240101'
and id = 1000
and group_index = 1
and shard_index = 2;

• 查询某个分群下用户个数

select sum(RB_CARDINALITY(bitmap)) as total
from user_group_bitmap
where ymd = '20240101'
and id = 1000;

• 计算并保存分群中的用户ID

自定义的 BitmapKey 类：

public class BitmapKey {
    /**
     * 分组
     */
    private Integer groupIndex;

    /**
     * bit位
     */
    private Integer bitIndex;

    public BitmapKey(Integer groupIndex, Integer bitIndex) {
        this.groupIndex = groupIndex;
        this.bitIndex = bitIndex;
    }
}

根据用户ID计算在 Bitmap 中存储的值：

private static final int ONE_BITMAP_SIZE = 1 << 20;

/**
 * 计算用户 ID 在 Bitmap 中的存储位置
 * @param userId 用户 ID
 * @return 用户 ID 在 Bitmap 中的存储位置
 */
public static BitmapKey computeUserGroup(Long userId) {
    // 计算分组
    Integer groupIndex = Convert.toInt(userId / ONE_BITMAP_SIZE);
    // 计算（分组-分片）下的offset位置
    Integer bitIndex = Convert.toInt(userId % ONE_BITMAP_SIZE);
    return new BitmapKey(groupIndex, bitIndex);
}

将包含用户 ID 信息的 groupIndex 和 bitIndex，通过上述 RB_BUILD 和 RB_OR 等函数保存和更新到 PostgreSQL 的 Roaring bitmap 类型字段中，内容如下：

其中 group_index 为分区，bit_index 中的值以 Roaring bitmap 存储，每组 group_index 和 bit_index 都存储了非常多的用户 ID。使用 RB_ITERATE 函数可以对其进行还原，如图：

3.3 使用 Roaring bitmap 前后对比

引入 Roaring bitmap 之前，用户分群数据以 MySQL 记录的形式存储，占用存储空间非常大，单日数据达到 50GB+，如果要保存一周的数据，大概有 300GB+。

使用 Roaring bitmap 后，现在每天分群数据占用空间大概为 300MB，而且查询速度也有较大提升。

得益于 Roaring bitmap 在用户分群的出色表现，当贝用户标签系统当前也正在改造实践中。

4. 小结

本文主要对 Bitmap 和 Roaring bitmap 的实现原理和优缺点进行了简要介绍，并分享了 PostgreSQL + Roaring bitmap 在当贝用户分群中的实践。

Bitmap 这种数据结构此前使用较少，但经过这次实践，收获到了不错的效果！Bitmap 还有其他更多的功能，感兴趣的朋友们可以进一步探索和分享。

本文分享就到这里，感谢大家！

参考链接

1. https://github.com/RoaringBitmap/

2. https://arxiv.org/pdf/1402.6407.pdf

3. https://help.aliyun.com/zh/rds/apsaradb-rds-for-postgresql/use-the-roaringbitmap-extension