Redis(开发与运维):23---常用功能之（HyperLogLog）

一、HyperLogLog概述

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

备注

• HyperLogLog的算法是由Philippe Flajolet（https://en.wikipedia.org/wiki/Philippe_Flajolet）在The analysis of a near-optimal cardinality estimation algorithm这篇论文中提出，读者如果有兴趣可以自行阅读

二、添加（pfadd）

pfadd key element [element …]

• pfadd用于向HyperLogLog添加元素，如果添加成功返回1
• 例如：下面向一个名为2016_06_06:unique:ids的hyperloglog中添加4个元素

 

三、计算独立用户数（pfcount）

pfcount key [key …]

• pfcount用于计算一个或多个HyperLogLog的独立总数
• 例如：接着上面的演示案例，2016_03_06:unique:ids的独立总数为4：

 

内存节省效果演示案例

• ①插入前使用info memory查看一下内存占用率

 

• ②下面建立一个名为test.sh的脚本，执行该脚本，向key为2016_05_01:unique:ids的HyperLogLog中插入100万个元素（循环每次插入1000条）

elements=""
key="2016_05_01:unique:ids"
for i in `seq 1 1000000`
do
    elements="${elements} uuid-"${i}
    if [[ $((i%1000)) == 0 ]];
    then
        redis-cli pfadd ${key} ${elements}
        elements=""
    fi
done

 

• ③执行完脚本之后，再次查看内存，发现内存只增加了14K左右

• ④但是，使用pfcount查看结果，发现执行的结果并不止100万个

• ⑤现在改为使用集合类型进行测试，那么可以看到内存使用率在脚本执行完之后涨到了几十MB，但是独立用户数为100万

elements=""
key="2016_05_01:unique:ids:set"
for i in `seq 1 1000000`
do
    elements="${elements} "${i}
    if [[ $((i%1000)) == 0 ]];
    then
        redis-cli sadd ${key} ${elements}
        elements=""
    fi
done

• 下图列出了使用集合类型和HperLogLog统计百万级用户的占用空间对比：

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

四、合并（pfmerge）

pfmerge destkey sourcekey [sourcekey ...]

• pfmerge可以求出多个HyperLogLog的并集并赋值给destkey
• 例如：要计算 2016年3月5日和3月6日的访问独立用户数，可以按照如下方式来执行，可以看到最终独立用户数是7：

五、HyperLogLog优缺点与使用建议

• HyperLogLog内存占用量非常小，但是存在错误率
• 开发者在进行数据结构选型时只需要确认如下两条即可：
  • 只为了计算独立总数，不需要获取单条数据
  • 可以容忍一定误差率，毕竟HyperLogLog在内存的占用量上有很大的优 势