您当前的位置:首页 > 电脑百科 > 数据库 > Redis

Redis之HyperLogLog(基数统计)

时间:2022-10-26 13:32:52  来源:今日头条  作者:搬长你好

HyperLogLog,可能很多人对redis这个功能都很陌生,在日常开发中也很少用到它,或者用了它也没有深入的了解过,下面我们将详细介绍。HyperLogLog简称HLL,它是LogLog算法的升级版,其功能是能够为大数据场景提供“不精确”的去重计数。

该算法具有以下特性:

  • 算法实现复杂,理解难度大
  • 计数存在一定的误差,Redis官方公布的误差率在0.81%左右
  • 通过设置辅助计算因子能够降低误差,辅助因子要根据不同的场景设置
  • 能够使用极少的内存来统计巨量的数据,Redis的实现中统计2^64个数据最大占用空间为16384*6/8/1024 = 12K

HLL算法原理

伯努利试验

要理解该算法,首先要从伯努利试验开始,伯努利试验的基本含义:

伯努利试验(Bernoulli trial,或译为白努利试验)是只有两种可能结果(“成功”或“失败”)的单次随机试验。

抛硬币就是一个典型的场景,硬币拥有正反两面,一次地上抛至落下,最终出现正反面的概率都是50%。假设一直抛一枚硬币直到出现正面为止,只要第一次出现正面我们就记录为一次试验。如果经过n伯努利试验(即出现了n次正面),假设每次试验的投掷次数为k,第一次试验的投掷次数为k1,类推得出第n次试验的投掷次数为kn,那么这 k1 ~ kn 中必然会有一个最大的抛掷次数,我们记为k_max

由此试验我们可以得到两个结论:

  • n次伯努利试验的投掷次数都不大于k_max
  • n次伯努利试验的投掷次数至少有一次等于k_max。

结合极大似然估算的方法,发现n与k_max存在估算关联:n=2^kmax,套用这个公式会发现,当实验次数较小时该算法的误差会非常大,我们来举一个简单的例子:

第1次实验:抛掷1次出现正面,则k=1,n=1

第2次实验:抛掷3次出现正面,则k=3,n=2

第3次实验:抛掷5次出现正面,则k=5,n=3

第n次实验:抛掷k次出现正面,则n=2^k

假设n组实验中k_max=5,最终的实验结果估算n=2^5,如果n很小时,等式很明显不成立

如何减小估算误差呢?通常的做法是增加实验次数,但是只做一轮的话误差率仍然不够小。那如果我们做多个轮次然后求平均呢?

LogLog

上述多轮次求平均的算法就是LogLog算法的实现了。

HyerLogLog

HyperLogLog算法在LogLog的基础上做了进一步的优化,为了解决k_max的出现个别大数值导致平均值波动过大的影响,HLL算法将k_max平均替换为调和平均值,具体计算方式变更为:k_max调和平均=m/(1/k_max1 + 1/k_max2 + ... + 1/k_maxn)。

HLL公式

一个可视化的HLL算法演示地址:
http://content.research.neustar.biz/blog/hll.html

Redis中的实现

上面的内容我们对伯努利试验到HLL算法的演化过程做了一个简单的推演,那么这种算法如何落地实现呢?如何用更少的内存,更加高性能的方式实现呢?

下面我们来看一个实际的场景:

拼刀刀有一个活动页面,我们需要统计每天该活动页的UV(一个用户的多次点击只算一次)。

我们结合上面的HLL算法很容易得出:

  • 活动页的UV = 预测结果n;
  • 某个用户点击活动页 = 一次试验,m个用户点击就是,m轮次;
  • 输入条件是用户id,那么我们可以使用用户id计得出试验轮次序号与每个轮次的k_max;

用户id如何得到轮次m与每个轮次的k_max呢?我们可以把用户id 通过hash函数计算得到一个bit串,可以使用bit串的低n位来表示实验轮次,用剩下的bit位表示每个轮次的k_max。如图:

用户id计算得到的bit串结构

在Redis中采用MurmurHash64A函数计算出64位的bit串来计算轮次序号每个轮次的k_max,其中低14位用于计算轮次序号,高50位用于计算轮次的k_max。Redis实现采用了16384轮次(刚好2^14+1次,加1是因为有0),高50位从低位到高位最先出现1的索引位置位为k_max,那么最极端的情况就是第50位出现1,50使用二进制存储最大需要6个二进制位,因此Redis每个轮次的k_max采用了6个bit位存储。因此得到了Redis统计2^64个数使用的空间是:16384*6/8/1024=12k。

说明:如果出现桶冲突,即低14位相同时,高50位保留k_max最大的。

数据结构

