用户行为分析是数据分析中非常重要的内容。它在统计活跃用户、分析保留率和转化率、改善产品体验、促进用户增长等领域发挥着重要作用。美团评论每天收集数百亿用户行为日志。如何在大量数据集中快速灵活地分析用户行为已成为一个巨大的挑战。为此，我们提出并实现了一套面向大量数据的用户行为分析解决方案，将单次分析的耗时从小时减少到秒，大大提高了分析经验，提高了分析师的工作效率。

本文以有序漏斗的需求为例，详细介绍了问题分析和思路设计，以及项目实现和优化的全过程。根据2017年12月ArchSummit北京站演讲整理而成，略有删改。

问题分析

下图描述了转换率分析中的一个常见场景，分析了访问路径主页-搜索-菜肴-订单-支付，并按顺序访问了每个节点的用户数量，以获得访问过程的转换率。统计数据有一些维度限制，如日期、时间窗口（整个访问过程在规定的时间内完成，否则统计数据无效）、城市或操作系统等，这也是一个典型的例子OLAP分析需求。此外，每个访问节点可能都有埋点属性，如搜索页面上的关键字属性、支付页面的价格属性等。从结果来看，用户数量逐层收敛，形成漏斗的可视化形状，因此这种需求也被称为有序漏斗。

这种分析通常是基于用户行为的日志表，每行数据记录用户事件的相关信息，包括发生时间和用户ID、事件类型、相关属性和维度信息等。业内流行的解决方案通常有两种。

基于Join的SQL

timestamp ts3 from data where timestamp >= 1510329600 and timestamp < 1510416000 and page = '菜品') t3on t1.id1 = t3.id3 and t2.ts2 < t3.ts3 and t1.ts1 < t3.ts3 and t3.ts3 - t1.ts1 < 3600timestamp ts3 from data where timestamp >= 1510329600 and timestamp < 1510416000 and page = '菜品') t3on t1.id1 = t3.id3 and t2.ts2 < t3.ts3 and t1.ts1 < t3.ts3 and t3.ts3 - t1.ts1 < 3600

基于UDAF(User Defined Aggregate Function)的SQL

               select funnel(timestamp,3600,'首页') stage0, funnel(timestamp,3600,'首页','搜索',keyword = '中餐') stage1,funnel(timestamp,3600,'首页','搜索','菜品') stage2 from data where timestamp >= 1510329600 and timestamp < 1510416000 group by uuid

对于第一个解决方案，最大的问题是需要做很多join除操作外，相关条件ID除了等值连接，还有时间戳的非等值连接。当数据规模较小时，此用法没有问题。但随着数据规模的扩大，在数百亿的数据集中join操作成本很高，甚至不可行。

第二种解法有了改进，通过聚合的方式避免了join通过操作将聚合数据改为UDAF做数据匹配。这种解决方案的问题是没有足够的筛选方法，这意味着数亿用户对应的数亿数据需要遍历筛选，性能难以接受。

那么这个问题的难点困难呢？为什么上述两种解决方案在实际应用中变得越来越不可行？主要问题有几点。

事件匹配有序列关系。如果没有序列关系，通过 很容易** 的交集和集合操作。时间窗口限制。这意味着事件匹配的最大长度限制，因此匹配算法的复杂性将进一步提高。对属性和维度的要求。SDK提供给每个业务线，每个页面的具体内容完全由业务决定，价值完全开放，因此属性基数已达到数百万水平。还有几十个维度可以用来筛选，有些维度的基础也很高。数据规模。目前，每天收集数百亿用户行为日志，这对资源和效率都是一个巨大的挑战。

基于对上述困难和实际需求的分析，可以总结出几个实际困难，称为坏消息。

漏斗定义完全随机。不同分析需求对应的漏斗定义完全不同，包括具体包含哪些事件，这些事件的顺序等，这意味着完全的预计算是不可能的。附加OLAP需求。除路径匹配外，还需要在属性和维度上满足要求OLAP上下钻的需求。规模和性能之间的矛盾。一方面，数百亿数据的规模很大，另一方面，它追求交互式分析效率的秒响应，这是一个非常激烈的冲突。

另一方面，在设计和优化中也可以从问题分析中得到一些好消息。

