您当前的位置:首页 > 电脑百科 > 程序开发 > 架构

大厂架构:每天数百亿用户行为数据,美团怎么实现秒级转化分析?

时间:2019-10-16 11:22:21  来源:  作者:

导读

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

本文以有序漏斗的需求为例,详细介绍了问题分析和思路设计,以及工程实现和优化的全过程。

问题分析

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

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

大厂架构:每天数百亿用户行为数据,美团怎么实现秒级转化分析?

 

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

  1. 基于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
  1. 基于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做数据匹配。这种解法的问题是没有足够的筛选手段,这意味着几亿用户对应的几亿条数据都需要遍历筛选,在性能上也难以接受。

那么这个问题的难点在哪里?为什么上述两个解法在实际应用中变得越来越不可行?主要问题有这么几点。

  1. 事件匹配有序列关系。如果没有序列关系就非常容易,通过集合的交集并集运算即可。
  2. 时间窗口约束。这意味着事件匹配的时候还有最大长度的约束,所以匹配算法的复杂度会进一步提升。
  3. 属性和维度的需求。埋点SDK提供给各个业务线,每个页面具体埋什么内容,完全由业务决定,而且取值是完全开放的,因此目前属性基数已经达到了百万量级。同时还有几十个维度用于筛选,有些维度的基数也很高。
  4. 数据规模。目前每天收集到的用户行为日志有几百亿条,对资源和效率都是很大的挑战。

基于上述难点和实际需求的分析,可以总结出几个实际困难,称之为“坏消息”。

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

另一方面,还是能够从问题的分析中得到一些“好消息”, 这些也是在设计和优化中可以利用的点。

  1. 计算需求非常单一。这个需求最终需要的就是去重计数的结果,这意味着不需要一个大而全的数据引擎,在设计上有很大的优化空间。
  2. 并发需求不高。漏斗分析这类需求一般由运营或者产品同学手动提交,查询结果用于辅助决策,因此并发度不会很高,这样可以在一次查询时充分调动整个集群的资源。
  3. 数据不可变。所谓日志即事实,用户行为的日志一旦收集进来,除非bug等原因一般不会再更新,基于此可以考虑一些索引类的手段来加速查询。
  4. 实际业务特点。最后是对实际业务观察得出的结论,整个漏斗收敛非常快,比如首页是几千万甚至上亿的结果,到了最下层节点可能只有几千,因此可以考虑一些快速过滤的方法来降低查询计算和数据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的时间开销。

大厂架构:每天数百亿用户行为数据,美团怎么实现秒级转化分析?

 

上述架构通过对数据的合理分区和资源的并发利用,可以实现一个查询请求在几分钟内完成。相对原来的几个小时有了很大改观,但还是不能满足交互式分析的需求,因此还需要做进一步的优化。

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

大厂架构:每天数百亿用户行为数据,美团怎么实现秒级转化分析?

 

2.内存映射。常规实现中,数据需要从磁盘拷贝到JVM的内存中,这会带来两个问题。一是拷贝的时间很长,几百MB的数据对CPU时间的占用非常可观;二是JVM的内存压力很大,带来GC等一系列的问题。通过mmap等内存映射的方式,数据可以直接读取,不需要再进JVM,这样就很好的解决了上述的两个问题。

大厂架构:每天数百亿用户行为数据,美团怎么实现秒级转化分析?

 

3.Unsafe调用。由于大部分的数据通过ByteBuffer访问,这里带来的额外开销对最终性能也有很大影响。JAVA lib中的ByteBuffer访问接口是非常安全的,但安全也意味着低效,一次访问会有很多次的边界检查,而且多层函数的调用也有很多额外开销。如果访问逻辑相对简单,对数据边界控制很有信心的情况下,可以直接调用native方法,绕过上述的一系列额外检查和函数调用。这种用法在很多系统中也被广泛采用,比如Presto和Spark都有类似的优化方法。

大厂架构:每天数百亿用户行为数据,美团怎么实现秒级转化分析?

 

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

总结

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

大厂架构:每天数百亿用户行为数据,美团怎么实现秒级转化分析?

 

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

作者简介

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

---------- END ----------

文章转载自公众号 美团技术团队 , 作者 业锐



