redis的几个数据结构 —— HyperLogLog

HyperLogLog

应用场景

在工作中经常会有uv、pv的统计,传统的实现方式就是用户日志上报到hbase,然后通过hive来查询,每日出报表。

如果是使用redis来实现,假设是使用ip来区分用户,假设存储一个ip为15个字节,300万的ip其开销是45MB,唯一ip可能每天出现数十万、数百万甚至数千万。

在redis中,有一种基于概率算法的计算集合的基数的数据结构,就是HyperLogLog,可以解决不要求百分百精度的UV计算。在上面例子中的300万ip,使用HyperLogLog只需要12字节即可计算。

UV 纯IP开销 HyperLogLog
记录300万 45MB 12字节

只需要12K内存,在标准误差0.81%的前提下,HyperLogLog能够统计2^64个数据。

原理

我们来看下HyperLogLog的原理:

  1. 抛硬币,一直抛到出现正面,记录下投掷次数k,该过程记为一次伯努利方程。
  2. n次伯努利过程的投掷次数都不大于k_max的概率
    hyperloglog1
  3. n次伯努利过程,至少有一次投掷次数等于k_max的概率
    hyperloglog2
  4. n ≪ 2^(𝑘_𝑚𝑎𝑥 ) 时,第一个公式概率接近0
  5. n ≫ 2^(𝑘_𝑚𝑎𝑥 ) 时,第二个公式概率接近0
  6. 我们似乎可以用2^(𝑘_𝑚𝑎𝑥 ) 估算n?

详细的推理步骤请参考HLL的论文: https://arxiv.org/pdf/1702.01284.pdf

误差

  1. 如图一,四次伯努利方程产生k_max =4,计算得到基数n为16
  2. 图二改进一:因为只做一次实验得到的数据是不准确的,所以改进实验:两两分组计算k_max 再平均得到n=8:只使用单一的估计量会由于偶然性造成比较大的误差,LogLog Counting采用分桶多次试验的方法减少误差。将比特长度为LL 哈希空间分为2l=m2l=m份,每一份被称为一个 bucket。哈希值的前ll位作为 bucket 的编号,后L−lL−l 位为哈希值,
  3. 图三改进二:使用调和平均数,得到n=6(2.667(2/(1/2+1/4))

图一:
hyperloglog3
图二:
hyperloglog4
图三:
hyperloglog5

Redis中的实现

实现原理

我们来看下redis中的实现:
对元素进行hash,64位hash值:

  • 低14位作为桶号码(2^14 =16384个桶)。
  • 高50位作为k_max,这高50位从低位到高位找到第一个1的位置,作为count,count再取低6位作为每个桶的值,即通过第一个1出现位置的最大值k_max 预估n。

其中,分桶就是分多少轮。

为什么需要16384个桶?这是根据“相对标准误差”(relative standard deviation,简称RSD)公式计算得来的。RSD的值与分桶数m存在如下的计算关系:

hyperloglog6

带入公式就是 1.04/math.sqrt(16384) = 0.008125。

每个桶用6位表示这个桶的k_max值,可表达最大数字63(2^6)

例子

我们来举个栗子:

  1. 假设一个用户id的哈希值:1001011000011
  2. 假设低两位作为桶,则放到桶3
  3. 剩下10010110000,从低位往高位看第一个1在位置5
  4. 则设第三个桶为101(如果该桶原来的值比101小)
  5. 计算的时候所有桶求调和平均数

hyperloglog7

comments powered by Disqus