内容简介:在了解 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…
相关文章:
相关代码在 github.com/fuzctc/tc-r…
更多Redis相关文章和讨论,请关注公众号:『 天澄技术杂谈 』
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 数仓主题域、主题、业务域之间有什么的关系
- 一个基于vuepress默认主题开发的主题-vuepress-theme-reform
- Flutter主题风格
- 把主题升级了一下
- Android自动切换夜间主题
- 「译」Web 安全高级主题
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。