Redis源码中hyperloglog结构的实现原理是什么?

  • 时间:
  • 浏览:0
  • 来源:跟我学网络

大数据领域的近似分析方法(一)

基数估算问题

基数估算(Cardinality Estimation),也称为 count-distinct problem,一直是大数据领域的重要问题之一。顾名思义,基数估算就是为了估算在一批数据中,它的不重复元素有多少个。

这个问题的应用场景十分广泛。例如:对于 Google 主页面而言,同一个账户可能会访问 Google 主页面多次。于是,在诸多的访问流水中,如何计算出 Google 主页面每天被多少个不同的账户访问过就是一个重要的问题。那么对于 Google 这种访问量巨大的网页而言,其实统计出有十亿 的访问量或者十亿零十万的访问量其实是没有太多的区别的,因此,在这种业务场景下,为了节省成本,其实可以只计算出一个大概的值,而没有必要计算出精准的值。

从数学上来说,基数估计这个问题的详细描述是:对于一个数据流 而言,它可能存在重复的元素,用 来表示这个数据流的不同元素的个数,i.e. 并且这个集合可以表示为 目标是:使用 这个量级的存储单位,可以得到 的估计值 其中 并且估计值 和实际值 的误差是可以控制的。

如果是想得到精确的基数,可以使用字典(dictionary)这一个数据结构。对于新来的元素,可以查看它是否属于这个字典;如果属于这个字典,则整体计数保持不变;如果不属于这个字典,则先把这个元素添加进字典,然后把整体计数增加一。当遍历了这个数据流之后,得到的整体计数就是这个数据流的基数了。

</svg>" width="1267">
Naive Solution

这种算法虽然精准度很高,但是使用的空间复杂度却很高。那么是否存在一些近似的方法,可以估算出数据流的基数呢?其实,在近几十年,不少的学者都提出了很多基数估算的方法,包括 LogLog,HyperLogLog,MinCount 等等。下面将会简要的介绍一下这些方法。

</svg>" width="2326">
基数估计的部分算法

HyperLogLog 的理论介绍

HyperLogLog 是大数据基数统计中的常见方法,无论是 Redis,Spark 还是 Flink 都提供了这个功能,其目的就是在一定的误差范围内,用最小的空间复杂度来估算一个数据流的基数。

</svg>" width="1076">
Spark 的 Logo

HyperLogLog 算法简要思路是通过一个 hash 函数把数据流 映射到 也就是说用二进制来表示数据流中的元素。每一个数据流中的元素 都对应着一个 序列。

在介绍 HyperLogLog 之前,我们可以考虑这个实际的场景。在一个抛硬币的场景下,假设硬币的正面对应着 硬币的反面对应着 依次扔出 的概率是多少?通过概率计算可以得到是这个概率是 那么相当于平均需要扔 次,才会获得 这个序列。反之,如果出现了 这个序列,说明起码抛了 次硬币。

考虑这样一个 序列, 令 表示第一个 出现的位置。也就是说 那么在扔硬币的场景下,出现这样的序列平均至少需要扔 次。对于一批大量的随机的 序列, 可以根据第一个 出现的位置来估算这批 序列的个数。也就是说:

  • 出现序列 意味着不重复的元素估计有 个;
  • 出现序列 意味着不重复的元素估计有 个;
  • 出现序列 意味着不重复的元素估计有 个;
  • 出现序列 意味着不重复的元素估计有 个。

于是,对于随机的 序列,可以定义函数 来表示 出现的第一个位置。i.e.

简单来看,其实 HyperLogLog 的基数统计就使用了这样的思想,通过二进制中 出现的第一个位置来估算整体的数量。首先把这批元素通过 hash 函数处理成 序列,然后把这批 序列都放入 个桶,然后通过计算这个桶里面所有 序列的 的最大值,就可以预估出整体的数量。i.e. 整体的数量预估是

  • 个桶:计算出 预估不重复的元素个数是

那么如果只有 个桶,其实是会存在一定的偏差的。为了解决这个问题,一种想法就是重复以上操作,从 hash 函数开始处理成 序列,每次都把这批 序列放入 个桶,每次获得一个 值。总共操作 次,第 次操作得到的值记为 于是就可以对 进行均值处理,可以使用以下方法:

  • 算术平均数:
  • 几何平均数:
  • 调和平均数:
  • 中位数:

从而可以预估整体的数量为

如果按照以上的步骤进行操作,就是需要重复进行多次操作,在足够多的情况下,其实是没有必要那么操作的。HyperLogLog 也是用了多个桶,但是用了一个截断的技巧。对于一个 序列 HyperLogLog 从某个位置 开始,低位 用于决定桶的序号,也就是第几个桶。桶的个数就是 高位 用于估算放在桶里面的元素个数。

每次都可以获得一个值,也就是桶里面第一次出现

  • 第 1 个桶:计算出 预估元素个数
  • 第 2 个桶:计算出 预估元素个数
  • ....
  • 第 个桶:计算出 预估元素个数

均值的计算,HyperLogLog 使用了调和平均数 来估算桶里面的元素个数,那么在有 个桶的情况下,整体的元素个数就可以估算为

</svg>" width="1296">
原始的 HyperLogLog 算法

其中的 当 的时候, 是发散的;当 的时候, 是收敛的。因此,在使用这个算法的时候最好放入 个桶。

