HyperLogLog原理及Redis实现分析

瑞军

HyperLogLog原理及Redis实现分析 HyperLogLog原理及Redis实现分析 柯慧淑@贝壳找房 贝壳产品技术 贝壳产品技术 “贝壳产品技术公众号”作为贝壳官方产品技术号，致力打造贝壳产品、技术干货分享平台，面向互联网/O2O开发/产品从业者，每周推送优质产品技术文章、技术沙龙活动及招聘信息等。欢迎大家关注我们。 242篇内容 2021年07月08日 23:37 在某次需求实现时，面临的业务场景是对千万级的用户id做去重。Set、HashMap等常用的数据结构都能处理这种情况，但是这些数据结构也面临这样的问题：随着数据量的增多，占用的内存空间会越来越大。出于对人力成本和内存资源消耗的考虑，最终我们选用了HyperLogLog来完成这一任务。什么是HyperLogLog？一个(有限)集合里不同的元素个数就称为该集合的基数(cardinality)，HyperLogLog是一种在大数据量下统计基数的算法，标准误差为0.81%。相较于其它算法，HyperLogLog的一个明显优势就是仅需要12KB内存，就可以对大数据量级的数据进行基数统计。在确定了0.81%的误差可接受之后，我们用pfadd的结果来判断用户id是否为重复id进行去重，预期是将误差控制在官方所说的0.81%左右。但结果却与预期的大相径庭，千万的用户id集合经过这样的去重过程，其中90%以上的id都被误判为重复id。为什么会产生如此大的差异呢？本文将从基数统计算法演进的过程出发，带大家了解HyperLogLog的算法原理，并向大家介绍Redis中HyperLogLog的具体实现，最后将通过一系列的实验去探讨这一问题的成因。1. 基数统计算法演进1.1 线性计数算法(Linear Counting)线性计数算法是由Whang等人在1990年提出的算法，它整体的算法流程是：下图是原论文中的一个例子，可以看到，使用上述过程，预估到的集合基数为线性计数算法的流程比较简单，相较于bitmap，它的空间存储方面小有提升，但实际应用所需的空间复杂度仍为。1.2 对数计数算法(LogLog Counting)对数计数算法(简称LLC)基本思想是：将集合中所有元素做哈希，生成一个长度固定的比特串，令表示比特串中第一个“1”出现的位置，表示所有元素哈希得到的比特串中的最大值，那么集合总量可近似估计为：为什么可以采用这种方式估计呢？因为比特串的每个比特都独立且服从0-1分布，那么扫描比特串寻找第一个“1”的过程，从统计学角度就可以认为是一次伯努利过程。类比于抛硬币试验，就可以看作不断抛掷一枚硬币直到得到一个正面的过程。那么进行次伯努利过程，所有投掷次数都不大于的概率为：至少有一次不小于的概率为：因此，所以一旦集合中出现，那么从概率上讲的值即不可能远大于，也不会远小于，因此可作为基数的一个粗略估计。不过如果直接使用单一的估计量进行基数估计，可能会因偶然性存在较大误差。所以LLC采用了均值法来尽可能地消减误差。基于上述思想，对数计数算法的整体流程如下：假设hash结果定长L为32位。前10位用于桶编号，因此记录每个桶的，仅需要5bit()。能统计到的最大基数个数为，实际占用的内存为。这也就是算法名称中LogLog的由来。但因为LLC使用的是算术平均数，对于离群值特别敏感，所以当要预估的值不是特别大时，它的误差可能较大。1.3 超对数计数算法(HyperLogLog Counting)如前所述，LLC算法使用的是算术平均数，当值较小时，会存在较多空桶，即为0的桶较多。并且因为计算的算术平均数被应用到2的指数上，这些离群值将会更大地干扰基数估计的结果，LLC的偏差就会很大。为了弥补LLC算法存在的这些问题，Flajolet等人提出了一种LLC的改进算法：超对数计数算法(HyperLogLog，后续简称HLL)。HLL中引入了分桶平均的概念，相较于LLC的改进如下：可以看到，当计算出的基数较小时，HLL就退化成了线性计数算法，当预估的基数值较大时，也对结果做了一定的修正，由此来尽可能降低估算的误差率。这三种算法的空间复杂度及标准差数据如下：2. Redis的HyperLogLog实现Redis定义的HyperLogLog使用了类似sds的结构存储数据，命名为hllhdr，采用了稀疏和密集两种编码处理和存储数据。提供了PFADD、PFCOUNT、PFMERGE三个命令来添加元素、计算基数和合并。它的基本数据结构如下图所示：其中：magic：占4字节，固定值“HYLL”，用于区别普通stringencoding：占1字节，存储registers保存的数据编码格式，取值为HLL_DENSE(0)、HLL_SPARSE(1)、HLL_RAW(255)，其中HLL_RAW只在内部使用。notused：占3字节，全为0，暂未使用。card：占8字节，用于缓存最新计算的近似基数。registers：动态字节数组，用于HLL数据存储，不论编码是稀疏还是密集，散列值的低14位都为分组序号，也就是说Redis使用了16384()个分组。从上述结构体可以大致看出，Redis实现的HLL结构大致分为两部分：头部信息和存储桶数据的registers。为了减少计算的成本，Redis的HLL实现使用card来保存基数估计的最新计算结果，card字段采用小端存储，用最高有效位来标识card内存储的结果是否还有效。由于Redis的HLL实现使用了16384个分组，基于前文所述的HLL的标准差计算方法，Redis的HLL实现的误差即是，也就是Redis官方文档中公布的误差率。由于内部编码(HLL_RAW)只是一个临时存储结构，仅在内部MERGE使用或用作具有多个键的PFCOUNT的加速，不对外暴露，所以接下来就仅对HLL的稀疏/密集编码的具体实现形式和命令的执行流程做介绍。2.1 HLL的稀疏编码在HLL初始化时，如果仅有少量数据存入，这时候会有大量的空桶。如果这个时候就采用固定位数来存储16384个桶的话，大量的内存空间就被浪费了。因此，Redis使用稀疏编码(HLL_SPARSE)初始化一个新的HLL结构，它是具有压缩性质的编码，将重复的分组计数压缩成操作码(opcode)，以此降低内存使用。那么什么时候会发生编码的转换呢？当HLL的任一组里的计数值大于32()，或总长度超过3000字节(由HLL_SPARSE_MAX_BYTES决定，可配置)时，发生编码转换。因为不管数据总长度还是计数值只会增加不会减少，所以不会发生由密集编码向稀疏编码的转换。稀疏编码使用ZERO、XZERO、VAL三种操作码对registers存储的数据进行编码，其中ZERO、VAL占一个字节，XZERO占两个字节：ZERO：操作码为00xxxxxx。6位xxxxxx表示有1到64(111111+1，0没有意义)个连续分组为空。XZERO：操作码由两个字节01xxxxxx yyyyyyyy表示。其中xxxxxx yyyyyyyy表示有1到16384(111111 11111111+1)个连续分组为空， xxxxxx为XZERO的高位，yyyyyyyy为低位。此操作码是初始化一个HLL时使用的默认值，也就是说2个字节就可以表示一个刚创建好的HLL结构的registers。VAL：操作码表示为1vvvvvxx。vvvvv表示投掷次数()，最大32（11111+1），这也是为什么 大于32时会发生编码转换的原因；xx表示连续n+1个分组，此操作码可以表示1到32之间的值， 重复1到4次。上图展示的是稀疏编码的三种操作码及示例，而下图则展示了HLL初始化结构以及插入部分元素后的状态。2.2 HLL的密集编码HLL的密集编码(HLL_DENSE)结构是由稀疏编码转换而来的，它的结构相对简单，由连续16384个桶拼接而成，每个组占用6位(16384×6/8，12KB的由来)。不过由于存储采用的是小端模式，所以每个桶的6bit计数值是从LSB(低位) 开始一个接一个地编码到MSB(高位)。具体可见下图：为了尽可能地节省内存，密集编码的采用的是6bit()存储单个桶，所以存在跨字节存储的情况，这里Redis采用了比较巧妙的方式去定位桶(HLL_DENSE_GET_REGISTER)和设置桶值(HLL_DENSE_SET_REGISTER)。上图展示的是跨字节情况获取桶值的方法HLL_DENSE_GET_REGISTER，而下面则是HLL_DENSE_SET_REGISTER相关的代码和图示。2.3 HLL的命令实现依据前述的HLL的数据结构，结合Redis源码，实际命令的执行过程可以用这些流程图来表述，PFADD命令：简单来说，PFADD命令首先使用MurmurHash64A计算元素的64位散列值，然后根据散列值定位当前元素对应的桶index和旧桶值oldcount，比较当前值count与旧桶值oldcount。如果count>oldcount，则将card置位无效，返回1；否则返回0。PFCOUNT命令的简要流程如下：由于篇幅限制，这里仅介绍统计单个key时的过程，对统计多个key以及PFMERGE流程感兴趣的同学可自行查看Redis源码。3. 关于HyperLogLog的一些实验最后来到我们的实验环节，在实验环节主要验证两件事：1. 在大数据量的基数估计场景下，HLL的内存占用是否优于bitmap和hashmap？2. 回到文章最初，使用HLL是否可以保证标准差在0.81%，到底为什么实际使用时和官方提供的标准差相去甚远呢？3.1 实验一：内存占用实验下面就来通过实验真实对比一下Bitmap、Hashmap以及HyperLogLog这三种数据结构的内存消耗。同时为了更接近于真实用户id的场景，以一个固定数值为起始，并加上一个random值作为下一次的id值，以查看更真实的内存占用数据。并分别选择了10、10000、10000000三个范围来进行测试。最后使用memory usage来查看各个数据结构的内存占用：整理后的最终实验结果如下：可以看到，即使在key的数量达到一千万的情况下，HyperLogLog也能保证以12KB的内存去进行基数估计，对内存的消耗是远远小于Bitmap和HashMap的。3.2 实验二：HLL标准差验证实验接下来进行标准差相关的实验。选取了人群包的id数据，还原当时需求的使用场景，同时选用一个set来记录真实的id值和校准。最开始进行1000个id的重复性实验：可以看到，在处理集合前1000个元素时，通过pfadd命令返回结果这种方式判断，HyperLogLog是判定存在21个重复元素，Set是判定无重复元素，那么实际通过pfcount和scard获取到的估计基数是多少呢？分别是999和1000，这样看来好像有些奇怪，为什么过程中显示重复了21个元素，但是结果却只是判定有1个元素重复呢？先继续我们的实验，最后再一起揭晓我们的答案。那么随着元素不断地被遍历，我们会发现每遍历1000个元素，HyperLogLog判定的重复元素会越来越多，但实际估计的基数差值与Set获取到的准确结果相差还尚在官方公布的标准差内。当遍历了一百万左右的元素后，可以看到，每一页处理的过程中甚至能误判990+次重复集合元素，而实际基数估计误差仅在0.53%左右。回顾上文提到的HyperLogLog的结构和PFADD/PFCOUNT实现机制，我们可以知道，随着集合元素的遍历，每个桶内的值(即count值)会越来越大，Hash处理后的值会越来越难以使动态字节数组registers发生变更(这个过程就恰似你在有多个靶子的靶场打靶，每次击中的环数都在0~10环。最开始每一轮的射击后，每个靶子命中的最高环数可能都不断在刷新。但是随着你打了一千轮、一万轮之后，每个靶的最高环数再被刷新的频次会越来越低)。每一次pfadd返回结果为1的过程，就是动态字节数组registers发生了一次变化，从而基数估计值发生变更的过程。HyperLogLog估计到的基数值并不是随着元素的遍历而递增，而是根据动态字节数组registers(即所有桶值count)而跳跃计算出的值。所以根据实验的结果可以看到，并不是HyperLogLog这个数据结构的问题，而是没有去合理地使用它，而导致了集合去重结果的错误。4. 总结与思考结合前文所述，我们可以了解到，HyperLogLog是一个仅使用12KB就可以近似计算大数据量级集合基数的算法，它的Redis实现标准误差在0.81%。所以在精度要求不那么高的基数统计业务场景下，HyperLogLog不失为一种不错的选择。不同的数据结构有不同的适用场景和优缺点，我们需要仔细权衡自己的需求之后，根据实际使用场景去合理地使用它们。希望在这次对HyperLogLog数据结构的探索中，可以帮助大家了解更多基数计数相关算法的思想，也能对Redis各种不同的数据结构使用有更多的思考。5. 参考文献[1]Flajolet P , éric Fusy, Gandouet O , et al. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm[J]. 2007.[2]陈雷 等. Redis 5设计与源码分析[M]. 北京: 机械工业出版社, 2019.[3]https://www.jianshu.com/p/4bddbcdd89df[4]Whang K Y , Vander-Zanden B T , Taylor H M . A linear-time probabilistic counting algorithm for database applications[J]. Acm Trans on Database Systems, 1990, 15(2):208-229.[5]Loglog Counting of Large Cardinalities. Springer Berlin Heidelberg, 2003.[6]https://www.jianshu.com/p/e7d9a4b630b4[7]http://content.research.neustar.biz/blog/hll.html[8]https://mp.weixin.qq.com/s/AvPoG8ZZM8v9lKLyuSYnHQ[9]http://dqyuan.top/2019/11/20/redis-read-5.html 预览时标签不可点 后端27策略&算法9后端 · 目录#后端上一篇为什么我们经常遇到curl域名解析超时？下一篇响应式编程和协程在Java语言的应用关闭更多小程序广告搜索「undefined」网络结果