如何基于 BitMap 进行海量数据分析

发布于: 2020 年 07 月 11 日
如何基于 BitMap 进行海量数据分析

作者:陈凯

GrowingIO 数据开发工程师,主要负责 SaaS 和 OP 产品数据平台的开发和设计,目前专攻于微服务、数仓建设方向。



GrowingIO 每天需要处理近千亿的用户行为数据,平台的「事件分析」模块是使用比较频繁的功能,简单且强大。在事件分析中,客户可以很灵活地使用多种维度组合去查看某个指标,并且查询的速度也十分可观。



本文抽取 GrowingIO 在事件分析中的通用数据模型,揭晓该功能背后的存储模型和实现原理。



在用户行为的数据分析中,无论是无埋点,还是埋点,对于某一条行为数据的表达形式往往是:「某人」于「某个时间」在「某个维度」下做了「某个动作」「多少次」。



所以在数据统计中,这种表达形式可以拆解成「指标量」和「维度」,指标量可以是用户量、页面浏览量、某个埋点的次数等,维度可以是时间、城市、浏览器、用户属性等。



在海量数据的背景下,如何比较高效地完成指标+维度的计算,一直是大数据分析领域比较热门的话题,下面将讲述在 GrowingIO ,我们是如何高效解决的。



1.从一个数据需求说起📈



假设给定如下一组用户行为的原始数据:

数据含义: 表示某个用户的某次访问记录。(这里仅列举了地区和设备维度,当然还会存在浏览器、平台、版本等维度,这里不一一列举了。)



1.1 使用 SQL 分析统计



🤔 现在业务想计算「过去7天」在「地区」维度下,「设备: Mac」的人数是多少?So Easy,一个 SQL 搞定



使用 GrowingIO 平台的分析工具可以表示如下:



但是通过 SQL 这种现查的方式,随着数据量的越来越大,几十亿或上百亿的时候,对计算所需要的资源和响应时间也会线性地增长,此时客户在使用平台工具最直观的感受就是“菊花”转转转,图表一直加载不出来。



1.2 如何使查询更加高效



1.2.1 堆机器,加资源



最直接粗暴的方式,就是增加更多的计算资源,或者对查询的结果进行缓存、预热。但是对于 SaaS 产品来讲,在查询并发比较高的时候,再多的计算资源也会因为查询排队而遇到性能瓶颈。



1.2.2 数据分层



😼 在数仓的分层架构中,对于经常使用的查询结果,我们可以通过离线计算的方式生成了一个结果表「过去7天-地区-设备-指标表」,示例如下:





这样在特性的查询场景中,只需要查询结果表就行,很大的减少了计算量,响应时间也短了不少。



😱 但是业务那边的需求往往是千变万化的,然后一堆统计的需求砸到了你的脑袋上



  • 「过去 30 天」的「总用户的量」和「总访问量」是多少?

  • 「昨天」「设备: Windows」的「用户量」是多少?

  • 「获取 30 天」按「平台」拆分的「用户量」是多少?

  • 「11 月- 11 日」来了哪些用户?请导出这个用户列表

  • 其他更多漏斗、留存、画像等数不尽的需求让人头晕目眩。

         ......



😫 你看了看生成结果表,发现并不能完全解决这些问题,你觉得需要生成更多的结果表来满足更多的需求。然而到最后你发现有些表居然仅仅只使用了一次,数仓里面堆了一堆垃圾。



1.2.3 数据预聚合



和数仓分层的理念类似,对数据进行预计算、预聚合,使用空间换时间的思想加快计算。这也是目前一些主流开源框架的解决思路,比如 SparkSQL 的物化视图、Kylin的 Cube、Druid 的 Segment 、Carbondata 的 MV 等。



下面使用一张图展示主要区别:



基于我们所追求的方式,我们首先需要寻找一种高效并且灵活的存储模型。



1.3 优化存储模型



基于上节中数据预聚合的思路,从预聚合的结果中,我们不难发现,其中有几个没有摆脱的点:

  • 多个维度依然是横向存储在一起

  • 维度和指标绑定在一条记录中

  • 因为存在这种局限性,刚好限制了我们灵活进行「维度+指标」的任意组装和扩展



🤔 如何才能更好的让维度和指标随心所欲地组合呢?我们在预聚合结果的基础之上做了一些改进:

  • 将每个维度纵向存储

  • 将维度和指标分开存储



2.1 纵向存储维度(人数)



依然以开篇的那组数据为例,此时将维度进行纵向存储:



此时想取「地区: 北京」和「设备: Mac」的「用户量」



OK!这样可以很灵活的解决各种维度组合起来的问题了,而且连用户的群体也能直接获取。



😇 但是从表格中发现,用户存储「用户集合」的数据结构还没有解决。那么既能以类似数组的方式存储整数值,还能使用交集(and)操作,还需要达到更好的数据压缩和计算。



此时你应该想到了 BitMap 这种数据结构



至于为何选用 BitMap 的数据结构,以及 BitMap 的功能和基本使用,这里不再探讨。可以参考 java 的实现 BitSet 以及优化的库 RoaringBitmap。



2.2 存储指标量(次数)