计算需求非常单一。这种需求最终需要的是重新计数的结果，这意味着没有大而完整的数据引擎，在设计上有很大的优化空间。并发性需求不高。漏斗分析等需求一般由操作人员或产品学生手动提交，辅助决策采用查询结果，并发度不高，可在查询过程中充分调动整个集群的资源。数据是不可变的。所谓的日志是事实，一旦收集到用户行为的日志，除非bug原因一般不会更新。基于此，我们可以考虑一些索引手段来加速查询。实际业务特点。最后，从实际业务观察中得出的结论是，整个漏斗收敛非常快。例如，主页是数千万甚至数亿的结果，最低节点可能只有数千个。因此，可以考虑一些快速过滤方法来减少查询计算和数据IO的压力。

如果用一句话来总结这个问题的核心本质，那就是基于多维分析和序列匹配的去重计数。具体来说，最终结果是每个节点都符合条件UUID有多少，也就是去重后的计数值。UUID要满足两个条件，一个是符合维度的筛选，另一个是事件序列可以匹配漏斗的定义。重量计数是一个相对容易解决的问题，所以问题的重点是快速有效地进行维度筛选和序列匹配。

算法设计

下图显示了一些行为日志的数据。正如前面提到的，很难直接进行维度筛选和序列匹配。因此，考虑如何预处理数据以提高执行效率。

基于自然的想法UUID做聚合，按时间排序，这也是前面提到的UDAF想法如下图所示。这里的问题是没有过滤的手段，每个UUID都需要遍历，成本很高。

此外，为了更快更方便地进行过滤，考虑提取维度和属性构成Key，把对应的UUID与时间戳组织形成value。如果你有搜索引擎的经验，很容易看出这很像倒排的想法。

这个数据结构还是有问题的。例如，获得某个数据。Key对应的UUID当列表需要遍历所有列表时value可以。再比如匹配时间序列，这里的时间戳信息被打散，实际处理起来比较困难。因此，可以在此基础上进行优化。

优化后可以看到Key内容保持不变，value被拆成了UUID ** 和时间戳序列 ** 这两部分有两个好处:一是可以快速做到。UUID筛选，通过Key对应的UUID ** 运算可以实现；第二，在匹配时间序列时，匹配算法和IO效率很友好，因为时间戳是统一连续存放的，处理起来很方便。

基于上述思路，最终索引格式如下图所示。每个色块对应一个索引block，包括属性名和取值三部分；二是对应UUID ** ，数据通过bit ** p快速筛选时，格式存储效率高；第三，每个UUID用于序列匹配的相应时间戳序列，在存储过程中使用差值或变长编码等编码压缩手段，提高存储效率。

在实际应用中，通常同时指定多个属性或维度条件AND或OR组织条件。这在处理过程中也很简单。通过语法分析，查询条件可以转化为表达树。树上的叶节点对应单个索引数据，非叶节点是AND或OR类型索引，通过并集或交集的思路做 ** 筛选和序列匹配。

以上解决了维度筛选问题，另一个序列匹配问题相对简单。基于上述数据格式，读取UUID检查每个事件的时间戳序列是否可以按顺序匹配。需要注意的是，由于最大时间窗口的限制，在匹配算法中需要考虑可追溯性，下图显示了一个具体的例子。在第一次匹配过程中，由于第一层节点的起始时间戳为100，时间窗口为10，第二层节点的时间戳为101，但第三层节点的时间戳超过最大截止时间戳110，只能匹配两层节点，但可追溯性后，第二次可以完全匹配三层节点。

通过上述讨论和设计，完整的算法如下图所示。核心点是先通过UUID ** 做快速的过滤，再对过滤后的UUID分别匹配时间戳，上节点输出也作为下节点输入，从而达到快速过滤的目的。

实现和优化工程

有了明确的算法理念，让我们来看看项目是如何实施的。首先，明确需要一个分布式服务，主要包括接口服务、计算框架和文件系统。接口服务用于接收查询请求、分析请求和生成实际查询逻辑；分布式执行查询逻辑的计算框架；文件系统存储实际索引数据以响应具体查询。

