Redis高级数据结构HyperLogLog

HyperLogLog(Hyper[ˈhaɪpə®])并不是一种新的数据结构(实际类型为字符串类型)，而是一种基数算法,通过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 统计需求了。

操作命令

HyperLogLog提供了3个命令: pfadd、pfcount、pfmerge。
例如08-15的访问用户是u1、u2、u3、u4，08-16的访问用户是u-4、u-5、u-6、u-7

pfadd

pfadd key element [element …]
pfadd用于向HyperLogLog 添加元素,如果添加成功返回1:
pfadd 08-15:u:id “u1” “u2” “u3” “u4”

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%的失误率。

pfmerge

pfmerge destkey sourcekey [sourcekey … ]
pfmerge可以求出多个HyperLogLog的并集并赋值给destkey，请自行测试。