易观大赛有序漏斗转化方案学习

  |   0 评论   |   1,853 浏览

背景

2017年,易观举办了OLAP算法大赛。赛题为有序漏斗的计算。具体见参考一,这里引用如下:

“有序漏斗”是易观在产品研发过程中发现的目前整个行业面临的难题。具体来讲,就是在大数据产品研发过程中,有个比较核心的需求叫做“有序漏斗”,是帮助运营人员分析一个多步骤过程中每一步的转化与流失情况。

“有序漏斗”问题定义虽然比较简单,但是计算过程比较复杂。目前市面上现有的解决方案在数据量较大的情况下,计算效率普遍较低。 为了更好的提升产品体验,易观决定将此需求对外公开,广发英雄帖,招募国内数据大牛一起共同解决行业难题。

目前大赛结果已经揭晓,见参考二。本文学习一下其中的算法思路。

漏斗分类

用户网购行为,可视为“浏览商品→加入购物车→生成订单→支付订单→完成支付”路径。路径中每一个节点都存在不同程度的用户流失,层层递减后整体形成漏斗形的模型。

目前公认的计算关键路径方法有两种:无序漏斗和有序漏斗。

无序漏斗

在无序漏斗中,前后事件的发生可任意排序,比如用户在页面间随意切换和返回主页操作,不受步骤间的逻辑顺序约束。

有序漏斗

有序漏斗的每个步骤之间有严格的顺序限制,第二步的事件必须发生在第一步之后。如支付过程中,需要先选择购买之物,才能进入相应的付款操作。

评价

有序漏斗广泛存在于购物支付、信息注册等逻辑层级要求严格的路径行为中。相较用户路径重合率极低的无序漏斗,有序漏斗的数据研究更有价值。

难点

有序漏斗有逻辑上的约束条件,在处理复杂数据时,如何提高计算速度,来保证实时出结果。

引用易观CTO郭炜在采访中的描述,分为四点:

  • 数据量巨大,达到几十亿量级
  • 漏斗是运营人员现创建的,不同的运营人员由于关注业务点不同,指定的事件发生的先后顺序也不一样,这就基本排除了预建Cube的可能性
  • 漏斗分析中包含“时间窗口”的概念,即需要保证所有事件在同一个窗口期内发生
  • 漏斗分析中可以设置事件属性。比如“搜索商品”事件,可以设置只计算“搜索商品”事件的属性中“content”字段为“computer”的用户。不同事件的属性不一、数量也不一样,这对数据的存储方式带来了不小的挑战

问题定义

引自2017易观OLAP算法大赛

漏斗分析是帮助运营人员分析一个多步骤过程中每一步的转化与流失情况。

假设我们在购买商品的过程中,需要触发的事件包括 “启动”,“登陆”,“搜索商品”,“查看商品”,“生成订单”等。

运营人员需要分析某段时间内(比如2017年1月5号到2017年2月5号),在全部用户中依次有序触发 “登陆”→“搜索商品”→“查看商品”→“生成订单“ 事件的人群的转化流失情况,即计算全部用户中触发了“登陆”事件的总人数A,A中触发“搜索商品”事件的总人数B,B中触发“查看商品”事件的总人数C,以及C中触发“生成订单”事件的总人数D。

展现形式如下:

src

同时,漏斗分析中包含“时间窗口”的概念,即需要保证所有事件在同一个窗口期内发生。

比如时间窗口为1天,用户001触发“搜索商品”事件的时间和触发“登陆”事件的时间间隔在一天内,“搜索商品”事件才有效,否则视为无效。

同理,用户001触发“查看商品”事件的时间和触发“登陆”事件的时间间隔也必须在一天内。

时间窗口可以为1天、3天、7天或者1小时、6小时等任意长时间段。

最后,在漏斗分析中,可以设置事件属性。

比如“搜索商品”事件,可以设置只计算“搜索商品”事件的属性中“content”字段为“computer”的用户。具体见详细数据。

测试数据

数据为文本文件格式,具体包含字段有:

  • 用户ID,字符串类型
  • 时间戳,毫秒级别,Long类型
  • 事件ID,Int类型,包含10001到10010十个事件
  • 事件名称,字符串类型,包含启动、登陆、搜索商品等十个事件
  • 事件属性,Json串格式
  • 日期,字符串类型

数据总条数6亿左右,日期范围:2017/01/01到2017/02/28。

示例如下:

src

完整测试数据下载方式,请在2017易观OLAP算法大赛页面寻找。

漏斗需求示例

漏斗需求举例如下:

  • 计算2017年1月份中,依次有序触发“搜索商品”、“查看商品”、“生成订单”的用户转化情况,且时间窗口为1天。
  • 计算2017年1月和2月份中,依次有序触发“登陆”、“搜索商品”、“查看商品”、“生成订单”、“订单付款”的用户转化情况,且时间窗口为7天,“搜索商品”事件的content属性为Apple,“浏览商品”事件的price属性大于5000。

目前通用算法与实例

目前通用60分的算法如下
(1)底层存储用HDFS
(2)建立Hive表,并以应用标识、日期、事件名称为分区
(3)查询用presto,并自定义UDAF,或者利用Spark core自定义相同逻辑

src

大赛结果

小组 新人王 思路 技术 备注
商业组 PingCAP 自研Magic引擎 多层pipeline、智能并发、暴力扫描
商业组 帆软软件 自研分布式引擎 存储为基于Alluxio和HDFS的列存储,计算为基于Spark流式计算,辅以高性能查询算法
商业组 GBase 自研GBase 8a MPP Cluster 行列混合存储,数据压缩算法,有效提高IO性能;并行的MPP + Share Nothing的分布式架构
开源组 向量线科技 ClickHouse
开源组 美团点评 利用Apache Spark、Alluxio等开源框架 bitmap快速过滤和基于时间戳序列匹配的算法
开源组 北邮 HDFS储存,将Spark作为数据预处理和核心过滤算法 最长递增子序列的存储和更新思想,将查找每个用户转化率的时间复杂度变为了0(n)