这里简单谈一下架构选型的方 ** ，主要有四点：简单、成熟、可控、可调。.简单。无论是架构设计、逻辑复杂性还是运维成本，都希望尽可能简单。这样的系统可以快速着陆，更容易控制。.成熟。评估一个系统是否成熟有很多方面，比如社区是否活跃，项目是否有明确的发展计划并可持续实施？另一个例子是，行业是否有足够的成功案例，实际应用效果如何？成熟的系统着陆问题相对较少，问题也可以很容易地参考其他案例来解决，从而大大降低了整个系统的风险。.可控。如果系统继续保持黑盒状态，则只能被动使用，问题难以解决。相反，现在有很多开源项目可以获得完整的代码，具有更强的控制能力，更容易实现问题的定位、修改、定制、优化等。.可调。一个设计良好的系统必须在架构上分层和模块化，并且具有合理的抽象性。在这种架构下，进一步定制或替换一些逻辑更方便，无需大规模更改代码，降低了更改成本和错误概率。

基于上述选型思路，分别选择了服务的三个核心架构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等一系列的问题。通过m ** p等内存映射的方式，数据可以直接读取，不需要再进JVM，这样就很好的解决了上述的两个问题。Unsafe调用。由于大部分的数据通过ByteBuffer访问，这里带来的额外开销对最终性能也有很大影响。Java lib中的ByteBuffer访问接口是非常安全的，但安全也意味着低效，一次访问会有很多次的边界检查，而且多层函数的调用也有很多额外开销。如果访问逻辑相对简单，对数据边界控制很有信心的情况下，可以直接调用native方法，绕过上述的一系列额外检查和函数调用。这种用法在很多系统中也被广泛采用，比如Presto和Spark都有类似的优化方法。

下图是对上述优化过程的对比展示。请注意纵轴是对数轴，也就是说图中每格代表了一个数据级的优化。从图中可以看到，常规的UDAF方案一次查询需要花几千秒的时间，经过索引结构的设计、本地化调度、内存映射和Unsafe调用的优化过程之后，一次查询只需要几秒的时间，优化了3~4个数据级，完全达到了交互式分析的需求。

这里想多谈几句对这个优化结果的看法。主流的大数据生态系统都是基于JVM系语言开发的，包括Hadoop生态的Java，Spark的Scala等等。由于JVM执行机制带来的不可避免的性能损失，现在也有一些基于C++或其它语言开发的系统，有人宣称在性能上有几倍甚至几十倍的提升。这种尝试当然很好，但从上面的优化过程来看，整个系统主要是通过更高效的数据结构和更合理的系统架构达到了3个数量级的性能提升，语言特性只是在最后一步优化中有一定效果，在整体占比中并不多。

有一句鸡汤说“以大多数人的努力程度而言，根本没有到拼天赋的地步”，套用在这里就是“以大多数系统的架构设计而言，根本没有到拼语言性能的地步”。语言本身不是门槛，代码大家都会写，但整个系统的架构是否合理，数据结构是否足够高效，这些设计依赖的是对问题本质的理解和工程上的权衡，这才是更考量设计能力和经验的地方。

总结

上述方案目前在美团点评内部已经实际落地，稳定运行超过半年以上。每天的数据有几百亿条，活跃用户达到了上亿的量级，埋点属性超过了百万，日均查询量几百次，单次查询的TP95时间小于5秒，完全能够满足交互式分析的预期。

整个方案从业务需求的实际理解和深入分析出发，抽象出了维度筛选、序列匹配和去重计数三个核心问题，针对每个问题都给出了合理高效的解决方案，其中结合实际数据特点对数据结构的优化是方案的最大亮点。在方案的实际工程落地和优化过程中，秉持“简单、成熟、可控、可调”的选型原则，快速落地实现了高效架构，通过一系列的优化手段和技巧，最终达成了3~4个数量级的性能提升。

作者简介

业锐，2015年加入美团，现任美团点评数据平台查询引擎团队负责人。主要负责数据生产和查询引擎的改进优化和落地应用，专注于分布式计算，OLAP分析，Adhoc查询等领域，对分布式存储系统亦有丰富经验。

发现文章有错误、对内容有疑问，都可以关注美团点评技术团队微信公众号（meituantech），在后台给我们留言。我们每周会挑选出一位热心小伙伴，送上一份精美的小礼品。快来扫码关注我们吧！

http://weixin.qq.com/r/9HVSSg3EOFBHrUkp9yDm (二维码自动识别)