首页 » 技术文章 » 技能进阶:redis求基数的常用方法分析

技能进阶:redis求基数的常用方法分析

 

数据统计的各个指标计算,简单的讲,就是求不同纬度数据的最大、最小、叠加、去重的过程。

Crasheye数据统计基本介绍

目前Crasheye的数据统计基本为复合维度统计,而多维度统计的复杂度要远远高于单维度的运算,无论是在RDB还是NoSQL,瓶颈都会落在IO上面,造成IO瓶颈的根源很大部分来自于数据维度的划分与聚合,特别是对于去重统计类型的数据。

Crasheye有多维度去重统计的多个数据指标,这种需要实时显示的去重指标统计,对后台的设计实现都是一种挑战。

先看一部分Crasheye的单一时间下的基本统计维度:

维度 APP APP版本 SDK版本 渠道 操作系统类型 操作系统版本 宕机 设备型号 网络环境
APP
APP版本
SDK版本
渠道
操作系统类型
操作系统版本
宕机
设备型号
网络环境

比如下面这个统计,APP启动次数在各个设备型号的分布情况,这个就是时间、APP、设备型号三个维度下的增量统计:

设备分布

如果换成受影响的用户统计呢 ?那就是时间、APP、宕机等多维度下的去重统计。这样的去重统计被称为求基数,先定义下面的三个概念:

  1. 基数:一个可重复集合中不重复元素的个数称基数
  2. 基数方法:计算可重复集合中不重复元素的个数的方法
  3. 基数估计算法:通过概率算法,在误差可控的前提下,对基数进行估计的方法

redis最常用的三种求基数方法

目前统计指标的计算均采用redis实现,接下来介绍下,redis最常用的三种求基数方法:

  • 基于set
  • 基于bitmap
  • 基于hyperloglog

基于set

Redis去重最常用的统计方式,set的概念就是一堆不重复值的组合,所以只需要将去重的数据插入一个set中,需要统计的时候直接使用scard统计该数据集的基数。对于时间、APP、版本之类等维度信息,可以拼接放在key中,那么这个多个维度的去重数据列表就是这个set

sadd

  • SADD命令:将一个或多个member元素加入到集合 key 当中,已经存在于集合的 member 元素将被忽略
  • SCARD命令:返回集合key的基数(集合中元素的数量)

基于bitmap

Redis以(Key,Value)的形式存储数据,这里的Value支持二进制数据。而bitmap就是一串连续的2进制数字(0或1),每一位所在的位置为偏移(offset),在bitmap上可执行位操作(余、或、非等)。

所以就可以通过一个bit的0或1来记录某个元素是否存在信息,这样相同的数据就会映射到同一个bit上,这样只要统计bitmap中值为1的位的个数,就是去重统计项的值了

setbit

  • SETBIT命令:设置在指定Offset上bit的值,该值只能为1或0,在设定后该命令返回该Offset上原有的BIT值。
  • BITCOUNT命令:计算给定字符串中,被设置为1的bit位的数量。

基于hyperloglog

hyperloglog是基于概率统计的一种方法,既然是概率统计,那么其准确度就不是百分之百,存在少量误差。其特点是在输入元素的数量非常非常大时,计算基数所需的空间总是固定的、并且是很小的。该特性对于大数据的统计而言,其误差是可以容忍的。

pfadd

  • PFADD命令:将所有元素的参数保存在指定为第一个参数的键名的HyperLogLog数据结构
  • PFCOUNT命令:用于获得近似的基数由存储在指定变量的HyperLogLog数据结构进行计算。如果键。不存在,则返回0。

三种去重统计方式数据去重计算对比

redis提供的这三种去重统计方式各有优劣,确切的说各有使用场景,不同场景可以考虑使用不同的方式进行数据去重计算。

我们来看看三种方式的对比:

所耗容量

  • Set:set的容量与member的大小与数量成线性关系,member越多占用内存空间越多
  • Bit:基于bit的方法比起set空间消耗小得多,它消耗的空间取决于最大偏移量,和member的大小无关。理论上来讲,        针对连续的2进制串,1M的空间就可以标示800万member
  • HyperLogLog:每个hyperloglog键只需要花费12KB内存,就可以计算接近2^64个不同元素的基数。这和计算基         数时,元素越多耗费内存就越多的set形成鲜明对比

假设去重统计项的单个member的大小为10个字节,那么三种方式不同数量级下的内存消耗如下:

