作者:陈璐,腾讯 CSIG 高级数据分析师

本文实践了对于千万级别的用户,操作总数达万级别,每日几十亿操作流水的留存分析工具秒级别查询的数据构建方案。同时,除了留存分析,对于用户群分析,事件分析等也可以尝试用此方案来解决。

背景

你可能听说过Growingio、神策等数据分析平台,本文主要介绍实现留存分析工具相关的内容。

留存分析是一种用来分析用户参与情况/活跃程度的分析模型,可考查进行初始行为后的用户中,有多少人会进行后续行为,这是衡量产品对用户价值高低的重要指标。如,为评估产品更新效果或渠道推广效果,我们常常需要对同期进入产品或同期使用了产品某个功能的用户的后续行为表现进行评估 [1]。大部分数据分析平台主要包括如图的几个功能(以神策为例):

clickhouse环比百分比数据分析(ClickHouse留存分析工具十亿数据秒级查询方案)(1)

本文主要介绍留存分析工具的优化方案(只涉及数据存储和查询的方案设计,不涉及平台)。

我想每个数据/产品同学在以往的取数分析过程中,都曾有一个痛点,就是每次查询留存相关的数据时,都要等到天荒地老,慢!而最近采用优化方案的目的也是为了提高查询的效率和减少数据的存储,可以帮助产品快速地查询/分析留存相关的数据。

优化方案的核心是在Clickhouse中使用Roaringbitmap对用户进行压缩,将留存率的计算交给高效率的位图函数,这样既省空间又可以提高查询速度。

希望本实践方案可以给你带来一些帮助和启示。下面主要分3个部分详细介绍:Roaringbitmap简介、思路与实现、总结与思考。

Roaringbitmap简介

下面先简单介绍一下高效的位图压缩方法Roaringbitmap。先来看一个问题:

给定含有40亿个不重复的位于[0,2^32-1]区间内的整数集合,如何快速判定某个数是否在该集合内?

显然,如果我们将这40亿个数原样存储下来,需要耗费高达14.9GB的内存,这是难以接受的。所以我们可以用位图(bitmap)来存储,即第0个比特表示数字0,第1个比特表示数字1,以此类推。如果某个数位于原集合内,就将它对应的位图内的比特置为1,否则保持为0,这样就能很方便地查询得出结果了,仅仅需要占用512MB的内存,不到原来的3.4% [3]。但是这种方式也有缺点:比如我需要将1~5000w这5000w个连续的整数存储起来,用普通的bitmap同样需要消耗512M的存储,显然,对于这种情况其实有很大的优化空间。

2016年由S. Chambi、D. Lemire、O. Kaser等人在论文《Better bitmap performance with Roaring bitmaps》与《Consistently faster and smaller compressed bitmaps with Roaring》中提出了roaringbitmap,主要特点就是可以极大程度地节约存储及提供了快速的位图计算,因此考虑用它来做优化。对于前文提及的存储连续的5000w个整数,只需要几十KB。

它的主要思路是:将32位无符号整数按照高16位分桶,即最多可能有2^16 =65536个桶,论文内称为container。存储数据时,按照数据的高16位找到container(找不到就会新建一个),再将低16位放入container中。也就是说,一个roaringbitmap就是很多container的集合 [3],具体细节可以自行查看文末的参考文章 。

思路与实现

我们的原始数据主要分为:

现在我们需要根据这两类数据,求出某天操作了某个行为的用户在后续的某一天操作了另一个行为的留存率,比如,在20200701这天操作了“点击banner”的用户有100个,这部分用户在20200702这天操作了“点击app签到”的有20个,那么对于分析时间是20200701,且“点击banner”的用户在次日“点击app签到”的留存率是20%。同时,还需要考虑利用用户属性对留存比例进行区分,例如只考虑广东省的用户的留存率,或者只考虑小米商店用户的留存率,或者在广东的小米商店的用户的留存率等等。

一般来说,求留存率的做法就是两天的用户求交集,例如前文说到的情况,就是先获取出20200701的所有操作了“点击banner”的用户标识id集合假设为S1,然后获取20200702的所有操作了“点击app签到”的用户标识id集合假设为S2,最后求解S1和S2的交集:

clickhouse环比百分比数据分析(ClickHouse留存分析工具十亿数据秒级查询方案)(2)

可以看到,当s1和s2的集合中用户数都比较大的时候,join的速度会比较慢。

