双维有序结构提速大数据量用户行为分析

用户分析(或帐户分析),是指对用户、帐户明细数据进行统计分析计算。常见的有:用户行为分析、银行帐户统计、漏斗转化率、保险单分析等等。

这类场景涉及众多用户的历史数据,总数据量巨大(几千万甚至上亿),需要外存;而每个用户的数据量相对较小(几条到几千条)。用户分析经常是在线计算的,要即时得到结果,对计算速度要求很高。需要深入分析这类场景的计算和数据特征,并以此为依据选择合适的优化算法,从而达到最佳性能。

用户分析的特征之一:一般都要对时间维度做过滤。全部数据涉及时间跨度较长,但过滤后数据的对应时间跨度相对不大。如果能不遍历全部数据就快速获得过滤结果,将会明显地提升性能。然而,在时间维度上建立索引并不会有多大效果,因为这种场景下过滤后的数据依然不小,即使能用索引快速地找到目标数据所在位置,但如果这些数据在硬盘的存储是不连续的,也仍然会造成大量无效读取,无法实质性提速。必须将数据在物理上按照时间维度有序存储才可以有效提速。但是,传统关系数据库基于无序集合概念,不保证物理有序,只能指望工程优化的手段。有些数据库可能会在优化引擎中利用存入数据的次序,但由于数据库理论上不保证这一点,是否能真正做到有序就很难说了。

用户分析的另一个特征:不同用户之间的数据无关,对一个用户的计算一般不涉及其他用户数据。假如很多不同用户的数据混杂在一起,即使是简单地按照用户去重计数,都会变得很麻烦。最好是将一个个用户的数据分别加载、计算,这样可以有效降低编码和计算的复杂度,同时提高性能。有些情况下,分析计算的逻辑很复杂,要把单个用户的数据加载到内存中,写较复杂的代码才能实现,这就更需要逐个用户做处理了。

同上面类似地,在用户维度上建立索引并不能帮助达到上述目标,如果同一个用户数据不是物理连续存储的,使用索引逐次读取用户数据通常只会导致更差的性能(而且差很多,因为所有用户数据都会被遍历到)。还是同样地,要做到上述目标,需要每个用户的数据在存储时是物理连续的,也就是要求数据对用户维度也有序。

这就产生了一个矛盾,数据即要对时间维度有序(以方便过滤),又要对用户维度有序(方便后续计算)。显然,同一套数据不可能同时对两个维度都有序(按两个维度依次排序是没意义的)。这时候,即使采用做了优化的关系数据库,能一定程度地利用写入次序,但数据写入时也只能按一个维度有序,也就没办法在时间或用户两个维度上都做优化,这种运算无论如何都很难跑得快。

开源数据计算引擎集算器 SPL 提供了双维有序结构,在用户分析场景中,可以做到数据整体上对时间维度有序(从而实现快速过滤),同时还可以做到访问时对用户有序(从而方便地逐个取出用户数据进行后续计算),看起来相当于实现了两个维度同时有序。这样,就可以利用上述两个特征来提升用户分析任务的计算性能。

SPL 将数据按时间顺序存入多个结构相同的数据表(简称分表),每个分表存一段时间的数据。这些分表整体上对时间维度有序,而每个分表内的数据则按用户、时间两个维度排序。

按照时间维度过滤时,SPL 用过滤条件中的起止时间,可以快速找到过滤后数据所在的分表。这些分表的个数,一般都比分表总数小得多,也就快速排除了大部分不需要涉及的数据。虽然找到的分表内部不再对时间有序,在读出数据时还要遍历并再次实施针对时间维度的过滤,但比起遍历所有数据来讲还是快了很多。

如果过滤后的分表只有一个,则这个分表中的数据直接对用户有序,可以逐个取出每个用户的数据快速完成后续的分析计算。如果过滤后还有多个分表,由于每个分表都是对用户有序的,SPL 将采用高效的有序归并算法,将多个分表数据归并成对用户维度有序的数据,仍然可以逐个取出每个用户的数据。

关于双维有序结构原理,更详细的介绍请参考: SPL 虚表的双维有序结构

这里通过两个实际例子来进一步说明,先看一个简单的涉及去重计数的常规任务。

设帐户交易明细表 T 存储了一年的明细数据,包含帐户 userid、日期 dt、帐户所在城市 city、商品 product、交易金额 amt 等字段。现在要过滤出 dt 字段值在指定时间段内的数据,再按照产品分组,求组内 userid 去重个数和金额总和。

这里比较麻烦的是去重运算,常规方法要一直保持一个去重后的结果集,每一条原数据都要到结果集中查找是否有相同的,以决定丢弃还是添加,这需要占用一块不小的内存并执行复杂的比对动作。按照用户去重的结果集有时会很大,如果无法装入内存,则要使用外存缓存,性能将会进一步急剧下降。

