【Redis】HyperLogLog-记录UV

快来打我* 2022-03-15 08:56 190阅读 0赞

Redis 提供了 HyperLogLog 数据结构就是用来解决这种统计问题的。HyperLogLog 提供不精确的去重计数方案，虽然不精确但是也不是非常不精确，标准误差是 0.81%，这样的精确度已经可以满足上面的 UV 统计需求了。

## 使用方法 ##

HyperLogLog 提供了两个指令 pfadd 和 pfcount，根据字面意义很好理解，一个是增加计数，一个是获取计数。pfadd 用法和 set 集合的 sadd 是一样的，来一个用户 ID，就将用户 ID 塞进去就是。pfcount 和 scard 用法是一样的，直接获取计数值。

127.0.0.1:6379> pfadd codehole user1
    (integer) 1
    127.0.0.1:6379> pfcount codehole
    (integer) 1
    127.0.0.1:6379> pfadd codehole user2
    (integer) 1
    127.0.0.1:6379> pfcount codehole
    (integer) 2
    127.0.0.1:6379> pfadd codehole user3
    (integer) 1
    127.0.0.1:6379> pfcount codehole
    (integer) 3
    127.0.0.1:6379> pfadd codehole user4
    (integer) 1
    127.0.0.1:6379> pfcount codehole
    (integer) 4
    127.0.0.1:6379> pfadd codehole user5
    (integer) 1
    127.0.0.1:6379> pfcount codehole
    (integer) 5
    127.0.0.1:6379> pfadd codehole user6
    (integer) 1
    127.0.0.1:6379> pfcount codehole
    (integer) 6
    127.0.0.1:6379> pfadd codehole user7 user8 user9 user10
    (integer) 1
    127.0.0.1:6379> pfcount codehole
    (integer) 10

public class PfTest {
      public static void main(String[] args) {
        Jedis jedis = new Jedis();
        for (int i = 0; i < 1000; i++) {
          jedis.pfadd("codehole", "user" + i);
          long total = jedis.pfcount("codehole");
          if (total != i + 1) {
            System.out.printf("%d %d\n", total, i + 1);
            break;
          }
        }
        jedis.close();
      }
    }

## pfmerge 适合什么场合用？ ##

HyperLogLog 除了上面的 pfadd 和 pfcount 之外，还提供了第三个指令 pfmerge，用于将多个 pf 计数值累加在一起形成一个新的 pf 值。

比如在网站中我们有两个内容差不多的页面，运营说需要这两个页面的数据进行合并。其中页面的 UV 访问量也需要合并，那这个时候 pfmerge 就可以派上用场了。

## 注意事项 ##

HyperLogLog 这个数据结构不是免费的，不是说使用这个数据结构要花钱，它需要占据一定 12k 的存储空间，所以它不适合统计单个用户相关的数据。如果你的用户上亿，可以算算，这个空间成本是非常惊人的。但是相比 set 存储方案，HyperLogLog 所使用的空间那真是可以使用千斤对比四两来形容了。

不过你也不必过于担心，因为 Redis 对 HyperLogLog 的存储进行了优化，在计数比较小时，它的存储空间采用稀疏矩阵存储，空间占用很小，仅仅在计数慢慢变大，稀疏矩阵占用空间渐渐超过了阈值时才会一次性转变成稠密矩阵，才会占用 12k 的空间。

## HyperLogLog 实现原理 ##

HyperLogLog 的使用非常简单，但是实现原理比较复杂，如果读者没有特别的兴趣，下面的内容暂时可以跳过不看。

为了方便理解 HyperLogLog 的内部实现原理，我画了下面这张图

![1][]

这张图的意思是，给定一系列的随机整数，我们记录下低位连续零位的最大长度 k，通过这个 k 值可以估算出随机数的数量。 首先不问为什么，我们编写代码做一个实验，观察一下随机整数的数量和 k 值的关系。

