双维有序结构提速大数据量用户行为分析
用户分析(或帐户分析),是指对用户、帐户明细数据进行统计分析计算。常见的有:用户行为分析、银行帐户统计、漏斗转化率、保险单分析等等。
这类场景涉及众多用户的历史数据,总数据量巨大(几千万甚至上亿),需要外存;而每个用户的数据量相对较小(几条到几千条)。用户分析经常是在线计算的,要即时得到结果,对计算速度要求很高。需要深入分析这类场景的计算和数据特征,并以此为依据选择合适的优化算法,从而达到最佳性能。
用户分析的特征之一:一般都要对时间维度做过滤。全部数据涉及时间跨度较长,但过滤后数据的对应时间跨度相对不大。如果能不遍历全部数据就快速获得过滤结果,将会明显地提升性能。然而,在时间维度上建立索引并不会有多大效果,因为这种场景下过滤后的数据依然不小,即使能用索引快速地找到目标数据所在位置,但如果这些数据在硬盘的存储是不连续的,也仍然会造成大量无效读取,无法实质性提速。必须将数据在物理上按照时间维度有序存储才可以有效提速。但是,传统关系数据库基于无序集合概念,不保证物理有序,只能指望工程优化的手段。有些数据库可能会在优化引擎中利用存入数据的次序,但由于数据库理论上不保证这一点,是否能真正做到有序就很难说了。
用户分析的另一个特征:不同用户之间的数据无关,对一个用户的计算一般不涉及其他用户数据。假如很多不同用户的数据混杂在一起,即使是简单地按照用户去重计数,都会变得很麻烦。最好是将一个个用户的数据分别加载、计算,这样可以有效降低编码和计算的复杂度,同时提高性能。有些情况下,分析计算的逻辑很复杂,要把单个用户的数据加载到内存中,写较复杂的代码才能实现,这就更需要逐个用户做处理了。
同上面类似地,在用户维度上建立索引并不能帮助达到上述目标,如果同一个用户数据不是物理连续存储的,使用索引逐次读取用户数据通常只会导致更差的性能(而且差很多,因为所有用户数据都会被遍历到)。还是同样地,要做到上述目标,需要每个用户的数据在存储时是物理连续的,也就是要求数据对用户维度也有序。
这就产生了一个矛盾,数据即要对时间维度有序(以方便过滤),又要对用户维度有序(方便后续计算)。显然,同一套数据不可能同时对两个维度都有序(按两个维度依次排序是没意义的)。这时候,即使采用做了优化的关系数据库,能一定程度地利用写入次序,但数据写入时也只能按一个维度有序,也就没办法在时间或用户两个维度上都做优化,这种运算无论如何都很难跑得快。
开源数据计算引擎集算器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提供的双维有序结构可以大致做到时间和用户两个维度同时有序,能有效利用用户分析场景的两个关键特征提高计算速度。
SPL资料
文章来源: zimug.blog.csdn.net,作者:字母哥哥,版权归原作者所有,如需转载,请联系作者。
原文链接:zimug.blog.csdn.net/article/details/125967301
- 点赞
- 收藏
- 关注作者
评论(0)