Redis-HyperLogLog 淡淡的烟草味﹌ 2021-09-25 11:18 365阅读 0赞 ## **关于基数统计** ## 维基百科解释: > cardinality of a set is a measure of the “number of elements“ of the set 中文释义是:一个集合(可以包含重复元素)中不重复元素的个数。例如集合\{1,2,3,1,2\},有5个元素,但它的基数为3。 **基数统计**通常是用来统计一个集合中不重复的元素个数。 ## 场景分析 ## 如果你负责开发维护一个网站,有天老板找你要网站上每个网页的UV,然后让你开发这个统计模块,你会如何实现? 如果统计PV,非常简单,给每个页面配置一个独立的 redis 计数器就可以了,把这个计数器的 key 后缀加上当天的日期。这样每来一个请求,就执行 INCRBY 命令一次,最终就可以统计出所有的PV数据了。 但UV不同,它需要去重,同一用户同一天多次访问只能计数一次。这就需要每个网页都要带上用户ID,无论是登录用户还是未登录的用户,都需要唯一ID来标识。 也许马上就能想到解决方案:那就是 为每个页面设置一个独立的 set 集合 来存储所有当天访问过此页面的用户ID。但问题是: 1. **存储空间巨大**:如果网站流量一大,用来存储的集合就会非常大,同时页面在一多。。。后果可想而知,绝对就不是删库跑路这么容易了; 2. **统计复杂**:那么多set集合如果要聚合统计一下,又是一个复杂的事情; ### 基数统计的演进 ### 对于上述需要涉及到 基数统计 问题,通常来说有两种比 set 集合更好的解决方案: 第一种:**B树** B树最大的优势就是插入和查找效率很高,如果用B树存储要统计的数据,可以快速判断新来的数据是否存在,并快速将元素插入B树。要计算基础值,只需要计算B树的节点个数就行了。 不过将B树结构维护到内存中,能够解决统计和计算的问题,但是 并没有节省内存 第二种:**bitmap** bitmap 可以理解为通过一个 bit 数组来存储特定数据的一种数据结构,每一个 bit 位都能独立包含信息,bit 是数据的最小存储单位,因此能大量节省空间,也可以将整个 bit 数据一次性 load 到内存计算。如果定义一个很大的 bit 数组,基础统计中 每一个元素对应到 bit 数组中的一位, bitmap 还有一个明显的优势是 可以轻松合并多个统计结果,只需要对多个结果求异或就可以了,也可以大大减少存储内存。可以简单做一个计算,如果要统计 1 亿 个数据的基数值,大约需要的内存:100\_000\_000/ 8/ 1024/ 1024 ≈ 12 M,如果用 32 bit 的 int 代表 每一个 统计的数据,大约需要内存:32 \* 100\_000\_000/ 8/ 1024/ 1024 ≈ 381 M 可以看到 bitmap 对于内存的节省显而易见,但仍然不够。统计一个对象的基数值就需要 12 M,如果统计 1 万个对象,就需要接近 120 G,对于大数据的场景仍然不适用。 **概率算法** 实际上目前还没更好的在 大数据场景 中 准确计算 基数的高效算法,因此在不追求绝对精确的情况下,使用概率算法算是一个不错的解决方案。 概率算法 不直接存储 数据集合本身,通过一定的 概率统计方法预估基数值,这种方法可以大大节省内存,同时保证误差控制在一定范围内。目前用于基数计数的概率算法包括: * Linear Counting(LC):早期的基数估计算法,LC 在空间复杂度方面并不算优秀,实际上 LC 的空间复杂度与上文中简单 bitmap 方法是一样的(但是有个常数项级别的降低),都是 O(Nmax) * LogLog Counting(LLC):LogLog Counting 相比于 LC 更加节省内存,空间复杂度只有 O(log2(log2(Nmax))) * HyperLogLog Counting(HLL):HyperLogLog Counting 是基于 LLC 的优化和改进,在同样空间复杂度情况下,能够比 LLC 的基数估计误差更小 其中,HyperLogLog 的表现是惊人的,上面我们简单计算过用 bitmap 存储 1 个亿 统计数据大概需要 12 M 内存,而在 HyperLoglog 中,只需要不到 1 K 内存就能够做到!在 Redis 中实现的 HyperLoglog 也只需要 12 K 内存,在 标准误差 0.81% 的前提下,能够统计 264 个数据! ## 1、HyperLogLog简介 ## HyperLogLog 是最早由 [Flajolet][] 及其同事在 2007 年提出的一种 估算基数的近似最优算法。但跟原版论文不同的是,好像很多书包括 Redis 作者都把它称为一种 新的数据结构(new datastruct)。 redis 在 2.8.9 版本新增HyperLogLog结构。HyperLogLog是用来做基数统计的算法,优点是,在输入元素的数量或者体积非常非常大时,计算基数所需的空间总是固定的、并且很小的。但是这个估算的基数并不一定准确,是一个带有0.81%标准错误的近似值。 在 redis 里面,每个HyperLogLog键只需要花费 12 kb 内存,就可以计算接近 2^64个不同元素的基数。这和计算基数时,元素越多耗费内存就越多的集合形成鲜明对比。 但因为HyperLogLog只会根据输入元素来计算基数,而不会存储输入元素本身,所以HyperLogLog不能像集合那样,返回输入的各个元素。 ### 1.1、HyperLogLog使用 ### redis为HyperLogLog提供三个命令:PFADD、PFCOUNT、PFMERGE。 * PFADD 将任意数量的元素添加到指定的 HyperLogLog 里面。时间复杂度: 每添加一个元素的复杂度为 O(1) 。如果 HyperLogLog 估计的近似基数(approximated cardinality)在命令执行之后出现了变化, 那么命令返回 1 , 否则返回 0 。 如果命令执行时给定的键不存在, 那么程序将先创建一个空的 HyperLogLog 结构, 然后再执行命令。 \# 命令格式:PFADD key element \[element …\] \# 如果给定的键不存在,那么命令会创建一个空的 HyperLogLog,并向客户端返回 1 127.0.0.1:6379> PFADD ip\_20190301 "192.168.0.1" "192.168.0.2" "192.168.0.3" (integer) 1 \# 元素估计数量没有变化,返回 0(因为 192.168.0.1 已经存在) 127.0.0.1:6379> PFADD ip\_20190301 "192.168.0.1" (integer) 0 \# 添加一个不存在的元素,返回 1。注意,此时 HyperLogLog 内部存储会被更新,因为要记录新元素 127.0.0.1:6379> PFADD ip\_20190301 "192.168.0.4" (integer) 1 * PFCOUNT 当 PFCOUNT key \[key …\] 命令作用于单个键时,返回储存在给定键的 HyperLogLog 的近似基数,如果键不存在,那么返回 0,复杂度为 O(1),并且具有非常低的平均常数时间; 当 PFCOUNT key \[key …\] 命令作用于多个键时,返回所有给定 HyperLogLog 的并集的近似基数,这个近似基数是通过将所有给定 HyperLogLog 合并至一个临时 HyperLogLog 来计算得出的,复杂度为 O(N),常数时间也比处理单个 HyperLogLog 时要大得多。 \# 返回 ip\_20190301 包含的唯一元素的近似数量 127.0.0.1:6379> PFCOUNT ip\_20190301 (integer) 4 127.0.0.1:6379> PFADD ip\_20190301 "192.168.0.5" (integer) 1 127.0.0.1:6379> PFCOUNT ip\_20190301 (integer) 5 127.0.0.1:6379> PFADD ip\_20190302 "192.168.0.1" "192.168.0.6" "192.168.0.7" (integer) 1 \# 返回 ip\_20190301 和 ip\_20190302 包含的唯一元素的近似数量 127.0.0.1:6379> PFCOUNT ip\_20190301 ip\_20190302 (integer) 7 * PFMERGE 将多个 HyperLogLog 合并(merge)为一个 HyperLogLog,合并后的 HyperLogLog 的基数接近于所有输入 HyperLogLog 的可见集合(observed set)的并集。时间复杂度是 O(N),其中 N 为被合并的 HyperLogLog 数量,不过这个命令的常数复杂度比较高。 命令格式:PFMERGE destkey sourcekey \[sourcekey …\],合并得出的 HyperLogLog 会被储存在 destkey 键里面,如果该键并不存在,那么命令在执行之前,会先为该键创建一个空的 HyperLogLog。 \# ip\_2019030102 是 ip\_20190301 与 ip\_20190302 并集 127.0.0.1:6379> PFMERGE ip\_2019030102 ip\_20190301 ip\_20190302 OK 127.0.0.1:6379> PFCOUNT ip\_2019030102 (integer) 7 ## 2、HyperLogLog应用场景 ## 鉴于HyperLogLog不保存数据内容的特性,所以只适用于一些特定的场景。例如:计算日活、7日活、月活数据。 假如每天访问的用户有几百万,如果把用户信息放到集合set中,无疑会占用大量的存储空间,且计算月活数据时需要将整月的数据全都加载内存,这随时都可能导致我们的程序OOM。但有了HyperLogLog,就变得很简单了,因为存储日活数据所需要的内存只有12k。 PFADD user\_20210626 user1 PFADD user\_20210626 user2 .... PFADD user\_20210630 user6 那么,计算某一天的日活,只需要 PFCOUNT user\_20210626 就可以了。每月第一天执行 PFMERGE 将上一个月的数据全都合并一个HyperLogLog,例如:user\_202106。再去执行 PFCOUNT user\_202106 ,就能得到6月的月活。 ### 3、SpringBoot中使用 Redis HyperLogLog ### 由于 Redis HyperLogLog只有三个命令,思想和操作也非常简单,直接给出代码实例。 import com.imooc.ad.Application; import org.junit.Test; import org.junit.runner.RunWith; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.boot.test.context.SpringBootTest; import org.springframework.data.redis.core.HyperLogLogOperations; import org.springframework.data.redis.core.StringRedisTemplate; import org.springframework.test.context.junit4.SpringRunner; /** * <h1>Redis HyperLogLog 测试用例</h1> * Created by Qinyi. */ @RunWith(SpringRunner.class) @SpringBootTest(classes = {Application.class}, webEnvironment = SpringBootTest.WebEnvironment.NONE) public class RedisHyperLogLogTest { /** 注入 StringRedisTemplate, 使用默认配置 */ @Autowired private StringRedisTemplate stringRedisTemplate; @Test @SuppressWarnings("all") public void testHyperLogLog() { HyperLogLogOperations operations = stringRedisTemplate.opsForHyperLogLog(); // add 方法对应 PFADD 命令 operations.add("user_20210621", "11", "12", "13"); // size 方法对应 PFCOUNT 命令 System.out.println(operations.size("user_20210621")); // 3 operations.add("user_20210621", "11", "14"); System.out.println(operations.size("user_20210621")); // 4 operations.add("user_20210622", "11", "15"); System.out.println(operations.size("user_20210622")); // 2 // union 方法对应 PFMERGE 命令 operations.union("user_202106", "user_20210621", "user_20210622"); System.out.println(operations.size("user_202106")); // 5 } } ## 小结 ## 当需要做大量数据统计时,普通集合已经不能满足我们需要,这个时候就可以借助提供的HyperLogLog来统计,它的优点是只需要使用12k的空间就能统计2^64的数据,但缺点是存在0.81%的误差,HyperLogLog提供三个操作方法:pfadd 添加元素、pfcount 统计元素和 pfmerge合并元素。 [Flajolet]: http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
还没有评论,来说两句吧...