网站文章优化技巧,中国建设银行官网站预约纪念币,网络域名综合查询,怎么做网站卡盟一#xff0c;前言
在互联网行业中存在两个比较重要的指标#xff1a;PV#xff08;页面访问量#xff09;和 UV#xff08;用户访问量#xff09;
如果有这样的一个业务#xff1a;
统计PV#xff0c;那么你会怎么做#xff1f; 我们可以使用Redis的incr、incrby指…一前言
在互联网行业中存在两个比较重要的指标PV页面访问量和 UV用户访问量
如果有这样的一个业务
统计PV那么你会怎么做 我们可以使用Redis的incr、incrby指令给每个网页配置一个独立Redis计数器就可以了把这个技术区的key后缀加上当它的日期这样一个请求过来就可以通过执行incr、incrby指令统计所有PV。
那么统计UV又该怎么做呢
UV和PV不同UV需要对同一用户的访问进行去重此时很快就能想到使用Redis中的set来存储但是会面临以下问题
对于数据量越来越大存储数据的空间占用越来越大统计的性能比较慢虽然可以通过异步方式统计但是性能并不理想
因此引入了Redis的新数据类型HyperLogLog。 二Hyperloglog简介
HyperLogLog 是一种概率数据结构用于在恒定的内存大小下估计集合的基数不同元素的个数。它不是一个独立的数据类型而是一种特殊的 string 类型它可以使用极小的空间来统计一个集合中不同元素的数量也就是基数。在Redis中每个HyperLogLog键只需要花费12KB内存就可以计算接近2^64个不同的基数。为什么是12KB呢下面会详细讲解
hyperloglog 类型的底层实现是 SDSsimple dynamic string它和 string 类型相同只是在操作时会使用一种概率算法来计算基数。hyperloglog 的误差率为 0.81%也就是说如果真实基数为 1000那么 hyperloglog 计算出来的基数可能在 981 到 1019 之间
三Redis中Hyperloglog的使用 PFADD key element [element …] 将任意数量的元素添加到指定的 HyperLogLog 里面当PFADD key element [element …]指令执行时如果HyperLogLog的估计近似基数在命令执行之后出现了变化那么命令返回1否则返回0如果HyperLogLog命令执行时给定的键不存在那么程序将先创建一个空的HyperLogLog结构再执行命令。 该命令可以只给定key不给element这种以方式被调用时
如果给定的键存在且已经是一个HyperLogLog那么这种调用不会产生任何效果 如果给定的键不存在那么命令会创建一个空的HyperLogLog并且给客户端返回1返回值 如果HyperLogLog数据结构内部存储的数据被修改了那么返回1否则返回0
时间复杂度O(1) PFCOUNT key [key …] PFCOUNT 指令后面可以跟多个key当PFCOUNT key [key …]命令作用于单个键时返回存储在给定键的HyperLogLog的近似基数如果键不存在则返回0当PFCOUNT key [key …]命令作用于多个键时返回所给定HyperLogLog的并集的近似基数这个近似基数是通过将索引给定HyperLogLog合并至一个临时HyperLogLog来计算得出的。
返回值返回给定HyperLogLog包含的唯一元素的近似数量的整数值
时间复杂度当命令作用于单个HyperLogLog时时间复杂度为O(1)并且具有非常低的平均常数时间。当命令作用于N个HyperLogLog时时间复杂度为O(N)常数时间会比单个HyperLogLog要大的多。 PFMERGE destkey sourcekey [sourcekey …] 将多个HyperLogLog合并到一个HyperLogLog中合并后HyperLogLog的基数接近于所有输入HyperLogLog的可见集合的并集合并后得到的HyperLogLog会被存储在destkey键里面如果该键不存在那么命令在执行之前会先为该键创建一个空的HyperLogLog。
返回值字符串回复返回OK
时间复杂度O(N)其中N为被合并的HyperLogLog的数量不过这个命令的常数复杂度比较高 四Hyperloglog原理
Hyperloglog基于概率论中的伯努利试验并结合了极大似然估算方法并进行了分桶优化。
1. 伯努利试验
在认识为什么Hyperloglog能够使用极少的内存12K来统计巨量的数据之前先认识一下伯努利试验。 伯努利试验是数学概率论中的一部分内容它的典故来源于抛硬币。 硬币拥有正反两面一次的上抛至落下最终出现正反面的概率都是50%。假设一直抛硬币直到它出现正面为止我们记录为一次完整的试验间中可能抛了一次就出现了正面也可能抛了4次才出现正面。无论抛了多少次只要出现了正面就记录为一次试验。这个试验就是伯努利试验。
那么对于多次的伯努利试验假设这个多次为n次。就意味着出现了n次的正面。假设每次伯努利试验所经历了的抛掷次数为k。第一次伯努利试验次数设为k1以此类推第n次对应的是kn。
其中对于这n次伯努利试验中必然会有一个最大的抛掷次数k例如抛了12次才出现正面那么称这个为k_max代表抛了最多的次数。
伯努利试验容易得出有以下结论
n 次伯努利过程的投掷次数都不大于 k_max。n 次伯努利过程至少有一次投掷次数等于 k_max 上述案例可以看出假设n3此时通过估算关系n2^kmax2^5 ≠3而且偏差很大。因此得出结论这种估算方法误差很大。 2. 估值优化
关于上述估值偏差较大的问题可以采用如下方式结合来缩小误差
增加测试的轮数取平均值。假设三次伯努利试验为1轮测试我们取出这一轮试验中最大的的kmax作为本轮测试的数据同时我们将测试的轮数定位100轮这样我们在100轮实验中将会得到100个kmax此时平均数就是(k_max_1 … k_max_m)/m这里m为试验的轮数此处为100.增加修正因子修正因子是一个不固定的值会根据实际情况来进行值的调整。
上述这种增加试验轮数取Kmax的平均值的方法是loglog算法的实现。因此loglog它的估算公式如下 loglog与Hyperloglog的区别在于loglog采用算数平均数而Hyperloglog采用调和平均数
调和平均数 调和平均数的效果更好例如以下例子
一个小区内有100户现在要统计小区的平均工资小区的工资可以分为大致6000左右10000左右的还有一户100000000以上。
此时使用算数平均会导致结果和现实相差很大。
使用调和平均那户工资上100000000的对整体的影响就几乎可以忽视。 3. Hyperloglog实现原理
图示
Redis中Hyperloglog前14位进行分桶后50位进行获取Kmax 3.1 将数据转化为bit串
通过Hash函数将数据转为64位的比特串例如输入5便转为101。为什么要这样转化呢
是因为要和抛硬币对应上比特串中0 代表了反面1 代表了正面如果一个数据最终被转化了 10010000那么从右往左从低位往高位看我们可以认为首次出现 1 的时候就是正面。
那么基于上面的估算结论我们可以通过多次抛硬币实验的最大抛到正面的次数来预估总共进行了多少次实验同样也就可以根据存入数据中转化后的出现了 1 的最大的位置 Kmax 来估算存入了多少数据。 3.2 分桶
分桶就是分多少轮。在抛硬币中我们可以将三次实验分为一组用这一组的Kmax求平均值当作一次的Kmax这样可以减少误差。
抽象到计算机存储中去就是存储的是一个以单位是比特(bit)长度为 L 的大数组 S 将 S 平均分为 m 组注意这个 m 组就是对应多少轮然后每组所占有的比特个数是平均的设为 P。容易得出下面的关系
L S.lengthL m * p以 K 为单位S 占用的内存 L / 8 / 1024
为什么Hyperloglog大小为12K? 由上图可知
后14位用于分桶也就是需要2^14 16384个桶0~16383也就是14位全0~全1每个桶子需要存储前50位得到的Kmax值起始开始最多连续零个数而50位最多有50个0因此Kmax最大取到502^6 64 50因此每个桶只需要6个bit位就可以保存Kmax每8个bit位为1字节每1024字节为1K
综合以上两点Hyperloglog的大小 16384 * 6 / 8 * 1024 12K 3.3 Hyperloglog估算公式 五Hyperloglog的优缺点
优点内存占用很小只有12K
缺点存在误差概率。不能存储元素本身只能统计集合基数值。 六Hyperloglog适用场景 统计一个 APP 的日活、月活数 统计一个页面的每天被多少个不同账户访问量Unique VisitorUV 统计用户每天搜索不同词条的个数 统计注册 IP 数。 七布隆过滤器布谷鸟过滤器Hyperloglog如何选择
可以设置误判率布隆过滤器
可以进行删除操作布谷鸟过滤器
占用空间小Hyperloglog
