本文介绍了Hologres RoaringBitmap的功能，希望可以帮助更多的业务利用Hologres RoaringBitmap能力，实现更快更准的画像分析。
业务介绍
我们团队所在的用户运营平台技术团队是一支懂用户，技术驱动的年轻队伍，团队立足体系化打造业界领先的用户增长基础设施，以媒体外投平台、ABTest平台、用户运营平台为代表的基础设施赋能用户增长，日均处理数据量千亿规模、调用QPS千万级。
在用户规模达到一定量级的情况下，单一的运营策略对于用户的效果愈发有限，人群分析的能力，因此显得尤为重要，它能帮助我们发现潜在用户、找寻运营时机，为策略调整提供数据支持。技术平台在过去一直采用MaxCompute进行画像分析，中途尝试过直接通过Hologres加速查询，但由于数据量级太大，在画像分析的效率上仍然存在一定的问题。为了解决Hologres的加速查询效率问题，我们团队调研了Hologres的RoaringBitmap画像方案，并在技术平台落地，成功让3-5min的画像分析提升到10s左右，显著提升人群分析的效率，为业务决策提供快速的依据。通过本文我将会分享RoaringBitmap方案在技术平台画像分析的应用实践。
Bitmap原理解释
▐ Bitmap数据结构
Bitmap是一种通过位（bit）来存储和操作数据的数据结构，具备高度的空间效率和计算效率。它在人群画像分析中，例如跟踪大型网站用户行为时，能够极大地节省存储空间，并提高处理速度。
原理描述：
- 用一个bit位来标记某个元素对应的Value，而Key即是该元素。
- 如果一个数存在，则将这个数对应bit设置为1，否则置为0。
如下图：有一堆用户id，其中用户id为3、4的用户是勇士球迷；如果用Bitmap表示的话，那么key是勇士球迷；value是Bit数组。那么最后用户id用Bitmap存储如下：
Bitmap的详细原理如下图：
- 默认情况下每个用户都有自己对应的一个特征，比如user0对于特征0，user1对应特征1，等等；这种是常规的存储方式，如果这样存储，计算特征的时候一般要进行关联查询。
- 我们需要把对应关系转换为Bitmap形式，Key为特征，特征背后对应的是一个Bit数组，如果用户拥有这个特征，那么对应的数组位Bit置为1。 这样只要给一个特征，就可以知道有多少用户拥有这个特征，而不需要遍历所有数据。
- 当多个特征都通过Bitmap存储的时候，多个特征进行计算只需要通过位运算就可以，而不需要再关联查询，所以极大的提升了数据处理效率。
从以上原理图可以看出，Bitmap可以将数据转化为数组位存储，不仅可以节约存储空间，也可以进一步提高查询效率。
▐ RoaringBitmap
虽然Bitmap已经让数据的存储空间有了N倍的缩减，但Bitmap的问题在于，不管业务中实际有多少个元素，它必须包含元素的最大值个bit空间，如果元素的取值范围是0-10亿，那么就要有10个bit空间，如果元素的取值比较稀疏，例如10亿个值中只有极少数据满足需求，那么这样的稀糊数据会造成严重的空间浪费，且也会占用大量的内存计算，所以我们一般还需要对Bitmap进行压缩处理。
RoaringBitmap就是一种高效的Bitmap压缩算法，适合计算超高基维的数据，常用于去重、标签筛选、时间序列等计算中。Roaring Bitmap算法是将32位的INT类型数据划分为216个数据块（Chunk），每一个数据块对应整数的高16位，并使用一个容器（Container）来存放一个数值的低16位。RoaringBitmap将这些容器保存在一个动态数组中，作为一级索引。
在 RoaringBitmap 中，容器（Container）是用于存储整数的数据结构，主要有三种类型：数组容器（Array Container）、位图容器（Bitmap Container）和运行长度编码容器（Run Container）。下面引用至RoaringBitmap的官方介绍，详情可以参考官网：https://roaringbitmap.org/
- 数组容器（Array Container）：这种容器使用一个数组来存储整数，适用于稀疏数据的情况，即数据之间的间隔较大。例如，如果一个容器内的整数数量小于4096，就使用数组容器来存储，因为在这种情况下，使用数组容器比使用位图容器更节省空间。
- 位图容器（Bitmap Container）：位图容器使用一个长度为65536的位数组（bit array）来存储数据，适用于稠密数据的情况，即数据之间的间隔较小。例如，如果一个容器内的整数数量大于4096，就使用位图容器来存储，因为在这种情况下，使用位图容器比使用数组容器更节省空间。
- 运行长度编码容器（Run Container）：运行长度编码（Run-length Encoding，RLE）是一种简单的数据压缩算法，适用于连续重复数据的情况。在 Roaring Bitmap 中，如果一系列连续的整数都存在于位图中，那么可以使用一个运行长度编码容器来存储这些连续的整数的起始值和长度，从而节省空间。
RoaringBitmap 根据实际的数据情况，动态地选择最适合的容器类型，从而实现了既高效的数据存储，又快速的数据查询。在做位图计算（AND、OR、XOR）时，RoaringBitmap提供了相应的算法来高效地实现在多个容器之间的运算，使得RoaringBitmap无论在存储和计算性能上都表现优秀。详细的实现原理图如下：
在实际的使用中一般使用RoaringBitmap来，并且官方也提供了对应的Java库地址，可以直接拿来使用。
技术平台基于RoaringBitmap的画像分析使用实践
技术用户画像分析是对一个或多个指定用户群，通过可视化的方式，可以多维、立体的展示用户群的画像信息，让运营更好的理解人群，实现人群细分及对个性化运营策略的制定提供能力支撑；在进行数据分析时，更加便捷的获得人群的特征信息，从而更好的进行定量的分析。
业务画像分析流程：
- 默认情况下平台有业务的所有标签在MaxCompute中存储，同时也会存储一份Bitmap的标签索引数据，再标签数据更新时构建。
- 业务可以使用标签和其他用户相关的数据圈选人群，人群圈选完成后，也会对其构建一份Bitmap索引数据。
- 圈选完人群后，就会进行画像分析，如果标签和人群都有Bitmap索引数据，就会通过Bitmap进行分析
▐ 方案对比
技术平台早期画像分析主要依赖于MaxCompute执行SQL，但这种方式耗时较长，对于需要实时洞察分析的业务场景，分析需要更加快速看到结果，高延迟无法满足业务需求。之前尝试通过将数据导入Hologres进行加速，然而由于数据量庞大，Hologres的执行耗时仍然超过3分钟。
在前期，根据业务需求我们也在技术上做了一些调研。从技术方案角度看，一些可以实现的画像分析的方案和其缺点：
| 方案名称 | 缺点 |
| MaxCompute进行查询 | MaxCompute的任务执行耗时较长，并且是异步的，无法满足实时查询的需求。 |
| Hologres JSONB | Hologres有JSONB列存方案，可以通过列式存储优化查询效率，但是因为业务还是有join，仍然是N^2的关联查询，大数据量的情况下查询效率相比Bitmap仍然有一定的不足。 |
| ClickHouse | 成本较高，在阿里集团内的应用场景较少，实践少。 |
而Hologres原生支持RoaringBitmap数据结构，特别适合大数据量级下的交并差运算，并且在画像分析的场景天然适合，因此我们最后选择了RoaringBitmap方案。虽然RoaringBitmap会带来额外的处理和优化步骤、索引构建过程，这可能会带来一定的初期成本上升。然而，在我们的场景中，数据更新不是那么频繁，数据量级也在可控范围内，因此这一成本上升在可接受范围。而且使用RoaringBitmap带来的效率提升非常明显，最终还是选择使用这一方案进行标签和人群加速。
▐ 核心流程
- 平台人员：筛选可加速的标签，然后配置在平台上，平台每天在标签数据更新完成后构建对应的标签Bitmap索引
- 小二同学：
- 在圈人的时候，可以考虑勾选人群开启分析加速、或者核心空间会圈完之后会自动构建人群的Bitmap索引。
- 在进行人群洞察分析的时候，点击画像分析，弹出可分析的标签，可进行加速的标签会标记🚀，然后运营可以勾选对应的标签进行分析，在1亿以下的规模，加速标签可在10秒内出结果。
- 技术平台：对平台小二筛选录入的标签进行构建Bitmap索引，人群构建Bitmap索引，画像分析的时候，执行RoaringBitmap的SQL查询操作。
▐ 整体功能设计
应用功能分层描述
- 底层存储的是我们的各种明细数据和元数据，包括 标签的明细数据、人群的明细数据以及标签和人群是否加速的配置信息。
- 中间部分是业务逻辑：通过调度任务，每日检查人群数据是否完成，标签数据是否完成，然后触发对应的加速流程；当触发对应的调度流程之后，走到右边的调度DAG任务，先构建MaxCompute Bitmap索引，然后将数据同步至Hologres，并在Hologres构建RoaringBitmap
- 最上面是Bitmap的应用场景：可以对有Bitmap索引的数据进行画像分析加速、模板分析加速、人群预估加速。
▐ 数据模型设计
由于Hologres的RoaringBitmap相关函数只支持32位，而当前uid的设计是64位的数字，并且量级也比较大，因此需要对用户ID进行分桶设计。将uid拆为低位和桶号。借鉴阿里妈妈Dolphin引擎分桶设计经验，我们将uid直接通过位移拆分为level（高44位）以及normal_uid（低20位）, 通过将uid拆分，把相同level下的normal_uid放入同一个bitmap中即可实现人群的高度压缩，减少对数据的IO操作，加速后续的查询。
标签RoaringBitmap构建结果表预估：假设每个标签平均有10个标签值，每个表存储1000个标签，按照分桶，可以根据自己的业务进行计算。记录数 = (用户量 / 2^20) * (标签个数 * 标签值 )。因为记录通过分桶被极大的进行压缩，因此在Hologres的高性能查询支撑范围之内。
对于人群也是同理，数据量级会压缩 2^20倍，因此Hologres的查询效率也会提升。业务可以按照自己的量级进行分桶设计：业务应根据具体场景进行测试，确定每个桶的最佳用户数。一般桶的用户数越多，越耗费CU，速度可能有一定提升。
- 分表策略
目前按照：用户属性rb表、人群rb表都分16个表；都是对16进行取余，然后落到对应的表上。
Hologres内表：
Hologres外部表：
- 人群和标签表，新增字段
- 标记人群是否开启加速
- 是否加速完成
- 最近一次的加速日期
public class AccelerateConfigDTO { private Boolean isAccelerationCompleted; private Boolean isAccelerationEnabled; private String lastDs; }
▐ 关键的业务SQL
- 在用Java提交MaxCompute任务的时候，记得设置如下参数
- sql.mapper.split.size默认 256M，mapper过程根据此大小进行任务数量计算。调整小容量小一点，会增大任务并发处理数量加快速度。增加速度，同时需要资源数量会增多。
- sql.submit.mode：改为script支持运行多条SQL
- 尽量选择以下几种类型的数据构建Bitmap
可枚举标签构建Bitmap
尽量选择性别、年龄、城市这种类型的有限的字段值构建bitmap，里面的value类型比较简单。MaxCompute中分桶以及构建bitmap的SQL如下：
说明：Bitmap通过在MaxCompute中构建UDF实现，不再本文中做详细描述
--MaxCompute SQL -- 创建表 CREATE TABLE IF NOT EXISTS 空间名.demo表名( field_value STRING COMMENT '标签value值', bucket BIGINT COMMENT '分桶', bitmap BINARY COMMENT 'uid bitmap' ) COMMENT '用户基础属性标签bitmap' PARTITIONED BY ( ds STRING COMMENT '日期', label_id STRING COMMENT '标签ID' ) LIFECYCLE 365 ; -- 插入数据 INSERT OVERWRITE TABLE 空间名.demo表名 PARTITION(ds='${bizdate}', label_id='${label_id}') SELECT COALESCE(${label_field}, 'NULL') as field_value ,SHIFTRIGHT(CAST(COALESCE(${uidField}, '0') AS BIGINT), 20) as bucket ,ENCODE(mc_rb_build_agg(CAST(COALESCE(${uidField}, '0') as BIGINT) & 1048575), 'utf-8') as bitmap FROM ${dataSource}.${dataTable} WHERE ds=MAX_PT('${dataSource}.${dataTable}') AND CAST(COALESCE(${uidField}, '0') AS BIGINT) > 0 GROUP BY COALESCE(${label_field}, 'NULL'), SHIFTRIGHT(CAST(COALESCE(${uidField}, '0') AS BIGINT), 20) ;
人群数据构建Bitmap
因为人群只包含uid的明细，构建起来会比较简单，并且快速。如下是在MaxCompute中分桶以及构建Bitamp，Bitmap通过udf构建。
--MaxCompute SQl CREATE TABLE IF NOT EXISTS 空间名.demo人群表名 ( bucket BIGINT COMMENT '分桶', bitmap BINARY COMMENT 'uid bitmap', ds STRING ) COMMENT '奥格圈人bitmap表' PARTITIONED BY ( crowd_id STRING ) LIFECYCLE 365; INSERT OVERWRITE TABLE 空间名.demo人群表名 PARTITION(crowd_id='${crowd_id}') SELECT SHIFTRIGHT(uid, 20) bucket ,ENCODE(mc_rb_build_agg(cast(uid as BIGINT ) & 1048575), 'utf-8') as bitmap ,ds FROM crowdSourceDemo -- 原始人群表 WHERE crowd_id = '${crowd_id}' GROUP BY SHIFTRIGHT(cast(uid as BIGINT ), 20),ds ;
- Bitmap标签数据同步Hologers
通过在Hologres中创建外表的方式将MaxCompute中的标签数据导入至Hologres。
--Hologres SQL CREATE FOREIGN TABLE IF NOT EXISTS public.foreign_table( field_value TEXT, bucket INT8, bitmap BYTEA, ds TEXT, label_id TEXT ) server odps_server options(project_name '${projectName}', table_name 'foreign_table_${index}'); BEGIN; CREATE TABLE IF NOT EXISTS public.holo_table( field_value TEXT, bucket INT8, bitmap roaringbitmap, ds TEXT, label_id TEXT, PRIMARY KEY (ds,label_id,bucket,field_value) ) PARTITION BY LIST(ds); call set_table_property('public.holo_table_${index}', 'distribution_key', 'field_value,bucket'); call set_table_property('public.holo_table_${index}', 'clustering_key', 'ds,label_id'); -- 表数据生命周期：365天 call set_table_property('public.holo_table_${index}', 'time_to_live_in_seconds', '31536000'); END; --创建分区子表 CREATE TABLE IF NOT EXISTS "public".holo_table_${bizdate} PARTITION OF "public".holo_table_${index} FOR VALUES IN ('${bizdate}'); --数据写入至Hologres INSERT INTO "public".holo_table_${bizdate} SELECT field_value, bucket, bitmap, ds, label_id FROM public.foreign_table_${index} WHERE ds='${bizdate}' and label_id='${label_id}' ON CONFLICT(ds,label_id,bucket,field_value) DO UPDATE SET (field_value, bucket, bitmap, ds, label_id) = ROW (excluded.*) ;
- Bitmap人群数据同步Hologres
通过在Hologres中创建外表的方式将MaxCompute中的人群数据导入至Hologres。
--Hologres SQL CREATE FOREIGN TABLE IF NOT EXISTS public.foreign_crowd_table( bucket INT8, bitmap BYTEA, ds TEXT, crowd_id TEXT ) server odps_server options(project_name '${projectName}', table_name 'foreign_crowd_table_${index}'); BEGIN; CREATE TABLE IF NOT EXISTS public.holo_crowd_table( bucket INT8, bitmap roaringbitmap, ds TEXT, crowd_id TEXT, PRIMARY KEY (ds,bucket,crowd_id) ) PARTITION BY LIST(crowd_id); call set_table_property('public.holo_crowd_table_${index}', 'distribution_key', 'bucket'); call set_table_property('public.holo_crowd_table_${index}', 'clustering_key', 'ds,crowd_id'); -- 表数据生命周期：365天 call set_table_property('public.holo_crowd_table_${index}', 'time_to_live_in_seconds', '31536000'); END; DROP TABLE IF EXISTS "public".holo_crowd_table_${crowd_id}; CREATE TABLE IF NOT EXISTS "public".holo_crowd_table_${index}_${crowd_id} PARTITION OF "public".holo_crowd_table_${index} FOR VALUES IN ('${crowd_id}'); INSERT INTO "public".holo_crowd_table_${index}_${crowd_id} SELECT bucket, bitmap, ds, crowd_id FROM public.foreign_crowd_table_${index} where crowd_id='${crowd_id}'
- 画像分析SQL
在Hologres中将进行画像分析。
--Hologres SQL SELECT ${label_alias} as "${label_name}" ,sum(rb_and_cardinality(t1.bitmap, t2.bitmap)) as "人数" FROM ( SELECT bucket ,bitmap FROM public.holo_crowd_table WHERE crowd_id='${crowd_id}' ) as t1 JOIN ( SELECT field_value ,bucket ,bitmap FROM public.holo_table WHERE ds= '${label_ds}' AND label_id = '${label_id}' ) as t2 on t1.bucket = t2.bucket GROUP BY ${label_alias}
说明：label_alias最简单的方式是t2.field_value；直接取构建的结果用来展示，复杂的则是要在代码层面做个映射关系，不同分级的中文含义。
▐ 方案的关键部分说明
- 用户识别码 (UID) 分桶设计：由于用户数量较大，决定在一个桶中放置多少用户变得尤为重要。业务应根据具体场景进行测试，确定每个桶的最佳用户数。一般桶的用户数越多，越耗费CU，速度可能有一定提升。
- 分析结果异步返回设计：虽然Bitmap加速后80%以上的场景都可以在10秒内返回，但对于可能产生大量桶的偏好类标签，可能会超过接口超时时长限制，因此需要设计一种有效的异步机制。如果初次查询未能返回结果，系统将返回相应的任务ID (taskid)。然后，通过taskid，交互侧可以进行轮询以获取结果。
- 构建任务调度设计：整个构建和同步过程都是耗时较长的任务，因此需要一个有效的调度机制。技术已经拥有一套基于有向无环图 (DAG) 的调度流程，在技术侧可以直接采用。
从3分钟到秒级，画像分析效率对比
基于Bitmap的画像分析，75%的的比例在10秒之内可以出结果，个别由于数量级过大(例如几十亿人群规模，以及一些复杂的标签) 会有一些长耗时的执行。
| 耗时 | bitmap占比 | ODPS占比 |
| 1~5s | 22.30% | 0% |
| 5~10s | 39.50% | 0% |
| 10~30s | 25.00% | 0% |
| 30~60s | 2.60% | 9.10% |
| 1~5m | 6.60% | 79.00% |
| 5~10m | 3.90% | 9.90% |
| >10m | 0% | 2.10% |
统计运营常用的10个标签，可以看到Bitmap的平均耗时对比maxCompute耗时缩短了至少2倍的时间，最高能提升20几倍的查询效率。
总结
通过Hologres RoaringBitmap的功能，我们技术平台实现了从原来的分钟级画像计算，到千亿级人群画像秒级分析体验，帮助业务查询效率提升几十倍，也进一步节约了计算资源。
也希望通过这篇文章的分享，帮助更多的业务利用Hologres RoaringBitmap能力，实现更快更准的画像分析。
团队介绍
大淘宝技术用户运营平台技术团队是一支最懂用户，技术驱动的年轻队伍，以用户为中心，通过技术创新提升用户全生命周期体验，持续为用户创造价值。
团队以创新为核心价值观之一，鼓励团队成员在工作中不断探索、实验和创新，以推动业界技术的进步和用户体验的提升。我们不仅关注当前业界领先的技术，更注重未来技术的预研和应用。团队成员会积极参与学术研究和技术社区，不断探索新的技术方向和解决方案。
团队立足体系化打造业界领先的用户增长基础设施，以媒体外投平台、ABTest平台、用户运营平台为代表的基础设施赋能阿里集团用户增长，日均处理数据量千亿规模、调用QPS千万级。在用户增长技术团队，我们提供“增长黑客”极客氛围和丰富的岗位选择，欢迎业界贤才加入。
