Redis 高级主题之HyperLogLog

栏目: 数据库 · 发布时间: 5年前

内容简介：在了解 HyperLogLog 之前，先来简单了解一下基数计数(Cardinality Counting).基数计数是用于统计一个集合中不重复的元素个数，比如日常需求场景有，统计页面的UV或者统计在线的用户数、注册IP数等。如果让你实现这个需求，会怎么思考实现了？简单的做法就是记录集合中的所有不重复的集合S，新来一个元素x，首先判断x在不在S中，如果不在，则将x加入到S，否则不记录。常用的SET数据结构就可以实现。

在了解 HyperLogLog 之前，先来简单了解一下基数计数(Cardinality Counting).

1.1 概念

基数计数是用于统计一个集合中不重复的元素个数，比如日常需求场景有，统计页面的UV或者统计在线的用户数、注册IP数等。

如果让你实现这个需求，会怎么思考实现了？简单的做法就是记录集合中的所有不重复的集合S，新来一个元素x，首先判断x在不在S中，如果不在，则将x加入到S，否则不记录。常用的SET数据结构就可以实现。

但是这样实现，如果数据量越来越大，会造成什么问题？

当统计的数据量变大时，相应的存储内存会线性增长。
当集合S越大时，判断x元素是否在集合S中的所花的成本会越大。

还有别的方案能减少上面2个问题带来的困扰吗，答案肯定是有的，下面简单介绍一下。

1.2 方法

常用的基数计数有三种： B+树、bitmap、概率算法。

B+ 树。 B+ 树插入和查找效率比较高。可以快速查找元素是否存在，以及进行插入。如果要计算基数值（不重复的元素值），则只需要树的节点个数即可。但是依然存在没有节省内存空间的问题。
bitmap。 bitmap 是通过一个bit数组来存在特定数据的一种数据结构。基数计数则将每一个元素对应到bit数组的其中一位，比如Bit数组010010101，代表[1,4,6,8]。新加入的元素只需要已有的Bit数组和新加入的元素进行按位或计算。这种方式可以大大减少内存，如果存储1亿数据的话，大概只需要 100000000/8/1024/1024 ≈ 12M 的内存。相比B+树确实节省不少，但是在某些非常大数据的场景下，如果有10000个对象有1亿数据，则需要120G内存，可以说在特定场景下内存的消耗还是蛮大的。
概率算法，概率算法是通过牺牲准确率来换取空间，对于不要求绝对准确率的场景下，概率算法是一种不错的选择，因为概率算法不直接存储数据集合本身，通过一定的概率统计方法预估基数值，同时保证误差在一定范围内，这种方式可以大大减少内存。HyperLogLog就是概率算法的一种实现，下面重点介绍一下此算法。

2. HyperLogLog

2.1 原理

HyperLogLog 原理思路是通过给定 n 个的元素集合，记录集合中数字的比特串第一个1出现位置的最大值k，也可以理解为统计二进制低位连续为零的最大个数。通过k值可以估算集合中不重复元素的数量m，m近似等于2^k。

下图来源于网络，通过给定一定数量的用户User，通过Hash得到一串Bitstring，记录其中最大连续零位的计数为4，User的不重复个数为 2 ^ 4 = 16.

下面代码演示一下。

2.2 代码演示

代码有部分参考https://kuaibao.qq.com/s/20180917G0N2C300?refer=cp_1026

# content of hyperloglog_test.py
class BitsBucket(object):
    def __init__(self):
        self.maxbit = 0

    @staticmethod
    def get_zeros(value):
        for i in range(31):
            if (value >> i) & 1:
                break
        return i

    def add(self, m):
        self.maxbit = max(self.maxbit, self.get_zeros(m))

