Kyligence Copilot - AI 数智助理,以 AI 变革企业经营与管理! 立即了解更多
AI 数智助理
Kyligence Zen Kyligence Zen
Kyligence Enterprise Kyligence Enterprise
Kyligence Turbo Kyligence Turbo
指标平台解决方案
OLAP 解决方案
行业解决方案
客户总览
金融
零售
制造
医药
其他
云平台
BI
寻求合作
资源
Kyligence Enterprise
Kyligence Zen
培训
Apache Kylin
Byzer
Gluten
博客
关于
市场活动
在上篇文章中,Kyligence 大数据工程师陶加涛为大家介绍了利用 Roaring Bitmap 来进行精确去重。虽然这种算法能大大地减少存储开销,但是随着数据量的增大,它依然面临着存储上的压力。在本篇文章中将要介绍的 HyperLogLog(下称 HLL)是一种非精确的去重算法,它的特点是具有非常优异的空间复杂度(几乎可以达到常数级别)。
HLL 算法需要完整遍历所有元素一次,而非多次或采样;该算法只能计算集合中有多少个不重复的元素,不能给出每个元素的出现次数或是判断一个元素是否之前出现过;多个使用 HLL 统计出的基数值可以融合。
HLL 算法有着非常优异的空间复杂度,可以看到它的空间占用随着基数值的增长并没有变化。HLL 后面不同的数字代表着不同的精度,数字越大,精度越高,占用的空间也越大,可以认为 HLL 的空间占用只和精度成正相关。
HLL 算法的原理会涉及到比较多的数学知识,这边对这些数学原理和证明不会展开。举一个生活中的例子来帮助大家理解HLL算法的原理:比如你在进行一个实验,内容是不停地抛硬币,记录你连续抛到正面的次数(这是数学中的伯努利过程,感兴趣同学可以自行研究下);如果你最多的连抛正面记录是3次,那可以想象你并没有做这个实验太多次,如果你最长的连抛正面记录是 20 次,那你可能进行了这个实验上千次。
一种理论上存在的情况是,你非常幸运,第一次进行这个实验就连抛了 20 次正面,我们也会认为你进行了很多次这个实验才得到了这个记录,这就会导致错误的预估;改进的方式是请 10 位同学进行这项实验,这样就可以观察到更多的样本数据,降低出现上述情况的概率。这就是 HLL 算法的核心思想。
HLL 会通过一个 hash 函数来求出集合中所有元素的 hash 值(二进制表示的 hash 值,就可以理解为一串抛硬币正反面结果的序列),得到一个 hash 值的集合,然后找出该 hash 值集合中,第一个 1 出现的最晚的位置。例如有集合为 [010, 100, 001], 集合中元素的第一个 1 出现的位置分别为 2, 1, 3,可以得到里面最大的值为 3,故该集合中第一个1出现的最晚的位置为 3。因为每个位置上出现1的概率都是 1/2,所以我们可以做一个简单的推断,该集合中有 8 个不重复的元素。
可以看到这种简单的推断计算出来集合的基数值是有较大的偏差的,那如何来减少偏差呢?正如我上面的例子里说的一样,HLL 通过多次的进行试验来减少误差。那它是如何进行多次的实验的呢?这里 HLL 使用了分桶的思想,上文中我们一直有提到一个精度的概念,比如说 HLL(10),这个 10 代表的就是取该元素对应 Hash 值二进制的后 10 位,计算出记录对应的桶,桶中会记录一个数字,代表对应到该桶的 hash 值的第一个 1 出现的最晚的位置。如上图,该 hash 值的后 10 位的 hash 值是 0000001001,转成 10 进制是 9,对应第 9 号桶,而该 hash 值第一个 1 出现的位置是第 6 位,比原先 9 号桶中的数字大,故把 9 号桶中的数字更新为 6。可以看到桶的个数越多,HLL 算法的精度就越高,HLL(10) 有 1024(210) 个桶,HLL(16)有 65536(216) 个桶。同样的,桶的个数越多,所占用的空间也会越大。
刚才的例子我们省略了一些细节,为了让大家不至于迷失在细节中而忽视了重点,真实的 HLL 算法的完整描述见上图,这边的重点是计算桶中平均数时使用调和平均数。调和平均数的优点是可以过滤掉不健康的统计值,使用算术平均值容易受到极值的影响(想想你和马云的平均工资),而调和平均数的结果会倾向于集合中比较小的元素。HLL 论文中还有更多的细节和参数,这边就不一一细举,感兴趣的同学可以自己阅读下论文。
HLL 的误差分布服从正态分布,它的空间复杂度: O(m log2log2N), N 为基数, m 为桶个数。这边给大家推导一下它的空间复杂度,我有 264 个的不重复元素(Long. MAX_VALUE),表达为二进制一个数是 64 位,这是第一重 log2, 那么第一个1最晚可能出现在第 64 位。64 需要 6 个 bit (26=64) 就可以存储,这是第二重 log2。如果精度为 10,则会有 1024 个桶,所以最外面还要乘以桶的个数。由于需要完整的遍历元素一遍,所以它的时间复杂度是一个线性的时间复杂度。
在 Kylin 中使用 HLL 非常简单,在编辑度量的页面选择 COUNT DISTINCT,Return Type 选为非 Precisely 的其他选项,大家根据自己的需求选择不同的精度就可以愉快地使用了。
我们回到最开始的去重场景,看看使用了 Bitmap 和 HLL 会给我们带来什么增益:无优化 case 下,每个 item 对应的 user_id 就可以看成存储原始值的一个集合;在使用 Bitmap 优化的case 下,每个 item 对应的 user_id 就可以看成一个 Bitmap 实例,同理 HLL就是一个 HLL 的实例,Bitmap/HLL 实例占用的空间都会比直接存储原始值的集合要小,这就达到了我们开始提的减少 shuffle 数据量的需求。
Q:您好,问一下关于精确去重的问题, 我选择了非精确去重,最后的误差率有时候会比界面上提示的值要高一些,这是为什么?
A:首先 HLL 的误差分布服从正态分布,也就是说是在99%的情况下是这个误差,同时 HLL 对于基数比较低的情况,误差会偏高。如果你的基数比较低的话,我推荐使用精确去重。
Q:我想要了解一下 Bitmap 在 Kylin 中,它最终落盘在 HBase 里面是什么样子的?
A:在 HBase 中存储的当然都是 Bytes。这个问题其实就是 Bitmap 的序列化的形式,Roaring Bitmap提供了序列化和反序列化的实现,你也可以写自己的序列化/反序列化的实现。
Q:Roaring Bitmap 里这些 container 要我们自己手动的指定吗。
A:不需要,Roaring Bitmap 会自动选择使用哪个 Container。
近年来,随着商业环境的竞争日益激烈,企业对于实时数据服务的需求急剧增加。Kyligence 在服务众多客户的过
数据要素在银行各业务领域和流程中发挥着至关重要的作用,面对激烈的市场竞争和客户需求,银行越来越注重从数据管理中
作为一名消费者,炎热的夏天我们会走进一家便利店,从冰柜中选出一瓶汽水;下午工作有点累了,我们会在公司的自动贩卖
2024 年伊始,Kyligence 联合创始人兼 CEO 韩卿(Luke)分享了对 AI 与数据行业的一些战
房地产行业是我国国民经济中的重要支柱产业之一,在房地产市场供求关系发生重大变化的当下,房企面临多重挑战。Kyl
今年年初,Kyligence 高级副总裁兼合伙人葛双寅(Silas Ge)受邀在阿斯利康“跃行致远三十周年年会
2024 年伊始,Kyligence 联合创始人兼 CEO 韩卿在公司内部的飞书订阅号发表了多篇 Rethin
400 8658 757
工作日:10:00 - 18:00
已有账号? 点此登陆
预约演示,您将获得
完整的产品体验
从数据导入、建模到分析的全流程操作演示。
行业专家解惑
与资深行业专家的交流机会,解答您的个性化问题。
请填写真实信息,我们会在 1-2 个工作日内电话与您联系。
全行业落地场景演示
涵盖金融、零售、餐饮、医药、制造等多个行业,最贴合您的业务需求与场景。
Data + AI 应用落地咨询
与资深技术专家深入交流,助您的企业快速落地 AI 场景应用。
申请体验,您将获得
体验数据处理性能 2x 加速
同等规模资源、同等量级数据、同一套数据处理逻辑,处理耗时下降一半
专家支持
试用部署、生成数据、性能对比各操作环节在线支持