性能

环境

4台UCloud云主机16核、16G内存、SSD数据盘300G硬件

性能

原文中没有放出实际的结果,只有部分结果。这里列出来仅供参考。

  • ClickHouse: 有序漏斗的计算时间从原始的24秒提高到0.5秒
  • 美团点评: 易观正式数据环境中,在26亿数据,400万用户,几十个属性的场景下,美团点评团队最低运算时间仅0.341秒。

CH解法

内容截选自《OLAP算法大赛 | 开源组冠军向量线科技的秒级实战分析》一文

最初思路

一般思路为:

  1. 根据事件和属性过滤
  2. 根据用户Id汇总
  3. 按时间戳排列
  4. 带时间窗口的子序列搜索
  5. 结果

耗时24s.

使用CH(ClickHouse)

耗时8s.

去掉跨节点调用

按照用户ID进行分区,去掉跨节点调用

耗时1.6s.

以(用户Id, 时间戳)做主键

主键 优点 不足 备注
(Timestamp, UserId) 根据时间做精准的过滤 UserId, Timestamp压缩率均不高, 聚合操作不友好
(UserId, Timestamp) UserId压缩率高, Timestamp不压缩, 聚合操作友好 只能按照月份做分区过滤(fw注: 最新版的CH可以按天啦)

耗时1.4s.

用户Id分组内预排序

我理解的和上面的是一件事情, MergeTree本身是会做排序的.

耗时0.9s.

搜索优化算法

带窗口的子序列搜索优化算法

将"从前往后搜索", 改为"从后往前搜索"

耗时0.8s.

数据结构优化

  • CH中从事件Id到数据下标index, 默认使用的std::unordered_map, 修改为了数组,由O(n)改到了O(1).
  • CH中存储事件序列使用的vector, 改为了纯数组. 去掉vector类的消耗, 同时可以控制内存分配策略.

耗时0.6s.

部分压缩

在压缩和计算之间做取舍

字段 类型 压缩
用户ID 字符串
时间戳(毫秒) Long
事件ID Int 10001 - 10010 10个事件
事件名称
事件属性 Json
日期 字符串
  • 全部压缩: 2.2G
  • 部分压缩: 2.7G

耗时0.5s.

拆分事件属性列

fw注:这部分其实不算了

拆分事件属性列, 用多个列存放

event\_tag 拆分成 event\_tag\_brandevent_tag\_content .

耗时0.8s.

美团点评Hadoop系解法

主要参考自美团点评用户行为分析系统的构建与优化一文

问题描述

  • 路径: 首页 –> 搜索 –> 菜品 –> 下单 –> 支付
  • 日期:2017-11-11
  • 时间窗口:1小时
  • 城市:北市
  • 操作系统:iOS

各路径描述:

  • 首页:page = 首页
  • 搜索:page = 搜索页 and keyword = 中餐
  • 菜品:page = 菜品页
  • 下单:page = 下单页 and price > 100
  • 支付:page = 支付成功

数据示例:

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

直观解法: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

缺点:

缺点:几亿条数据的多层Join代价很高, 时间很长.

直观解法:UDAF

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

时间:5000秒

缺点:⼏几亿个UUID的聚合 没有⾼高效的过滤条件

问题难点

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

问题挑战性

  • 漏斗定义随机:事件组合,时间窗口是随机的,不能实现完全预计算
  • 漏斗维度随机:可以事件维度,也可以事件+属性维度,需要OLAP下钻和筛选的能力
  • 规模和性能的取舍:海量数据下,实现交互式分析

问题约束条件

  • 不需要完整SQL能力,重点是支持集合运算和去重计数
  • 查询并发度低,可以调度所有资源
  • 数据不会修改,可能构建索引
  • 业务特点:指标收敛过快,重点分析转化率偏低的场景,可能快速过滤

算法优化

数据排序

按(UUID, timestamp)排序

对各字段做索引

如果没有索引,按照筛选条件来取数据,需要遍历全部日志。(fw注: 为什么不做主键索引呢?)

所以对page, city等每一个筛选项做一个类倒排索引,即从筛选项到(UUID, timestamp)的索引。

索引优化

在漏斗的非第一步计算时,是需要在满足日志筛选条件的基础上,同时满足对UUID进行筛选的。因此把UUID从索引中单独拆了出来,做成了bitmap,方便快速查找。

索引设计

请参考美团点评用户行为分析系统的构建与优化中的PPT内容。

组合索引

多个维度时,需要在单维度索引的基础上,进行AND/OR的逻辑运算。

工程设计

  • Spring: 接收前端请求, Netty/Jetty
  • Spark: 分布式调度框架(Spark Master / Spark Worker),MapReduce
  • Alluxio: 轻量级异构存储(Alluxio Master / Alluxio Worker),HDFS/HBase

工程要点

  • 查询条件:JSON格式,REST服务
  • 属性表达式:Antlr解析,生成表达树
  • Bitmap快速过滤:RoaringBitmap
  • 时间戳序列匹配:差值存储,平均长度从8字节到1.5字节

工程优化

UUID分区,Spark长作业

180秒

本地化调度

将Spark和Alluxio的分区对应在一台机器上

60秒

内存映射

减少一次磁盘IO?

10秒

Unsafe调用

绕过了Java检查过程

3秒

参考

评论

发表评论

validate