Redis中的HyperLogLog浅析

Redis 在 2.8.9 版本添加了 HyperLogLog 结构。
Redis HyperLogLog 是用来做基数统计的算法。

什么是基数？
比如数据集 {1, 3, 5, 7, 5, 7, 8}， 那么这个数据集的基数集为 {1, 3, 5 ,7, 8}, 基数(不重复元素)为5。 基数估计就是在误差可接受的范围内，快速计算基数。

基数计数(cardinality counting)通常用来统计一个集合中不重复的元素个数，例如统计某个网站的UV，或者用户搜索网站的关键词数量。如果统计 PV 那非常好办，给每个网页一个独立的 Redis 计数器就可以了，这个计数器的 key 后缀加上当天的日期。这样来一个请求，INCRBY 一次，最终就可以统计出所有的 PV 数据。

但是 UV 不一样，它要去重，同一个用户一天之内的多次访问请求只能计数一次。这就要求每一个网页请求都需要带上用户的 ID，无论是登陆用户还是未登陆用户都需要一个唯一 ID 来标识。如果采用元素越多耗费内存就越多的集合（HashSet、B+ Tree、BitMap）来存储已登录的用户ID，那么在输入元素的数量或者体积非常大时查重时间（O(log n)）与内存开销（O(n)）都是十分巨大的。相比之下HyperLogLog 计算基数所需的空间总是固定的、并且是很小的。在 Redis 里面，每个 HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基数。

但是，因为 HyperLogLog 只会根据输入元素来计算基数，而不会储存输入元素本身，所以 HyperLogLog 不能像集合那样，返回输入的各个元素，也不能删除元素，这一点和布隆过滤器非常相似。

此外，HyperLogLog 提供的是不准确的去重计数方案，但是可以保证基数随统计量单调递增，并且标准误差达到 0.81%，这样的精确度已经可以满足大部分统计需求了。

HyperLogLog有三个非常简单的API：

• PFADD 将多个值存入指定的HyperLogLog
• PFCOUNT 获取指定HyperLogLog的基数
• PFMERGE 合并多个HyperLogLog，合并前的结果和合并后的统计结果完全一致（取并集），不存在因合并导致的误差

HyperLogLog原理

举一个我们最熟悉的抛硬币例子，出现正反面的概率都是1/2，一直抛硬币直到出现正面，记录下投掷次数k，将这种抛硬币多次直到出现正面的过程记为一次伯努利过程，对于n次伯努利过程，我们会得到n个出现正面的投掷次数值其中最大值记为k​max，那么可以得到下面结论：

• n次伯努利过程的投掷次数都不大于k​max
• ​n次伯努利过程，至少有一次投掷次数等于k​max

那么根据最大似然估计的原理，我们可以反过来讲：进行了n次进行抛硬币实验，每次分别记录下第一次抛到正面的抛掷次数k，那么可以用n次实验中最大的抛掷次数k​max来预估实验组数量n：

N=2^K

HyperLog.jpg

基于这个原理，如果我们对存入HyperLogLog的值进行hash运算，所得hash码的二进制位就可以看做一次伯努利过程。每一位上的0或1就可以看作每次投掷硬币的结果，那么第一次出现1的位置所对应的索引就可以看作kmax，那么根据kmax就可以估算存入的数据基数。

但是如果 N 介于 2^K 和 2^(K+1) 之间，用这种方式估计的值都等于 2^K，所以用这样的单一估计偶然性较大，导致误差较大，因此在实际的 HyperLogLog 算法中，会先分桶统计然后计算平均值来消除误差。这里使用的平均值是调和平均 (倒数的平均)。普通的平均法可能因为个别离群值对平均结果产生较大的影响，调和平均可以有效平滑离群值的影响。

上述经过分桶平均后的估计量看似已经很不错了，不过通过数学分析可以知道这并不是基数n的无偏估计，因此需要修正成无偏估计。当HyperLogLog开始统计数据时，统计数组中大部分位置都是空数据，并且需要一段时间才能填满数组，这种阶段引入一种小范围修正方法；当统计数组已满的时候，需要统计的数据基数很大，这时候hash空间会出现很多碰撞情况，这种阶段引入一种大范围修正方法。其中系数由统计数组的大小决定，最终算法用伪代码可以表示为：

// m 为桶数 b是m的以2为底的对数
m = 2^b 

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   # initialize m registers to 0

###########################################################################
# Construct the HLL structure
for h in hashed(data):
    register_index = 1 + get_register_index( h,b ) # binary address of the rightmost b bits
    run_length = run_of_zeros( h,b ) # length of the run of zeroes starting at bit b+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: # small range correction
    V = count_of_zero_registers( registers ) # the number of registers equal to zero
    if V == 0:  # if none of the registers are empty, use the HLL estimate
          DV = DV_est
    else:
          DV = m * log(m/V)  # i.e. balls and bins correction

if DV_est <= ( 1/30 * 2^32 ):  # intermediate range, no correction
     DV = DV_est
if DV_est > ( 1/30 * 2^32 ):  # large range correction
     DV = -2^32 * log( 1 - DV_est/2^32)

Redis中的实现细节

数据在存入时，value 会被 hash 成 64 位，即 64 bit 的比特字符串，前 14 位用来选择这个 value 的比特串中从右往左第一个 1 出现的下标位置数值要存到那个桶中去，即前 14 位用来分桶。之所以选 14位 来表达桶编号是因为，分了 16384 个桶，而 2^14 = 16384，刚好可以把每个编号都利用上，不造成浪费。假设一个字符串的前 14 位是：00 0000 0000 0010 (从右往左看) ，其十进制值为 2。那么 index 将会被转化后放到编号为 2 的桶。每个桶的index 需要 6 个 bits 来存储，最大可以表示 index=63，于是总共占用内存就是2^14 * 6 / 8 = 12k字节。

因为完整的 value 比特字符串是 64 位形式，减去 14 后，剩下 50 位，那么极端情况，出现 1 的位置，是在第 50 位，即位置是 50。此时 index = 50。此时先将 index 转为 2 进制，它是：110010 。因为16384 个桶中，每个桶是 6 bit 组成的。刚好 110010 就被设置到了第 2 号桶中去了。请注意，50 已经是最坏的情况，且它都被容纳进去了。那么其他的不用想也肯定能被容纳进去。

fpadd 的 key 可以设置多个 value。所以根据上面的做法，不同的 value，会被设置到不同桶中去，如果出现了在同一个桶的，即前 14 位值是一样的，但是后面出现 1 的位置不一样。那么比较原来的 index 是否比新 index 大。是，则替换。否，则不变。最终，一个 key 所对应的 16384 个桶都设置了很多的 value 了，每个桶有一个k_max。此时调用 pfcount 时，按照前面介绍的估算方式，便可以计算出 key 的设置了多少次 value，也就是统计值。value 被转为 64 位的比特串，最终被按照上面的做法记录到每个桶中去。

此外，Redis 对 HyperLogLog 的存储进行了优化，在计数比较小时，它的存储空间采用稀疏矩阵存储，空间占用很小，仅仅在计数慢慢变大，稀疏矩阵占用空间渐渐超过了阈值时才会一次性转变成稠密矩阵，才会占用 12k 的空间。