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的相关源码。