Reids(4)——神奇的HyperLoglog解决统计问题

免费项目 2 周前 0

点击此处查看最新的网赚项目教程

//n   n/log2 maxbit
34000 15.05 13
35000 15.10 13
36000 15.14 16
37000 15.18 17
38000 15.21 14
39000 15.25 16
40000 15.29 14
41000 15.32 16
42000 15.36 18

会发现 K 和 N 的对数之间存在显著的线性相关性：N 约等于 2k

更近一步：分桶平均

如果 N 介于 2k 和 2k+1 之间，用这种方式估计的值都等于 2k，这明显是不合理的，所以我们可以使用多个 BitKeeper 进行加权估计，就可以得到一个比较准确的值了：

public class PfTest {

    static class BitKeeper {
        // 无变化, 代码省略
    }

    static class Experiment {

        private int n;
        private int k;
        private BitKeeper[] keepers;

        public Experiment(int n) {
            this(n, 1024);
        }

        public Experiment(int n, int k) {
            this.n = n;
            this.k = k;
            this.keepers = new BitKeeper[k];
            for (int i = 0; i < k; i++) {
                this.keepers[i] = new BitKeeper();
            }
        }

        public void work() {
            for (int i = 0; i < this.n; i++) {
                long m = ThreadLocalRandom.current().nextLong(1L << 32);
                BitKeeper keeper = keepers[(int) (((m & 0xfff0000) >> 16) % keepers.length)];
                keeper.random();
            }
        }

        public double estimate() {
            double sumbitsInverse = 0.0;
            for (BitKeeper keeper : keepers) {
                sumbitsInverse += 1.0 / (float) keeper.maxbit;
            }
            double avgBits = (float) keepers.length / sumbitsInverse;
            return Math.pow(2, avgBits) * this.k;
        }
    }

    public static void main(String[] args) {
        for (int i = 100000; i < 1000000; i += 100000) {
            Experiment exp = new Experiment(i);
            exp.work();
            double est = exp.estimate();
            System.out.printf("%d %.2f %.2fn", i, est, Math.abs(est - i) / i);
        }
    }
}

这个过程有点类似于选秀节目里面的打分，一堆专业评委打分，但是有一些评委因为自己特别喜欢所以给高了，一些评委又打低了，所以一般都要屏蔽最高分和最低分，然后再计算平均值，这样的出来的分数就差不多是公平公正的了。

计算机源码商城_网站计数器源码,0,0,0,0.0,0,0,0,,-_源代码统计工具

上述代码就有 1024 个 "评委"，并且在计算平均值的时候，采用了调和平均数，也就是倒数的平均值，它能有效地平滑离群值的影响：

avg = (3 + 4 + 5 + 104) / 4 = 29
avg = 4 / (1/3 + 1/4 + 1/5 + 1/104) = 5.044

观察脚本的输出，误差率百分比控制在个位数：

100000 94274.94 0.06
200000 194092.62 0.03
300000 277329.92 0.08
400000 373281.66 0.07
500000 501551.60 0.00
600000 596078.40 0.01
700000 687265.72 0.02
800000 828778.96 0.04
900000 944683.53 0.05

真实的 HyperLogLog 要比上面的示例代码更加复杂一些，也更加精确一些。上面这个算法在随机次数很少的情况下会出现除零错误，因为 maxbit = 0 是不可以求倒数的。

真实的 HyperLogLog

有一个神奇的网站，可以动态地让你观察到 HyperLogLog 的算法到底是怎么执行的：

源代码统计工具_网站计数器源码,0,0,0,0.0,0,0,0,,-_计算机源码商城

其中的一些概念这里稍微解释一下，您就可以自行去点击 step 来观察了：

为什么要统计 Hash 值中第一个 1 出现的位置？

