作者：陈凯
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. 基于 BitMap 的存储模型 ????
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」满足才对。
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. 简略的性能比照
环境筹备：SparkSQL（local[16], 内存 4G）, BitMap 单线程计算（内存 4G）
场景：简略的 2 ~ 3 个维度组合求人数、次数，依照值的降序取 Top 1000
x 轴含意: 数据量 / 用户量。
y 轴含意: 计算工夫, 单位毫秒。
能够看到随着数据量的一直递增，SparkSQL 的计算工夫也在一直递增，然而 BitMap 的计算工夫却绝对比较稳定。
5. 总结
BitMap 是一个合并计算和存储劣势的数据结构，在存储上百万甚至上千万的 ID 时，也能失去很好的计算成果。
并且当你应用 BitMap 存储的时候，就曾经人造反对很多的业务场景，比方 分群计算、标签计算、漏斗剖析、留存剖析、用户触达 等，因为无需再从新计算人群。
本篇次要揭晓咱们是如何基于 BitMap 来作为底层的数据模型，当然在理论利用过程中还有很多的挑战，因为篇幅起因，这里就不开展讲述了。
以下列出一些咱们后续的工作内容和攻克方向：
bitmap 是以 int 值进行存储的，然而在理论生产中，你的 ID 数据可能是相似 UUID 的这种字符串，那么须要解决 string 转惟一 int 的问题。
- 如何使 bitmap 在分布式环境下达到更好的计算成果
- 如何解决高基维度所带来的挑战
- 如何在实时、图表剖析、分群画像以及更多的业务场景中进行应用
- 如何设计一个类 SQL 语言来兼容这种数据模型
……
对于 GrowingIO
GrowingIO 是基于用户行为数据的增长平台，国内当先的数据经营解决方案供应商。为产品、经营、市场、数据团队及管理者提供客户数据平台、获客剖析、产品剖析、智能经营等产品和咨询服务，帮忙企业在数据化降级的路上，晋升数据驱动能力，实现更好的增长。
如果对咱们的产品感兴趣，欢送点击此处支付 15 天收费试用！