但如果数据已经对用户维度有序,就可以按顺序读入,发现用户维度值发生变化时就做简单计数。这样,遍历一次就可以实现快速去重计数,不占用多少内存,比对也很简单,无论多大数据量都不需要外存缓存。

使用 SPL 的双维有序结构,将一年的明细数据按顺序存入 12 个分表中,每个分表存储一个月的数据。分表之间,整体上是按照 dt 有序的。在每个分表内部,则是按照 userid、dt 有序。然后就可以利用上面的办法快速计算出去重的结果:


A

1

=create(file,zone,user,date).record(["T.ctx",to(12),"userid","dt"])

2

=pseudo(A1,0)

3

=A2.select(dt>=date("2021-05-15") && dt<= date("2021-07-05") )

4

=A3.groups(product;icount(userid),sum(amt))

A1 A2 生成双维有序的表对象。

A3 利用 dt 有序做快速过滤。A4 的 groups 利用 userid 有序执行上面的办法做快速有序去重计算。

再举一个帐户内计算较复杂的场景:电商漏斗转化分析。

设帐户事件表 T1 也采用上述方式,存储了 12 个月的数据。T1 包括字段:帐号 userid、事件发生时间 etime、事件类型 etype。etype 可能是登录 "login",搜索 "search",查看 "pageview" 等等。现在,要计算一定时间内,连续完成登录、搜索、查看等多个步骤的去重帐户数。越是后续的事件帐户数越少,就像一个上大下小的漏斗一样。

漏斗分析本质上是时序计算,每个用户都要按照时间顺序去找发生的事件。SQL 基于无序集合概念,实现复杂的时序计算非常困难,即使勉强写出来也要数百行,而且代码和事件数量相关,增加了事件又要改写代码,性能优化基本上无从谈起。很多程序员都是在数据库中写复杂的 UDF 来实现,很繁琐难以维护,因为数据存储依赖于数据库,无法保证对两个维度的有序性,仍然难以高性能完成这个运算。

如果数据对用户维度有序,就可以逐个把每个帐号的数据读入内存形成有序集合,集合中记录顺序就是事件发生顺序,那就比较容易写出这个运算了,通用代码也不难。

SPL 的双维有序结构可以支持这个运算原理:按照时间快速过滤后的结果集是对帐户有序的,可以循环逐个取出各个帐户数据装入内存。且每个帐户的数据又是按照时间有序的,很容易用多步骤代码来完成漏斗分析计算,代码量要比 SQL 少的多,性能也好很多。代码写法大致如下:


A

B

C

D

1

=["login","search","pageview"]

=A1.(0)


2

=T1.select(dt>=date("2021-05-15") && dt<=date("2021-06-14")).cursor()

3

for A2;userid

=first=A3.select(etype==A1(1))

if first.len()==0

next

4


=t=null

=A1.(null)


5


for A1

if #B5==1

>C4(1)=t=t1=first.dt

6



else

>C4(#B5)=t=if(t,A3.select@1(etype==B5 && dt>t && dt<elapse(t1,7)).dt,null)

7


=C4.(if(~==null,0,1))

>C1=C1++B7


A2 定义时间过滤后的游标,A3 循环每次取出一个帐户的数据做复杂计算。由于每次循环都能快速取出一个 user 的全部数据,所以仅用很少的代码就能实现漏斗转化这样复杂的计算。

关于这个漏斗转化计算详细的介绍参考这里:SQL 提速:漏斗转化分析

SPL 的双维有序结构还支持多线程并行计算,可以利用多 CPU、多 CPU 核的计算能力,进一步提速。

要对用户分析场景提速,既需要利用时间维度有序,又需要利用用户维度有序。而传统的关系数据库基于无序集合概念,难以利用数据的有序性。即使在工程上做了优化,可以利用数据的写入顺序,也无法做到两个字段都有序。SPL 提供的双维有序结构可以大致做到时间和用户两个维度同时有序,能有效利用用户分析场景的两个关键特征提高计算速度。


以下是广告时间

对润乾产品感兴趣的小伙伴,一定要知道软件还能这样卖哟性价比还不过瘾? 欢迎加入好多乾计划。
这里可以低价购买软件产品,让已经亲民的价格更加便宜!
这里可以销售产品获取佣金,赚满钱包成为土豪不再是梦!
这里还可以推荐分享抢红包,每次都是好几块钱的巨款哟!
来吧,现在就加入,拿起手机扫码,开始乾包之旅



嗯,还不太了解好多乾?
猛戳这里
玩转好多乾