redis专题05 海量数据处理之HyperLogLog

文章目录

1. 1. HyperLogLog数据结构基础应用
2. 2. HyperLogLog 实现原理
3. 3. 总结

HyperLoglog是redis新支持的两种类型中的另外一种(上一种是位图类型Bitmaps)。主要适用场景是海量数据的计算。特点是速度快, 占用空间小。

同样是用于计算，Bitmaps可能更适合用于验证的大数据，比如签到，记录某用户是不是当天进行了签到，签到了多少天的时候。也就是说，你不光需要记录数据，还需要对数据进行验证的时候使用Bitmaps。

而HyperLoglog则用于只记录的时候，如统计每个网页每天的访问UV,

如果统计PV那非常好办，给每个网页一个独立的Redis计数器就可以了，这个计数器的key后缀加上当天的日期。这样来一个请求，incrby一次，最终就可以统计出所有的PV数据。

但是UV不一样，它要去重，同一个用户一天之内的多次访问请求只能计数一次。这就要求每一个网页请求都需要带上用户的ID，无论是登陆用户还是未登陆用户都需要一个唯一ID来标识。

你也许已经想到了一个简单的方案，那就是为每一个页面一个独立的set集合来存储所有当天访问过此页面的用户ID。当一个请求过来时，我们使用sadd将用户ID塞进去就可以了。通过scard可以取出这个集合的大小，这个数字就是这个页面的UV数据。没错，这是一个非常简单的方案。

但如果页面访问量非常大，比如一个爆款页面几千万的UV，你需要一个很大的set集合来统计，这就非常浪费空间。如果这样的页面很多，那所需要的存储空间是惊人的。为这样一个去重功能就耗费这样多的存储空间，值得么？

由此可以用redis提供的HyperLogLog数据结构来解决这种统计问题的。

HyperLogLog提供不精确的去重计数方案，虽然不精确但是也不是非常不精确，标准误差是0.81%，这样的精确度已经可以满足上面的UV统计需求了。

HyperLogLog数据结构基础应用

redis为操作HyperLogLog数据结构提供了三条命令，

• pfadd 添加计数
• pfcount 获取计数

• pfmerge 合并两个数据的数据

• pfadd 添加数据

命令：PFADD key element [element ...]

• 功能：将除了第一个参数以外的参数存储到以第一个参数为变量名的HyperLogLog结构中。

• 如果一个HyperLogLog的估计的近似基数在执行命令过程中发了变化，PFADD返回1，否则返回0，如果指定的key不存在，这个命令会自动创建一个空的HyperLogLog结构（指定长度和编码的字符串）。
• 如果在调用该命令时仅提供变量名而不指定元素也是可以的，如果这个变量名存在，则不会有任何操作，如果不存在，则会创建一个数据结构。
• 返回值：如果HyperLogLog的内部被修改了,那么返回 1,否则返回 0 。

• pfcount

命令：PFCOUNT key [key ...]

• 功能：当参数为一个key时,返回存储在HyperLogLog结构体的该变量的近似基数，如果该变量不存在,则返回0。

• 当参数为多个key时，返回这些HyperLogLog并集的近似基数，这个值是将所给定的所有key的HyperLoglog结构合并到一个临时的HyperLogLog结构中计算而得到的;
• HyperLogLog可以使用固定且很少的内存（每个HyperLogLog结构需要12K字节再加上key本身的几个字节）来存储集合的唯一元素。返回的可见集合基数并不是精确值， 而是一个带有 0.81% 标准错误（standard error）的近似值。
• 返回值：PFADD添加的唯一元素的近似数量;

pfadd和pfcount用法和set集合的sadd和scard是一样的，添加数据，获取计数/长度;

# pfadd 添加计算，若修改了HyperLogLog结构则返回1 ，否则返回0
127.0.0.1:6379> pfadd page user1
(integer) 1
127.0.0.1:6379> pfadd page user1
(integer) 0
127.0.0.1:6379> pfcount page
(integer) 1
127.0.0.1:6379> pfadd page user2
(integer) 1
127.0.0.1:6379> pfcount page
(integer) 2
# pfadd 可以一次添加多个计数
127.0.0.1:6379> pfadd page user3 user4 user5
(integer) 1
127.0.0.1:6379> pfcount page
(integer) 5
127.0.0.1:6379>

• pfmerge

命令：PFMERGE destkey sourcekey [sourcekey ...]

