如何在 1 秒内做到大数据精准去重?

史少锋
Apache Kylin committer & PMC
2019年 9月 27日

去重计数在企业日常分析中应用广泛,如用户留存、销售统计、广告营销等。海量数据下的去重计数十分消耗资源,动辄几分钟,甚至几小时,Apache Kylin 如何做到秒级的低延迟精确去重呢?


什么是去重计数

去重计数是数据分析中的常用分析函数,指查询某列中不同值的个数,在 SQL 中的函数是 count(distinct col)。它与 count(col) 函数的区别在于有一个 distinct 描述符,意思是去掉重复值,因此称为去重计数。

去重计数使用广泛,例如:在网站/app 使用统计中,PV/UV 是最常用的指标,其中 UV(unique visitor,独立访问用户)就是去重后的数字,即同一个用户的所有访问记录只计入一次。对于网站/app 所有者,PV (page view)代表的使用量的高低,UV 代表用户的多少,两个数字都很重要;只有结合两个数字一起,才能更加准确地了解网站/app的用户、用量增长情况。

图 1:PV/UV 统计


大数据上去重运算的难点与挑战

去重运算因为涉及到数值的比较,因此它的计算要比单纯的 PV 计数要略复杂。当数据量不大的时候,单机运行的性能或许还能忍受。但是当数据量渐长的时候,所花的时间越来越长,依靠单节点处理难以满足,此时就需要依靠分布式框架如 MapReduce 或 Spark 等并行处理,把大数据分而治之。

学习过 MapReduce 的朋友,一定对它的 WordCount  范例非常了解。下图解释了使用MapReduce 进行并行词语出现次数统计的过程:

图2:WordCount 过程示例

试想,如果你的网站/app,访问用户数较大,如一千万,访问记录一亿(假设一个人平均点击 10 次)。假如每个用户的 ID 已经用 int 表示了,那么一次简单的去重运算,需要 shuffle 的数据量就是:1亿*4字节 = 400 MB = 3200 Mb。以内网千兆网 1000 Mbps 来计算,至少也需要 3 秒的传输;再加上磁盘读写、排序、序列化、反序列化操作,这样的一个计数运算最终的时间基本在 10 秒以上。现实中情况可能更加复杂:

  • 用户标识符可能是 email、uuid、身份证、手机号等更长的字符,空间占用更大;
  • 去重之前需要某些条件过滤,占用更多计算资源,如查询过去 2 天在某几个地区的 UV;
  • 访问记录多(行为日志往往在数十亿以上);
  • 网络和磁盘 IO 忙,查询性能会出现抖动。

总之,大数据上的去重计数是一个耗资源的计算,做到秒级的低延迟响应十分困难;如果这方面查询较频繁,必定需要优化数据结构和算法。

大数据去重算法

事实上,研究人员早就意识到了这里存在优化空间,开发了多种算法和数据结构。最著名的当属 HyperLogLog 和 Bitmap 两种。前不久,Kyligence工程师在 2019 年 4 月的北京 Kylin Meetup 上做了分享,并撰写了技术文章,感兴趣的同学请参考文末的“参考阅读”【1】【2】

这两种算法结构的共同点是,以非常精凑的结构存储去重集合的特征(或完整集合),这样不但可以回答去重数,还可以用于后续合并运算(如昨天和今天的去重)。相比较于每次都从原始值上做去重,它的存储和计算效率可以大大提高。

但这两种算法也有明显的差异点:

1) HyperLogLog,以下简称 HLL,它的空间复杂度非常低(log(log(n)) ,故而得名 HLL),几乎不随存储集合的大小而变化;根据精度的不同,一个 HLL 占用的空间从 1KB 到 64KB 不等。而 Bitmap 因为需要为每一个不同的 id 用一个 bit 位表示,所以它存储的集合越大,所占用空间也越大;存储 1 亿内数字的原始 bitmap,空间占用约为 12MB。可以看到,Bitmap 的空间要比 HLL 大约一两个数量级。

2)HLL 支持各种数据类型作为输入,使用方便;Bitmap 只支持 int/long 类型的数字作为输入,因此如果原始值是 string 等类型的话,用户需要自己提前进行到 int/long 的映射。