为了解决存储指标次数的存储问题,你需要用一个Map 的结构来存储「总的次数」: Map<Int, BitMap> (其中key为次数,value为符合访问次数的人)



访问量表示: 总共访问「1次」有哪些人,访问「2次」的有哪些人等等。



此时计算「地区: 北京」和「设备: Mac」的「访问量」



2.3 使用更优雅的方式存储次数



在 Map<Int, BitMap> 这个结构中,key 存储的是 10 进制的数字。这就会导致 Map 的 key 变得特别特别多,所以需要有一种方式来优化一下结构。



方式就是用将 10 进制转化为 2 进制的方式去存储次数,此时 Map 的 key 存储是 二进制为 1 的位置:



比如 2 的二进制是: 「10」,从右向左分别表示(下标i从0开始)「第0位是0」,「第1位是1」。所以将key为1的 bitmap 中存储这个人。



比如5的二进制是: 「101」,从右向左分别表示「第0位是1」,「第1位是0」,「第2位是1」。所以将 key 为 0 和 2 的 bitmap 中存储这个人。



然后将上节 2.2 中结果表示如下:



此时计算「地区: 北京」和「设备: Mac」的「访问量」



3. 多维度交叉的问题 ⚔️



理想是美好的,但是现实很残酷。在 2.1 小节的例子中,每个用户的维度组合只有一种,但是现实中往往一个用户行为可能会存在多种维度组合的情况。



那么什么是维度组合: 一条数据中唯一的所有维度值,称为一个组合。



PS: 如果你的系统中某个 ID 的维度组合只有一种。比如某个订单,一旦生成了,他的价格,商品,物流等信息基本都是固定的。那么之前的模型基本都能满足大多场景了。



3.1 面临的问题



🤔 那么会导致什么问题呢?此时回到起点,又来了一批用户行为的数据如下:



此时多了一个「用户1」在「杭州」使用了「Windows」。如果按照之前的模型存储如下:

此时计算「地区: 北京」的用户:直接返回 [ 1 , 2 , 3 ],问题不大



此时计算「地区: 北京」和「设备: Windows」的用户



3.2 使用维度组合编号的方式解决



其实问题出在将维度分开进行存储的时候,丢失了「维度组合关系」这个重要的衡量条件。「用户 1 」虽然在「北京」待过,也使用过「Windows」,但是他却没有同时满足这个条件,这就是问题所在。



所以需要一种方式来存储「维度组合关系」这一重要信息。



将每个人维度组合进行顺序编号,得到如下结果:

注意:编号是对应到每个人的,相同的维度组合,编号是一样的。



此时对应的存储结构也发生了变化:Map<Short, BitMap>( key 代表编号,value 代表人的集合



此时我们再来计算「地区: 北京」和 「设备: Windows」维度的用户



最后得到的结果就是「用户3」,算出来的数据就变准确了。



3.3 多维度情况下计算次数



其实稍微想一下就是两层的 Map 结构:Map<Int, Map<Short, BitMap>>,比如刚刚的那组数据表示如下:



比如「用户1」这个用户,在「编号0」发生的 2 次,在「编号1」发生了 1 次





此时我们来计算「地区: 北京」和 「设备: Mac」维度的访问量



4. 简单的性能对比



场景:简单的 2 ~ 3 个维度组合求人数、次数,按照值的降序取 Top 1000



x轴含义: 数据量/用户量。

y轴含义: 计算时间, 单位毫秒。



可以看到随着数据量的不断递增,SparkSQL 的计算时间也在不断递增,但是 BitMap 的计算时间却相对比较稳定。



5. 总结



BitMap 是一个兼并计算和存储优势的数据结构,在存储上百万甚至上千万的 ID 时,也能得到很好的计算效果。



并且当你使用 BitMap 存储的时候,就已经天然支持很多的业务场景,比如分群计算、标签计算、漏斗分析、留存分析、用户触达等,因为无需再重新计算人群。



本篇主要揭晓我们是如何基于 BitMap 来作为底层的数据模型,当然在实际应用过程中还有很多的挑战,由于篇幅原因,这里就不展开讲述了。



以下列出一些我们后续的工作内容和攻克方向:

bitmap 是以 int 值进行存储的,但是在实际生产中,你的 ID 数据可能是类似 UUID 的这种字符串,那么需要解决 string 转唯一 int 的问题。

  • 如何使 bitmap 在分布式环境下达到更好的计算效果

  • 如何解决高基维度所带来的挑战

  • 如何在实时、图表分析、分群画像以及更多的业务场景中进行使用

  • 如何设计一个类 SQL 语言来兼容这种数据模型



关于 GrowingIO



GrowingIO 是基于用户行为数据的增长平台,国内领先的数据运营解决方案供应商。为产品、运营、市场、数据团队及管理者提供客户数据平台、获客分析、产品分析、智能运营等产品和咨询服务,帮助企业在数据化升级的路上,提升数据驱动能力,实现更好的增长。

jin

发布于: 2020 年 07 月 11 日 阅读数: 28
用户头像

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

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

评论

发布
暂无评论
如何基于 BitMap 进行海量数据分析