写点什么

BitMap 转置算法:不一样的 Count 求解方式

发布于: 2021 年 05 月 19 日
BitMap 转置算法:不一样的 Count 求解方式

背景


通常在移动端 APP 的数据统计分析中,用户在未登录的情况使用 APP 都会被赋予一个基于设备标识 ( 例如 IDFA , AndroidID ) 的访问用户 ID ,在登录后会被 APP 端根据账号信息赋予一个全局唯一的登录用户 ID ,基于访问用户 ID 或登录用户 ID , 数据平台可以轻松的统计出该用户在 APP 端的访问情况。

但是移动端的灵活导致了同一用户可以在多个设备上登录同一 APP ,  也可以在同一设备上登录不同的账号,这些行为导致在做移动端数据分析时,会遇到下列几个问题:

  • 同一个登录账号跨设备访问的问题

  • 登录行为和非登录行为无法串联分析的问题

  • 设备与登录账号多对多关联的问题

如何正确识别多个登录用户 ID 或访问用户 ID 的行为归属?如何将某个用户在多设备或多账号下的行为数据归一,是移动端统计的难题。

一般情况下都会建立两套 ID 系统来解决上述问题,将多个设备的登录用户 ID 或访问用户 ID 映射到一个统计 ID 上, 将每个用户 ID 下的用户行为统计数据都累计到统计 ID 上,这样一个用户跨账号或跨设备的行为可以被正确的统计。


常用解决方案


对于存在两套 id 系统时,通常的处理办法是维护一张 ID 关系表 (mapping_table)。



如上表,访问数据 (例如 访问,点击,页面浏览)中的 ID 是访问用户 ID , 先基于访问用户 ID 计算出每个访问用户 ID 的数据 (pv_table)。



然后和关系表通过访问用户 ID 做 join。


select statistics_id, sum(pv) pv from (  (select visit_id, pv from pv_table) A  join  (select visit_id, statistics_id from mapping_table) B  on A.visit_id = B.visit_id) Tgroup by statistics_id
复制代码


将访问用户 ID 转化为统计 ID , 在基于统计 ID 将数据归一,得出结果。



这种方案的优点在于方便计算,数据量小时可以快速统计,但是在数据量特别大时,或者 ID 关系表累计的关系数据过大后,例如超过几亿行数据时,在做 join 时速度会非常慢,这时候再使用这种方案就会让系统变得极为缓慢,那么,如何在大数据量的情况下做两套 ID 系统的数据转换,就是接下来需要解决的问题。


转置算法 - CBitmap 存储映射关系


转置算法是一种通过 CBitmap 来维护 ID 映射关系,并且通过 CBitmap 的交叉计算来完成 ID 的转换,得到最终的结果数据。


由于转置算法会涉及到部分 CBitmap 的逻辑,如果想快速理解接下来的内容,建议大家看一下 CBitmp 部分的原理,基于 BitMap 的海量数据分析


下面开始介绍一下:


CBitmap 的结构简化来看是一个 map[Int, Bitmap]  代码实际上是  Map[short, Bitmap], 为了理解上更直接,这里说的是逻辑上的结构, 业务上的含义是 key 为次数,value 为对应的用户 ID 的 bitmap 集合, GrowingIO 在 CBitmap 的使用上是用来做次数存储,每个数字对应的 bitmap 中存储了一组 ID,下图展示了一个 CBitmap 中存储的数据格式。



看到这里大家有没有觉得这个存储结构有些眼熟,下面将上表展开大家看一下:



是的,展开后的表结构和之前展示的 ID 关系表是一样的,CBitmap 是一个维护了 ID 和次数的关系表,那么将次数的概念换为统计 ID ,  CBitmap 就可以表示维护了用户 ID 和统计 ID 关系的表,了解了 CBitmap 如何存储 ID 关系,再看一下 ID 关系表的数据:



将这张表的数据改为 CBitmap 存储后,结构如下:



转置算法 - 统计数据用户 ID 转换


通过一个简单的 CBitmap, 就可以存储一张关系表的全部数据,节约了大量的存储成本, 在准备好映射关系数据后,接下来的难点在于如果将统计数据的用户 ID 转化为统计 ID,这里举计算基于统计 ID 的 PV 次数的场景帮助大家更好的理解何如进行转换。

GrowingIO 对于统计数据存储采用了 bitmap 的形式存储,存储数据如下图:



每天的离线任务都会统计每个项目的用户 ID 的来源归属,并提取出统计 ID, 存储成 CBitmap , 结构如下:



计算首先会拆开 PV 统计数据,将每条数据单独计算,先取出次数为 1 的 PV 数据:



用这条数据的 bitmap 和存储映射关系的 CBitmap 做下每个 bitmap 做交集预算:



通过上述计算可以得到 PV 次数为 1 的数据转为统计 ID 后的数据:



根据用户 ID 数计算每个统计 ID 下所对应的用户人数:



统计 ID 90001 有一个对应的用户 ID, 这个用户 ID 的 PV 次数是 1,那么 90001 的 PV 次数也就是 1 * 1 = 1,统计 ID 90002 有两个对应的用户 ID, 每个用户 ID 的 PV 次数是 1,那么 90002 的 PV 次数是 2 * 1 = 2,可以得到 PV 次数为 1 的数据转换 ID 后的 CBitmap 。



根据上述计算逻辑可以得出 PV 次数为 2 的数据转换 ID 后的 CBitmap :



统计 ID 90002 有一个对应的用户 ID, 每个用户 ID 对应的 PV 次数是 2 , 90002 的 PV 次数是 1 * 2 = 2 次。



将多个 PV 次数计算的 CBitmap 结果聚合可得 90001 的 PV 次数为 1, 90002 的 PV 次数为 4。



通过上述计算,可以通过 bitmap 交叉计算的方式将一套 ID 系统的统计转为另一套 ID 系统的统计,使用 bitmap 内部的位运算,避免了大数量下 join 的性能问题,提升了运算效率。


性能对比



上述测试均单核情况下运行。


映射关系表数据量在 500 万,PV 数据 500 万时,通过 join 方式需要 170 秒可以计算出结果,bitmap 方式需要 7 秒,在映射关系表数据量在 1500 万,PV 数据 1500 万时 通过 join 方式需要 420 秒可以计算出结果,bitmap 方式需要 19 秒,极大优化了计算性能。


总结


通过 Bitmap 的转置算法对映射数据和 CBitmap 统计数据做计算,很好地解决了 GrowingIO 在应对业务需求中遇到的多种难题,在存储,运算速度上都有较好的支持。



作者: 高向林 / 数据开发


招聘信息


GrowingIO 技术团队是一个活力四射、对技术充满激情的团队,多个岗位持续招聘中!诚招 大数据工程师 / ClickHouse 工程师 / Java 工程师
 等。欢迎有兴趣的同学投递简历至:jianli@growingio.com(邮件标题请注明具体岗位名称)。更多职位及信息可进入招聘官网查看
!


关于 GrowingIO


GrowingIO 是国内领先的一站式数据增长引擎整体方案服务商,创立于 2015 年,以数据智能分析能力为核心,通过构建客户数据平台,打造增长营销闭环,帮助企业提升数据驱动能力,赋能商业决策、实现业务增长。


发布于: 2021 年 05 月 19 日阅读数: 48
用户头像

GrowingIO 技术团队经验分享 2020.05.09 加入

GrowingIO(官网网站www.growingio.com)的官方技术专栏,内容涵盖微服务架构,前端技术,数据可视化,DevOps,大数据方面的经验分享。 公众号:GrowingIO技术团队

评论

发布
暂无评论
BitMap 转置算法:不一样的 Count 求解方式