阅读 927

记一次服务端大数据处理过程

业务背景

用户留存分析

如图所示为用户留存分析功能

需求分析

该柱状图展示的为用户留存百分比.

以按周展示为例

U:活跃用户数 x:第几周 y:活跃占比

公式

需求整理:

  1. 按日,按周,按月 三种固定日期的对比
  2. 日期选择 随机日期的对比

对于这种数据后台的功能,作为服务端开发,我们会尽量要求数据库将结果统计好,由我们服务端直接取结果做展示.

但是由于有随机日期的对比,假设由数据组来进行统计,意味着需要对每天都做对比统计(统计结果数据量大,耗费性能),并不现实.

所以最终还是决定由服务端来做实时统计.

实时统计,主要考虑前端的响应速度.

方案1: 以天维度存放用户登录信息

采用bitmap按天纬度来存放用户登录数据.

实现过程:

  1. 估算总用户量为4亿,使用bitmap存储大概需要50M大小
  2. 给用户排序,简单实现:存表取id自增 (暂不考虑存表效率)
  3. 每天的登录用户生成一条bitmap
  4. 当计算y(x(i))时,只需提取x(1)与x(i)的bitmap做and操作,再统计结果为1的个数,再除以x(i)的bitmap中为1的个数

方案2: 以用户维度存放用户登陆时间信息

采用bitmap按用户纬度存放登录时间信息(哪几天登录)

  1. 记当天为标准第0天

  2. 对每个登录用户,将对每个登录用户,将当前天数对应的位置为1

  3. 当计算y(x(i))时

    用户 描述 bitmap
    a 第-4,-3,-1,0天登录 [1,1,0,1,1]
    b 第-3,-2,0天登录 [1,1,0,1]
    B(-3,0) 第-3,0天登录 [1,0,0,1]
    B(0) 第0天登录 [1]
    1. 遍历a,b与B(1,4)做and操作,统计结果==B(1,4)的个数,即1,4天都登录用户个数
    2. 再如法炮制得到第4天登录用户个数,相除即得到结果
优点 缺点
方案一 查询快,只需要做一次and操作 空间占用太大,每天都要以最大用户量生成一条bitmap
方案二 节省空间,空间占用随用户量增长,每个用户的bitmap随登陆情况变化 查询略慢,需要遍历所有用户做and操作

简单概括: 方案一费空间,方案二查询慢

实际开发过程中,由于我们采用redis进行存储.

采用方案一的话内存过于浪费.而采用方案二,以我的macpro-i5配置只能负载20w/s的and操作,响应速度方面难以接受.

综合上述方式一二都不能满足要求,只能看是否还有优化空间.

经过同事提醒,针对方式一采用一种空间压缩算法,解决了方案一空间浪费的缺陷.

方案3: 使用RoaringBitmap以天维度存放用户登录信息

RoaringBitmap介绍看这

简单概括:

  1. 假设数据量为不超过2^32.

  2. 将数据拆分为高16位,低16位

  3. 对高位进行聚合(以高位做key,value为有相同高位的所有低位数组)

  4. 根据低位的数据量(不同高位聚合出的低位数组长度不相同),使用不同的container(数据结构)存储

    1. len<4K ArrayContainer 直接存值

    2. len>=4K BitmapContainer 使用bitmap存储

      4K的取值原因:value的最大总数是为2^16=65536. 假设以bitmap方式存储需要65536bit=8kb,而直接存值的方式,一个值16,4K个总共需要2byte*4K=8kb.所以当value总量<4k时,使用直接存值的方式更节省空间

    3. RunContainer 压缩存储

      RunContainer中的Run指的是行程长度压缩算法(Run Length Encoding),对连续数据有比较好的压缩效果.对于数列11,12,13,14,15,21,22 它会压缩为11,4,21,1

      1. 最优,value数组完全连续,那么只会存储2个short,占用4kb
      2. 最差,value数组完全不连续(全奇/全偶),那么会存储需要存储65536个short,128kb.

内存占用

  1. 空间压缩主要体现在:

    1. 高位聚合(假设数据中有100w个高位相同的值,原先需要100w*2byte,现在只要1*2byte)
    2. 低位压缩(ArrayContainer省空间,BitmapContainer不省,RunContainer可能省)
  2. 对数据的位操作速度有影响(3种container相互and.乐观情况两个BitmapContainer做and切BitCount()>4096,则数据无影响)

综上: 使用RoaringBitmap的优缺点

  1. 节约空间(最优数据集高位都相同,最差数据集高位都不同)
  2. 位操作速度对原生bitmap有所下降

方案3可以说是平衡了方案一二,是本次的最优选择

关注下面的标签,发现更多相似文章
评论