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

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

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

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

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

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

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

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

  SPL将数据按时间顺序存入多个结构相同的数据表（简称分表），每个分表存一段时间的数据。这些分表整体上对时间维度有序，而每个分表内的数据则按用户、时间两个维度排序。 按照时间维度过滤时，SPL用过滤条件中的起止时间，可以快速找到过滤后数据所在的分表。这些分表的个数，一般都比分表总数小得多，也就快速排除了大部分不需要涉及的数据。虽然找到的分表内部不再对时间有序，在读出数据时还要遍历并再次实施针对时间维度的过滤，但比起遍历所有数据来讲还是快了很多。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

SPL资料

• SPL下载
• SPL源代码