Redis与HyperLogLog
今天,我有幸拜读了老钱的《Redis深度历险:核心原理与应用实践》,小册里面有一篇关于HyperLogLog的文章,其中算法部分对本菜鸟来说还是有些晦涩难懂。因而,我写下这篇博客,一是为了将我对Redis与HyperLogLog的了解记录下来;二是为了以更白话的方式来形容Redis与HyperLogLog之间的关系,让小白都能读懂。
一、Redis与HyperLogLog
Redis是什么我就不再详述了,不知道的人可自行谷歌(baidu)。而HyperLogLog则是一种算法,它提供了不准确的去重计数方案。
举个栗子:如果我要统计网页的UV(浏览客户数量,一天内同一个客户屡次访问只能算一次),传统的处理方案是使用Set来保存客户id,而后统计Set中的元素数量来获取页面UV。但这种方案只能承载一些客户,一旦客户数量大起来就需要消耗大量的空间来存储客户id。我的目的是统计客户数量而不是保存客户,这简直是个费劲不讨好的方案!而使用Redis的HyperLogLog最多需要12k即可以统计大量的客户数,虽然它大概有0.81%的错误率,但对于统计UV这种不需要很准确的数据是可以忽略不计的。
那么,为什么HyperLogLog可以在不保存数据的情况下进行去重计数呢?让我们拭目以待!
二、HyperLogLog算法
在真正详情HyperLogLog算法之前,我们来回顾一个简单的概率论知识:
抛一个硬币,抛一次为反面的概率是1/2,抛两次都为反面的概率是1/4,抛三次都为反面的概率是1/8……依次类推,连续抛k次都是反面的概率1为2^(-k)。 因而,从概率论上来说,如果每一轮抛硬币的结果都不一样,我们最多尝试2^k轮就能抛出连续反面的情况。
HyperLogLog算法也是基于上面这个概率论知识,他认为:给定一系列的随机整数,我们可以通过这些随机整数的低位连续零位的最大长度 k,估算出随机数的数量,估算的公式为:n=2^k(n为随机数数量)。
接下来我们用代码来验证这个结论:
public class HyperLogLog { /* 低位连续0的最大数量 */ private int maxZero; /* 随机数数量 */ private int count; public HyperLogLog(int count){ this.count = count; } private void lowZero(long value){ int i = 1; for ( ; i<32; i++){ /* 假如一个数右移i位后再左移i位还是保持值不变,那么它的低i位都是0 */ if (value >> i << i != value){ break; } } /* 由于i是从1开始的,所以要减1 */ i = i - 1; if (this.maxZero < i){ this.maxZero = i; } } public void random(){ for (int i=0; i<this.count; i++){ long m = ThreadLocalRandom.current().nextLong(1L << 32); lowZero(m); } } public int getMaxZero(){ return this.maxZero; } public static void main(String[] args) { for (int i=10000; i<=100000; i+=10000){ HyperLogLog hll = new HyperLogLog(i); hll.random(); System.out.printf("期待连续0的个数为:%.0f,统计连续0的个数为:%d" , Math.log(i)/Math.log(2), hll.getMaxZero()); System.out.println(); } }}
输出结果为:
期待连续0的个数为:13,统计连续0的个数为:14期待连续0的个数为:14,统计连续0的个数为:15期待连续0的个数为:15,统计连续0的个数为:15期待连续0的个数为:15,统计连续0的个数为:16期待连续0的个数为:16,统计连续0的个数为:14期待连续0的个数为:16,统计连续0的个数为:15期待连续0的个数为:16,统计连续0的个数为:16期待连续0的个数为:16,统计连续0的个数为:16期待连续0的个数为:16,统计连续0的个数为:14期待连续0的个数为:17,统计连续0的个数为:17
由输出结果可以看出,随机数数量n大概介于2(k-1)到2(k+1)之间。
三、优化HyperLogLog算法
上述HyperLogLog算法误差还是比较大,个别案例统计与期待低位连续0个数相差了2。为了减少特例带来的影响,数学家们给这个算法引入了调和平均的概念。
所谓调和平均,其实就是倒数的平均:
普通平均:avg=(1+2+3+4)/4
调和平均:avg=4/(1/1+1/2+1/3+1/4)
为什么调和平均能降低特例带来的误差呢?我们举个栗子来说明:
如果小猿月薪1000大洋,他老板月薪10000大洋,假如按传统的方法来算平均工资,平均月薪=(1000+10000)/2=5500,这对小猿来说会很不公,“为什么我会这么严重地拉低平均工资? 不行,我要回农村”,小猿如是想。
假如用调和平均来算,平均月薪=2/(1/1000+1/10000)=1818.18,小猿会觉得他也没拉低平均工资多少,努力一把就上去了,这样他会继续留在城里打拼,走上人生巅峰,迎娶白富美。
从上述例子可以看出:调和平均算法总是偏向低的一方。这对HyperLogLog算法是很有帮助的:如果我只尝试了两个不同的数,它们的二进制分别为“00010”和“10000”,用普通求平均数算法估算出我们出尝试了2^4 =16个不同的数,但用调和平均算法估算出我们尝试了2^(2/(1/1+1/4)) =2^1.6=3个不同的数,因而使用调和平均的算法更贴近实际值。
为了使用调和平均,Redis引入了桶的概念,上述算法可以演变成以下公式:假设不同随机数数量为n,桶树为k,第i个桶的低位连续0最大个数为z[i],则
废话不多说,码上见分晓:
class Experiment{ /* 桶数 */ private int bucketCount; /* 随机值数量 */ private int valueCount; private Bucket[] buckets; public Experiment(int bucketCount, int valueCount){ this.bucketCount = bucketCount; this.valueCount = valueCount; this.buckets = new Bucket[bucketCount]; for (int i=0; i<bucketCount; i++){ buckets[i] = new Bucket(32); } } /** * 将valueCount个随机值散列到各个桶中 */ public void work() { for (int i = 0; i < this.valueCount; i++) { long m = ThreadLocalRandom.current().nextLong(1L << 32); Bucket bucket = buckets[(int) (((m & 0xfff0000) >> 16) % bucketCount)]; bucket.lowZero(m); } } /** * 使用调和平均计算低位连续0的最大数量的平均值 * @return */ public double caculate(){ double totalBit = 0.0; for (int i=0; i<bucketCount; i++){ totalBit += 1.0 / (double)this.buckets[i].getMaxZero(); } double averageBit = (double)bucketCount / totalBit; return Math.pow(2, averageBit) * bucketCount; } public static void main(String[] args) { for (int i = 100000; i < 1000000; i += 100000){ Experiment e = new Experiment(1024, i); e.work(); double num = e.caculate(); System.out.printf("实际数量:%d,计算数量:%.2f,错误率:%.2f", i, num, Math.abs(num-i)/i); System.out.println(); } }}/** * 桶 */class Bucket{ private int maxZero; private int bit; public Bucket(int bit){ this.bit = bit; } /** * 计算低位连续0的最大数量 */ public void lowZero(long value){ int i = 1; for (; i<bit; i++){ if (value >> i << i != value){ break; } } maxZero = maxZero>i-1 ? maxZero:i-1; } public int getMaxZero() { return maxZero; }}
输出结果如下:
实际数量:100000,计算数量:92466.71,错误率:0.08实际数量:200000,计算数量:193525.45,错误率:0.03实际数量:300000,计算数量:291640.53,错误率:0.03实际数量:400000,计算数量:383235.77,错误率:0.04实际数量:500000,计算数量:464098.22,错误率:0.07实际数量:600000,计算数量:651661.94,错误率:0.09实际数量:700000,计算数量:694357.90,错误率:0.01实际数量:800000,计算数量:837294.56,错误率:0.05实际数量:900000,计算数量:872591.90,错误率:0.03
错误率比不使用调和平均党的方式低了好多。
四、再谈Redis与HyperLogLog
Redis在去重计算时怎样和HyperLogLog算法联络起来呢?这个问题我(小菜鸟)思考了好久。
当在Redis中增加(pfadd命令)一个计数元素时,这个元素会被散列到某个桶中,它就相当于上述代码中的随机数,最终我们可以通过pfcount命令获取去重之后的随机数个数。
当统计元素很少时,使用12k太白费空间了,Redis针对这个问题做了少量优化。在计数比较小时,Redis使用稀疏矩阵存储,空间占用很小,仅仅在计数慢慢变大后,稀疏矩阵占用空间渐渐超过了阈值时才会一次性转变成稠密矩阵,占用 12k的空间。这就是为什么说Redis最多占用12的内存了。
那么这12k的空间是怎样分配给每个桶的呢?Redis的HyperLogLog实现中用到了2^14 =16384个桶,每个桶占6bit,因而总共占用内存就是2^14*6/8=12k字节。
五、结尾
本文只是浅析了一下Redis底层的HyperLogLog算法,实际上Redis里的HyperLogLog还做了很多优化,感兴趣的小伙伴可以阅读Redis的相关源码。
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » Redis与HyperLogLog