Redis 高级数据结构 HyperLogLog

介绍

    HyperLogLog(Hyper[ˈhaɪpə(r)])并不是一种新的数据结构(实际类型为字符串类型)，而是一种基数算法,通过HyperLogLog可以
利用极小的内存空间完成独立总数的统计，数据集可以是IP、Email、ID等。如果你负责开发维护一个大型的网站，有一天产品经理要网站每个网页每天的 UV 数据，然后让你来开发这个统计模块，你会如何实现？如果统计 PV 那非常好办，给每个网页一个独立的 Redis 计数器就可以了，这个计数器的 key 后缀加上当天的日期。这样来一个请求，
incrby 一次，最终就可以统计出所有的 PV 数据。但是 UV 不一样，它要去重，同一个用户一天之内的多次访问请求只能计数一次。这就要求每一个网页请求都需要带上用户的 ID，无论
是登陆用户还是未登陆用户都需要一个唯一 ID 来标识。一个简单的方案，那就是为每一个页面一个独立的 set 集合来存储所有当天访问过此页面的用户 ID。当一个请求过来时，我们使用
sadd 将用户 ID 塞进去就可以了。通过 scard 可以取出这个集合的大小，这个数字就是这个页面的 UV 数据。但是，如果你的页面访问量非常大，比如一个爆款页面几千万的 UV，你需要一个很大的 set集合来统计，这就非常浪费空间。如果这样的
页面很多，那所需要的存储空间是惊人的。为这样一个去重功能就耗费这样多的存储空间，值得么？其实需要的数据又不需要太精确，105w 
和 106w 这两个数字对于老板们来说并没有多大区别，So，有没有更好的解决方案呢？这就是HyperLogLog的用武之地，Redis 提供了 HyperLogLog 数据结构就是用来解决这种统计问题的。HyperLogLog 提供不精确的
去重计数方案，虽然不精确但是也不是非常不精确，Redis官方给出标准误差是0.81%，这样的精确度已经可以满足上面的UV 统计需求了。

百万级用户访问网站

操作命令

HyperLogLog提供了3个命令: pfadd、pfcount、pfmerge。

1、pfadd key element [element …] pfadd用于向HyperLogLog 添加元素,如果添加成功返回1

127.0.0.1:6379> pfadd u-6-1 u1 u2 u3
(integer) 1

2、pfcount pfcount key [key …] pfcount用于计算一个或多个HyperLogLog的独立总数

127.0.0.1:6379> pfcount u-6-1
(integer) 3如果此时向插入一些用户，用户并且有重复
127.0.0.1:6379> pfadd u-6-1 u1 u2 u3 u4 u5
(integer) 1
127.0.0.1:6379> pfcount u-6-1
(integer) 5
127.0.0.1:6379> pfadd u-6-2 u6 u7 u8 u9 u10
(integer) 1
127.0.0.1:6379> pfcount u-6-2
(integer) 5
127.0.0.1:6379> PFMERGE  u-6 u-6-1 u-6-2
OK
127.0.0.1:6379> pfcount u-6
(integer) 10

3、pfmerge destkey sourcekey [sourcekey … ] pfmerge可以求出多个HyperLogLog的并集并赋值给destkey

127.0.0.1:6379> pfcount u-6-1
(integer) 3如果此时向插入一些用户，用户并且有重复
127.0.0.1:6379> pfadd u-6-1 u1 u2 u3 u4 u5
(integer) 1
127.0.0.1:6379> pfcount u-6-1
(integer) 5
127.0.0.1:6379> pfadd u-6-2 u6 u7 u8 u9 u10
(integer) 1
127.0.0.1:6379> pfcount u-6-2
(integer) 5
127.0.0.1:6379> PFMERGE  u-6 u-6-1 u-6-2
OK
127.0.0.1:6379> pfcount u-6
(integer) 10

原理概述
1、基本原理
HyperLogLog基于概率论中伯努利试验并结合了极大似然估算方法，并做了分桶优化。
实际上目前还没有发现更好的在大数据场景中准确计算基数的高效算法，因此在不追求绝对准确的情况下，使用概率算法算是一个不错的解决方案。概率算法不直接存储数据集合本身，通过一定的概率统计方法预估值，这种方法可以大大节省内存，同时保证误差控制在一定范围内。目前用于基数计数的概率算法包括:

