1、美团点评用户行为分析系统的构建与优化美团点评数据平台团队问题分析算法思路工程实现性能优化总结问题背景Growth HackingAcquisition用户获取Activation激活注册Retention活跃留存Referral推荐分享Revenue变现模式转化率转化率分析（有序漏斗）路径：上海品茶-搜索-菜品-下单-支付日期：2017-11-11时间窗口：1小时城市：北京操作系统：iOSpage=下单页 and price 100page=支付成功page=上海品茶page=搜索页 and keyword=中餐page=菜品页2017.11.11北京市iOS1小时数据探查UUIDtimestampp

2、agecitykeywordAAA100上海品茶北京AAA102搜索页北京中餐AAA130菜品页北京BBB102上海品茶北京BBB103上海品茶北京BBB140搜索页北京西餐CCC101上海品茶上海CCC110菜品页上海CCC151搜索页上海中餐直观解法1：Joinselect 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=1510329600 and

3、 timestamp 1510416000 and page=搜索页 and keyword=中餐)t2on t1.id1=t2.id2 and t1.ts1 t2.ts2 and t2.ts2-t1.ts1=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=1510329600 and timestamp 1510416000group by uuid几亿个UUID的聚合没有高效的过滤条件问题难点事

4、件有序序列匹配运算复杂度超过普通的集合运算时间窗口最大长度约束下的序列匹配丰富属性埋点完全开放属性基数超百万维度下钻分析数据规模单天日志数百亿条时间跨度6个月坏消息1.完全随机的漏斗定义-事件组合、时间窗口完全随机-不能实现完全预计算2.不同粒度的深入分析-多个层次维度，事件附加属性-需要OLAP下钻和筛选能力3.规模与性能的矛盾-在海量数据下实现交互式分析好消息1.支持能力：模式相对确定-核心是集合运算和去重计数-不需要完整的SQL能力2.使用场景：查询并发度低-主要是人工探索式分析-可以调度所有资源3.数据特点：入库不会修改-可能构建索引4.业务特点：指标收敛较快-重点分析转化率偏低的场景

5、-可能快速过滤问题本质多维分析和序列匹配下的去重计数实现目标实现多维分析和序列匹配下的去重计数、支持海量数据、交互式响应、可能利用索引或有限预处理等手段、充分利用资源的算法和系统问题分析算法思路工程实现性能优化总结对应策略实现多维分析和序列匹配下的去重计数、支持海量数据、交互式响应、可能利用索引或有限预处理等手段、充分利用资源的算法和系统根据多个维度做筛选UUID内事件按照时间排序漏斗每层节点符合条件的UUID计数数据探查UUIDtimestamppagecitykeywordAAA100上海品茶北京AAA102搜索页北京中餐AAA130菜品页北京BBB102上海品茶北京BBB103上海品茶北京BBB14

6、0搜索页北京西餐CCC101上海品茶上海CCC110菜品页上海CCC151搜索页上海中餐UUID的事件没有排序序列匹配困难数据整理UUIDevent1event2event3 event nAAAts=100 page=上海品茶 city=北京ts=102 page=搜索页 city=北京 keyword=中餐ts=130 page=菜品页 city=北京BBBts=102 page=上海品茶 city=北京 ts=103 page=上海品茶 city=北京ts=140 page=搜索页 city=北京 keyword=西餐CCCts=101 page=上海品茶 city=上海ts=110 page=菜品页 ci

7、ty=上海ts=151 page=搜索页 city=上海 keyword=中餐需要遍历每个UUID维度筛选和序列匹配都很慢构建索引keyvalue1value2value3 value npage=上海品茶UUID=AAA ts=100UUID=BBB ts=102UUID=CCC ts=101UUID=BBB ts=103page=搜索页UUID=AAA ts=102UUID=BBB ts=140UUID=CCC ts=151page=菜品页UUID=CCC ts=110UUID=AAA ts=130city=北京UUID=AAA ts=100UUID=AAA ts=102UUID=BBB ts

