有限空间存储无限大数字，神奇的HyperLogLog算法

2018-11-28 本文已影响3人无敌的CF

最近的项目组做了一个EDM(Email Direct Marketing)后台项目。其中一个重要的环节就是tracking. 要记录邮件的发送成功数，打开总数，打开用户数，邮件里面每个连接的点击率等等。邮件数目是千万级别的，这就对存储数据提出了一点小要求。我们最终是选用Redis的BitMap结构来实现记录。BitMap很好理解，其实就是对存储空间的极致利用。
更吸引我的是同样Redis也支持的HyperLogLog结构。与其说HLL是一种存储结构，我认为它的算法部分更为重要。下文就一点一点讲一讲吧~
咳咳，讲之前不如我们先做一个友好的约定，那就是：绝对不会出现数学公式~！毕竟我为写此文，参考文章无数，看算式看得我脑壳疼。

1. 基数计数(cardinality counting)

基数（cardinality）就是一个集合中不同元素的个数。

举个栗子，qq的同时在线人数有三亿多人，这就是一次基数计数。有些大型的网站每天的访问量都是亿级别的，这么大的数字要怎么计数呢？一个用户不停刷新网页应该只被记录为一个访问用户，怎么判断一个用户是否已经在这个集合中了呢？难道每次都要遍历整个集合吗？如果我想要的是一周的上线人数，需要把7天的上线人数加起来，怎样才能让每天重复登陆的人只计数一次呢。这就需要用到HLL算法了。好吧，我承认我有点标题党了，HLL只是能在有限的空间下保存一个几乎无限大的集合中不同元素的总数，并且会有一些误差存在。Redis上面的HLL能做到在12K内存中，标准误差0.81%的前提下，存储最大到2的64次方的数字。具体怎么实现呢，请继续往下看~

2. 伯努利过程（Bernoulli process）

在说伯努利过程之前，我们先来讲讲伯努利试验。

伯努利试验（Bernoulli trial）就是结果有且仅有两种可能性的单次随机试验。

举个简单的例子，不抬杠而论，我抛一次硬币只会有两种结果，正面或者反面。抛一次硬币就是一次伯努利试验。

一系列的互相独立并且结果概率相同的伯努利试验就是一个伯努利过程（Bernoulli process）。

所以我们可以设想这样一个伯努利过程：抛n次硬币，直到有一次正面朝上为止。一般常识来讲，抛个一两次，就会遇到正面，但是如果我们重复这个伯努利过程次数够多，就可能出现抛很多次才出现正面的情况。换句话说，我们根据最多抛了几次才出现正面，就可以大约估算出我们进行了多少次伯努利过程。用这样的办法，我们可以在只记录一个很小的数字的前提下，同时也推算出一个大得多的数字。

3. 散列（hash）

怎样把每次基数的增加类比成一连串掷硬币呢？我们用到了散列算法。散列算法又是一个很大的话题了。

散列（hash）是一种从任何一种数据中创建小的数字“指纹”的方法。

而这个算法中我们主要关心的就是它可以把任何数据都变成一个不太长的数字，并且这个过程是幂等（idempotent）的。

幂等（idempotent）在算法中的意思是多次重复获得的结果相同。

比如，同一个用户id经过hash之后总会得到相同的数字，这样我们就不会把同一个用户重复记录两次。接下来，我们可以观察hash得到的数字的二进制形式中第一个1出现的位置，这就和上一步中的掷硬币直到正面是一样的了。

4. 分桶（bucket）平均

上述步骤中对于伯努利过程的反向推算还是太不靠谱了，瞎眼可见的误差。这就需要我们进行分桶。每次“掷硬币”之前，我们会先随机分配一个桶，这次掷硬币的结果就纪录在这个桶中。之后再把每个桶中的最大值取调和平均数（harmonic mean）。这样可以规避一些极端值的影响。Redis对HLL的实现用了16834个桶。

5. 修正

当需要统计的数字很小或者很大时，HLL还是会有一些误差需要修正，具体的做法是在数字很小时换用另一种较简单的基数计数方法Linear Counting，在数字很大时利用统计学的方法进行修正。

6. 伪代码

可怕的地方来了，我只说了不列公式，没有说不放代码啊~ HLL算法实现的伪代码如下：

m = 2^b # b取值范围在[4...16]，Redis中b=14, m=16834
 
if m == 16:
    alpha = 0.673
elif m == 32:
    alpha = 0.697
elif m == 64:
    alpha = 0.709
else:
    alpha = 0.7213/(1 + 1.079/m)
 
registers = [0]*m # 每个桶的初始值都是0
 
##############################################################################################
# Construct the HLL structure
for h in hashed(data):
    register_index = 1 + get_register_index( h,b ) # 用二进制最左边的b位作为桶的index
    run_length = run_of_zeros( h,b ) # 从第b+1位开始寻找第一个出现的1
    registers[ register_index ] = max( registers[ register_index ], run_length )
 
##############################################################################################
# Determine the cardinality
DV_est = alpha * m^2 * 1/sum( 2^ -register )  # the DV estimate
 
if DV_est < 5/2 * m: # 小范围修正
    V = count_of_zero_registers( registers ) # 有多少个桶目前的计数还是0
    if V == 0:  # 如果都不是0，无法使用Linear Counting
          DV = DV_est
    else:
          DV = m * log(m/V)  # Linear Counting
 
if DV_est <= ( 1/30 * 2^32 ):  # 不用修正
     DV = DV_est
if DV_est > ( 1/30 * 2^32 ):  # 大范围修正
     DV = -2^32 * log( 1 - DV_est/2^32)

感悟

Loglog的意思就是这个算法的空间复杂度是 O(loglogN)，也就是说存储一个大小为N的数字最多只会占用loglogN级别的空间。所以也不是无限大，只是可以看作无限大。

参考文献

Sketch of the Day: HyperLogLog — Cornerstone of a Big Data Infrastructure
Redis new data structure: the HyperLogLog