public class PfTest {
    
      static class BitKeeper {
        private int maxbits;
    
        public void random() {
          long value = ThreadLocalRandom.current().nextLong(2L << 32);
          int bits = lowZeros(value);
          if (bits > this.maxbits) {
            this.maxbits = bits;
          }
        }
    
        private int lowZeros(long value) {
          int i = 1;
          for (; i < 32; i++) {
            if (value >> i << i != value) {
              break;
            }
          }
          return i - 1;
        }
      }
    
      static class Experiment {
        private int n;
        private BitKeeper keeper;
    
        public Experiment(int n) {
          this.n = n;
          this.keeper = new BitKeeper();
        }
    
        public void work() {
          for (int i = 0; i < n; i++) {
            this.keeper.random();
          }
        }
    
        public void debug() {
          System.out.printf("%d %.2f %d\n", this.n, Math.log(this.n) / Math.log(2), this.keeper.maxbits);
        }
      }
    
      public static void main(String[] args) {
        for (int i = 1000; i < 100000; i += 100) {
          Experiment exp = new Experiment(i);
          exp.work();
          exp.debug();
        }
      }
    
    }

运行观察输出：

36400 15.15 13
    36500 15.16 16
    36600 15.16 13
    36700 15.16 14
    36800 15.17 15
    36900 15.17 18
    37000 15.18 16
    37100 15.18 15
    37200 15.18 13
    37300 15.19 14
    37400 15.19 16
    37500 15.19 14
    37600 15.20 15

通过这实验可以发现 K 和 N 的对数之间存在显著的线性相关性：

N=2^K  # 约等于

如果 N 介于 2^K 和 2^(K+1) 之间，用这种方式估计的值都等于 2^K，这明显是不合理的。这里可以采用多个 BitKeeper，然后进行加权估计，就可以得到一个比较准确的值。

public class PfTest {
    
      static class BitKeeper {
        private int maxbits;
    
        public void random(long value) {
          int bits = lowZeros(value);
          if (bits > this.maxbits) {
            this.maxbits = bits;
          }
        }
    
        private int lowZeros(long value) {
          int i = 1;
          for (; i < 32; i++) {
            if (value >> i << i != value) {
              break;
            }
          }
          return i - 1;
        }
      }
    
      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(m);
          }
        }
    
        public double estimate() {
          double sumbitsInverse = 0.0;
          for (BitKeeper keeper : keepers) {
            sumbitsInverse += 1.0 / (float) keeper.maxbits;
          }
          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 %.2f\n", i, est, Math.abs(est - i) / i);
        }
      }
    
    }

代码中分了 1024 个桶，计算平均数使用了调和平均 (倒数的平均)。普通的平均法可能因为个别离群值对平均结果产生较大的影响，调和平均可以有效平滑离群值的影响。

![1 1][]

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

100000 97287.38 0.03
    200000 189369.02 0.05
    300000 287770.04 0.04
    400000 401233.52 0.00
    500000 491704.97 0.02
    600000 604233.92 0.01
    700000 721127.67 0.03
    800000 832308.12 0.04
    900000 870954.86 0.03
    1000000 1075497.64 0.08

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

## pf 的内存占用为什么是 12k？ ##

我们在上面的算法中使用了 1024 个桶进行独立计数，不过在 Redis 的 HyperLogLog 实现中用到的是 16384 个桶，也就是 2^14，每个桶的 maxbits 需要 6 个 bits 来存储，最大可以表示 maxbits=63，于是总共占用内存就是`2^14 * 6 / 8 = 12k`字节。

[1]: https://user-gold-cdn.xitu.io/2018/7/12/1648f0af2621881b?imageView2/0/w/1280/h/960/format/webp/ignore-error/1
[1 1]: https://user-gold-cdn.xitu.io/2018/7/12/1648f0fa8841ceb1?imageView2/0/w/1280/h/960/format/webp/ignore-error/1