3)HLL 之所以支持各种数据类型,是因为其采用了哈希函数,将输入值映射成一个二进制字节,然后对这个二进制字节进行分桶以及再判断其首个1出现的最后位置,来估计目前桶中有多少个不同的值。由于使用了哈希函数,以及使用概率估计的方式,因此 HLL 算法的结果注定是非精确的;尽管 HLL 采用了多种纠正方式来减小误差,但无法改变结果非精确的事实,即便最高精度,理论误差也超过了 1%。

4)Bitmap 忠实地为每个 id 使用一个 bit 位来代表其出现(1)或不出现(0);所以只要能保证不同的用户被映射成不同的 id 值,那么 Bitmap 的结果就是精确的。

综合看下来,这两个算法都有各自明显的优劣:HLL 各种好,但是不精确;Bitmap 虽然占用空间比 HLL多,但能保证精确。

为什么精确去重如此重要

其实,Kylin 在最开始的时候只支持 HLL 算法,因为 HLL 在大数据领域被普遍使用:无奈数据量大性能要求高呀,那就损失点精度吧。如果有人问起有误差的事情该怎么回答呢,当时我们的说法是:在几千万上亿的结果上,你还在意那 1% 的误差吗?

然而,用户不是这么想的,在一些场景下,有误差的结果是难以被接受的。

例如:在渠道导流或广告投放方面,费用的结算按导流或点击用户数来统计的。有误差的数字,对于业务双方来说都是难以接受的:购买方担心多付钱,服务方担心少收钱。更何况,HLL 的误差率也是有几率的,也就是说,可能 99% 的情况下它的错误范围在 1% 内,剩下 1% 的情况下误差有多大就不好说了,万一大不少,岂不要造成生产事故了?

此外,如果 UV 结果还要做乘除法,那么这个误差率会进一步放大。例如用户增长率=今天用户数/昨天用户数;如果分子的数字偏大,分母的数字偏小,那么最终的误差就更大了,并且你还不知道误差是多少。一亿用户基数下,1% 的误差就是一百万用户,对于流量比较平稳的网站/app,这点误差率足以将实际运营效果直接掩盖,从而失去指导业务的意义。所以,如果你不想某天半夜被老板或业务方叫起来查数据,那还是想想办法一次解决准确性这个难题吧,以确保日后睡个安稳觉。

所以,没过多久,我们便意识到,仅有近似算法是不够的,Kylin 需要支持精确的去重,否则在重要场景中将失去机会。

Kylin 精确去重是如何做到的

如果读者对 Kylin 有一定了解的话会知道,Kylin 会按照用户指定的维度、度量对数据进行预计算,将计算出来的度量值,以维度的值为索引存储在 Cube (默认 HBase 表)中,例如每天的销售记录数、销售额等。

图3:OLAP Cube

对于 count distinct 度量,只存储一个数字是不够的,因为用户的查询可能需要遍历许多单元格然后再做合并,单纯的 int 数字不能再做去重合并。因此,过去Kylin 会将 HLL 对象整个序列化后,存储在 Cube 中维度值所对应的 cell 中。查询时,将其反序列化,交给 SQL 执行器做合并运算(通过 Kylin 的聚合函数),最后返回结果时,再从 HLL 对象中获取去重数。同样的道理,只要把 HLL替换成 Bitmap,理论上就可以实现精确的去重计数的存储和查询。

思路清楚了,但这里依然面临两个挑战:

1)Bitmap 空间占用大

如前面提到的,Bitmap 的空间占用相比于 HLL 是比较大的,但是相比于存储原始值的集合来说,它又是最小的。一个存储最大基数是1亿的 Bitmap,大约需要(1亿/8) 个字节,也就是 12MB,当维度多、基数高的时候,可想而知,这个 Cube 构建出来会占用很大存储。

调研以后,Kylin 引入了带压缩的 Bitmap 实现:Roaring Bitmap。Roaring Bitmap 把一个 32 位的 Integer 划分为高 16 位和低 16 位,取高 16 位找到该条数据所对应的 key,每个 key 都有自己的一个 Container。把剩余的低 16 位放入该 Container 中。依据不同的场景,有 3 种不同的 Container,分别是 Array Container、Bitmap Container 和 Run Container,它们分别通过不同的压缩方法来压缩。实践证明,Roaring Bitmap 可以显著减小 Bitmap 的存储空间和内存占用。

2)Bitmap 只接受 int/long 类型作为输入

前面提到过,Bitmap 只接受int/long(或可以直接 cast 成这两种的类型)为输入值。因此当去重列的类型不是这两个的时候,用户需要做一个 1:1 的映射,方能利用 Bitmap 进行去重,这样使用的难度大大提高了。