class HyperLogLogTest(object):
    def __init__(self, n, bucket_cnt=1024):
        self.n = n
        self.bucket_cnt = bucket_cnt
        self.bits_bucket = [BitsBucket() for i in range(bucket_cnt)]

    @staticmethod
    def generate_value():
        return random.randint(1, 2**32 - 1)

    def pfadd(self):
        for i in range(self.n):
            value = self.generate_value()
            bucket = self.bits_bucket[((value & 0xfff0000) >> 16) % self.bucket_cnt]
            bucket.add(value)

    def pfcount(self):
        sumbits_inverse = 0
        for bucket in self.bits_bucket:
            if bucket.maxbit == 0:
                continue
            sumbits_inverse += 1.0 / float(bucket.maxbit)
        avgbits = float(self.bucket_cnt) / sumbits_inverse
        return 2**avgbits * self.bucket_cnt
复制代码

BitsBucket 类，是计算一个集合中连续低位的最大个数，HyperLogLogTest实现2个方法，pfadd是随机n个元素，将元素加入某一集合桶中，pfcount是算出bucket_cnt个桶的平均基数计数值。

为什么会去计算bucket_cnt桶了，因为此算法随机概率性，如果一个桶，误差率非常大，然后就提出了分桶平均的概念，将统计数据划分为m个桶，每个桶分别统计各自的基数预估值，最后对这些预估值求平均得到整体的基数估计值。

现在测试一下:

# content of hyperloglog_test.py
def main(bucket_cnt=1024):
    print("bucket cnt: {}, start".format(bucket_cnt))
    for i in range(100000, 1000000, 100000):
        hyperloglog = HyperLogLogTest(i, bucket_cnt)
        hyperloglog.pfadd()
        pfcount = hyperloglog.pfcount()
        print("original count: {} ".format(i),
              "pfcount: {}".format('%.2f' % pfcount), "error rate: {}%".format(
                  '%.2f' % (abs(pfcount - i) / i * 100)))
    print("bucket cnt: {}, end \n\n".format(bucket_cnt))


buckets = [1, 1024]
for cnt in buckets:
    main(cnt)
复制代码

分别对 bucket_cnt 为1 和 1024 进行测试，结果如下:

➜  HyperLogLog git:(master) ✗ python3 hyperloglog_test.py
bucket cnt: 1, start
original count: 100000  pfcount: 65536.00 error rate: 34.46%
original count: 200000  pfcount: 131072.00 error rate: 34.46%
original count: 300000  pfcount: 131072.00 error rate: 56.31%
original count: 400000  pfcount: 524288.00 error rate: 31.07%
original count: 500000  pfcount: 1048576.00 error rate: 109.72%
original count: 600000  pfcount: 2097152.00 error rate: 249.53%
original count: 700000  pfcount: 262144.00 error rate: 62.55%
original count: 800000  pfcount: 1048576.00 error rate: 31.07%
original count: 900000  pfcount: 262144.00 error rate: 70.87%
bucket cnt: 1, end

bucket cnt: 1024, start
original count: 100000  pfcount: 97397.13 error rate: 2.60%
original count: 200000  pfcount: 192659.65 error rate: 3.67%
original count: 300000  pfcount: 287909.86 error rate: 4.03%
original count: 400000  pfcount: 399678.34 error rate: 0.08%
original count: 500000  pfcount: 515970.76 error rate: 3.19%
original count: 600000  pfcount: 615906.34 error rate: 2.65%
original count: 700000  pfcount: 735321.47 error rate: 5.05%
original count: 800000  pfcount: 808206.55 error rate: 1.03%
original count: 900000  pfcount: 950692.17 error rate: 5.63%
bucket cnt: 1024, end
复制代码

可以看到bucket_cnt=1，误差非常大，为1024时则算法基本可以使用。而 Redis 中实现的HyperLogLog更复杂，可以控制误差在0.81%。下面重点看看Redis中HyperLogLog的应用。

3. Redis中HyperLogLog实现

Redis中HyperLogLog在 2.8.9 版本中出现，想了解其中细节，可以查看Redis作者antirez写的一篇博文： Redis new data structure: the HyperLogLog

3.1 用法

用法涉及到3个命令:

pfadd 增加一个元素到key中
pfcount 统计key中不重复元素的个数
Pfmerge 合并多个Key中的元素

