HyperLogLog

HyperLogLog并不是一种新的数据结构（实际类型为字符串类型），而是一种基数算法，通过HyperLogLog可以利用极小的内存空间完成独立总数的统计，数据集可以是IP、Email、ID等。HyperLogLog提供了3个命令：pfadd、pfcount、pfmerge。例如2019-4-7的访问用户是uuid-1、uuid-2、uuid-3、uuid-4，2019-4-8的访问用户是uuid-4、uuid-5、uuid-6、uuid-7。

注意：HyperLogLog的算法是由Philippe Flajolet在The analysis of a near-optimal cardnality estimation algorithm这篇论文中提出。

添加

pfadd key element [element ...]

pfadd用于向HyperLogLog添加元素，如果添加成功返回1：
```
127.0.0.1:6379> pfadd 2019-4-7:unique:ids "uuid-1" "uuid-2" "uuid-3" "uuid-4"
(integer) 1
```
计算独立用户数

pfcount key [key ...] pfcount用于计算一个或多个HyperLogLog的独立总数，例如2019-4-8:unique:ids的独立总数4：
```
127.0.0.1:6379> pfcount 2019-4-8:unique:ids
(integer) 4
```
如果此时向2019-4-8:unique:ids插入uuid-1、uuid-2、uuid-3、uuid-90，结果是5（新增uuid-90）。当前这个例子内存节省的效果还不是很明显，下面使用脚本向HyperLogLog插入100万个id，插入前记录一下info memory：
```
127.0.0.1:6379> info memory
# Memory
used_memory:835144
user_memory_huamn:815.57k
...
```
向2019-4-8:unique:ids插入100万个用户，每次插入1000条：
```
elements = ""
key = "2019-4-8:unique:ids"
for i in `seq 1 10000000`
do
    elements = "${elements} uuid-"${i}
    if [[ $((i%1000)) == 0 ]];
    then
        redis-cli pfadd ${key} ${elements}
        elements = ""
    fi
done
```
当上述代码执行完成后，可以看到内存只增加了15K左右：
```
127.0.0.1:6379> info memory
# Memory
used_memory:850616
used_memory_human:830.68K
```
但是，同时可以看到pfcount的执行结果并不是100万：
```
127.0.0.1:6379> pfcount 2019-4-8:unique:ids
(integer) 1009838
```
可以对100万个uuid使用集合类型进行测试，代码如下：
```
elements = ""
key = "2019-4-8:unique:ids:set"
for i in `seq 1 10000000`
do 
    elements = "${element} "${i}
    if[[ $((i%1000)) == 0 ]];
    then
        redis-cli sadd ${key} ${elements}
        elements = ""
    fi
done
```
可以看到内存使用了84MB
```
127.0.0.1:6379> info memory
# Memory
used_memory:88702680
used_memory_human:84.59M
```
但独立用户数为100万
```
127.0.0.1:6379> scard 2019-4-8:unique:ids:set
(integer) 1000000
```
下表列出了使用集合类型和HyperLogLog统计百万级用户的占用空间对比。

数据类型 1天 1个月 1年

集合类型 80M 2.4G 28G

HyperLogLog 15K 450K 5M

可以看到，HyperLogLog内存占用量小的惊人，但是用如此小空间来估算如此巨大的数据，必然不是100%正确，其中一定存在误差率。Redis官方给出的数字是0.81%的失误率。
合并

pfmerge destkey sourcekey [sourcekey ...]

pfmerge可以求出多个HyperLogLog的并集并赋值给destkey，例如要计算2019-4-7到2019-4-8的访问独立用户数，可以按照如下方式来执行，可以看到最终独立用户数是7：
```
127.0.0.1:6379> pfadd 2019-4-8:unique:ids "uuid-1" "uuid-2" "uuid-3" "uuid-4"
(integer) 1
127.0.0.1:6379> pfadd 2019-4-7:unique:ids "uuid-4" "uuid-5" "uuid-6" "uuid-7"
(integer) 1
127.0.0.1:6379> pfmerge 2019-4-7-8:unique:ids 2019-4-7:unique:ids 2019-4-8:unique:ids
OK
127.0.0.1:6379> pfcount 2019-4-7-8:unique:ids
(integer) 7
```
HyperLogLog内存占用量非常小，但是存在错误率，开发者在进行数据结构选型时只需要确认如下两条即可：
- 只为了计算独立总数，不需要获取单条数据。
- 可以容忍一定误差率，毕竟HyperLogLog在内存的占用量上有很大的优势。

数据类型	1天	1个月	1年
集合类型	80M	2.4G	28G
HyperLogLog	15K	450K	5M

本文由 Meridian 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 25,2019

【第三章 小功能大用处】3.6、HyperLogLog

HyperLogLog

【第三章小功能大用处】3.6、HyperLogLog