比较巧的是,Kylin 默认会对维度构建数据字典(dictionary),然后通过字典将 string 等值 1:1 映射成 int 值,这样在后续 Cube 运算和存储时,使用 int 值代替 string 值,可以大大减少空间占用。让 Kylin 对去重列也用字典先进行编码,岂不就可以支持 Bitmap 了?

基本可行,但是 Kylin 维度字典不是完全适用去重。主要原因是:

a) 维度字典是保序的(order preserving),因此构建后不能再追加修改;

b) 维度字典是对应于每一个 segment 来创建的,当构建下一个 segment 的时候,会重新创建另一个字典。这样会导致同一个 string 值在两个 segment 中可能会被编码成不同的 int 值;或者不同的 string 值,在不同的 cube segment 中可能被编码成相同的 int 值,那么用在 bitmap 的话,会造成跨 segment 的去重合并后的数值错误,所以行不通。

因此,Kylin 需要引入一个可以被追加的、保证在所有segment 中做到唯一映射的字典;因为只是为了回答去重数,它不需要支持反向映射,为了跟普通字典相区分,我们称之为全局字典(Global Dictionary)(代码中称为 AppendTrieDictionary),意思是它服务于所有 segment 的(当然也可以服务多个 cube)。跟普通字典相比,全局字典放弃了保序性,也不再支持双向映射(从 int 再解码回原始 string 值),它是完全为非 int 数值的精确去重而准备的,在使用中请注意区分。更多关于全局字典的介绍,请参考文末的“参考阅读”文章【3】【4】。

在解决了上述挑战之后,Kylin 就可以对海量数据集,根据用户建立的模型进行 Cube 计算,各维度组合、各维度值组合下的去重集合以 Bitmap 形式存储下来:

图 4:含 Bitmap 的 Cube 构建示例

查询时基于 Bitmap 进行后续运算,如:

select count(distinct 用户ID) from access_log where 日期 = ‘2019/09/09’

图 5:含Bitmap 的查询示例

工作还不是到这里就结束了,在多年的实践中,Kylin 社区开发者们不断完善 Kylin 的精确去重能力,使得其越来越健壮和完善,其中的一些重要改进包括:

1. 使用Segment Global Dictionary

前面提到,为了确保跨 segment 的合并时,同一值可以被始终映射成一个 int,所以开发了全局字典(Global dictionary),它是可以增长的。那么随着数据的增加,这个全局字典会逐渐变大,加载它会变得吃力;虽然全局字典内部做了分页处理,不用一次全部加载到内存,但是如果内存不足的话,依然会影响效率。而有些场景中,业务只看按天的去重结果,不做跨天的去重合并,这样一来,维护全局的映射也就没必要了,而只需要维护一个 segment 级别的字典映射(segment 往往按天构建),就能够满足需求。这样的局部全局字典相比于正常全局字典会更小,更易于加载到内存中处理;当构建完成后,它甚至可以被删除以节省空间;缺点是,这样的 cube 的 segment 将不支持合并,因此在使用的时候需要略加注意。

2. 切分小字典提速 Cube 构建

刚提到,全局字典变大以后,在构建的时候,会加载其中的某些页到内存,内存不够的时候再载出;如果输入数据比较乱序,分布在全局字典的很多页,那么这种载入载出会消耗大量时间。所以,Kylin 引入一种优化策略,在进行编码之前,先翻出每一个 Mapper 数据中的去重列的 distinct 值,然后用此值去全局字典中查找对应的 int 值,然后生成一个仅供当前 mapper 使用的小字典;在 Cube 构建的时候,使用此小字典而非大字典给当前 Mapper 来使用,从而减少字典页换入换出操作,提高构建性能。

3. 使用 Hive/Spark 分布式构建外部全局字典

使用全局字典也存在一些局限,例如:

1)字典的构建在任务节点单机上完成,存在性能瓶颈,当有多个去重任务并行执行时,造成任务等待;

2)全局字典不能用于解码,也不能被其它大数据应用直接使用,导致数据资产浪费。

因此,社区贡献者提出将全局字典外置成一张 Hive 表(两个列,一个是原始值,一个是编码的int值),利用 Hive/Spark 进行分布式的生成和追加,并在 Cube 构建的时候可以做分布式映射,使 Kylin 任务节点的负载得以减轻,同时外部全局字典可以很容易地被复用,成为企业的数据资产。目前这个功能已经开发完成,将在 Kylin 3.0 中正式发布,敬请期待。

