AS北京2017-《美团点评用户行为分析系统的构建与优化》-孙业锐.key

美团点评 用户 行行为分析系统的 构建与优化 孙业锐 美团点评数据平台团队

孙业锐 美团点评 高级技术专家 Apache Kylin PMC 美团点评数据平台查询引擎 方向负责 人 负责数据 生产和查询引擎的改进优化和落地应 用 专注于分布式计算,OLAP 分析,Adhoc 查询等领域 包括但不不限于 Hive SparkSQL Presto Apache Kylin Druid 等

问题分析 算法思路路 工程实现 性能优化 总结

问题背景 Growth Hacking Acquisition Activation Retention Referral Revenue 用户获取 激活注册 活跃留留存 推荐分享 变现模式 转化率

转化率分析 ( 有序漏漏 斗 ) 路路径 : 首 页 - 搜索 - 菜品 - 下单 - 支付 2017.11.11 1 小时北北京市 ios 日期 :2017-11-11 page = 首 页 时间窗 口 :1 小时 page = 搜索 页 and keyword = 中餐 page = 菜品 页 城市 : 北北京 page = 下单 页 and price > 100 操作系统 :ios page = 支付成功

数据探查 UUID timestamp page city keyword AAA 100 首 页 北北京 AAA 102 搜索 页 北北京 中餐 AAA 130 菜品 页 北北京 BBB 102 首 页 北北京 BBB 103 首 页 北北京 BBB 140 搜索 页 北北京 西餐 CCC 101 首 页 上海海 CCC 110 菜品 页 上海海 CCC 151 搜索 页 上海海 中餐

直观解法 1:Join 几亿条数据的多层 Join 代价很 高, 时间很 长 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

直观解法 2:UDAF 几亿个 UUID 的聚合 没有 高效的过滤条件 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

问题难点 事件有序 时间窗 口 丰富属性 数据规模 序列列匹配运算 最 大 长度约束下的 埋点完全开放 单天 日志数百亿条 复杂度超过 序列列匹配 属性基数超百万 时间跨度 6 个 月 普通的集合运算 维度下钻分析

坏消息 1. 完全随机的漏漏 斗定义 3. 规模与性能的 矛盾 - 事件组合 时间窗 口完全随机 - 在海海量量数据下实现交互式分析 - 不不能实现完全预计算 2. 不不同粒度的深 入分析 - 多个层次维度, 事件附加属性 - 需要 OLAP 下钻和筛选能 力力

好消息 1. 支持能 力力 : 模式相对确定 3. 数据特点 : 入库不不会修改 - 核 心是集合运算和去重计数 - 可能构建索引 - 不不需要完整的 SQL 能 力力 2. 使 用场景 : 查询并发度低 4. 业务特点 : 指标收敛较快 - 主要是 人 工探索式分析 - 重点分析转化率偏低的场景 - 可以调度所有资源 - 可能快速过滤

问题本质 多维分析和序列列匹配下的去重计数

实现 目标 实现多维分析和序列列匹配下的去重计数 支持海海量量数据 交互式响应 可能利利 用索引或有限预处理理等 手段 充分利利 用资源的 算法和系统

问题分析 算法思路路 工程实现 性能优化 总结

对应策略略 根据多个维度做 筛选 UUID 内事件 按照时间排序 漏漏 斗每层节点 符合条件的 UUID 计数 实现多维分析和序列列匹配下的去重计数 支持海海量量数据 交互式响应 可能利利 用索引或有限预处理理等 手段 充分利利 用资源的 算法和系统

数据探查 UUID 的事件没有排序 序列列匹配困难 UUID timestamp page city keyword AAA 100 首 页 北北京 AAA 102 搜索 页 北北京 中餐 AAA 130 菜品 页 北北京 BBB 102 首 页 北北京 BBB 103 首 页 北北京 BBB 140 搜索 页 北北京 西餐 CCC 101 首 页 上海海 CCC 110 菜品 页 上海海 CCC 151 搜索 页 上海海 中餐

数据整理理 需要遍历每个 UUID 维度筛选和序列列匹配都很慢 UUID event1 event2 event3 event n AAA ts = 100 page = 首 页 city = 北北京 ts = 102 page = 搜索 页 city = 北北京 keyword = 中餐 ts = 130 page = 菜品 页 city = 北北京 BBB ts = 102 page = 首 页 city = 北北京 ts = 103 page = 首 页 city = 北北京 ts = 140 page = 搜索 页 city = 北北京 keyword = 西餐 CCC ts = 101 page = 首 页 city = 上海海 ts = 110 page = 菜品 页 city = 上海海 ts = 151 page = 搜索 页 city = 上海海 keyword = 中餐

构建索引 维度对应的 UUID 集合需遍历 序列列匹配更更困难 key value1 value2 value3 value n page = 首 页 UUID = AAA ts = 100 UUID = BBB ts = 102 UUID = CCC ts = 101 UUID = BBB ts = 103 page = 搜索 页 UUID = AAA ts = 102 UUID = BBB ts = 140 UUID = CCC ts = 151 page = 菜品 页 UUID = CCC ts = 110 UUID = AAA ts = 130 city = 北北京 UUID = AAA ts = 100 UUID = AAA ts = 102 UUID = BBB ts = 102 UUID = BBB ts = 103 city = 上海海 UUID = CCC ts = 101 UUID = CCC ts = 110 UUID = CCC ts = 151 keyword =

