导读
用户行为分析是数据分析中非常重要的一项内容，在统计活跃用户，分析留存和转化率，改进产品体验、推动用户增长等领域有重要作用。美团点评每天收集的用户行为日志达到数百亿条，如何在海量数据集上实现对用户行为的快速灵活分析，成为一个巨大的挑战。为此，我们提出并实现了一套面向海量数据的用户行为分析解决方案，将单次分析的耗时从小时级降低到秒级，极大的改善了分析体验，提升了分析人员的工作效率。
本文以有序漏斗的需求为例，详细介绍了问题分析和思路设计，以及工程实现和优化的全过程。本文根据2017年12月ArchSummit北京站演讲整理而成，略有删改。
问题分析
下图描述了转化率分析中一个常见场景，对访问路径“首页-搜索-菜品-下单-支付”做分析，统计按照顺序访问每层节点的用户数，得到访问过程的转化率。
统计上有一些维度约束，比如日期，时间窗口（整个访问过程在规定时间内完成，否则统计无效），城市或操作系统等，因此这也是一个典型的OLAP分析需求。此外，每个访问节点可能还有埋点属性，比如搜索页上的关键词属性，支付页的价格属性等。从结果上看，用户数是逐层收敛的，在可视化上构成了一个漏斗的形状，因此这一类需求又称之为“有序漏斗”。
这类分析通常是基于用户行为的日志表上进行的，其中每行数据记录了某个用户的一次事件的相关信息，包括发生时间、用户ID、事件类型以及相关属性和维度信息等。现在业界流行的通常有两种解决思路。
-
基于Join的SQL
-
基于UDAF(User Defined Aggregate Function)的SQL
对于第一种解法，最大的问题是需要做大量join操作，而且关联条件除了ID的等值连接之外，还有时间戳的非等值连接。当数据规模不大时，这种用法没有什么问题。但随着数据规模越来越大，在几百亿的数据集上做join操作的代价非常高，甚至已经不可行。
第二种解法有了改进，通过聚合的方式避免了join操作，改为对聚合后的数据通过UDAF做数据匹配。这种解法的问题是没有足够的筛选手段，这意味着几亿用户对应的几亿条数据都需要遍历筛选，在性能上也难以接受。
那么这个问题的难点在哪里？为什么上述两个解法在实际应用中变得越来越不可行？主要问题有这么几点。
● 事件匹配有序列关系 。如果没有序列关系就非常容易，通过集合的交集并集运算即可。● 时间窗口约束 。这意味着事件匹配的时候还有最大长度的约束，所以匹配算法的复杂度会进一步提升。
● 属性和维度的需求 。埋点SDK提供给各个业务线，每个页面具体埋什么内容，完全由业务决定，而且取值是完全开放的，因此目前属性基数已经达到了百万量级。同时还有几十个维度用于筛选，有些维度的基数也很高。
● 数据规模 。目前每天收集到的用户行为日志有几百亿条，对资源和效率都是很大的挑战。
基于上述难点和实际需求的分析，可以总结出几个实际困难，称之为“坏消息”。
● 漏斗定义完全随机 。不同分析需求对应的漏斗定义完全不同，包括具体包含哪些事件，这些事件的顺序等，这意味着完全的预计算是不可能的。● 附加OLAP需求 。除了路径匹配之外，还需要满足属性和维度上一些OLAP的上卷下钻的需求。
● 规模和性能的矛盾 。一方面有几百亿条数据的超大规模，另一方面又追求秒级响应的交互式分析效率，这是一个非常激烈的矛盾冲突。
另一方面，还是能够从问题的分析中得到一些“好消息”, 这些也是在设计和优化中可以利用的点。
● 计算需求非常单一 。这个需求最终需要的就是去重计数的结果，这意味着不需要一个大而全的数据引擎，在设计上有很大的优化空间。● 并发需求不高 。漏斗分析这类需求一般由运营或者产品同学手动提交，查询结果用于辅助决策，因此并发度不会很高，这样可以在一次查询时充分调动整个集群的资源。
● 数据不可变 。所谓日志即事实，用户行为的日志一旦收集进来，除非bug等原因一般不会再更新，基于此可以考虑一些索引类的手段来加速查询。
● 实际业务特点 。最后是对实际业务观察得出的结论，整个漏斗收敛非常快，比如首页是几千万甚至上亿的结果，到了最下层节点可能只有几千，因此可以考虑一些快速过滤的方法来降低查询计算和数据IO的压力。
如果用一句话总结这个问题的核心本质，那就是“多维分析和序列匹配基础上的去重计数”。具体来说，最终结果就是每层节点符合条件的UUID有多少个，也就是去重后的计数值。这里UUID要符合两个条件，一是符合维度的筛选，二是事件序列能匹配漏斗的定义。去重计数是相对好解的问题，那么问题的重点就是如果快速有效的做维度筛选和序列匹配。
算法设计
下图是部分行为日志的数据，前面已经提到，直接在这样的数据上做维度筛选和序列匹配都是很困难的，因此考虑如何对数据做预处理，以提高执行效率。
可以看到优化后的Key内容保持不变，value被拆成了UUID集合和时间戳序列集合这两部分，这样的好处有两点：一是可以做快速的UUID筛选，通过Key对应的UUID集合运算就可以达成；二是在做时间序列匹配时，对于匹配算法和IO效率都是很友好的，因为时间戳是统一连续存放的，在处理时很方便。
上面解决的是维度筛选的问题，另一个序列匹配的问题相对简单很多。基于上述的数据格式，读取UUID对应的每个事件的时间戳序列，检查是否能按照顺序匹配即可。需要注意的是，由于存在最大时间窗口的限制，匹配算法中需要考虑回溯的情况，下图展示了一个具体的例子。在第一次匹配过程中，由于第一层节点的起始时间戳为100，并且时间窗口为10，所以第二层节点的时间戳101符合要求，但第三层节点的时间戳112超过了最大截止时间戳110，因此只能匹配两层节点，但通过回溯之后，第二次可以完整的匹配三层节点。
这里简单谈一下架构选型的方法论，主要有四点：简单、成熟、可控、可调。
基于上述的选型思路，服务的三个核心架构分别选择了Spring，Spark和Alluxio。其中Spring的应用非常广泛，在实际案例和文档上都非常丰富，很容易落地实现；Spark本身是一个非常优秀的分布式计算框架，目前团队对Spark有很强的掌控力，调优经验也很丰富，这样只需要专注在计算逻辑的开发即可；Alluxio相对HDFS或HBase来说更加轻量，同时支持包括内存在内的多层异构存储，这些特性可能会在后续优化中得到利用。
在具体的部署方式上，Spring Server单独启动，Spark和Alluxio都采用Standalone模式，且两个服务的slave节点在物理机上共同部署。Spring进程中通过SparkContext维持一个Spark长作业，这样接到查询请求后可以快速提交逻辑，避免了申请节点资源和启动Executor的时间开销。
● 本地化调度。存储和计算分离的架构中这是常见的一种优化手段。以下图为例，某个节点上task读取的数据在另外节点上，这样就产生了跨机器的访问，在并发度很大时对网络IO带来了很大压力。如果通过本地化调度，把计算调度到数据的同一节点上执行，就可以避免这个问题。实现本地化调度的前提是有包含数据位置信息的元数据，以及计算框架的支持，这两点在Alluxio和Spark中都很容易做到。
● 内存映射。常规实现中，数据需要从磁盘拷贝到JVM的内存中，这会带来两个问题。一是拷贝的时间很长，几百MB的数据对CPU时间的占用非常可观；二是JVM的内存压力很大，带来GC等一系列的问题。通过mmap等内存映射的方式，数据可以直接读取，不需要再进JVM，这样就很好的解决了上述的两个问题。
● Unsafe调用。由于大部分的数据通过ByteBuffer访问，这里带来的额外开销对最终性能也有很大影响。Java lib中的ByteBuffer访问接口是非常安全的，但安全也意味着低效，一次访问会有很多次的边界检查，而且多层函数的调用也有很多额外开销。如果访问逻辑相对简单，对数据边界控制很有信心的情况下，可以直接调用native方法，绕过上述的一系列额外检查和函数调用。这种用法在很多系统中也被广泛采用，比如Presto和Spark都有类似的优化方法。
上述方案目前在美团点评内部已经实际落地，稳定运行超过半年以上。每天的数据有几百亿条，活跃用户达到了上亿的量级，埋点属性超过了百万，日均查询量几百次，单次查询的TP95时间小于5秒，完全能够满足交互式分析的预期。
原文发布时间为：2018-08-29
本文作者：业锐
