美团-百亿用户行为数据，美团点评如何实现秒级转化剖析

　　用户行为剖析是数据剖析中十分重要的一项内容，在统计活跃用户，分析存留和转化率，改进产品体验、推动用户下降等领域有重要作用。美团点评每晚搜集的用户行为日志达到数百亿条，如何在海量数据集上实现对用户行为的快速灵活剖析，成为一个巨大的挑战。为此，我们提出并实现了一套面向海量数据的用户行为剖析解决方案，将单次剖析的历时从小时级增加到秒级，极大的改善了剖析体验，提升了剖析人员的工作效率。

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

　　问题剖析

　　下图描述了转化率剖析中一个常见场景，对访问路径“首页-搜索-菜品-下单-支付”做剖析，统计根据次序访问每层节点的用户数，得到访问过程的转化率。

　　统计上有一些维度约束，比如日期，时间窗口（整个访问过程在规定时间内完成，否则统计无效），城市或操作系统等，因此这也是一个典型的OLAP剖析需求。此外，每个访问节点可能还有埋点属性，比如搜索页上的关键词属性，支付页的价钱属性等。从结果上看，用户数是逐层收敛的，在可视化上构成了一个漏斗的形状，因此这一类需求又称之为“有序漏斗”。

　　

　　这类剖析一般是基于用户行为的日志表上进行的，其中每行数据记录了某个用户的一次风波的相关信息，包括发生时间、用户ID、事件类型以及相关属性和维度信息等。现在业界流行的一般有两种解决思路。

　　基于Join的SQL

　　select count (distinct t1.id1), count (distinct t2.id2), count (distinct t3.id3)

from (select uuid id1, timestamp ts1 from data where timestamp >= 1510329600 and timestamp < 1510416000 and page = '首页') t1

left join

(select uuid id2, timestamp ts2 from data where timestamp >= 1510329600 and timestamp < 1510416000 and page = '搜索' and keyword = '中餐') t2

on t1.id1 = t2.id2 and t1.ts1 < t2.ts2 and t2.ts2 - t1.ts1 < 3600

left join

(select uuid id3, timestamp ts3 from data where timestamp >= 1510329600 and timestamp < 1510416000 and page = '菜品') t3

on 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集合，数据通过bitmap格式储存，在快速筛选时效率很高；三是每位UUID对应的时间戳序列，用于序列匹配，在储存时使用差值或变长编码等一些编码压缩手段提升储存效率。

　　

　　在实际应用中，通常会同时指定多个属性或维度条件，通过AND或OR的条件组织上去。这在处理时也很简单，通过句型剖析可以把查询条件转为一颗抒发树，树上的叶子节点对应的是单个索引数据，非叶子节点就是AND或OR类型的索引，通过并集或交集的思路做集合筛选和序列匹配即可。

　　上面解决的是维度筛选的问题，另一个序列匹配的问题相对简单好多。基于上述的数据格式，读取UUID对应的每位风波的时间戳序列，检查是否能依照次序匹配即可。需要注意的是，由于存在最大时间窗口的限制，匹配算法中须要考虑回溯的情况，下图展示了一个具体的反例。在第一次匹配过程中，由于第一层节点的起始时间戳为100，并且时间窗口为10，所以第二层节点的时间戳101符合要求，但第三层节点的时间戳112超过了最大截至时间戳110，因此只能匹配两层节点，但通过回溯以后，第二次可以完整的匹配三层节点。

　　

　　通过上述的讨论和设计，完整的算法如下图所示。其中的核心要点是先通过UUID集合做快速的过滤，再对过滤后的UUID分别做时间戳的匹配，同时上一层节点输出也作为下一层节点的输入，由此达到快速过滤的目的。

　　

　　工程实现和优化

　　有了明晰的算法思路，接下来再瞧瞧工程怎么落地。

　　首先明晰的是须要一个分布式的服务，主要包括插口服务、计算框架和文件系统三部份。其中插口服务用于接收查询恳求，分析恳求并生成实际的查询逻辑；计算框架用于分布式的执行查询逻辑；文件系统储存实际的索引数据，用于响应具体的查询。

　　这里简单谈一下构架选型的方法论，主要有四点：简单、成熟、可控、可调。

　　1.简单。不管是构架设计，还是逻辑复杂度和运维成本，都希望尽可能简单。这样的系统可以快速落地，也比较容易掌控。

　　2.成熟。评估一个系统是否成熟有很多方面，比如社区是否活跃，项目是否有明晰的发展规划并能持续落地推动？再例如业界有没有足够多的成功案例，实际应用疗效怎样？一个成熟的系统在落地时的问题相对较少，出现问题也能参考其它案例比较容易的解决，从而很大程度上增加了整体系统的风险。

　　3.可控。如果一个系统持续保持黑盒的状态，那只能是被动的使用，出了问题也很难解决。反之现今有很多的开源项目，可以领到完整的代码，这样就可以有更强的掌控力，不管是问题的定位解决，还是更改、定制、优化等，都更容易实现。

　　4.可调。一个设计良好的系统，在构架上一定是分层和模块化的，且有合理的具象。在这样的构架下，针对其中一些逻辑做进一步订制或替换时就比较便捷，不需要对代码做大范围的改动，降低了改建成本和出错机率。

　　基于上述的选型思路，服务的三个核心构架分别选择了Spring，Spark和Alluxio。其中Spring的应用十分广泛，在实际案例和文档上都十分丰富，很容易落地实现；Spark本身是一个特别优秀的分布式估算框架，目前团队对Spark有太强的掌控力，调优经验也太丰富，这样只须要专注在估算逻辑的开发即可；Alluxio相对HDFS或HBase来说愈发轻量，同时支持包括显存在内的多层异构储存，这些特点可能会在后续优化中得到借助。

　　在具体的布署形式上，Spring Server单独启动，Spark和Alluxio都采用Standalone模式，且两个服务的slave节点在化学机上共同布署。Spring进程中通过SparkContext维持一个Spark长作业，这样接到查询恳求后可以快速递交逻辑，避免了申请节点资源和启动Executor的时间开支。

　　

　　上述构架通过对数据的合理分区和资源的并发借助，可以实现一个查询恳求在几分钟内完成。相对原先的几个小时有了很大改观，但还是不能满*敏*感*词*互式剖析的需求，因此还须要做进一步的优化。

　　本地化调度。存储和估算分离的构架中这是常见的一种优化手段。以下图为例，某个节点上task读取的数据在另外节点上，这样就形成了跨机器的访问，在并发度很大时对网路IO带来了很大压力。如果通过本地化调度，把估算调度到数据的同一节点上执行，就可以避免这个问题。实现本地化调度的前提是有收录数据位置信息的元数据，以及估算框架的支持，这两点在Alluxio和Spark中都很容易做到。

　　

　　内存映射。常规实现中，数据须要从c盘拷贝到JVM的显存中，这会带来两个问题。一是拷贝的时间太长，几百MB的数据对CPU时间的占用特别可观；二是JVM的显存压力很大，带来GC等一系列的问题。通过mmap等显存映射的方法，数据可以直接读取，不需要再进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个数量级的性能提高。