Redis高级数据结构HyperLogLog原理详解和应用场景

本文将介绍Redis的数据结构HyperLogLog原理和应用场景。

Redis高级数据结构HyperLogLog

HyperLogLog类似set的使用方法，可以接受元素添加，并给出key包含的唯一元素的近似数量。
为什么说是近似数量，这和其实现有关系，先看完api再看实现原理和应用场景。

> PFADD key element [element … //将任意数量的元素添加到指定的 HyperLogLog 里面。
> PFADD KEY SWH
(integer) 1
> PFCOUNT key [key …] //储存在给定键的 HyperLogLog 的近似基数
> PFMERGE destkey sourcekey [sourcekey …] //合并key，基数是两者并集

HyperLogLog占用的空间固定，12k左右，可以估算出大约2^64个元素的基数。HyperLogLog本身不存储元素，不能获取从中获取元素。

实现原理

基数基数就是统计集合中不重复的元素的个数。最简单的算法是，建立一个集合将元素添加进去，新增元素之前先判断元素是否存在，不存在就不添加。这样的问题是：
1、这个集合占用的空间非常大。
2、集合大了之后判断一个元素是否存在变得困难。
基数计数方法
1、B树：插入和查找效率很高，但是不节省存储空间，hashset数据结构。
2、数据库也可以做，准确但性能较差。
3、bitmap：维护一个bit数组进行逻辑运算，这样确实大大减少内存占用
如果一个数据id长度是32bit，那么统计1亿的数据大概需要空间300M左右，空间占用不容小觑，而且加载到内存中运算时间也很长。
4、概率算法
概率算法不操作数据，而是根据概率算法估算出大约多少个基数，由于是基于概率的，所以基数值可能有偏差。算法主要有Linear Counting(LC)，LogLog Counting(LLC)和HyperLogLog Counting(HLL)。其中HLL在空间复杂度和错误率方面最优。一亿的数据HLL需要内存 不到1k就能做到，效率惊人，我们重点介绍下HLL。
HLL实现原理
先看下网上大神的总结：我们丢硬币的场景，第一次出现正面，之前都是反面的概率与实验次数有一个关系 n = 2^k，那么我们将 key 映射成 二进制hashcode，0001010, 该过程完全随机，那么 n 就等于 2的4次方，也就是说试验次数达到 8，但误差较大，所以我们采用多个映射取平均，这样误差就会变小。

HyperLogLog算法是用来计算基数的，这个抛硬币的序列和基数有什么关系呢？比如在数据库中，我只要在每次插入一条新的记录时，计算这条记录的hash，并且转换成二进制，就可以将其看成一个硬币序列了。大致原理的伪代码如下：

输入：一个集合
输出：集合的基数
算法：
     max = 0
     对于集合中的每个元素：
               hashCode = hash(元素)
               num = hashCode二进制表示中最前面连续的0的数量
               if num > max:
                   max = num
     最后的结果是2的(max + 1)次幂  

这样算法可能过于简单，redis把数据分成m(16384)个均等的部分，分别估计其总数求平均后再乘以m(16384)，称之为分桶；此外redis还采用调和平均数来减小估值的偏差，在下只能讲解这么多了，更多参考一下两篇文章

https://www.jianshu.com/p/55defda6dcd2
https://blog.51cto.com/13732225/2167661

应用场景

使用的场景都是一个大集合中，找出不重复的基数数量。比如
1、获取每天独立IP的访问量
2、获取每天某个页面user的独立访问量
这样的的场景不能考虑使用set去做，因为涉及大量的存储，占用很大的空间，可以考虑采用HyerLogLog去做，当然数值不是很精确。