Tags:美团   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
今天我们介绍写作最重要的两个落地场景:一个是文档沉淀。走进美团的内网,你会惊叹于美团人如此完整、准确、详细的书面化了一切体系的由来和发展步骤。另一个就是开会。没错,美...【详细内容】
2021-12-22  Tags: 美团  点击:(6)  评论:(0)  加入收藏
快快快!拿起手机在设置里面找到“记录APP活动”或“权限访问记录”功能,看看你被美团、淘宝、支付宝偷窥了多少次。APP疯狂定位、读取数据这事最先是被一位网友发现的,他在手机...【详细内容】
2021-10-15  Tags: 美团  点击:(31)  评论:(0)  加入收藏
赶在双11前夕,京东发布了全新的即时零售品牌“小时购”。消费者下单带有“小时购”标识的商品后,系统会基于LBS周边3-5公里的门店发货,从而实现1小时内配送到家。供给端,小时购...【详细内容】
2021-10-14  Tags: 美团  点击:(40)  评论:(0)  加入收藏
美团月付类似于支付宝的花呗一样,可以先下单购买商品,在每个月的八号可以支付订单,那我们使用的美团月付还款日可以更改吗,在哪里可以该还款日金额呢,下面就和小编一起来看看吧!美...【详细内容】
2021-09-08  Tags: 美团  点击:(86)  评论:(0)  加入收藏
当我们在开启美团月付功能时,每个月消费的订单将会在次月的1日直接出消费账单,如果在8号前未支付上个月的月付账单,将会自动还款,那在哪里可以关闭美团月付自动还款功能呢,下面就...【详细内容】
2021-09-08  Tags: 美团  点击:(52)  评论:(0)  加入收藏
偏安一隅并不安全,进攻才是最好的防守。所谓 " 超级 App",指的是将多元化的业务功能融合在一个大 App 平台上,这是移动互联网发展至今所形成的主流趋势。比如支付宝、微信除了...【详细内容】
2021-08-11  Tags: 美团  点击:(74)  评论:(0)  加入收藏
美团我是在拉勾网上投的简历,之前也投过一次,简历都没通过筛选,后来让学姐帮我改了一下简历,重新投另一个部门,获得了面试机会。...【详细内容】
2021-05-26  Tags: 美团  点击:(187)  评论:(0)  加入收藏
在历经股价十连跌,以及因外包骑手社保缴纳模式引发的舆论风波后,美团向商家示好,调整了佣金抽成。在反垄断调查结果出来前,先树立一个良好态度,祈求不要把从前吃进去的再吐出来,恐怕这就是美团眼下所想。...【详细内容】
2021-05-18  Tags: 美团  点击:(134)  评论:(0)  加入收藏
“一套代码,多端运行。”是很多开发团队的梦想,直到 2018 年 12 月 5 日,谷歌正式发布 Flutter 1.0 版本,前端开发者向这一梦想前进了一大步。Flutter 仅用了不到一年的时间就在...【详细内容】
2020-12-09  Tags: 美团  点击:(150)  评论:(0)  加入收藏
互联网大公司负责进货,让小区有人缘的宝妈,也就是所谓的团长,囤货、卖货,社区团购这个生意已经热闹到,原菜鸟网络副总裁史苗顶着竞业协议,也要去创业做个竞品。今年年中起,滴滴出...【详细内容】
2020-12-02  Tags: 美团  点击:(135)  评论:(0)  加入收藏
▌简易百科推荐
为了构建高并发、高可用的系统架构,压测、容量预估必不可少,在发现系统瓶颈后,需要有针对性地扩容、优化。结合楼主的经验和知识,本文做一个简单的总结,欢迎探讨。1、QPS保障目标...【详细内容】
2021-12-27  大数据架构师    Tags:架构   点击:(5)  评论:(0)  加入收藏
前言 单片机开发中,我们往往首先接触裸机系统,然后到RTOS,那么它们的软件架构是什么?这是我们开发人员必须认真考虑的问题。在实际项目中,首先选择软件架构是非常重要的,接下来我...【详细内容】
2021-12-23  正点原子原子哥    Tags:架构   点击:(7)  评论:(0)  加入收藏
现有数据架构难以支撑现代化应用的实现。 随着云计算产业的快速崛起,带动着各行各业开始自己的基于云的业务创新和信息架构现代化,云计算的可靠性、灵活性、按需计费的高性价...【详细内容】
2021-12-22    CSDN  Tags:数据架构   点击:(10)  评论:(0)  加入收藏
▶ 企业级项目结构封装释义 如果你刚毕业,作为Java新手程序员进入一家企业,拿到代码之后,你有什么感觉呢?如果你没有听过多模块、分布式这类的概念,那么多半会傻眼。为什么一个项...【详细内容】
2021-12-20  蜗牛学苑    Tags:微服务   点击:(9)  评论:(0)  加入收藏
我是一名程序员关注我们吧,我们会多多分享技术和资源。进来的朋友,可以多了解下青锋的产品,已开源多个产品的架构版本。Thymeleaf版(开源)1、采用技术: springboot、layui、Thymel...【详细内容】
2021-12-14  青锋爱编程    Tags:后台架构   点击:(21)  评论:(0)  加入收藏
在了解连接池之前,我们需要对长、短链接建立初步认识。我们都知道,网络通信大部分都是基于TCP/IP协议,数据传输之前,双方通过“三次握手”建立连接,当数据传输完成之后,又通过“四次挥手”释放连接,以下是“三次握手”与“四...【详细内容】
2021-12-14  架构即人生    Tags:连接池   点击:(17)  评论:(0)  加入收藏
随着移动互联网技术的快速发展,在新业务、新领域、新场景的驱动下,基于传统大型机的服务部署方式,不仅难以适应快速增长的业务需求,而且持续耗费高昂的成本,从而使得各大生产厂商...【详细内容】
2021-12-08  架构驿站    Tags:分布式系统   点击:(23)  评论:(0)  加入收藏
本系列为 Netty 学习笔记,本篇介绍总结Java NIO 网络编程。Netty 作为一个异步的、事件驱动的网络应用程序框架,也是基于NIO的客户、服务器端的编程框架。其对 Java NIO 底层...【详细内容】
2021-12-07  大数据架构师    Tags:Netty   点击:(17)  评论:(0)  加入收藏
前面谈过很多关于数字化转型,云原生,微服务方面的文章。虽然自己一直做大集团的SOA集成平台咨询规划和建设项目,但是当前传统企业数字化转型,国产化和自主可控,云原生,微服务是不...【详细内容】
2021-12-06  人月聊IT    Tags:架构   点击:(23)  评论:(0)  加入收藏
微服务看似是完美的解决方案。从理论上来说,微服务提高了开发速度,而且还可以单独扩展应用的某个部分。但实际上,微服务带有一定的隐形成本。我认为,没有亲自动手构建微服务的经历,就无法真正了解其复杂性。...【详细内容】
2021-11-26  GreekDataGuy  CSDN  Tags:单体应用   点击:(35)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条