索引优化 基于 UUID 集合快速过滤, 迅速收敛 UUID 对应的时间序列列集中读取 key UUID collection sequence page = 首 页 AAA,BBB,CCC AAA(100), BBB(102,103), CCC(101) page = 搜索 页 AAA,BBB,CCC AAA(102), BBB(140), CCC(151) page = 菜品 页 AAA,CCC AAA(130),CCC(110) city = 北北京 AAA,BBB AAA(100,102,130), BBB(102,103,140) city = 上海海 CCC CCC(101,110,151) keyword =

索引设计 0 12768 15162 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, 1493609873,...... UUID Collection Bitmap UUID sequence Index File Trailer page = : 0, 12768 page = : 12768, 2394 keyword = : 15162, 379105...

组合索引 {"expr": "page = 首 页 "}, {"expr": "page = 搜索 页 and keyword in ( 中餐, 西餐 ) }, {"expr": "page = 菜品 页 "} page = AND child = 2 page = page = OR child = 2 keyword = keyword =

查询过程 page = UUID page = UUID page = UUID

序列列匹配 starttimestamp : 100, endtimestamp : 130, maxwindow : 10 page = AAA 100 110 115 120 130 140 150 page = AAA 90 99 101 106 114 116 120 page = AAA 85 95 100 112 113 115 140

核 心思路路 查询条件 索引构建 维度筛选的表达 基于 bitmap 快速过滤 通过时间戳 序列列匹配 按照属性值分别构建索引包括 bitmap 和 sequence 两部分 多个维度表达为 AND/OR 组合条件 转换为索引树 维度间的过滤 节点间的过滤 非常适合快速收敛 匹配过程需要回溯

问题分析 算法思路路 工程实现 性能优化 总结

具体需求 分布式 REST 服务 计算框架 文件系统

架构权衡 简单 成熟 可控 可调 成熟稳定 简单易易 用 掌控能 力力 工程优化 应 用 广泛 快速落地 深度定制 持续迭代 生态活跃

实际选择 Spring Spark Alluxio 应 用 广泛 文档丰富 简单易易 用 分布式调度框架掌控 力力强可 高度定制专注逻辑 部署简单相对轻量量级异构存储性能优化空间 Netty/Jetty MapReduce HDFS/HBase

整体架构 Master Query Request REST Server SparkContext Spark Master Alluxio Master Slave Spark Worker Slave Spark Worker Slave Spark Worker Alluxio Worker Alluxio Worker Alluxio Worker

工程要点 属性表达树 基于 Bitmap 通过时间戳 查询条件 的组合 快速过滤 序列列匹配 采 用 Json 格式 使 用 采 用差值存储 REST 服务接收 Antlr 解析条件 RoaringBitmap 平均 长度由 8 字节 请求 生成表达树 易易 用, 快速 降到 1.5 字节

问题分析 算法思路路 工程实现 性能优化 总结

核 心关注 眼镜 尺 子 资源利利 用率 JVM 有效 Profiling 手段 CPU 可量量化的指标 内存 内存 GC JStack/JStat 磁盘 时延 / 吞吐 方法热点 JMap/JHat 网络 MAT/JMC

基本优化 : 几分钟 数据按照 UUID 分区 Master Spark 长作业 Query Request REST Server SparkContext Spark Master Alluxio Master Slave Spark Worker Slave Spark Worker Slave Spark Worker Alluxio Worker Alluxio Worker Alluxio Worker

本地化调度 : 分钟内 Master Master Spark Master Spark Master Alluxio Master Alluxio Master Slave Slave Slave Slave 2 3 1 4 1 2 3 4 1 2 3 4 1 2 3 4

内存映射 :10 秒内 Slave Slave 2 2 2 1 2 1 2

Unsafe 调 用 :5 秒内 UserCode ByteBuffer.getInt() UserCode Slice.getIntUnchecked() JavaLibrary getint(ix(nextgetindex((1 << 2)))) NativeCode public native int getint(long var1) NativeCode public native int getint(long var1)

优化历程 10000 5000 1000 时间 ( 秒 ) 100 180 60 10 10 3 1 常规 UDAF 高效索引架构本地化调度内存映射 Unsafe 调 用

问题分析 算法思路路 工程实现 性能优化 总结

发展现状 超百万 亿级 UV 属性埋点 数百亿 事件 数百次 查询 TP95 小于 5 秒

方法总结 项 目阶段 方法要点实际应 用 需求分析 理理解问题本质 基于本质确定 目标 有序漏漏 斗的本质理理解 在此基础上确定实现 目标 算法设计 正反分析, 确定边界 问题拆解与转化, 方案借鉴 坏消息和好消息 直观解法 入 手, 逐步优化思路路 工程实现选型权衡的原则和 方法简单 成熟 可控 可调 优化迭代 眼镜和尺 子 持续抓瓶颈 Profiling 手段和可量量化的指标 常 见的可能瓶颈和对应优化 方法

未来规划 代码开源, 社区共建 功能与性能的迭代 - 留留存统计和路路径分析 - 更更 高的执 行行效率 - 更更紧凑的存储格式 - 更更合理理的系统架构

加 入我们 我们有 近万台机器器, 数百 PB 数据 数 十业务线, 数百分析师 业界突破 :HDFS 异地跨机房,YARN 调度百倍性能提升,Spark 核 心性能优化 我们要 追求极致, 持续深耕的领域专家 充满激情, 挑战 自我的技术新兵 联系 方式 :sunyerui@{meituan.com, gmail.com, apache.org}