用户个人行为分析是数据信息分析中十分关键的一项內容，在统计分析活跃性用户，分析存留和转换率，改善商品感受、促进用户提高等行业有关键功效。美团点评每日搜集的用户个人行为日志做到数百亿条，怎样在海量信息集在完成对用户个人行为的迅速灵便分析，变成一个极大的挑戰。因此，大家明确提出并达到了一套面对海量信息的用户个人行为分析解决方法，将一次分析的用时从钟头级减少到秒级，巨大的缓解了分析感受，提高了分析工作人员的工作效能。
文中以井然有序布氏漏斗的要求为例子，详解了问题分析和思路设计方案，及其工程项目建立和改进的整个过程。文中依据2017年12月ArchSummit北京站演说梳理而成，略微删减。
问题分析下面的图叙述了转换率分析中一个普遍情景，对访问途径“主页-检索-菜肴-提交订单-付款”做分析，统计分析依照次序访问各层连接点的用户数，获得访问全过程的转换率。统计分析上面有一些层面管束，例如日期，周期时间（全部访问全过程在要求时间段内进行，不然统计分析失效），大城市或电脑操作系统等，因而这也是一个非常典型的OLAP分析要求。除此之外，每一个访问连接点很有可能也有前后端分离属性，例如检索页上的关键字属性，付款页的价钱属性等。从結果上看，用户数是逐级收敛性的，在数据可视化上组成了一个布氏漏斗的样子，因而这一类要求又称作“井然有序布氏漏斗”。
这类分析通常是根据用户个人行为的日志表上实现的，在其中每排数据信息统计了某一用户的一次事情的有关信息，包含产生時间、用户ID、事情种类及其有关属性和层面信息内容等。如今业内时兴的通常有2种处理思路。
根据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 = '主页') t1left join(select uuid id2, timestamp ts2 from data where timestamp >= 1510329600 and timestamp < 1510416000 and page = '检索' and keyword = '午餐') t2on t1.id1 = t2.id2 and t1.ts1 < t2.ts2 and t2.ts2 - t1.ts1 < 3600left join(select uuid id3, 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 < 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做数据匹配。这类打法的问题是没非常的挑选方式，这代表着上亿用户相匹配的上亿条信息都必须解析xml挑选，在功能上也无法接纳。
那麼这个问题的难题在哪儿？为什么以上2个打法在具体运用中显得更加不行得通？关键问题有那么几个方面。
事情配对有编码序列关联。要是没有编码序列关联就很容易，根据 ** 的交集并集计算就可以。周期时间管束。这代表着事情配对的情况下也有较大长短的管束，因此搜索算法的复杂性会进一步提升。属性和层面的要求。前后端分离SDK给予给每个工作线，每一个网页页面实际埋哪些內容，彻底由业务流程决策，并且选值是充分对外开放的，因而现阶段属性数量早已到达了千万数量级。与此同时也有几十个层面用以挑选，有一些层面的数量也很高。数据信息经营规模。现阶段每日搜集到的用户个人行为日志有几十亿条，对資源和高效率是挺大的挑戰。根据以上难题和现实需要的分析，可以归纳出好多个因难，称作“不好的消息”。
布氏漏斗界定彻底任意。不一样分析要求相匹配的布氏漏斗界定彻底不一样，包含实际包括什么事情，这种事情的次序等，这代表着彻底的预估算得上不太可能的。额外OLAP要求。除开途径配对以外，还要达到属性和纬度上一些OLAP的卷起下钻的要求。经营规模和特性的分歧。一方面有几十亿条数据信息的集成电路工艺，另一方面又追求完美秒级回应的互动式分析高效率，这是一个十分强烈的主要矛盾矛盾。另一方面，或是可以从问题的分析中获得一些“喜讯”, 这种也是在设计和提升中可以运用的点。
测算要求十分单一。这一要求最后必须的便是去重复记数的結果，这代表着不用一个专而精的数据信息模块，在设计上面有非常大的提升室内空间。高并发要求不高。布氏漏斗分析这类要求一般由经营或是商品同学们手动式递交，查询记录用以协助管理决策，因而高并发度并不会很高，那样可以在一次查看时不断加强全部群集的資源。数据信息不能变。所说日志即客观事实，用户个人行为的日志一旦搜集进去，除非是bug等因素一般不易再升级，根据此可以考虑到一些数据库索引类的方法来加快查看。具体业务流程特性。最终是对具体业务流程观查得到的结果，全部布氏漏斗收敛性十分快，例如主页是几千万乃至上亿的結果，到了最下一层连接点很有可能仅有好几千，因而可以考虑到一些迅速过虑的办法来减少查看测算和数据信息IO的工作压力。假如用一句话汇总这一根本矛盾实质，那便是“多维度分析和编码序列配对基本上的去重复记数”。从总体上，最后结论便是各层连接点满足条件的UUID有多少个，也就是去重复后的计标值。这儿UUID要合乎2个标准，一是合乎层面的挑选，二是事情编码序列能配对布氏漏斗的界定。去重复记数是相对性好解的问题，那麼问题的重中之重便是假如迅速高效的做层面挑选和编码序列配对。
算法设计下面的图是一部分个人行为日志的数据信息，前边己经提及，立即在那样的信息上做层面挑选和编码序列配对全是很不便的，因而考虑到怎么对数据信息做预备处理，以提升实行高效率。
很肯定的见解是根据UUID做汇聚，依据时间排序，这也是前边提及的UDAF的思路，如下图所示。这儿的问题是沒有过虑的方式，每一个UUID都必须解析xml，成本费很高。
再进一步，为了更好地迅速更便捷的做过虑，考虑到把层面和属性抽离出来组成Key，把相应的UUID和时间格式机构起來组成value。如果有百度搜索引擎工作经验得话，非常容易看出去这十分像倒排的思路。
这一算法设计或是存在的问题。例如要取得某一Key相匹配的UUID目录时，必须解析xml全部的value才可以。再例如做时间序列分析的配对，这儿的时间格式信息内容被拆开了，具体处置起來更艰难。因而还能够在这个基础上再提升。
能够看见提升后的Key內容不变，value被分解成了UUID ** 和时间格式编码序列 ** 这两一部分，那样的作用有二点：一是可以做迅速的UUID挑选，根据Key相匹配的UUID ** 计算就可以达到；二是在做时间序列分析配对时，针对搜索算法和IO高效率全是很和谐的，由于时间格式是统一持续储存的，在解决时很便捷。
根据以上的思路，最后的数据库索引文件格式如下图所示。这儿每一个图形相匹配了一个数据库索引的block，主要包括三部份內容，一是属性名和选值；二是相应的UUID ** ，数据信息根据bit ** p文件格式储存，在迅速挑选时高效率很高；三是每一个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方式，且2个服务项目的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 (二维码自动识别)
扫码咨询与免费使用
申请免费使用