十:redis之HyperLogLog的使用与应用场景

HyperLogLog为实现一种基数统计的算法，redis采用HyperLogLog来进行基数统计。
(redis2.8.9及之后的版本有提供这个功能)

基数统计； 通常来统计一个集合中不重复的元素个数。

为什么使用HyperLogLog而不是set或者bitmap

如果我们使用set来进行基数统计，那么假设每一个元素的32Bit(2^24 ≈ 1600万; 2^32 ≈ 42亿)，
假设我们存储1亿个不重复的元素那么我们需要 100 000 000 * 32 /8/1024/1024 ≈ 381MB;

如果我们用bitmap来进行基数统计,每个元素对应一位(bit),假设我们存储1亿个不重复的元素那么我们需要
100 000 000 /8/1024/1024 ≈ 12MB;

然而我们使用HyperLogLog, 一个键占用的内容空间是12KB，并且这个键可以处理海量数据。

那么是不是以后有统计不重复元素的个数这种场景，我们可以直接选择HyperLogLog呢？
仔细想想，有没有十分完美的方案呢？解决一切烦恼呢。现实是天下没有免费的午餐。使用HyperLogLog是需要
忍受误差的，HyperLogLog的结果会有一个0.81%的标准错误。

三者统计不重复元素的场景

• 也就是说HyperLogLog的场景是海量数据，可以忍受0.81%误差的场景。
• 而bitmap是元素连续的(自增的用户主键id)，数据量不大，不能忍受误差。
• set的元素没有规律，数据量不大，不能忍受误差，并且需要返回实际的单个元素。

常见命令

pfadd

• 解释
  HyperLogLog中增加元素，当键不存在则创建键；
  重复的元素只添加一次。
  当返回1，表示HyperLogLog的内部结构被改变了，本次有
  元素插入;如果返回0表示本次没有元素插入。

• 用法 pfadd key element [element]

• 示例

127.0.0.1:6379> pfadd key1 1 2 3
(integer) 1
127.0.0.1:6379> pfadd key1 2 3
(integer) 0
127.0.0.1:6379> pfadd key1 4
(integer) 1

pfcount

• 解释
  当传参一个键的时候，返回这个键的近似基数（个数）;
  当传参多个键的时间，返回这个键的并集的近似基数（其中不重复元素的总和）；
  当返回0，表示键不存在

• 用法 pfcount key [key]

• 示例

127.0.0.1:6379> pfadd key1 1 2 3
(integer) 1
127.0.0.1:6379> pfadd key1 2 3
(integer) 0
127.0.0.1:6379> pfadd key1 4
(integer) 1
127.0.0.1:6379> pfcount key1 
(integer) 4
127.0.0.1:6379> pfcount key2 
(integer) 0

pfmerge

• 解释
  合并多个键，生成一个新的键;
  如果合并的目标键已经存在，
  则合并源的结果会合并到目标键中。

• 用法 pfmerge destkey sourcekey [sourcekey]

• 示例

127.0.0.1:6379> pfadd key1  1 2 3
(integer) 1
127.0.0.1:6379> pfadd key2 3 4 5 
(integer) 1
127.0.0.1:6379> pfmerge key3 key1  key2
ok
127.0.0.1:6379> pfcount key3
(integer) 5
127.0.0.1:6379> pfmerge key2 key1 
ok
127.0.0.1:6379> pfcount key2
(integer) 5

应用场景

• 统计某个网站的的UV
• 爬虫判断网页是否已经爬过了
• 统计网站的日活、月活

HyperLogLog的算法是怎么实现的呢

HyperLogLog的在线演示

HyperLogLog的算法的核心思想是通过局部信息预估整体数据流特性。

以抛硬币例子来说，每次出现正反的概率是相等的， 现在我们抛N次硬币，
每一次直到正面出现，则停止这一次的抛硬币，记录下这次出现正面的抛掷次数k，
将这种抛硬币多次直到出现正面的过程记为一次伯努利过程，当我们及进行了N次
伯努利过程，我们会得到N个出现正面的投掷次数k1,k2,…kn,其中最大的K值记为
k_{max}kmax ,因此可以到的下面的结论：

1. n次伯努利过程的投掷次数都不大于Kmax
2. n次伯努利过程，至少有一次投掷次数等于Kmax
   ​​
   ​推导出公式为(详细参考本文下方给出的参考链接):进行了n次进行抛硬币实验，每次分别记录下第一次抛到正面的抛掷次数k，那么可以用n次实验中最大的抛掷次数Kmax来预估试验组的数量N：^N= 2^Kmax

为了减少单组kmax推导的基数（不同的元素个数）误差，HyperLogLog使用分桶数组来削减因偶然带来的误差。

参考

redis官方文档pfmerge

神奇的HyperLogLog算法

七redis的set数据类型常见命令、内部编码、场景