您当前的位置:首页 > 电脑百科 > 数据库 > 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   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
HyperLogLog,可能很多人对Redis这个功能都很陌生,在日常开发中也很少用到它,或者用了它也没有深入的了解过,下面我们将详细介绍。HyperLogLog简称HLL,它是LogLog算法的升级版,其功...【详细内容】
2022-10-26  Tags: Redis  点击:(0)  评论:(0)  加入收藏
下载地址:下载界面:下载好之后进行安装安装界面下一步安装路径的改动默认下一步继续下一步安装点击完成这是我们的安装目录最简单的启动方式是直接双击redis-server.exe如果要...【详细内容】
2022-10-10  Tags: Redis  点击:(15)  评论:(0)  加入收藏
很难大规模操作有状态的分布式系统,Redis 也不例外。托管数据库通过承担大部分繁重工作使生活变得更轻松。但是您仍然需要一个健全的架构并在服务器(Redis)和客户端(应用程序)上...【详细内容】
2022-10-08  Tags: Redis  点击:(11)  评论:(0)  加入收藏
Apache Kafka 已成为大多数技术栈中的主流组件。使用 Kafka 的好处包括确保事件中的因果顺序,同时保持并行性,通过在服务器之间快速复制分区来恢复故障,等等。 然而,运行 Kafka...【详细内容】
2022-10-04  Tags: Redis  点击:(23)  评论:(0)  加入收藏
一、背景公司基于业务发展以及战略部署,需要实现在多个数据中心单元化部署,一方面可以实现多数据中心容灾,另外可以提升用户请求访问速度。需要保证多数据中心容灾或者实现用户...【详细内容】
2022-09-28  Tags: Redis  点击:(39)  评论:(0)  加入收藏
一、RedisInsight 简介RedisInsight 是一个高颜值,直观高效的 Redis GUI 管理工具,它可以对 Redis 的内存、连接数、命中率以及正常运行时间进行监控,并且可以在界面上使用 CL...【详细内容】
2022-09-18  Tags: Redis  点击:(97)  评论:(0)  加入收藏
一、Redis为什么那么快 QPS达到10万/秒 用C语言实现 基于内存 单线程,不用线程上下文切换及加锁二、redis数据类型 String,常见的缓存,存储登录session等 hash,存储对象,单独修...【详细内容】
2022-09-16  Tags: Redis  点击:(67)  评论:(0)  加入收藏
1、集群原理简介1.1、什么是集群?什么是分区?集群简单的说就是将同一个服务部署在不同的机器上,从而提高服务的横向扩展能力。分区就是将数据分布在多个实例(服务器)上,让每一个实...【详细内容】
2022-09-15  Tags: Redis  点击:(46)  评论:(0)  加入收藏
Redis 的持久化方式有两种:AOF 日志和 RDB 快照。所以接下来,针对这两种持久化方式具体分析分析...【详细内容】
2022-09-14  Tags: Redis  点击:(45)  评论:(0)  加入收藏
前言在开发中遇到一个业务诉求,需要在千万量级的底池数据中筛选出不超过 10W 的数据,并根据配置的权重规则进行排序、打散(如同一个类目下的商品数据不能连续出现 3 次)。下面对...【详细内容】
2022-09-08  Tags: Redis  点击:(25)  评论:(0)  加入收藏
▌简易百科推荐
HyperLogLog,可能很多人对Redis这个功能都很陌生,在日常开发中也很少用到它,或者用了它也没有深入的了解过,下面我们将详细介绍。HyperLogLog简称HLL,它是LogLog算法的升级版,其功...【详细内容】
2022-10-26  搬长你好  今日头条  Tags:Redis   点击:(0)  评论:(0)  加入收藏
下载地址:下载界面:下载好之后进行安装安装界面下一步安装路径的改动默认下一步继续下一步安装点击完成这是我们的安装目录最简单的启动方式是直接双击redis-server.exe如果要...【详细内容】
2022-10-10  分享电脑学习  搜狐号  Tags:Redis   点击:(15)  评论:(0)  加入收藏
很难大规模操作有状态的分布式系统,Redis 也不例外。托管数据库通过承担大部分繁重工作使生活变得更轻松。但是您仍然需要一个健全的架构并在服务器(Redis)和客户端(应用程序)上...【详细内容】
2022-10-08  qaseven  网易号  Tags:Redis   点击:(11)  评论:(0)  加入收藏
Apache Kafka 已成为大多数技术栈中的主流组件。使用 Kafka 的好处包括确保事件中的因果顺序,同时保持并行性,通过在服务器之间快速复制分区来恢复故障,等等。 然而,运行 Kafka...【详细内容】
2022-10-04  解道Jdon  今日头条  Tags:Redis   点击:(23)  评论:(0)  加入收藏
一、背景公司基于业务发展以及战略部署,需要实现在多个数据中心单元化部署,一方面可以实现多数据中心容灾,另外可以提升用户请求访问速度。需要保证多数据中心容灾或者实现用户...【详细内容】
2022-09-28  京东云    Tags:Redis   点击:(39)  评论:(0)  加入收藏
一、RedisInsight 简介RedisInsight 是一个高颜值,直观高效的 Redis GUI 管理工具,它可以对 Redis 的内存、连接数、命中率以及正常运行时间进行监控,并且可以在界面上使用 CL...【详细内容】
2022-09-18  Python部落  今日头条  Tags:Redis   点击:(97)  评论:(0)  加入收藏
一、Redis为什么那么快 QPS达到10万/秒 用C语言实现 基于内存 单线程,不用线程上下文切换及加锁二、redis数据类型 String,常见的缓存,存储登录session等 hash,存储对象,单独修...【详细内容】
2022-09-16  互联网资讯看板  网易号  Tags:Redis   点击:(67)  评论:(0)  加入收藏
1、集群原理简介1.1、什么是集群?什么是分区?集群简单的说就是将同一个服务部署在不同的机器上,从而提高服务的横向扩展能力。分区就是将数据分布在多个实例(服务器)上,让每一个实...【详细内容】
2022-09-15  互联共商   网易号  Tags:Redis集群   点击:(46)  评论:(0)  加入收藏
Redis 的持久化方式有两种:AOF 日志和 RDB 快照。所以接下来,针对这两种持久化方式具体分析分析...【详细内容】
2022-09-14  IT互联网新资讯  今日头条  Tags:Redis   点击:(45)  评论:(0)  加入收藏
redisson相比原生的jredis具有排队的功能,不一致秒杀时,一时获取锁失败就返回失败。秒杀的原理就是使用redis的分布式锁的功能,保证每次抢购不会出现超卖的情况 1 引入pom...【详细内容】
2022-09-01  留住此刻  今日头条  Tags:redisson   点击:(63)  评论:(0)  加入收藏
站内最新
站内热门
站内头条