写点什么

Hologres RoaringBitmap 实践:千亿级画像数据秒级分析

  • 2023-09-18
    浙江
  • 本文字数:7178 字

    阅读完需:约 24 分钟

简介:  淘宝用户增长团队使用 Hologres 的 RoaringBitmap 画像方案,成功让 3-5min 的画像分析提升到 10s 左右,显著提升人群分析的效率,为业务决策提供快速的依据。本文将会分享 Hologres RoaringBitmap 方案在画像分析的应用实践。


作者:艾贺(致问) 阿里集团技术开发

业务介绍

淘宝用户增长团队所在的用户运营平台技术团队是一支懂用户,技术驱动的年轻队伍,团队立足体系化打造业界领先的用户增长基础设施,以媒体外投平台、ABTest 平台、用户运营平台为代表的基础设施赋能用户增长,日均处理数据量千亿规模、调用 QPS 千万级。


在用户规模达到一定量级的情况下,单一的运营策略对于用户的效果愈发有限,人群分析的能力,因此显得尤为重要,它能帮助我们发现潜在用户、找寻运营时机,为策略调整提供数据支持。技术平台在过去一直采用 MaxCompute 进行画像分析,中途尝试过直接通过 Hologres 加速查询,但由于数据量级太大,在画像分析的效率上仍然存在一定的问题。为了解决 Hologres 的加速查询效率问题,我们团队调研了 Hologres 的 RoaringBitmap 画像方案,并在技术平台落地,成功让 3-5min 的画像分析提升到 10s 左右,显著提升人群分析的效率,为业务决策提供快速的依据。通过本文我将会分享 RoaringBitmap 方案在技术平台画像分析的应用实践。

Bitmap 原理解释

1、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 可以将数据转化为数组位存储,不仅可以节约存储空间,也可以进一步提高查询效率。

2、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 的画像分析使用实践

技术用户画像分析是对一个或多个指定用户群,通过可视化的方式,可以多维、立体的展示用户群的画像信息,让运营更好的理解人群,实现人群细分及对个性化运营策略的制定提供能力支撑;在进行数据分析时,更加便捷的获得人群的特征信息,从而更好的进行定量的分析。


业务画像分析流程:


1、默认情况下平台有业务的所有标签在 MaxCompute 中存储,同时也会存储一份 Bitmap 的标签索引数据,再标签数据更新时构建。


2、业务可以使用标签和其他用户相关的数据圈选人群,人群圈选完成后,也会对其构建一份 Bitmap 索引数据。


3、圈选完人群后,就会进行画像分析,如果标签和人群都有 Bitmap 索引数据,就会通过 Bitmap 进行分析



1、方案对比

技术平台早期画像分析主要依赖于 MaxCompute 执行 SQL,但这种方式耗时较长,对于需要实时洞察分析的业务场景,分析需要更加快速看到结果,高延迟无法满足业务需求。之前尝试通过将数据导入 Hologres 进行加速,然而由于数据量庞大,Hologres 的执行耗时仍然超过 3 分钟。


在前期,根据业务需求我们也在技术上做了一些调研。从技术方案角度看,一些可以实现的画像分析的方案和其缺点:


而 Hologres 原生支持 RoaringBitmap 数据结构,特别适合大数据量级下的交并差运算,并且在画像分析的场景天然适合,因此我们最后选择了 RoaringBitmap 方案。虽然 RoaringBitmap 会带来额外的处理和优化步骤、索引构建过程,这可能会带来一定的初期成本上升。然而,在我们的场景中,数据更新不是那么频繁,数据量级也在可控范围内,因此这一成本上升在可接受范围。而且使用 RoaringBitmap 带来的效率提升非常明显,最终还是选择使用这一方案进行标签和人群加速。

2、核心流程

  • 平台人员:  筛选可加速的标签,然后配置在平台上,平台每天在标签数据更新完成后构建对应的标签 Bitmap 索引

  • 小二同学:

  • 在圈人的时候,可以考虑勾选人群开启分析加速、或者核心空间会圈完之后会自动构建人群的 Bitmap 索引。

  • 在进行人群洞察分析的时候,点击画像分析,弹出可分析的标签,可进行加速的标签会标记🚀,然后运营可以勾选对应的标签进行分析,在 1 亿以下的规模,加速标签可在 10 秒内出结果。

  • 技术平台:  对平台小二筛选录入的标签进行构建 Bitmap 索引,人群构建 Bitmap 索引,画像分析的时候,执行 RoaringBitmap 的 SQL 查询操作。

3、整体功能设计

应用功能分层描述


  • 底层存储的是我们的各种明细数据和元数据,包括 标签的明细数据、人群的明细数据以及标签和人群是否加速的配置信息。

  • 中间部分是业务逻辑:通过调度任务,每日检查人群数据是否完成,标签数据是否完成,然后触发对应的加速流程; 当触发对应的调度流程之后,走到右边的调度 DAG 任务,先构建 MaxCompute Bitmap 索引,然后将数据同步至 Hologres,并在 Hologres 构建 RoaringBitmap

  • 最上面是 Bitmap 的应用场景:可以对有 Bitmap 索引的数据进行画像分析加速、模板分析加速、人群预估加速。

