前言

经过上次的教训，这次不写那么多前言了。

什么是基数

一个集合中不同元素的个数

看两个简单的例子
{1，2，3，4，1，2，3}
{apple, banana, peach, app1e, banana}

基数统计应用场景

网站首页的独立访问量
商品的独立访问量
广告的独立受众人数

如何实现

运用第一性原理我们知道最基本的步骤是

存储
比较

业界普遍使用的方案

bitmap

优点：

那是非常简单

缺点：

分配的内存取决于统计最大的数

B树

btree

优点：

插入效率高
查找效率高
空间复杂度不高

缺点：

随着数据量变大存储空间变大
不能高效地合并两棵B树

Redis实现的方案

Set 数据结构

我们知道 redis set 结构本身具备了去重的功能，所以只要把元素
sadd uv 192.168.1.1
(疯狂地sadd…)
scard uv
搞定！

优点：

高效

缺点：

空间随数量增大而增大

所以到底增加多少？已独立IP为例

数量	一天	一月	一年
一百万	15 MB	450 MB	5.4 GB
一千万	150 MB	4.5 GB	54 GB
一亿	1.5 GB	45 GB	540 GB

至此，无论是 bitmap, B树，还是 Redis set 结构

都是精确统计，因为会存储每一个元素
使用空间基本都是跟元素数量成正比

那么，有没有一种可能不需要绝对精确，并且存储空间不随元素成正比的？

HyperLogLog 数据结构

当然有，就是楼上了！

Available since 2.8.9.

关于命名：简单说一下，有一种统计算法叫做 loglog counting，有人在这个基础上改进了，所以叫 Hyperloglog counting

关于原理：我还没看懂，只知道它是一个基于统计原理的基数统计方法，有兴趣可以自行维基，这里只讲 redis 中它的用法

pfadd key element [element …]
命令的复杂度为 O(N) ，N 为被添加元素的数量

pfcount key [key …]
当命令作用于单个 HLL 时，复杂度为 O(1) ，并且具有非常低的平均常数时间
当命令作用于多个 HLL 时，复杂度为 O(N) ，并且常数时间也比处理单个 HLL 时要大得多

pfmerge destkey sourcekey [sourcekey …]
命令的复杂度为 O(N) ，其中 N 为被合并的 HLL 数量，不过这个命令的常数复杂度比较高

优点

即使元素的数量或者体积非常非常大，HLL 所需的空间总是固定的，并且是很小的，在 Redis 里面，每个 HLL 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基数

缺点

由于 HyperLogLog 只会根据输入元素来计算基数，而不会储存输入元素本身，所以 HyperLogLog 不能像 Set 那样，返回输入的各个元素

下面看下用 HLL 统计独立 IP 的数据

数量	一天	一月	一年
一百万	12 KB	360 KB	4.32 MB
一千万	12 KB	360 KB	4.32 MB
一亿	12 KB	360 KB	4.32 MB

总结

空间及时间是计算机领域永远的主题
还是要看业务场景！！！

参考

https://chenjiehua.me/database/hyperloglog-bigdata.html
http://www.cnblogs.com/ysuzhaixuefei/p/4052110.html
http://blog.codinglabs.org/articles/algorithms-for-cardinality-estimation-part-i.html

基于 Redis HyperLogLog 的基数统计

前言