因为第一个 1 出现的位置可以同我们抛硬币的游戏中第一次抛到正面的抛掷次数对应起来，根据上面掷硬币实验的结论，记录每个数据的第一个出现的位置 K，就可以通过其中最大值 Kmax 来推导出数据集合中的基数：N = 2Kmax

PF 的内存占用为什么是 12 KB？

我们上面的算法中使用了 1024 个桶，网站演示也只有 64 个桶，不过在 Redis 的 HyperLogLog 实现中，用的是 16384 个桶，即：214，也就是说，就像上面网站中间那个 Register Values 大表格有 16384 格。

而Redis 最大能够统计的数据量是 264，即每个桶的 maxbit 需要 6 个 bit 来存储，最大可以表示 maxbit = 63，于是总共占用内存就是：(214) x 6 / 8 (每个桶 6 bit，而这么多桶本身要占用 16384 bit，再除以 8 转换成 KB),算出来的结果就是 12 KB。

三、Redis 中的 HyperLogLog 实现

从上面我们算是对 HyperLogLog 的算法和思想有了一定的了解，并且知道了一个 HyperLogLog 实际占用的空间大约是 12 KB，但 Redis 对于内存的优化非常变态，当计数比较小的时候，大多数桶的计数值都是零，这个时候 Redis 就会适当节约空间，转换成另外一种稀疏存储方式，与之相对的，正常的存储模式叫做密集存储，这种方式会恒定地占用 12 KB。

密集型存储结构

密集型的存储结构非常简单，就是 16384 个 6 bit 连续串成的字符串位图：

网站计数器源码,0,0,0,0.0,0,0,0,,-_计算机源码商城_源代码统计工具

我们都知道，一个字节是由 8 个 bit 组成的，这样 6 bit 排列的结构就会导致，有一些桶会跨越字节边界，我们需要对这一个或者两个字节进行适当的移位拼接才可以得到具体的计数值。

假设桶的编号为 index，这个 6 bity 计数值的起始字节偏移用 offset_bytes 表示，它在这个字节的其实比特位置偏移用 offset_bits 表示，于是我们有：

offset_bytes = (index * 6) / 8
offset_bits = (index * 6) % 8

前者是商，后者是余数。比如 bucket 2 的字节偏移是 1，也就是第 2 个字节。它的位偏移是 4，也就是第 2 个字节的第 5 个位开始是 bucket 2 的计数值。需要注意的是字节位序是左边低位右边高位，而通常我们使用的字节都是左边高位右边低位。

这里就涉及到两种情况，如果 offset_bits 小于等于 2，说明这 6 bit 在一个字节的内部，可以直接使用下面的表达式得到计数值 val：

val = buffer[offset_bytes] >> offset_bits  # 向右移位

如果 offset_bits 大于 2，那么就会涉及到跨越字节边界，我们需要拼接两个字节的位片段：

# 低位值
low_val = buffer[offset_bytes] >> offset_bits
# 低位个数
low_bits = 8 - offset_bits
# 拼接，保留低6位
val = (high_val << low_bits | low_val) & 0b111111

不过下面 Redis 的源码要晦涩一点，看形式它似乎只考虑了跨越字节边界的情况。这是因为如果 6 bit 在单个字节内，上面代码中的 high_val 的值是零，所以这一份代码可以同时照顾单字节和双字节：

// 获取指定桶的计数值
#define HLL_DENSE_GET_REGISTER(target,p,regnum) do { 
    uint8_t *_p = (uint8_t*) p; 
    unsigned long _byte = regnum*HLL_BITS/8; 
    unsigned long _fb = regnum*HLL_BITS&7;   # %8 = &7
    unsigned long _fb8 = 8 - _fb; 
    unsigned long b0 = _p[_byte]; 
    unsigned long b1 = _p[_byte+1]; 
    target = ((b0 >> _fb) | (b1 << _fb8)) & HLL_REGISTER_MAX; 
} while(0)

