redis“冷门”知识点：HyperLogLog

前言

前几天，我司大牛分享redis知识点，讲到redis数据结构的时候，抛出一个问题：如果要统计网站uv，你准备怎么实现？

和大多数普通开发人员一样，想到的第一个想法是存到set集合里。可是这样真的好吗？

后来找到了更好的方式，redis“冷门”数据结构:HyperLogLog。（说是“冷门”，可能只是我不知道罢了:D）

问题回顾

你准备如何实现统计大型网站的网页UV数据？

uv数据不像pv数据，pv可能只需要在redis中使用一个计数器，每次访问incrby一次即可。uv数据需要根据用户id来标识唯一来统计，集合中的数据需要去重，那么set是一个最容易想到的数据结构。现在的问题是，大型网站，可能这是一个爆款商品的秒杀页面，用户访问量非常大，假如有上千万的uv估计，那么占用的空间就非常大，而我仅仅只是想要一个set的size，岂不是杀鸡用了宰牛刀了？而且，uv数据一定要精确吗？uv数据存在一些误差可不可以？有没有更好的解决方案？

uv数据当然可以存在误差，更好的解决方案当然有。那就是redis的HyperLogLog。

HyperLogLog

本文主角HyperLogLog，redis的一种数据结构，可能不被大多数人知道，但却是非常有用的数据。

HyperLogLog是什么

Redis 在 2.8.9 版本添加了HyperLogLog结构。

Redis HyperLogLog 是用来做基数统计的算法，HyperLogLog的优点是，在输入元素的数量或者体积非常非常大时，计算基数所需的空间总是固定的、并且是很小的。

但是，因为HyperLogLog只会根据输入元素来计算基数，而不会储存输入元素本身，所以HyperLogLog 不能像集合那样，返回输入的各个元素。

可见，专业的人做专业的事，HyperLogLog在做基数统计方面是一流的。

HyperLogLog怎么玩

`HyperLogLog`的三个指令:

命令	描述
PFADD key element [element …]	添加指定元素到 HyperLogLog 中。
PFCOUNT key [key …]	返回给定 HyperLogLog 的基数估算值。
PFMERGE destkey sourcekey [sourcekey …]	将多个 HyperLogLog 合并为一个 HyperLogLog

小试牛刀

以计算uv为例，假如统计网站首页uv人数，路径/index，我们使用pfadd增加计数，pfcount统计人数。使用方式类似于set集合的sadd和scard。

127.0.0.1:6379[1]> pfadd /index user_1
(integer) 1
127.0.0.1:6379[1]> pfadd /index user_2
(integer) 1
127.0.0.1:6379[1]> pfcount /index
(integer) 2
127.0.0.1:6379[1]> pfadd /index user_3
(integer) 1
127.0.0.1:6379[1]> pfcount /index
(integer) 3
127.0.0.1:6379[1]> pfadd /index user_4
(integer) 1
127.0.0.1:6379[1]> pfcount /index
(integer) 4
127.0.0.1:6379[1]> pfadd /index user_1
(integer) 0
127.0.0.1:6379[1]> pfcount /index
(integer) 4
127.0.0.1:6379[1]> pfadd /index user_5 user_6 user_7
(integer) 1
127.0.0.1:6379[1]> pfcount /index
(integer) 7

目前看数值都是正确的，我们用程序加大user数据看看精确度怎么样。

此处用Python实现吧，你懂的，毕竟人生苦短。

# coding: utf-8

import redis

def start_test():
    r = redis.Redis(host='localhost', port=6379, decode_responses=True)
    client = redis.StrictRedis()
    for i in range(100000):
        client.pfadd("/index", "user%d" % i)
    print("用户真实人数:", 100000, ",统计uv数:" , client.pfcount("/index"))


if __name__ == '__main__':
    start_test();

输出结果:

用户真实人数: 100000 ,统计uv数: 99723

可见正确率有99.723%，误差可以接受的范围

HyperLogLog的底层原理

建议阅读文章：神奇的HyperLogLog算法

其底层的实现原理还是比较复杂，感兴趣的童鞋可以多多了解。

结论

在统计不是很要求精确的统计计数时，可以考虑使用redis的HyperLogLog数据结构。它的占用内存非常小，每个 HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基数。当数值非常大时，它的优势就越发明显。

前言