Redis——Redis扩展应用HyperLog原理

摘要

如果你负责开发维护一个大型的网站，有一天老板找产品经理要网站每个网页每天的 UV 数据，然后让你来开发这个统计模块，你会如何实现？如果统计 PV 那非常好办，给每个网页一个独立的 Redis 计数器就可以了，这个计数器的 key 后缀加上当天的日期。这样来一个请求，incrby 一次，最终就可以统计出所有的 PV 数据。但是 UV 不一样，它要去重，同一个用户一天之内的多次访问请求只能计数一次。这就要求每一个网页请求都需要带上用户的 ID，无论是登陆用户还是未登陆用户都需要一个唯一 ID 来标识。你也许已经想到了一个简单的方案，那就是为每一个页面一个独立的 set 集合来存储所有当天访问过此页面的用户 ID。当一个请求过来时，我们使用 sadd 将用户 ID 塞进去就可以了。通过 scard 可以取出这个集合的大小，这个数字就是这个页面的 UV 数据。没错，这是一个非常简单的方案。但是，如果你的页面访问量非常大，比如一个爆款页面几千万的 UV，你需要一个很大的 set 集合来统计，这就非常浪费空间。如果这样的页面很多，那所需要的存储空间是惊人的。为这样一个去重功能就耗费这样多的存储空间，值得么？其实老板需要的数据又不需要太精确，105w 和 106w 这两个数字对于老板们来说并没有多大区别，有没有更好的解决方案呢？

一、Redis的去重解决方案

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

二、HyperLog实现原理

HyperLogLog 的使用非常简单，但是实现原理比较复杂。给定一系列的随机整数N，记录低位遥续零兖最大长度K;随机整数数量N和最大长度K的关系?通过这个 k 值可以估算出随机数的数量。

当一个元素到来时，它会散列到一个桶中，以一定的概率影响这个桶的计数值，因为是概率算法，单个桶的计数值并不准确，但是将所有的桶计数值进行调和均值累加起来，结果就会非常接近真实的计数值;

在Redis 的HLL中共有2^14个桶，而每个桶是一个6bit的数组。hash生成64位整数，其中后14位用来索引桶子;后面50位共有用来统计累计0的个数;保存对数的话最大值为49;6位对应的是2^6对应整数值为64。2^6的可以装50个。

class PfTest {
    static class BitKeeper {
        private int maxbits;
        public void random() {
            long value = ThreadLocalRandom.current().nextLong(2L  this.maxbits) {
                this.maxbits = bits;
            }
        }
        private int lowZeros(long value) {
            int i = 1;
            for (; i < 32; i++) {
                if (value >> i  this.maxbits) {
                this.maxbits = bits;
            }
        }
        private int lowZeros(long value) {
            int i = 1;
            for (; i < 32; i++) {
                if (value >> i  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);
        }
    }
}

三、HyperLog去重复实战

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();
    }
}

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

实验结果表明：

差了 277 个，按百分比是 0.277%，对于上面的 UV 统计需求来说，误差率也不算高。然后我们把上面的脚本再跑一边，也就相当于将数据重复加入一边，查看输出，可以发现，pfcount 的结果没有任何改变，还是 99723，说明它确实具备去重功能

package com.zhuangxiaoyan.springbootredis.hyperlog;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.data.redis.core.StringRedisTemplate;

/**
 * @Classname HyperLogTest
 * @Description HyperLogTest add  count merge function
 * @Date 2022/4/11 8:11
 * @Created by xjl
 */
public class HyperLogTest {

    /**
     * redis 客户端
     */
    @Autowired
    private StringRedisTemplate redisTemplate;

    /**
     * @description 添加一跳记录
     * @param: key
     * @param: obj
     * @date: 2022/4/11 8:15
     * @return: boolean
     * @author: xjl
     */
    public boolean add(String key, String obj) {
        return redisTemplate.opsForHyperLogLog().add(key, obj) > 0;
    }

    /**
     * @description pfcount 非精准统计 key的计数
     * @param: key
     * @date: 2022/4/11 8:16
     * @return: long
     * @author: xjl
     */
    public long count(String key) {
        return redisTemplate.opsForHyperLogLog().size(key);
    }

    /**
     * @description pfmerge out key1 key2  ---> 将key1 key2 合并成一个新的hyperloglog out
     * @param: out
     * @param: key
     * @date: 2022/4/11 8:16
     * @return: boolean
     * @author: xjl
     */
    public boolean merge(String out, String... key) {
        return redisTemplate.opsForHyperLogLog().union(out, key) > 0;
    }
}

四、HyperLog应用场景

HyperLogLog 除了上面的 pfadd 和 pfcount 之外，还提供了第三个指令 pfmerge，用于将多个 pf 计数值累加在一起形成一个新的 pf 值。比如在网站中我们有两个内容差不多的页面，运营说需要这两个页面的数据进行合并。其中页面的 UV 访问量也需要合并，那这个时候 pfmerge 就可以派上用场了。

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

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

五、HyperLog总结

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

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

博文参考

Redis深度历险：核心原理与应用实战