下面我们看一下HLL在Redis中的实际存储结构,如下图:

HLL存储结构

  • Redis的HLL实现有两种编码,一种是稀疏编码,一种是密集编码。
  • 稀疏编码:在HLL初期只存入了少量的数据时,存在大量的空桶,如果这个时候仍然用16384个桶来存储会造成很大的空间浪费,因此会利用压缩空间来存储。
  • 密集编码:当桶的数量达到一定数量时,会进行一次编码转换,转换后会形成一个完整的结构,即16384个桶,每个桶占6bit。

HLL编码

在实际的算法实现中要考虑到空间利用率问题,因此Redis设计了不同的编码来存储不同阶段的统计数据,以此来提升空间利用率,有以下几种编码:

密集编码:

HLL密集编码

密集编码每个桶需要了6bit,那么必然存在跨字节的情况,Redis采用了比较巧妙的方式去定位桶,具体实现如下:

#define HLL_BITS 6 /* Enough to count up to 63 leading zeroes. */
// 二进制为:00111111
#define HLL_REGISTER_MAX ((1<<HLL_BITS)-1)

/* Store the value of the register at position 'regnum' into variable 'target'.
* 'p' is an array of unsigned bytes. */
// 将位置为'regnum'的值存入变量'target','p'是一个无符号字节的数组
// 获取指定桶
#define HLL_DENSE_GET_REGISTER(target,p,regnum) do { 
    uint8_t *_p = (uint8_t*) p; 
	// 计算桶所属哪一个字节
    unsign计算ed long _byte = regnum*HLL_BITS/8; 
	// 计算桶起始bit的所属位置
    unsigned long _fb = regnum*HLL_BITS&7; 
	// 处理跨字节
    unsigned long _fb8 = 8 - _fb; 
	// 获取第一个字节中的位
    unsigned long b0 = _p[_byte]; 
	// 获取第二个字节中的位
    unsigned long b1 = _p[_byte+1]; 
	// 计算跨字节合并后的序列(第一个字节的高_fb位与第二个字节的低_fb8位合并,可结合上面图看)
    target = ((b0 >> _fb) | (b1 << _fb8)) & HLL_REGISTER_MAX; 
} while(0)

/* Set the value of the register at position 'regnum' to 'val'.
* 'p' is an array of unsigned bytes. */
 // 设置指定桶
#define HLL_DENSE_SET_REGISTER(p,regnum,val) do { 
    uint8_t *_p = (uint8_t*) p; 
    unsigned long _byte = regnum*HLL_BITS/8; 
    unsigned long _fb = regnum*HLL_BITS&7; 
    unsigned long _fb8 = 8 - _fb; 
    unsigned long _v = val; 
    // 设置跨字节的第一个字节的低_fb位
    _p[_byte] &= ~(HLL_REGISTER_MAX << _fb); 
    _p[_byte] |= _v << _fb; 
	// 设置跨字节的第二个字节的高_fb8位
    _p[_byte+1] &= ~(HLL_REGISTER_MAX >> _fb8); 
    _p[_byte+1] |= _v >> _fb8; 
} while(0)

稀疏编码:

稀疏编码-XZERO


稀疏编码-ZERO+VAL

  • XZERO编码:操作码由两个字节"01xxxxxx yyyyyyyy"模式表示,其中"xxxxxx yyyyyyyy"表示由1到16384(111111 11111111+1)个连续分组为空, "xxxxxx"为XZERO的高位,"yyyyyyyy"为低位,该编码是HLL的初始结构,大小刚好为两个字节(uint8_t registers[1])。
  • ZERO编码:操作码用一个字节"00xxxxxx"模式表示,6位"xxxxxx"表示有1到64(111111+1)个连续分组为空,此编码可以有效压缩空桶。
  • VAL编码:操作码用一个字节"1xxxxxyy"模式表示,"xxxxx"表示投掷次数,最大次数为32(11111+1),这也是为什么大于32时会发生编码转换的原因,"yy"表示连续(n+1)个分组,此操作码可以表示1到32之间的值, 重复1到4次。

HLL相关命令

PFADD:将一个输入参数存入到HyperLogLog结构中,如果输入引起近似基数变化,该命令返回1,否则返回0。

redis> PFADD hll a b c d e f g

(integer) 1

redis> PFCOUNT hll

(integer) 7

PFCOUNT:返回指定key的近似基数值,支持多个key的查询,当多key查询时,会将多个key的HLL结构合并为一个临时HLL,然后返回这个合并结果的基数值。

redis> PFADD hll foo bar zap

(integer) 1

redis> PFADD hll zap zap zap

(integer) 0

redis> PFADD hll foo bar

(integer) 0

redis> PFCOUNT hll

