32.Redis高级数据结构HyperLogLog
1.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 集合来统计，这就非常浪费空间。如果这样的页面很多，那所需要的存储空间是惊人的。为这样一个去重功能就耗费这样多的存储空间，值得么？其实需要的数据又不需要太精确，1050w 和 1060w 这两个数字对于老板们来说并没有多大区别，So，有没有更好的解决方案呢？
这就是HyperLogLog 的用武之地，Redis 提供了 HyperLogLog 数据结构就是用来解决这种统计问题的。HyperLogLog 提供不精确的去重计数方案，虽然不精确但是也不是非常不精确，Redis官方给出标准误差是 0.81%，这样的精确度已经可以满足上面的 UV 统计需求了。
2.操作命令
HyperLogLog 提供了 3个命令: pfadd、pfcount、pfmerge。
例如08-15 的访问用户是u1、u2、u3、u4，08-16的访问用户是u-4、u-5、u-6、u-7
2.1 pfadd
pfadd key element [element …]
pfadd 用于向HyperLogLog 添加元素,如果添加成功返回1:
pfadd 08-15:u:id "u1" "u2" "u3" "u4
2.2 pfcount
pfcount key [key …]
pfcount 用于计算一个或多个HyperLogLog的独立总数，例如08-15:u:id的独立总数为4:
pfcount 08-15:u:id
如果此时向插入u1、u2、u3、u90，结果是5:
pfadd 08-15:u:id "u1" "u2" "u3" "u90" pfcount 08-15:u:id
如果我们继续往里面插入数据，比如插入100万条用户记录。内存增加非常少，但是pfcount 的统计结果会出现误差。
以使用集合类型和 HperLogLog统计百万级用户访问次数的占用空间对比：
数据类型 1天 1个月 1年
集合类型 80M 2.4G 28G
HyperLogLog 15k 450k 5M
可以看到，HyperLogLog内存占用量小得惊人，但是用如此小空间来估算如此巨大的数据，必然不是100%的正确，其中一定存在误差率。前面说过，Redis官方给出的数字是0.81%的失误率。
2.3 pfmerge
pfmerge destkey sourcekey [sourcekey ... ]
pfmerge 可以求出多个HyperLogLog 的并集并赋值给destkey
3.数学原理
HyperLogLog 基于概率论中伯努利试验并结合了极大似然估算方法，并做了分桶优化。
实际上目前还没有发现更好的在大数据场景中准确计算基数的高效算法，因此在不追求绝对准确的情况下，使用概率算法算是一个不错的解决方案。概率算法不直接存储数据集合本身，通过一定的概率统计方法预估值，这种方法可以大大节省内存，同时保证误差控制在一定范围内。目前用于基数计数的概率算法包括:
Linear Counting(LC)：早期的基数估计算法，LC在空间复杂度方面并不算优秀；
LogLog Counting(LLC)：LogLog Counting 相比于 LC 更加节省内存，空间复杂度更低；
HyperLogLog Counting(HLL)：HyperLogLog Counting 是基于 LLC 的优化和改进，在同样空间复杂度情况下，能够比LLC的基数估计误差更小。
4.Redis 中的 HyperLogLog 实现
Redis 的实现中，HyperLogLog 占据12KB(占用内存为=16834 * 6 / 8 / 1024 = 12K)的大小，共设有 16384 个桶，即：2^14 = 16384，每个桶有 6 位，每个桶可以表达的最大数字是：25+24+...+1 = 63 ，二进制为： 111 111 。
对于命令：pfadd key value
在存入时，value 会被 hash 成 64 位，即 64 bit 的比特字符串，前 14 位用来分桶，剩下50位用来记录第一个1出现的位置。
之所以选 14位 来表达桶编号是因为分了 16384 个桶，而 2^14 = 16384，刚好地，最大的时候可以把桶利用完，不造成浪费。假设一个字符串的前 14 位是：00 0000 0000 0010 (从右往左看) ，其十进制值为 2。那么 value 对应转化后的值放到编号为 2 的桶。
index 的转化规则：
首先因为完整的 value 比特字符串是 64 位形式，减去 14 后，剩下 50 位，假设极端情况，出现 1 的位置，是在第 50 位，即位置是 50。此时 index = 50。此时先将 index 转为 2 进制，它是：110010 。
因为16384 个桶中，每个桶是 6 bit 组成的。于是 110010 就被设置到了第 2 号桶中去了。请注意，50 已经是最坏的情况，且它都被容纳进去了。
那么其他的不用想也肯定能被容纳进去。
因为 fpadd 的 key 可以设置多个 value。
例如下面的例子：
pfadd lgh golang
pfadd lgh python
pfadd lgh java
根据上面的做法，不同的 value，会被设置到不同桶中去，如果出现了在同一个桶的，即前 14 位值是一样的，但是后面出现 1 的位置不一样。那么比较原来的 index 是否比新 index 大。是，则替换。否，则不变。
最终地，一个 key 所对应的 16384 个桶都设置了很多的 value 了，每个桶有一个k_max。此时调用 pfcount 时，按照调和平均数进行估算，同时加以偏差修正，便可以计算出 key 的设置了多少次 value，也就是统计值，具体的估算公式如下：
value 被转为 64 位的比特串，最终被按照上面的做法记录到每个桶中去。64 位转为十进制就是：2^64，HyperLogLog 仅用了：16384 * 6 /8 / 1024 =12K 存储空间就能统计多达 2^64 个数。同时，在具体的算法实现上，HLL还有一个分阶段偏差修正算法。我们就不做更深入的了解了。