4、数据模型设计

由于 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 分桶,可以根据自己的业务进行计算。 记录数 = (用户量 / 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;}
复制代码

5、关键的业务 SQL

1)在用 Java 提交 MaxCompute 任务的时候,记得设置如下参数:


  • sql.mapper.split.size 默认 256M,mapper 过程根据此大小进行任务数量计算。调整小容量小一点,会增大任务并发处理数量加快速度。 增加速度,同时需要资源数量会增多。

  • sql.submit.mode:改为 script 支持运行多条 SQL


2)尽量选择以下几种类型的数据构建 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 bitmapFROM ${dataSource}.${dataTable}WHERE ds=MAX_PT('${dataSource}.${dataTable}') AND CAST(COALESCE(${uidField}, '0') AS BIGINT) > 0GROUP BY COALESCE(${label_field}, 'NULL'), SHIFTRIGHT(CAST(COALESCE(${uidField}, '0') AS BIGINT), 20);
复制代码


  • 人群数据构建 Bitmap


因为人群只包含 uid 的明细,构建起来会比较简单,并且快速。如下是在 MaxCompute 中分桶以及构建 Bitamp,Bitmap 通过 udf 构建。


--MaxCompute SQlCREATE 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 ,dsFROM crowdSourceDemo -- 原始人群表WHERE crowd_id = '${crowd_id}'GROUP BY SHIFTRIGHT(cast(uid as BIGINT ), 20),ds;
复制代码


3)Bitmap 标签数据同步 Hologers


通过在 Hologres 中创建外表的方式将 MaxCompute 中的标签数据导入至 Hologres。


--Hologres SQLCREATE FOREIGN TABLE IF NOT EXISTS public.foreign_table(  field_value TEXT,  bucket INT8,  bitmap BYTEA,  ds TEXT,  label_id TEXT)server odps_serveroptions(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}');
--数据写入至HologresINSERT INTO "public".holo_table_${bizdate}SELECT field_value, bucket, bitmap, ds, label_idFROM 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.*);
复制代码


4)Bitmap 人群数据同步 Hologres


通过在 Hologres 中创建外表的方式将 MaxCompute 中的人群数据导入至 Hologres。


--Hologres SQLCREATE FOREIGN TABLE IF NOT EXISTS public.foreign_crowd_table(  bucket INT8,  bitmap BYTEA,  ds TEXT,  crowd_id TEXT)server odps_serveroptions(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_idFROM public.foreign_crowd_table_${index}where crowd_id='${crowd_id}'
复制代码


5)画像分析 SQL


在 Hologres 中将进行画像分析。


--Hologres SQLSELECT ${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.bucketGROUP BY ${label_alias}
复制代码


说明:label_alias 最简单的方式是 t2.field_value;直接取构建的结果用来展示,复杂的则是要在代码层面做个映射关系,不同分级的中文含义。

6、方案的关键部分说明

1、用户识别码 (UID) 分桶设计:  由于用户数量较大,决定在一个桶中放置多少用户变得尤为重要。业务应根据具体场景进行测试,确定每个桶的最佳用户数。一般桶的用户数越多,越耗费 CU,速度可能有一定提升。


2、分析结果异步返回设计:  虽然 Bitmap 加速后 80%以上的场景都可以在 10 秒内返回,对于可能产生大量桶的偏好类标签,可能会超过接口超时时长限制,因此需要设计一种有效的异步机制。如果初次查询未能返回结果,系统将返回相应的任务 ID (taskid)。然后,通过 taskid,交互侧可以进行轮询以获取结果。


3、构建任务调度设计:  整个构建和同步过程都是耗时较长的任务,因此需要一个有效的调度机制。技术已经拥有一套基于有向无环图 (DAG) 的调度流程,在技术侧可以直接采用。

从 3 分钟到秒级,画像分析效率对比

基于 Bitmap 的画像分析,75%的的比例在 10 秒之内可以出结果,个别由于数量级过大(例如几十亿人群规模,以及一些复杂的标签) 会有一些长耗时的执行。



统计运营常用的 10 个标签,可以看到 Bitmap 的平均耗时对比 maxCompute 耗时缩短了至少 2 倍的时间,最高能提升 20 几倍的查询效率。



总结

通过 Hologres RoaringBitmap 的功能,我们技术平台实现了从原来的分钟级画像计算,到千亿级人群画像秒级分析体验,帮助业务查询效率提升几十倍,也进一步节约了计算资源。


也希望通过这篇文章的分享,帮助更多的业务利用 Hologres RoaringBitmap 能力,实现更快更准的画像分析。

发布于: 刚刚阅读数: 3
用户头像

还未添加个人签名 2020-10-15 加入

分享阿里云计算平台的大数据和AI方向的技术创新和趋势、实战案例、经验总结。

评论

发布
暂无评论
Hologres RoaringBitmap实践:千亿级画像数据秒级分析_大数据_阿里云大数据AI技术_InfoQ写作社区