member总量/单日 Set Bit HyperLogLog
100万 10M 150K 12K
500万 50M 750K 12K
1千万 100M 1.5M 12K

由此可见,set的内存消耗是最大的,如果是大数据统计,比如单日上亿数据且数据失效时间比较长,那么内存的消耗就非常大,这个时候set的选择就要非常慎重,持续增长的数据+持续消耗的内存,往往会造成更多地问题。相反,如果数据量比较小,或者数据过期时间很短,内存消耗不大的情况,set也是不错的选择。

统计准确度

  • Set:计数精确
  • Bit:元素映射为位偏移的方法正确,则计数精确
  • HyperLogLog:采用基数估计算法,计数结果存在小量误差

由此可见,如果你要计数结果十分精确的话,采用hyperloglog就要谨慎了。

使用复杂度

  • Set:方法简单有效,适用面广,易于理解,且可以返回去重后的列表数据
  • Bit:要求元素能映射为位偏移,适用面窄,实现与维护成本略高,不可以返回去重后的列表数据
  • HyperLogLog:方法简单有效,适用面广,但内部算法较难理解,不可以返回去重后的列表数据

由此可见,在使用难易程度上,bit较为复杂,set与hyperloglog则容易操作的多。如果需要返回去重后的列表数据,那显然bit与hyperloglog是满足不了的。

时间复杂度

  • Set:SADD命令复杂度为O(N),N是被添加的元素的数量;SCARD命令复杂度为O(1)
  • Bit:SETBIT命令复杂度为O(1);BITCOUNT命令复杂度为O(N)
  • HyperLogLog:PFADD命令的复杂度为 O(N) ,N 为被添加元素的数;PFCOUNT命令复杂度为O(1)

单从时间复杂度上看时间消耗并不严谨,那么写了例子,简单测试下set与hyperloglog的耗时。

如下面代码所示,测试连续写入100万数据下,对比set与hyperloglog

hyperloglog

测试结果如下,写入数据前后redis的内存变化及写入耗时对比

HyperLogLog
used_memory:1006248 used_memory:1022520
used_memory_human:982.66K used_memory_human:998.55K
used_memory_rss:7229440 used_memory_rss:7200768
used_memory_peak:1200040 used_memory_peak:1200040
used_memory_peak_human:1.14M used_memory_peak_human:1.14M
used_memory_lua:36864 used_memory_lua:36864
mem_fragmentation_ratio:7.18 mem_fragmentation_ratio:7.04
mem_allocator:jemalloc-3.6.0 mem_allocator:jemalloc-3.6.0
耗时
start 2016-04-13 10:37:33.308076
end 2016-04-13 10:40:04.704386
Set
used_memory:1022520 used_memory:121413800
used_memory_human:998.55K used_memory_human:115.79M
used_memory_rss:7213056 used_memory_rss:131321856
used_memory_peak:1200040 used_memory_peak:121433784
used_memory_peak_human:1.14M used_memory_peak_human:115.81M
used_memory_lua:36864 used_memory_lua:36864
mem_fragmentation_ratio:7.05 mem_fragmentation_ratio:1.08
mem_allocator:jemalloc-3.6.0 mem_allocator:jemalloc-3.6.0
耗时
start 2016-04-13 10:52:19.418109
end 2016-04-13 10:55:18.209096

由上图可见,同样的数据量连续写入的耗时,两者是差不多的,但内存的消耗则有相当大的区别。

上边四方面对比,总结一下,精确度要求百分之百的,不建议使用hyperloglog,大数据量的不建议使用set。通常情况下,统计方式选择的参考,一般是由下面三者的平衡决定的。

流程图

后台优化中,往往有空间换时间的做法,例如以增加机器的方式,提高响应的速度。数据统计过程中,也同样有类似的做法。如为了提高性能,降低计算准确度、减少运算数据量或者增加内存等,上边介绍的hyperloglog就是用准确性换取数据空间的例子。

大数据量下的实时统计计算,对性能提出要求;统计结果准确度的要求,也往往会牺牲掉部分性能;不断累积的数据又对存储容量提出更高的要求。可见一种统计方式的选择就是要在计算性能、计算精度、数据量三个方面做一个平衡的选择。

 

本文作者:郭大侠

原文链接:技能进阶:redis求基数的常用方法分析,转载请注明来源!

5