在此我们考虑前文说到的bitmap,假若每一个用户都可以表示成一个32位的无符号整型,用bitmap的形式去存储,S1和S2的求交过程就是直接的一个位比较过程,这样速度会得到巨大的提升。而Roaringbitmap对数据进行了压缩,其求交的速度在绝大部分情况下比bitmap还要快,因此这里我们考虑使用Roaringbitmap的方法来对计算留存的过程进行优化。

1.数据构建

整个过程主要是:首先对初始的两张表——用户操作数据表table_oper_raw和用户筛选维度数据表table_attribute_raw中的user_id字段进行编码,将每个用户映射成唯一的id(32位的无符号整型),分别得到两个新表table_oper_middle和table_attribute_middle。再将他们导入clickhouse,使用roaringbitmap的方法对用户进行压缩存储,最后得到压缩后的两张表table_oper_bit和table_attribute_bit,即为最终的查询表。流程图如下:

clickhouse环比百分比数据分析(ClickHouse留存分析工具十亿数据秒级查询方案)(3)

clickhouse环比百分比数据分析(ClickHouse留存分析工具十亿数据秒级查询方案)(4)

同 样的,在clickhouse中 创建表table_attribute_middle_ch。 然后用spark将这两份数据分别导入这 两张表。 这一步导入很快,几十亿的数据大概10分多钟 就可以完成。

2. 查询过程

首先,简要地介绍下方案中常用的bitmap函数(详细见文末的参考资料):

1.bitmapCardinality 返回一个UInt64类型的数值,表示bitmap对象的基数。用来计算不同条件下的用户数,可以粗略理解为count(distinct)

2.bitmapAnd 为两个bitmap对象进行与操作,返回一个新的bitmap对象。可以理解为用来满足两个条件之间的and,但是参数只能是两个bitmap

3.bitmapOr 为两个bitmap对象进行或操作,返回一个新的bitmap对象。可以理解为用来满足两个条件之间的or,但是参数也同样只能是两个bitmap。如果是多个的情况,可以尝试使用groupBitmapMergeState

举例来说,假设20200701这天只有[1,2,3,5,8]这5个用户点击了banner,则有:

# 返回5

select bitmapCardinality ( user_bit )

from tddb . table_oper_bit

where ds = 20200701 AND oper_name =

'点击banner'

又如果20200701从小米商店新进的用户是[1,3,8,111,2000,100000],则有:

# 返回3,因为两者的重合用户只有1,3,8这3个用户

select bitmapCardinality ( bitmapAnd (

( SELECT user_bit

FROM tddb . table_oper_bit

WHERE ( ds = 20200701 ) AND ( oper_name = '点击banner' )),

( SELECT user_bit

FROM tddb . table_attribute_bit

WHERE ds = 20200701 and ( attr_id = 'first_channel' ) and ( attr_value IN ( '小米商店'

)))))

有了以上的数据生成过程和bitmap函数,我们就可以根据不同的条件使用不同的位图函数来快速查询,具体来说,主要是以下几种情况:

3. 实践效果

根据这套方案做了实践,对每日按时间分区、用户、操作名称去重后包括几十亿的操作记录,其中包含千万级别的用户数,万级别的操作数。最后实现了:

总结与思考

总的来说,本方案的优点是:

另外,根据本方案的特点,除了留存分析工具,对于用户群分析,事件分析等工具也可以尝试用此方案来解决。

PS : 作者初入坑ch,对于以上内容,有不正确/不严谨之处请轻拍~ 欢迎交流~

参考文献:

[1] 解析常见的数据分析模型——留存分析:https://www.sensorsdata.cn/blog/jie-xi-chang-jian-de-shu-ju-fen-xi-mo-xing-liu-cun-fen-xi/

[2] RoaringBitmap数据结构及原理: https://blog.csdn.net/yizishou/article/details/78342499

[3] 高效压缩位图RoaringBitmap的原理与应用: https://www.jianshu.com/p/818ac4e90daf

[4] 论文:Better bitmap performance with Roaring bitmaps: https://arxiv.org/abs/1402.6407v9?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed: DanielLemiresArticlesOnArxiv (Daniel Lemire's articles on arXiv)

[5] Clickhouse文档-位图函数: https://clickhouse.tech/docs/zh/sql-reference/functions/bitmap-functions/

原文地址:https://mp.weixin.qq.com/s?__biz=MjM5ODYwMjI2MA==&mid=2649748113&idx=1&sn=2f0ea3ba734f29e0c3df8a88fb73058d

,