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

约定不等于承诺〃 2023-02-17 03:12 113阅读 0赞

# 十: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]

> 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][redis_pfmerge]

[神奇的HyperLogLog算法][HyperLogLog 1]

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

[HyperLogLog]: http://content.research.neustar.biz/blog/hll.html
[redis_pfmerge]: https://redis.io/commands/pfmerge
[HyperLogLog 1]: http://www.rainybowe.com/blog/2017/07/13/%E7%A5%9E%E5%A5%87%E7%9A%84HyperLogLog%E7%AE%97%E6%B3%95/index.html?utm_source=tuicool&utm_medium=referral
[redis_set]: https://blog.csdn.net/u013565163/article/details/105586138