// 设置指定桶的计数值
#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; 
    _p[_byte] &= ~(HLL_REGISTER_MAX << _fb); 
    _p[_byte] |= _v << _fb; 
    _p[_byte+1] &= ~(HLL_REGISTER_MAX >> _fb8); 
    _p[_byte+1] |= _v >> _fb8; 
} while(0)

稀疏存储结构

稀疏存储适用于很多计数值都是零的情况。下图表示了一般稀疏存储计数值的状态：

源代码统计工具_网站计数器源码,0,0,0,0.0,0,0,0,,-_计算机源码商城

当多个连续桶的计数值都是零时，Redis 提供了几种不同的表达形式：

注意上面第三种方式的计数值最大只能表示到 32，而 HyperLogLog 的密集存储单个计数值用 6bit 表示，最大可以表示到 63。当稀疏存储的某个计数值需要调整到大于 32 时，Redis 就会立即转换 HyperLogLog 的存储结构，将稀疏存储转换成密集存储。

对象头

HyperLogLog 除了需要存储 16384 个桶的计数值之外，它还有一些附加的字段需要存储，比如总计数缓存、存储类型。所以它使用了一个额外的对象头来表示：

struct hllhdr {
    char magic[4];      /* 魔术字符串"HYLL" */
    uint8_t encoding;   /* 存储类型 HLL_DENSE or HLL_SPARSE. */
    uint8_t notused[3]; /* 保留三个字节未来可能会使用 */
    uint8_t card[8];    /* 总计数缓存 */
    uint8_t registers[]; /* 所有桶的计数器 */
};

所以 HyperLogLog 整体的内部结构就是 HLL 对象头加上 16384 个桶的计数值位图。它在 Redis 的内部结构表现就是一个字符串位图。你可以把 HyperLogLog 对象当成普通的字符串来进行处理：

> PFADD codehole python java golang
(integer) 1
> GET codehole
"HYLLx01x00x00x00x00x00x00x00x00x00x00x80Cx03x84MKx80Pxb8x80^xf3"

但是不可以使用 HyperLogLog 指令来操纵普通的字符串，因为它需要检查对象头魔术字符串是否是 "HYLL"。

四、HyperLogLog 的使用

HyperLogLog 提供了两个指令 PFADD 和 PFCOUNT，字面意思就是一个是增加，另一个是获取计数。PFADD 和 set 集合的 SADD 的用法是一样的，来一个用户 ID，就将用户 ID 塞进去就是，PFCOUNT 和 SCARD 的用法是一致的，直接获取计数值：

> PFADD codehole user1
(interger) 1
> PFCOUNT codehole
(integer) 1
> PFADD codehole user2
(integer) 1
> PFCOUNT codehole
(integer) 2
> PFADD codehole user3
(integer) 1
> PFCOUNT codehole
(integer) 3
> PFADD codehole user4 user 5
(integer) 1
> PFCOUNT codehole
(integer) 5

我们可以用 Java 编写一个脚本来试试 HyperLogLog 的准确性到底有多少：

public class JedisTest {
  public static void main(String[] args) {
    for (int i = 0; i < 100000; i++) {
      jedis.pfadd("codehole", "user" + i);
    }
    long total = jedis.pfcount("codehole");
    System.out.printf("%d %dn", 100000, total);
    jedis.close();
  }
}

结果输出如下：

100000 99723

发现 10 万条数据只差了 277，按照百分比误差率是 0.277%，对于巨量的 UV 需求来说，这个误差率真的不算高。

当然，除了上面的 PFADD 和 PFCOUNT 之外，还提供了第三个 PFMEGER 指令，用于将多个计数值累加在一起形成一个新的 pf 值：

> PFADD  nosql  "Redis"  "MongoDB"  "Memcached"
(integer) 1

> PFADD  RDBMS  "MySQL" "MSSQL" "PostgreSQL"
(integer) 1

> PFMERGE  databases  nosql  RDBMS
OK

> PFCOUNT  databases
(integer) 6