分布式缓存Redis之HyperLogLog

亦凉 2022-05-10 06:10 217阅读 0赞

### 写在前面 ###

本学习教程所有示例代码见GitHub：[https://github.com/selfconzrr/Redis\_Learning][https_github.com_selfconzrr_Redis_Learning]

**基数估计算法**就是使用准确性换取空间。 为了说明这一点，我们用三种不同的计算方法**统计所有莎士比亚作品中不同单词的数量**。请注意，我们的输入数据集增加了额外的数据以致比问题的参考基数更高。 这三种技术是：Java HashSet、Linear Probabilistic Counter以及一个Hyper LogLog Counter。结果如下：

![这里写图片描述][SouthEast]

该表显示，我们统计这些单词只用了512 bytes，而误差在3%以内。相比之下，HashMap的计数准确度最高，但需要近10MB的空间，你可以很容易地看到为什么基数估计是有用的。在实际应用中准确性并不是很重要的，这是事实，在大多数网络规模和网络计算的情况下，用概率计数器会节省巨大的空间。

再者，**如果我们要实现记录网站每天访问的独立IP数量**这样的一个功能：

**集合实现：**

使用集合来储存每个访客的 IP ，通过集合性质（集合中的每个元素都各不相同）来得到多个独立 IP，然后通过调用 SCARD 命令来得出独立 IP 的数量。

举个例子，程序可以使用以下代码来记录 2017 年 12 月 5 日，每个网站访客的 IP ：

ip = get_vistor_ip()
    SADD '2017.12.5::unique::ip' ip

然后使用以下代码来获得当天的唯一 IP 数量：

SCARD '2017.12.5::unique::ip'

**集合实现的问题**

使用字符串来储存每个IPv4 地址最多需要耗费15 字节（格式为 ‘XXX.XXX.XXX.XXX’，比如’202.189.128.186’）。

下表给出了使用集合记录不同数量的独立 IP 时，需要耗费的内存数量：

<table> 
 <thead> 
  <tr> 
   <th>独立IP数量</th> 
   <th>一天</th> 
   <th>一个月</th> 
   <th>一年</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>一百万</td> 
   <td>15 MB</td> 
   <td>450 MB</td> 
   <td>5.4 GB</td> 
  </tr> 
  <tr> 
   <td>一千万</td> 
   <td>150 MB</td> 
   <td>4.5 GB</td> 
   <td>54 GB</td> 
  </tr> 
  <tr> 
   <td>一亿</td> 
   <td>1.5 GB</td> 
   <td>45 GB</td> 
   <td>540 GB</td> 
  </tr> 
 </tbody> 
</table>

随着集合记录的 IP 越来越多，消耗的内存也会越来越多。另外如果要储存 IPv6 地址的话，需要的内存还会更多一些。为了更好地解决像独立 IP 地址计算这种问题，Redis 在 2.8.9 版本添加了 HyperLogLog 结构（一般12kb就够了）。

### Redis数据结构HyperLogLog ###

Redis HyperLogLog 是用来做**基数统计**的算法，HyperLogLog 的优点是，在输入元素的数量或者体积非常非常大时，计算基数所需的空间总是固定的、并且是很小的。在Redis 里面，每个 HyperLogLog 键只**需要花费 12 KB 内存**，就可以计算接近 2^64 个不同元素的基数。这和使用集合计算基数时，元素越多耗费内存就越多的集合形成鲜明对比。但是，因为 HyperLogLog 只会根据输入元素来计算基数，而不会储存输入元素本身，所以 HyperLogLog 不能像集合那样，返回输入的各个元素。

**基于HyperLogLog算法分析：**

redis中统计数组大小设置为m=16384，hash函数生成64位bit数组，其中 log2(16834)=14位用来找到统计数组的位置，剩下50位用来记录第一个1出现的位置，最大位置为50，需要log2(50)=6位记录。那么统计数组需要的最大内存大小为： 6bit∗16834≈12k **（为什么是12k？？？）** 。基数估计的标准误差为0.81%

### 什么是基数? ###

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

估算值：算法给出的基数并不是精确的，可能会比实际稍微多一些或者稍微少一些，但会控制在合理的范围之内。

### 几个命令 ###

**将元素添加至 HyperLogLog**

1、PFADD key element \[element …\]

将任意数量的元素添加到指定的 HyperLogLog 里面。

这个命令可能会对 HyperLogLog的基数估算值进行修改，以便反映新的基数估算值，如果 HyperLogLog 的基数估算值在命令执行之后出现了变化，那么命令返回1，否则返回0。

命令的复杂度为 O(N) ，N 为被添加元素的数量。

2、PFCOUNT key \[key …\]

返回给定 HyperLogLog 的基数估算值。

当只给定一个 HyperLogLog 时，命令返回给定 HyperLogLog 的基数估算值。

当给定多个 HyperLogLog 时，命令会先对给定的 HyperLogLog 进行并集计算，得出一个合并后的HyperLogLog ，然后返回这个合并 HyperLogLog 的基数估算值作为命令的结果（合并得出的HyperLogLog 不会被储存，使用之后就会被删掉）。

当命令作用于单个 HyperLogLog 时， 复杂度为 O(1) ， 并且具有非常低的平均常数时间。

当命令作用于多个 HyperLogLog 时， 复杂度为 O(N) ，并且常数时间也比处理单个 HyperLogLog 时要大得多。

**PFADD 和 PFCOUNT 的使用示例**

redis> PFADD unique::ip::counter '192.168.0.1'
    (integer) 1
    redis> PFADD unique::ip::counter '127.0.0.1'
    (integer) 1
    redis> PFADD unique::ip::counter '255.255.255.255'
    (integer) 1
    redis> PFCOUNT unique::ip::counter
    (integer) 3

![这里写图片描述][1512521287_4168.png]

**合并多个 HyperLogLog**

3、PFMERGE destkey sourcekey \[sourcekey …\]

将多个 HyperLogLog 合并为一个 HyperLogLog ，合并后的 HyperLogLog 的基数估算值是通过对所有给定 HyperLogLog 进行并集计算得出的。

**PFMERGE 的使用示例**

redis> PFADD str1 "apple" "banana" "cherry"
    (integer) 1
    redis> PFCOUNT str1
    (integer) 3
    redis> PFADD str2 "apple" "cherry" "durian" "mongo"
    (integer) 1
    redis> PFCOUNT str2
    (integer) 4
    redis> PFMERGE str1&2 str1 str2
    OK
    redis> PFCOUNT str1&2
    (integer) 5

### Hyperloglog（HLL）算法浅说 ###

这里有个HLL demo：[http://content.research.neustar.biz/blog/hll.html][http_content.research.neustar.biz_blog_hll.html]可以看一下HLL到底是怎么做到这种超乎想象的事情的。

1、通过hash函数计算输入值对应的比特串；

2、比特串的低 t(t=log2(m))位对应的数字用来找到数组S中对应的位置 i；

3、t+1位开始找到第一个1出现的位置 k，将 k记入数组S\_i位置；

4、基于数组S记录的所有数据的统计值，计算整体的基数值，计算公式可以简单表示为：n^=f(S)n^=f(S)

原理理解

（摘自  
[http://rainybowe.com/blog/2017/07/13/%E7%A5%9E%E5%A5%87%E7%9A%84HyperLogLog%E7%AE%97%E6%B3%95/index.html?utm\_source=tuicool&utm\_medium=referral][http_rainybowe.com_blog_2017_07_13_E7_A5_9E_E5_A5_87_E7_9A_84HyperLogLog_E7_AE_97_E6_B3_95_index.html_utm_source_tuicool_utm_medium_referral]）

看到这里心里应该有无数个问号，这样真的就能统计到上亿条数据的基数了吗？我总结一下，先抛出三个疑问：

1、为什么要记录第一个1出现的位置？  
2、为什么要有分桶数组 S？  
3、通过分桶数组 S计算基数的公式是什么？

![这里写图片描述][SouthEast 1]

可以通过一组小实验验证一下这种估计方法是否基本合理。

回到基数统计的问题，我们需要统计一组数据中不重复元素的个数，集合中每个元素的经过hash函数后可以表示成0和1构成的二进制数串，一个二进制串可以类比为一次抛硬币实验，1是抛到正面，0是反面。二进制串中从低位开始第一个1出现的位置可以理解为抛硬币试验中第一次出现正面的抛掷次数k，那么基于上面的结论，我们可以通过多次抛硬币实验的最大抛到正面的次数来预估总共进行了多少次实验，同样可以可以通过第一个1出现位置的最大值k\_max来预估总共有多少个不同的数字（整体基数）。

这种通过局部信息预估整体数据流特性的方法似乎有些超出我们的基本认知，需要用概率和统计的方法才能推导和验证这种关联关系。HyperLogLog核心在于观察集合中每个数字对应的比特串，通过统计和记录比特串中最大的出现1的位置来估计集合整体的基数，可以大大减少内存耗费。

现在回到关于HyperLogLog的第一个疑问，为什么要统计hash值中第一个1出现的位置？第一个1出现的位置可以类比为抛硬币实验中第一次抛到正面的抛掷次数，根据抛硬币实验的结论，记录每个数据的第一个出现的位置k，就可以通过其中最大值kmaxkmax推导出数据集合的基数：n^=2kmaxn^=2kmax

HLL的基本思想是利用集合中数字的比特串第一个1出现位置的最大值来预估整体基数，但是这种预估方法存在较大误差，为了改善误差情况，HLL中引入**分桶平均**的概念。

同样举抛硬币的例子，如果只有一组抛硬币实验，运气较好，第一次实验过程就抛了10次才第一次抛到正面，显然根据公式推导得到的实验次数的估计误差较大；如果100个组同时进行抛硬币实验，同时运气这么好的概率就很低了，每组分别进行多次抛硬币实验，并上报各自实验过程中抛到正面的抛掷次数的最大值，就能根据100组的平均值预估整体的实验次数了。

**分桶平均的基本原理**是将统计数据划分为m个桶，每个桶分别统计各自的kmaxkmax并能得到各自的基数预估值 n^n^，最终对这些 n^n^求平均得到整体的基数估计值。LLC中使用几何平均数预估整体的基数值，但是当统计数据量较小时误差较大；HLL在LLC基础上做了改进，采用**调和平均数**，调和平均数的优点是可以过滤掉不健康的统计值。

虽然调和平均数能够适当修正算法误差，但作者给出一种**分阶段修正算法**。当HLL算法开始统计数据时，统计数组中大部分位置都是空数据，并且需要一段时间才能填满数组，这种阶段引入一种小范围修正方法；当HLL算法中统计数组已满的时候，需要统计的数据基数很大，这时候hash空间会出现很多碰撞情况，这种阶段引入一种大范围修正方法。

回到关于HLL的第二个疑问，为什么要有分桶数组 S？分桶数组是为了消减因偶然性带来的误差，提高预估的准确性。

该算法出自论文《HyperLogLog the analysis of a near-optimal cardinality estimation algorithm》，下载链接：[http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf][http_algo.inria.fr_flajolet_Publications_FlFuGaMe07.pdf]。具体论文的理论推导不详细介绍，简述下其思想核心。

HLL中实际存储的是一个长度为m的大数组S，将待统计的数据集合划分成m组(分桶数组)，每组根据算法记录一个统计值存入数组中。数组的大小m由算法实现方自己确定，redis中这个数组的大小是16834，m越大，基数统计的误差越小，但需要的内存空间也越大。

算法实现：

m = 2^b   # with b in [4...16]
    
    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)

**Java源代码实现参考：**

[https://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/cardinality/HyperLogLog.java][https_github.com_addthis_stream-lib_blob_master_src_main_java_com_clearspring_analytics_stream_cardinality_HyperLogLog.java]

**若想深入了解Hyper LogLog，还可以参考这篇论文：**

[http://www.ic.unicamp.br/~celio/peer2peer/math/bitmap-algorithms/durand03loglog.pdf][http_www.ic.unicamp.br_celio_peer2peer_math_bitmap-algorithms_durand03loglog.pdf]

\--------------------- 本文来自 BugFree\_张瑞 的CSDN 博客 ，全文地址请点击：https://blog.csdn.net/u011489043/article/details/78727128?utm\_source=copy

[https_github.com_selfconzrr_Redis_Learning]: https://github.com/selfconzrr/Redis_Learning
[SouthEast]: /images/20220510/dc2413e7a29841f39342cc0a63f4256a.png
[1512521287_4168.png]: https://img-my.csdn.net/uploads/201712/06/1512521287_4168.png
[http_content.research.neustar.biz_blog_hll.html]: http://content.research.neustar.biz/blog/hll.html
[http_rainybowe.com_blog_2017_07_13_E7_A5_9E_E5_A5_87_E7_9A_84HyperLogLog_E7_AE_97_E6_B3_95_index.html_utm_source_tuicool_utm_medium_referral]: http://rainybowe.com/blog/2017/07/13/%E7%A5%9E%E5%A5%87%E7%9A%84HyperLogLog%E7%AE%97%E6%B3%95/index.html?utm_source=tuicool&utm_medium=referral
[SouthEast 1]: /images/20220510/1204652a200841ac8b3c4d8fa9c62fec.png
[http_algo.inria.fr_flajolet_Publications_FlFuGaMe07.pdf]: http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
[https_github.com_addthis_stream-lib_blob_master_src_main_java_com_clearspring_analytics_stream_cardinality_HyperLogLog.java]: https://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/cardinality/HyperLogLog.java
[http_www.ic.unicamp.br_celio_peer2peer_math_bitmap-algorithms_durand03loglog.pdf]: http://www.ic.unicamp.br/~celio/peer2peer/math/bitmap-algorithms/durand03loglog.pdf