举个例子来理解HyperLogLog
规则如下: 抛硬币的游戏，每次抛的硬币可能正面，可能反面，每回合一直抛，直到每当抛到正面回合结束，抛到正面最长的回合用到了7次，你来猜一猜，我用到了多少个回合做到的？

进行了n次实验，比如上图：

第一次试验: 抛了3次才出现正面，此时 k=3，n=1

第二次试验: 抛了2次才出现正面，此时 k=2，n=2

第三次试验: 抛了4次才出现正面，此时 k=4，n=3

…………

第n 次试验：抛了7次才出现正面，此时我们估算，k=7

k是每回合抛到1所用的次数，我们已知的是最大的k值，可以用kmax表示。由于每次抛硬币的结果只有0和1两种情况，因此，能够推测出kmax在任意回合出现的概率，并由kmax结合极大似然估算的方法推测出n的次数n =2^(k_max) 。概率学把这种问题叫做伯努利实验。这种本身就是概率的问题，所以这种预估方法存在较大误差，为了改善误差情况，HLL中引入分桶平均的概念。

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

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

什么叫调和平均数呢？举个例子

求平均工资：A的是1000/月，B的30000/月。采用平均数的方式就是：
(1000 + 30000) / 2 = 15500

采用调和平均数的方式就是：
2/(1/1000 + 1/30000) ≈ 1935.484

可见调和平均数比平均数的好处就是不容易受到大的数值的影响，比平均数的效果是要更好的。

结合Redis的实现理解原理

现在我们和前面的业务场景进行挂钩：统计网页每天的 UV 数据。

1.转为比特串

通过hash函数，将数据转为二进制的比特串，例如输入5，便转为：101。为什么要这样转化呢？

是因为要和抛硬币对应上，比特串中，0 代表了反面，1 代表了正面，如果一个数据最终被转化了 10010000，那么从右往左，从低位往高位看，我们可以认为，首次出现 1 的时候，就是正面。

那么基于上面的估算结论，我们可以通过多次抛硬币实验的最大抛到正面的次数来预估总共进行了多少次实验，同样也就可以根据存入数据中，转化后的出现了 1 的最大的位置 k_max 来估算存入了多少数据。

2.分桶

分桶就是分多少轮。抽象到计算机存储中去，就是存储的是一个以单位是比特(bit)，长度为 L 的大数组 S ，将 S 平均分为 m 组，注意这个 m 组，就是对应多少轮，然后每组所占有的比特个数是平均的，设为 P。容易得出下面的关系：

比如有4个桶的话，那么可以截取低2位作为分桶的依据。

比如

10010000 进入0号桶

10010001 进入1号桶

10010010 进入2号桶

10010011 进入3号桶

Redis 中的 HyperLogLog 实现

pfadd

127.0.0.1:6379> pfadd u-6-1 u1
(integer) 1

当我们执行这个操作时，u1 这个字符串就会被转化成64个bit的二进制比特串。

0010…0001 64位

然后在Redis中要分到16384个桶中（为什么是这么多桶：第一降低误判，第二，用到了14位二进制：2的14次方=16384）

怎么分？根据得到的比特串的后14位来做判断即可。

根据上述的规则，我们知道这个数据要分到 1号桶，同时从右往左（低位到高位）计算第1个出现的1的位置，这里是第4位，那么就往这个1号桶插入4的数据（转成二进制）

如果有第二个数据来了，按照上述的规则进行计算。

那么问题来了，如果分到桶的数据有重复了（这里比大小，大的替换小的）：

规则如下，比大小（比出现位置的大小），比如有个数据是最高位才出现1，那么这个位置算出来就是50，50比4大，则进行替换。1号桶的数据就变成了50（二进制是110010）

所以这里可以看到，每个桶的数据一般情况下6位存储即可。

所以我们这里可以推算一下一个key的HyperLogLog只占据多少的存储。

16384*6 /8/1024=12k。并且这里最多可以存储多少数据，因为是64位吗，所以就是2的64次方的数据，这个存储的数据非常非常大的，一般用户用long来定义，最大值也只有这么多。

pfcount

进行统计的时候，就是把16384桶，把每个桶的值拿出来，比如取出是 n,那么访问次数就是2的n次方。

然后把每个桶的值做调和平均数，就可以算出一个算法值。

同时，在具体的算法实现上，HLL还有一个分阶段偏差修正算法。我们就不做更深入的了解了。

const和m都是Redis里面根据数据做的调和平均数。