大数据分析常用去重算法分析『HyperLogLog 篇』

电玩女神 2022-02-03 10:45 287阅读 0赞

在[上篇推送][Link 1]中，Kyligence 大数据工程师陶加涛为大家介绍了利用 Roaring Bitmap 来进行精确去重。虽然这种算法能大大地减少存储开销，但是随着数据量的增大，它依然面临着存储上的压力。在本篇推送中将要介绍的 HyperLogLog（下称 HLL）是一种非精确的去重算法，它的特点是具有非常优异的空间复杂度（几乎可以达到常数级别）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saWRvbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70]  
HLL 算法需要完整遍历所有元素一次，而非多次或采样；该算法只能计算集合中有多少个不重复的元素，不能给出每个元素的出现次数或是判断一个元素是否之前出现过；多个使用 HLL 统计出的基数值可以融合。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saWRvbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saWRvbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 2]  
HLL 算法有着非常优异的空间复杂度，可以看到它的空间占用随着基数值的增长并没有变化。HLL 后面不同的数字代表着不同的精度，数字越大，精度越高，占用的空间也越大，可以认为 HLL 的空间占用只和精度成正相关。

#### HLL算法原理感性认知 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saWRvbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 3]  
HLL 算法的原理会涉及到比较多的数学知识，这边对这些数学原理和证明不会展开。举一个生活中的例子来帮助大家理解HLL算法的原理：比如你在进行一个实验，内容是不停地抛硬币，记录你连续抛到正面的次数（这是数学中的伯努利过程，感兴趣同学可以自行研究下）；如果你最多的连抛正面记录是3次，那可以想象你并没有做这个实验太多次，如果你最长的连抛正面记录是 20 次，那你可能进行了这个实验上千次。

一种理论上存在的情况是，你非常幸运，第一次进行这个实验就连抛了 20 次正面，我们也会认为你进行了很多次这个实验才得到了这个记录，这就会导致错误的预估；改进的方式是请 10 位同学进行这项实验，这样就可以观察到更多的样本数据，降低出现上述情况的概率。这就是 HLL 算法的核心思想。

#### HLL算法具体实现 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saWRvbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 4]  
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) 个桶。同样的，桶的个数越多，所占用的空间也会越大。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saWRvbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 5]  
刚才的例子我们省略了一些细节，为了让大家不至于迷失在细节中而忽视了重点，真实的 HLL 算法的完整描述见上图，这边的重点是计算桶中平均数时使用调和平均数。调和平均数的优点是可以过滤掉不健康的统计值，使用算术平均值容易受到极值的影响（想想你和马云的平均工资），而调和平均数的结果会倾向于集合中比较小的元素。HLL 论文中还有更多的细节和参数，这边就不一一细举，感兴趣的同学可以自己阅读下论文。

#### HLL评估 ####

HLL 的误差分布服从正态分布，它的空间复杂度: O(m log2log2N), Ｎ 为基数, m 为桶个数。这边给大家推导一下它的空间复杂度，我有 264 个的不重复元素(Long. MAX\_VALUE)，表达为二进制一个数是 64 位，这是第一重 log2, 那么第一个1最晚可能出现在第 64 位。64 需要 6 个 bit (26=64) 就可以存储，这是第二重 log2。如果精度为 10，则会有 1024 个桶，所以最外面还要乘以桶的个数。由于需要完整的遍历元素一遍，所以它的时间复杂度是一个线性的时间复杂度。

在Kylin中的应用  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saWRvbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 6]  
在 Kylin 中使用 HLL 非常简单，在编辑度量的页面选择 COUNT DISTINCT，Return Type 选为非 Precisely 的其他选项，大家根据自己的需求选择不同的精度就可以愉快地使用了。

#### 总结 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saWRvbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 7]

我们回到最开始的去重场景，看看使用了 Bitmap 和 HLL 会给我们带来什么增益：无优化 case 下，每个 item 对应的 user\_id 就可以看成存储原始值的一个集合；在使用 Bitmap 优化的case 下，每个 item 对应的 user\_id 就可以看成一个 Bitmap 实例，同理 HLL就是一个 HLL 的实例，Bitmap/HLL 实例占用的空间都会比直接存储原始值的集合要小，这就达到了我们开始提的减少 shuffle 数据量的需求。

#### Q&A ####

Q：您好，问一下关于精确去重的问题， 我选择了非精确去重，最后的误差率有时候会比界面上提示的值要高一些，这是为什么？

A：首先 HLL 的误差分布服从正态分布，也就是说是在99%的情况下是这个误差，同时 HLL 对于基数比较低的情况，误差会偏高。如果你的基数比较低的话，我推荐使用精确去重。

Q：我想要了解一下 Bitmap 在 Kylin 中，它最终落盘在 HBase 里面是什么样子的？

A：在 HBase 中存储的当然都是 Bytes。这个问题其实就是 Bitmap 的序列化的形式，Roaring Bitmap提供了序列化和反序列化的实现，你也可以写自己的序列化/反序列化的实现。

Q：Roaring Bitmap 里这些 container 要我们自己手动的指定吗。

A：不需要，Roaring Bitmap 会自动选择使用哪个 Container。

转自微信公众号 - apache kylin

[Link 1]: https://mp.weixin.qq.com/s?__biz=MzAwODE3ODU5MA==&mid=2653079161&idx=1&sn=ccee7eb24dec7a2dbcd4e6431dbcec3b&scene=21#wechat_redirect
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saWRvbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70]: /images/20220203/7c341364e70e495fa93626d8e93575a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saWRvbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 1]: /images/20220203/82bf9dff6d584136aa0fa8f07309ccad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saWRvbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 2]: /images/20220203/1e6f800f1a784301b72f5e4abfbd0639.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saWRvbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 3]: /images/20220203/36914c66ddd741748bb2b04fb9685c2d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saWRvbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 4]: /images/20220203/743ede89aa074f5285d118bcead5e163.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saWRvbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 5]: /images/20220203/8a6eaf5c028641d68489c8ad3a4624f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saWRvbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 6]: /images/20220203/d5791b025573443cadc259434d8cf30f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saWRvbmcuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 7]: /images/20220203/4bc0582e384f4d58a074d4e1c2568242.png