共计 2685 个字符，预计需要花费 7 分钟才能阅读完成。
背景
通常在挪动端 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
) T
group by statistics_id将拜访用户 ID 转化为统计 ID , 在基于统计 ID 将数据归一，得出后果。
这种计划的长处在于不便计算，数据量小时能够疾速统计，然而在数据量特地大时，或者 ID 关系表累计的关系数据过大后，例如超过几亿行数据时，在做 join 时速度会十分慢，这时候再应用这种计划就会让零碎变得极为迟缓，那么，如何在大数据量的状况下做两套 ID 零碎的数据转换，就是接下来须要解决的问题。
转置算法 – CBitmap 存储映射关系
转置算法是一种通过 CBitmap 来保护 ID 映射关系，并且通过 CBitmap 的穿插计算来实现 ID 的转换，失去最终的后果数据。
因为转置算法会波及到局部 CBitmap 的逻辑，如果想疾速了解接下来的内容，倡议大家看一下 CBitmp 局部的原理，基于 BitMap 的海量数据分析基于 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 年，以数据智能剖析能力为外围，通过构建客户数据平台，打造增长营销闭环，帮忙企业晋升数据驱动能力，赋能商业决策、实现业务增长。