HyperLogLog 分成两块,第一块就是 add 模块,用于分桶和统计;

for v in M:
    set x := h(v);
    set j = 1 + <x(b),...,x(2),x(1)>;
    set w := x(b+1)x(b+2)...; 
    set M[j] := max(M[j], \rho(w));

在 HyperLogLog 算法中,对于集合 中的每一个元素 可以通过 hash 函数转换成一个 序列 h(v)=x=<\cdots x_{b+2}x_{b+1}x_{b}\cdots x_{1}>, 其中 表示二进制中的最低位, 表示次低位。

然后可以通过 <x_{b}\cdots x_{1}>_{2} 来计算放在第 个桶,这里  j=1+<x_{b}\cdots x_{1}>_{2}. 同时将 的高位拿出来,也就是 计算这批序列的 函数的最大值,然后记为 这一步也可以称为 merge 模块,也就是进行更新合并。

compute Z := (\sum_{j=1}^{m}2^{-M[j]})^{-1};

上一步就是 HyperLogLog 的另外一步,count 模块,于是,进一步估算出

HyperLogLog 的空间复杂度特别低,大约是 这个量级的,其中 是桶的个数, 是基数。HyperLogLog 的时间复杂度则是 只需要遍历一遍所有元素即可得到最终结果。

  • 假设基数为 二进制就是 位, 最晚就会出现在第 个位置上;而 只需要 个 bit 就能够存储;
  • 假设基数为 二进制就是 位, 最晚会出现在第 个位置上;而 需要 个 bit 就可以存储。
</svg>" width="2076">
算法对比

在论文中,论文 "Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm" 的作者们针对各种算法进行了对比,其实 HyperLogLog 的空间复杂度是非常小的,并且误差也在可控的范围内。

</svg>" width="1868">
HyperLogLog 的定理证明

在论文 "Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm" 作者们得到上述定理,精准的给出了 HyperLogLog 算法的误差估计。因此,HyperLogLog 算法其实是有数学定理证明的。

以上只是获得了理论上的 HyperLogLog 算法,但是在实战中,其实是需要进行微调的。主要的微调部分是根据理论中的 值来进行调整。将 值进行调整的话,情况可以分成三种:

  • 小范围;
  • 中等范围;
  • 大范围;
</svg>" width="1698">
实战中的 HyperLogLog

Case(1):小范围

在小范围的情况下, 此时的基数相对于桶的数量而言不算太多,因此可能存在多个空桶,需要进行调整。

可以思考这样一个问题:假设有 个桶,同时有 个球,把这 个球随机往这 个桶里面扔,每个球只能够进入一个桶,那么空桶个数的期望是多少个?

Answer:假设 是 个桶,

表示桶 空的概率;

表示桶 同时为空的概率( );

那么空桶个数的期望就是 当 充分大的时候,约为 个。

因此,在小范围的情况下,如果空桶的个数 那么可以更新为 事实上,可以通过 解出

Case(2):中等范围

值不作调整。

Case(3):大范围

E>2^{32}/30, 那么更新为 其中 E^{*}>E.

通过这样的方法, 的误差大约在 左右。

除此之外, 其实也可以用近似值来代替,毕竟如下公式的计算是有一定的成本的。

近似的值为 当

HyperLogLog 的案例分析

有一个关于 HyperLogLog 的 demo 网站可以看到 HyperLogLog 的算法过程,其链接是 http://content.research.neustar.biz/blog/hll.html

在这个 demo 中,作者对比了 LogLog 和 HyperLogLog 的区别和运行过程,有助于大家理解整个过程。其中 LogLog 与 HyperLogLog 的区别就在与它们平均值的处理方式不一样,前者是使用算术平均值,后者是使用调和平均值。

  • LogLog
  • HyperLogLog
</svg>" width="1366">
HyperLogLog Demo:初始化
</svg>" width="1368">
第一个 hash 值:3852172429

3852172429 的二进制是:11100101100110110111110010001101,可以划分为100 110110111110010 001101。最后的六位是 001101,十进制就是 13,那么这个数字就会被放入第 13 个桶;而 110110111110010(从低位到高位看), 函数的值就是 2;于是在第 13 个桶就会把 0 更新成 2。

</svg>" width="1362">
第二个 hash 值:2545698499

2545698499 的二进制是 10010111101111000100011011000011,用同样的分析可得结论。

</svg>" width="1368">
第三个 hash 值:2577699815

2577699815 的二进制是 10011001101001001001001111100111。

</svg>" width="1376">
第四个 hash 值:775376803

775376803 的二进制是 101110001101110100111110100011。

</svg>" width="1382">
运行结束

从以上的 Demo 运行过程可以看出,整个 HyperLogLog 的算法逻辑还是相对清晰的,其整个算法的亮点应该在于借助了抛硬币的场景,用抛硬币的结果来估算抛硬币的次数。

参考文献:

  1. Count-distinct Problem 的维基百科:https://en.wikipedia.org/wiki/Count-distinct_problem
  2. Heule, Stefan, Marc Nunkesser, and Alexander Hall. "HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm." Proceedings of the 16th International Conference on Extending Database Technology. 2013.
  3. Flajolet, Philippe, et al. "Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm." 2007.
  4. HyperLogLog 的 demo 网站:http://content.research.neustar.biz