(integer) 3

redis> PFADD some-other-hll 1 2 3

(integer) 1

redis> PFCOUNT hll some-other-hll

(integer) 6

PFMERGE:将多个HLL结构合并为一个HHL结构。

redis> PFADD hll1 foo bar zap a

(integer) 1

redis> PFADD hll2 a b c foo

(integer) 1

redis> PFMERGE hll3 hll1 hll2

OK

redis> PFCOUNT hll3

(integer) 6

性能对比

为什么要用使用HyperLogLog?举一个例子:"我们统计一下莎士比亚所有作品中不同的单词数"

数据结构

占用字节数

词数

误差率

HashMap

10447016

67801

0%

Bitmap

3384

67080

1%

HyperLogLog

512

70002

3%

可以看出HyperLogLog能够使用更小的空间完成统计,试想如果你统计的是全球每个作者的所有作品中不同的单词数,HyperLogLog的优势就更加突出。但同时其也存在一些统计精度问题。

应用场景

如果是允许一定误差的统计,可以选择HyperLogLog。如果需要较为精确的统计可以使用Bitmap,详见我的另外一篇文章《Redis之Bitmap(位图)》。下面是一些常见的HyperLogLog使用场景:

统计网站不重复用户的访问量(可以用用户id作为输入)。

  • 统计城市交通网中每个红绿灯路口车次

比如我们可以统计经过路口的不同车辆数(可以用车牌作为输入)。

  • 统计大数据集不重复记录数

统计百度每天不同搜索关键词查询的次数。

以上就是Redis HyperLogLog(基数统计)的介绍