4. Bitmap 数值直接返回

Kylin 保存 Bitmap 是为了 UV 值的二次计算;然而有的查询是比较简单的,Cube 预计算已经一步到位了,Bitmap 不会参与二次计算,这种情况下各个HBase 节点就不需要将 Bitmap 传输给Kylin,而只要把结果值返回就可以,从而大大减少各个 HBase 节点到Kylin查询节点的网络传输。Kylin 会自动判断查询是否精准匹配预计算结果,决定是否使用此优化。

为什么 Kylin 是唯一能做到秒级去重的引擎

我们知道,Apache Kylin 是为数不多的能够在超大数据集上做到亚秒级低延迟的 OLAP 分析引擎;Apache Kylin 基于独特的预计算思想,将整个过程分为离线的 Cube 构建过程和在线的 Cube 查询两个阶段,且这两步可以分在两个独立集群,互不影响。虽然 Cube 构建会花费一定的时间,但带来的是后续查询的大大提速,对于频繁需要进行检索/查询的场景来说,一次构建多次受益,是非常值得的。而没有预计算的引擎,每次都需要从原始数据开始计算,不但占用大量计算资源,而且在性能、并发和效率方面都难以满足业务用户的苛刻要求。

图 6:Apache Kylin 架构图

引入 Bitmap 和全局字典后,Kylin 实现了秒级的精确去重查询,在大数据领域可以说是唯一的通用型方案(这句话来自某大型互联网用户)。有读者可能会问,大数据分析引擎这么多,Spark SQL,Presto,ClickHouse,Phoenix,Redshift等等,难道它们做不到吗?其实没有什么是做不到,只是受架构的限制,没有预先的数据准备,要想做到快速的精确去重,需要投入大量的计算资源,例如数据都预热在内存中、节点之间使用万兆网连接等等,但这恰恰是多数用户无法承担的。此外,随着数据量和并发的增长,性能和稳定性往往会出现显著下降,造成用户体验急剧下降,也就失去了可行性。当然,如果用户对性能和并发的要求不高,使用频率也不高,那么这些技术都是可以满足的。

总结

Kylin 既支持非精确去重,也支持精确去重,用户可以根据自己的场景要求选择合适的去重算法。Kylin 精确去重相比于其它技术的优势在于:

  • 数据离线自动生成压缩 Bitmap,查询时没有数据 shuffle 和落盘,保证了低延迟的同时 100% 准确;
  • UV 值可二次合并,满足灵活查询的需要;
  • 查询使用标准 SQL 的标准函数,无缝兼容已有系统;
  • 既支持整数类型,也支持 string 等类型;
  • 使用简单,无需编程开发;
  • 基于 Kylin 的 UDAF,Bitmap 还可以做交集(intersect)运算,实现留存、漏斗等分析功能;
  • 已经在 eBay、美团点评、滴滴、丁香园、Vivo、华为、满帮集团等大型用户生产环境平稳使用数年。

Apache Kylin 精确去重功能,是 Kylin 社区开发者们在各种复杂情况下不断研究和努力的成果,凝结了许多人的汗水和智慧,在此向孙业锐、高大月、康凯森、钟阳红、靳国卫等同学表示感谢!引入 Bitmap 后,Kylin 的能力大大加强,使用场景得到丰富,这部分内容我们将在下次文章中为您分享。

Q:想体验 Kylin 秒级精确去重?

A:Kylin 官网文档中有操作指南哦:https://kylin.apache.org/docs/tutorial/create_cube.html

参考阅读

【1】陶加涛 《大数据分析常用去重算法分析『HyperLogLog 篇』》https://kyligence.io/zh/blog/count-distinct-hyperloglog/

【2】陶加涛 《大数据分析常用去重算法分析『Bitmap 篇』》https://kyligence.io/zh/blog/count-distinct-bitmap/

【3】康凯森,《Apache Kylin 精确去重和全局字典权威指南》, https://blog.bcmeng.com/post/kylin-distinct-count-global-dict.html

【4】孙业锐,贺小桥《Apache Kylin精确计数与全局字典揭秘》, https://hexiaoqiao.github.io/blog/2016/11/27/exact-count-and-global-dictionary-of-apache-kylin/