• 功能：将多个HyperLogLog合并（merge）为一个HyperLogLog, 合并后的HyperLogLog的基数接近于所有输入HyperLogLog的可见集合（observed set）的并集;

• 合并得出的HyperLogLog会被储存在目标变量（第一个参数）里面， 如果该键并不存在， 那么命令在执行之前， 会先为该键创建一个空的;
• 返回值：这个命令只会返回 OK

127.0.0.1:6379> pfadd home user1
(integer) 1
127.0.0.1:6379> pfcount home
(integer) 1
127.0.0.1:6379> pfadd about user1
(integer) 1
127.0.0.1:6379> pfcount about
(integer) 1
# pfmerge 将home和about两个page的计算合并为total, 注意合并时会将home和about中相同的部分在进行Pfadd加入到新`total` HyperLogLog结构中时， 因其近似基数部分相同所以会被忽略而不会重复计数；
127.0.0.1:6379> pfmerge total home about
OK
# 合并生成 的total 并不是2 而是1， 因为home和about的计数值都是user1
127.0.0.1:6379> pfcount total
(integer) 1
127.0.0.1:6379> pfadd home user2
(integer) 1
127.0.0.1:6379> pfcount home
(integer) 2
127.0.0.1:6379> pfmerge total home about
OK
# 再次合并后就变成了2了， 因为不重复访问用户只有 user1, user2
127.0.0.1:6379> pfcount total
(integer) 2
127.0.0.1:6379> pfcount about
(integer) 1
# 注意pfmerge 是把source列表去重后合并到destkey， 如果destkey已经存在，和覆盖其之前值
# 同时合并仅对destkey值产生变更，其他不变
127.0.0.1:6379> pfmerge about home
OK
127.0.0.1:6379> pfcount about
(integer) 2
127.0.0.1:6379>

HyperLogLog 实现原理

上述实现过程中可以看到HyperLogLog 在统计计数时可以很好的处理重复值问题， 那它是如何做到的呢？ 这就需要进一步了解HyperLogLog的内部实现原理了，

redis内部HyperLogLog中会先给其分配一定数量的桶， 这些桶就是用来存储创建的key值的， 即pfadd key elmement中的key, 然后通过hash将element存储下来， 这样相同的element的近似基数是一样的，所以相同的element插入不在往桶中添加了，故在pfcount基数时 则只会算一次了，

上说的pfcount计算的是近似估值，误差在0.81%标准错误, 这是因为HyperLogLog在统计时计算的就是估值而不是精确值，因为在pfadd时是通过element的近似基数进行更新HyperLogLog结构的， 案例分析如下，

`pfadd nums 随机数1， 随机数2， 随机数3 … 随机数N

高位 <—————– 低位

随机数1 1 0 0 1 0 1 0 1 1 0 0 0 0
随机数2 1 0 0 1 0 1 0 1 0 1 0 0 0
随机数3 1 0 0 0 0 0 0 0 0 0 0 0 0
随机数4 1 0 0 1 0 1 0 1 1 1 1 0 0
随机数5 1 0 0 1 0 1 0 0 0 0 0 0 0
……
随机数N 1 0 0 1 0 0 0 0 0 0 0 0 0

如上， 给定一系列的随机整数，通过记录下低位连续零位的最大长度k，通过这个k值可以估算出随机数的数量，实验发现K和N的对数之间存在显著的线性相关性, 通过这种线性近似计算可以得到pfcount 指定key的近似估值， 详细的原理这里不在进一步阐述；

可进一步参看HyperLogLog 复杂的公式推导

redis的HyperLogLog实现中用到的是16384个桶，也就是2^14，每个桶的maxbits需要6 bits来存储，最大可以表示maxbits=63，于是总共占用内存就是2^14 * 6 / 8 = 12k字节。

总结

• 从处理海量数据count distict问题场景入手，引入redis的HyperLogLog数据结构解决方案，总结了使用方法并进行了实例分析说明；
• 对HyperLogLog 如何进行count distict计数的原理进行了简要探讨和实例分析说明，并给出了进一步参看建议;
• HyperLogLog结构主要是为了count-distinct问题，尤其是处理海量数据时，速度快，占用内存小，但是统计值是有误差的，并且只能递增，不能递减；
• redis对HyperLogLog的存储进行了优化，在计数比较小时，它的存储空间采用稀疏矩阵存储，空间占用很小，仅仅在计数慢慢变大，稀疏矩阵占用空间渐渐超过了阈值时才会一次性转变成稠密矩阵，才会占用12k的空间;