8、=102UUID=BBB ts=103city=上海UUID=CCC ts=101UUID=CCC ts=110UUID=CCC ts=151keyword=维度对应的UUID集合需遍历序列匹配更困难索引优化keyUUID collectionsequencepage=上海品茶AAA,BBB,CCCAAA(100),BBB(102,103),CCC(101)page=搜索页AAA,BBB,CCCAAA(102),BBB(140),CCC(151)page=菜品页AAA,CCCAAA(130),CCC(110)city=北京AAA,BBBAAA(100,102,130),BBB(102,103,14

9、0)city=上海CCCCCC(101,110,151)keyword=基于UUID集合快速过滤，迅速收敛UUID对应的时间序列集中读取索引设计Index File page=?bitmap:1,3,5,7,9,1:1493568000,1493609880,3:1493696280,1493699880,page=?bitmap:2,4,6,8,10,.2:1493568722,1493609873,.4:1493620787,1493669382,.keyword=?bitmap:1,2,3,5,7,.1:1493568000,1493609880,.2:1493568722,149360

10、9873,.Trailer page=?:0,12768 page=?:12768,2394 keyword=?:15162,379105.UUID Collection?Bitmap?UUID?sequence?0 12768 15162 组合索引expr:page=上海品茶,expr:page=搜索页 and keyword in(中餐,西餐)”,expr:page=菜品页?page=?AND?child=2?page=?OR?child=2?keyword=?keyword=?page=?查询过程?page=?UUID?page=?UUID?page=?UUID?序列匹配“startTime

11、stamp”:100,“endTimestamp”:130,“maxWindow”:10 page=?AAA?page=?AAA?page=?AAA?100 110 115 120 130 140 150 90 85 99 101 106 120 116 114 95 100 112 113 115 140 核心思路查询条件维度筛选的表达基于bitmap快速过滤通过时间戳序列匹配多个维度表达为AND/OR组合条件转换为索引树维度间的过滤节点间的过滤非常适合快速收敛匹配过程需要回溯索引构建按照属性值分别构建索引包括bitmap和sequence两部分问题分析算法思路工程实现性能优化总结具体需求分

12、布式REST服务计算框架文件系统架构权衡简单易用快速落地简单成熟稳定应用广泛生态活跃成熟掌控能力深度定制可控工程优化持续迭代可调实际选择应用广泛文档丰富简单易用Netty/JettySpring分布式调度框架掌控力强可高度定制专注逻辑MapReduceSpark部署简单相对轻量级异构存储性能优化空间HDFS/HBaseAlluxio整体架构Slave Alluxio Worker Spark Worker Slave Alluxio Worker Spark Worker Slave Alluxio Worker Spark Worker Master Alluxio Master Spark

13、 Master REST Server SparkContext Query Request 工程要点查询条件属性表达树的组合基于Bitmap快速过滤通过时间戳序列匹配采用Json格式REST服务接收请求Antlr解析条件生成表达树使用RoaringBitmap易用，快速采用差值存储平均长度由8字节降到1.5字节问题分析算法思路工程实现性能优化总结核心关注眼镜有效Profiling手段JStack/JStatJMap/JHatMAT/JMC尺子可量化的指标时延/吞吐JVM内存GC方法热点资源利用率CPU内存磁盘网络基本优化：几分钟数据按照UUID分区Spark长作业Slave Alluxio

14、Worker Spark Worker Slave Alluxio Worker Spark Worker Slave Alluxio Worker Spark Worker Master Alluxio Master Spark Master REST Server SparkContext Query Request 本地化调度：分钟内Slave Slave Master Alluxio Master Spark Master 2 1 3 4 1 4 2 3 Slave Slave Master Alluxio Master Spark Master 2 1 3 4 3 4 1 2 内存映

15、射：10秒内Slave 2 1 2 2 Slave 2 1 2 Unsafe调用：5秒内UserCode ByteBuffer.getInt()JavaLibrary getInt(ix(nextGetIndex(1 2)NativeCode public native int getInt(long var1)UserCode Slice.getIntUnchecked()NativeCode public native int getInt(long var1)优化历程时间（秒）0000常规UDAF高效索引架构本地化调度内存映射Unsafe调用3问题分析算法思路工程实现性能优化总结发展现状数百亿事件亿级UV超百万属性埋点数百次查询TP95小于5秒方法总结项目阶段方法要点实际应用需求分析理解问题本质 基于本质确定目标有序漏斗的本质理解 在此基础上确定实现目标算法设计正反分析，确定边界 问题拆解与转化，方案借鉴坏消息和好消息 直观解法入手，逐步优化思路工程实现选型权衡的原则和方法简单、成熟、可控、可调优化迭代眼镜和尺子 持续抓瓶颈Profiling手段和可量化的指标 常见的可能瓶颈和对应优化方法未来规划代码开源，社区共建功能与性能的迭代-留存统计和路径分析-更高的执行效率-更紧凑的存储格式-更合理的系统架构