127.0.0.1:6379> PFADD pf_tc tc01
(integer) 1
127.0.0.1:6379> PFADD pf_tc tc02
(integer) 1
127.0.0.1:6379> PFADD pf_tc tc03
(integer) 1
127.0.0.1:6379> PFADD pf_tc tc04 tc05 tc06
(integer) 1
127.0.0.1:6379> PFCOUNT pf_tc
(integer) 6
127.0.0.1:6379> PFADD pf_tc tc04 tc05 tc06
(integer) 0
127.0.0.1:6379> PFCOUNT pf_tc
(integer) 6

127.0.0.1:6379> PFADD pf_tc01 tc07 tc08 tc09 tc10 tc01 tc02 tc03
(integer) 1
127.0.0.1:6379> PFCOUNT pf_tc01
(integer) 7
127.0.0.1:6379> PFMERGE pf_tc pf_tc01
OK
127.0.0.1:6379> PFCOUNT pf_tc
(integer) 10
127.0.0.1:6379> PFCOUNT pf_tc01
(integer) 7
复制代码

感觉是不是很准，接下来写个脚本测试一下。

3.2 误差分析

下面写一段 Python 代码测试一下误差

class HyperLogLogRedis(object):
    def __init__(self, n):
        self.n = n
        self.redis_client = redis.StrictRedis()
        self.key = "pftest:{}".format(n)

    @staticmethod
    def generate_value():
        return random.randint(1, 2**32 - 1)

    def pfadd(self):
        for i in range(self.n):
            value = self.generate_value()
            self.redis_client.pfadd(self.key, value)

    def pfcount(self):
        return self.redis_client.pfcount(self.key)


def main():
    for i in range(100000, 1000000, 100000):
        hyperloglog = HyperLogLogRedis(i)
        hyperloglog.pfadd()
        pfcount = hyperloglog.pfcount()
        print("original count: {} ".format(i),
              "pfcount: {}".format('%.2f' % pfcount), "error rate: {}%".format(
                  '%.2f' % (abs(pfcount - i) / i * 100)))

main()
复制代码

代码部分还是在2.2的基础稍微改动，将redis的HyperLogLog功能替换之前自己测试的部分。

测试结果如下:

➜  HyperLogLog git:(master) ✗ python3 hyperloglog_redis.py
original count: 100000  pfcount: 99763.00 error rate: 0.24%
original count: 200000  pfcount: 200154.00 error rate: 0.08%
original count: 300000  pfcount: 298060.00 error rate: 0.65%
original count: 400000  pfcount: 394419.00 error rate: 1.40%
original count: 500000  pfcount: 496263.00 error rate: 0.75%
original count: 600000  pfcount: 595397.00 error rate: 0.77%
original count: 700000  pfcount: 712731.00 error rate: 1.82%
original count: 800000  pfcount: 793678.00 error rate: 0.79%
original count: 900000  pfcount: 899268.00 error rate: 0.08%
复制代码

基本误差都在 0.81% 左右，为什么标准的误差是0.81%了，因为Redis中用了16384个桶，HyperLogLog的标准误差公式是1.04/sqrt(m), m是桶的个数，所以在Redis中,m=16384，标准误差则为0.81%。

3.3 内存分析

Redis采用了16384个桶来存储计算HyperLogLog，那所占的内存会是多少？ Redis最大可以统计2^64个数据，也就是说每个桶的最大maxbits需要 6 个bit来存储(2^6=64)。那么所占内存就是 16384 * 6 / 8 = 12kb。

第一节提到 BitMap 1亿数据就需要 12M，如果 2^64个数据，粗略计算需要 1500 TB，而 HyperLogLog 只需要12kb，可以想象HyperLogLog的强大，但这里并不是说bitmap不好，每一个数据结构都有它最适合的应用场景，只能说在基数统计的场景中HyperLogLog是目前非常强大的算法。

如果元素个数不多时，Redis会采用稀疏存储结构，其大小会少于12kb，采用密集存储结构，大小固定为12kb，存储的实现采用Redis的字符串位图bitmap实现，即连续个16384个桶，每个桶占6个Bits。

更多的细节可以阅读Redis的源码: github.com/antirez/red…