Tags:Redis   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
16个Redis常见使用场景总结
来源:blog.csdn.net/qq_39938758/article/details/105577370目录 缓存 数据共享分布式 分布式锁 全局ID 计数器 限流 位统计 购物车 用户消息时间线timeline 消息...【详细内容】
2024-04-11  Search: Redis  点击:(4)  评论:(0)  加入收藏
Linux获取Redis 性能指标方法
一、监控指标&Oslash; 性能指标:Performance&Oslash; 内存指标: Memory&Oslash; 基本活动指标:Basic activity&Oslash; 持久性指标: Persistence&Oslash; 错误指标:Error二、监...【详细内容】
2024-04-11  Search: Redis  点击:(4)  评论:(0)  加入收藏
Redis与缓存一致性问题
缓存一致性问题是在使用缓存系统,如Redis时经常遇到的问题。当数据在原始数据源(如数据库)中发生变化时,如何确保缓存中的数据与数据源保持一致,是开发者需要关注的关键问题。一...【详细内容】
2024-04-11  Search: Redis  点击:(3)  评论:(0)  加入收藏
Redis 不再 “开源”,未来采用 SSPLv1 和 RSALv2 许可证
Redis 官方于21日宣布修改开源协议 &mdash;&mdash; 未来所有版本都将使用 “源代码可用” 的许可证 (source-available licenses)。具体来说,Redis 将不再遵循 BSD 3-Clause...【详细内容】
2024-03-27  Search: Redis  点击:(14)  评论:(0)  加入收藏
Redis“叛逃”开源,得罪了几乎所有人
内存数据库供应商Redis近日在开源界砸下了一块“巨石”。Redis即将转向双许可模式,并实施更为严格的许可条款。官方对此次变更的公告直截了当:从Redis 7.4版本开始,Redis将在Re...【详细内容】
2024-03-25  Search: Redis  点击:(10)  评论:(0)  加入收藏
如何使用 Redis 实现消息队列
Redis不仅是一个强大的内存数据存储系统,它还可以用作一个高效的消息队列。消息队列是应用程序间或应用程序内部进行异步通信的一种方式,它允许数据生产者将消息放入队列中,然...【详细内容】
2024-03-22  Search: Redis  点击:(18)  评论:(0)  加入收藏
Redis不再 “开源”
Redis 官方今日宣布修改开源协议 &mdash;&mdash; 未来所有版本都将使用 “源代码可用” 的许可证 (source-available licenses)。具体来说,Redis 将不再遵循 BSD 3-Clause 开...【详细内容】
2024-03-21  Search: Redis  点击:(11)  评论:(0)  加入收藏
在Redis中如何实现分布式锁的防死锁机制?
在Redis中实现分布式锁是一个常见的需求,可以通过使用Redlock算法来防止死锁。Redlock算法是一种基于多个独立Redis实例的分布式锁实现方案,它通过协调多个Redis实例之间的锁...【详细内容】
2024-02-20  Search: Redis  点击:(49)  评论:(0)  加入收藏
手动撸一个 Redis 分布式锁
大家好呀,我是楼仔。今天第一天开工,收拾心情,又要开始好好学习,好好工作了。对于使用 Java 的小伙伴,其实我们完全不用手动撸一个分布式锁,直接使用 Redisson 就行。但是因为这些...【详细内容】
2024-02-19  Search: Redis  点击:(40)  评论:(0)  加入收藏
工作中Redis有哪些好用的运维工具
工作中使用 Redis 时,如果大家公司没有专业运维,可能开发人员就会面临这些运维的工作,包括 Redis 的运行状态监控,数据迁移,主从集群、切片集群的部署和运维等等。本文我就从这三...【详细内容】
2024-02-06  Search: Redis  点击:(56)  评论:(0)  加入收藏
▌简易百科推荐
16个Redis常见使用场景总结
来源:blog.csdn.net/qq_39938758/article/details/105577370目录 缓存 数据共享分布式 分布式锁 全局ID 计数器 限流 位统计 购物车 用户消息时间线timeline 消息...【详细内容】
2024-04-11    书圈  Tags:Redis   点击:(4)  评论:(0)  加入收藏
Linux获取Redis 性能指标方法
一、监控指标&Oslash; 性能指标:Performance&Oslash; 内存指标: Memory&Oslash; 基本活动指标:Basic activity&Oslash; 持久性指标: Persistence&Oslash; 错误指标:Error二、监...【详细内容】
2024-04-11  上海天正信息科技有限    Tags:Redis   点击:(4)  评论:(0)  加入收藏
Redis与缓存一致性问题
缓存一致性问题是在使用缓存系统,如Redis时经常遇到的问题。当数据在原始数据源(如数据库)中发生变化时,如何确保缓存中的数据与数据源保持一致,是开发者需要关注的关键问题。一...【详细内容】
2024-04-11  后端Q    Tags:Redis   点击:(3)  评论:(0)  加入收藏
Redis 不再 “开源”,未来采用 SSPLv1 和 RSALv2 许可证
Redis 官方于21日宣布修改开源协议 &mdash;&mdash; 未来所有版本都将使用 “源代码可用” 的许可证 (source-available licenses)。具体来说,Redis 将不再遵循 BSD 3-Clause...【详细内容】
2024-03-27  dbaplus社群    Tags:Redis   点击:(14)  评论:(0)  加入收藏
Redis“叛逃”开源,得罪了几乎所有人
内存数据库供应商Redis近日在开源界砸下了一块“巨石”。Redis即将转向双许可模式,并实施更为严格的许可条款。官方对此次变更的公告直截了当:从Redis 7.4版本开始,Redis将在Re...【详细内容】
2024-03-25    51CTO  Tags:Redis   点击:(10)  评论:(0)  加入收藏
如何使用 Redis 实现消息队列
Redis不仅是一个强大的内存数据存储系统,它还可以用作一个高效的消息队列。消息队列是应用程序间或应用程序内部进行异步通信的一种方式,它允许数据生产者将消息放入队列中,然...【详细内容】
2024-03-22  后端Q  微信公众号  Tags:Redis   点击:(18)  评论:(0)  加入收藏
Redis不再 “开源”
Redis 官方今日宣布修改开源协议 &mdash;&mdash; 未来所有版本都将使用 “源代码可用” 的许可证 (source-available licenses)。具体来说,Redis 将不再遵循 BSD 3-Clause 开...【详细内容】
2024-03-21  OSC开源社区    Tags:Redis   点击:(11)  评论:(0)  加入收藏
在Redis中如何实现分布式锁的防死锁机制?
在Redis中实现分布式锁是一个常见的需求,可以通过使用Redlock算法来防止死锁。Redlock算法是一种基于多个独立Redis实例的分布式锁实现方案,它通过协调多个Redis实例之间的锁...【详细内容】
2024-02-20  编程技术汇    Tags:Redis   点击:(49)  评论:(0)  加入收藏
手动撸一个 Redis 分布式锁
大家好呀,我是楼仔。今天第一天开工,收拾心情,又要开始好好学习,好好工作了。对于使用 Java 的小伙伴,其实我们完全不用手动撸一个分布式锁,直接使用 Redisson 就行。但是因为这些...【详细内容】
2024-02-19  楼仔  微信公众号  Tags:Redis   点击:(40)  评论:(0)  加入收藏
工作中Redis有哪些好用的运维工具
工作中使用 Redis 时,如果大家公司没有专业运维,可能开发人员就会面临这些运维的工作,包括 Redis 的运行状态监控,数据迁移,主从集群、切片集群的部署和运维等等。本文我就从这三...【详细内容】
2024-02-06  waynaqua    Tags:Redis   点击:(56)  评论:(0)  加入收藏
站内最新
站内热门
站内头条