易观 > 公司新闻 >

OLAP算法大赛 | 开源组冠军向量线科技的秒级实战分析

OLAP算法大赛 | 开源组冠军向量线科技的秒级实战分析

2017-11-07 来源:易观

开源组冠军向量线科技的秒级实战分析

算法是大数据发展的核心引擎,有序漏斗是技术领域影响计算效率的行业难题。易观举办的2017OLAP算法大赛,从今年7月到10月份,历经四月的比赛角逐,于1028日在易观A10峰会用户视图主论坛上,正式公布比赛结果并向获奖团队颁发证书及奖金。

其中,来自广州的向量线科技团队,以比主办方提供60分时间提速10倍的优异成绩,获得开源组冠军并收获10万元奖金。

OLAP到底是什么样的多维数据分析?参赛队伍又是如何实现秒级甚至毫秒级的实战分析?以下为向量线科技韦万在论坛现场进行产品演示的演讲实录:

我是向量线科技创始人韦万,非常感谢易观举办了这次OLAP大赛,这次比赛非常有挑战性的,也很荣幸取得本次开源组的第一名。原来易观提供的24秒,我们在相同场景下用了0.5秒。我们是如何实现测试环境下0.5秒这样的速度,下面我将详细讲解我们的优化思路。

 

首先来简单看一下本次比赛的具体的问题,我们本次比赛具体的产品叫有序漏斗,这是一个比较重要的分析场景。比如说我们是一个电商网站,我们运营人员要进行这样的环节,需要分析在某个时间段之内,用户在有序触发事件,从启动、登陆、搜索商品、查看商品、生成订单转化率是多少,流失率是多少,这对整个网站的流程设计是非常有帮助的。在这个场景之下,我们这个测试数据有6亿,正式比赛数据量有26亿,但只可以跑在四台Ucloud云主机上(16核、16G)。我们做了优化,效率提升了几十倍。

 

以上是对有序漏斗问题的计算流程图

首先我们在查询有序漏斗的时候,需要对时间区间以及事件还有属性进行过滤,经过过滤之后, 将数据按照uid聚合在一起,然后根据时间进行排序,最后对每个用户的事件序列进行搜索, 得出最终的结果。从这个流程可以看出, 由于不同场景的漏斗路径以及时间窗口都是动态的, 所以数据不像多维分析那样可以做预聚合, 必须对原始数据全盘扫描来进行计算计算量也非常大。整体来说,这个问题还是非常有挑战性的。

要解决这个问题,首先需要我们选择一个高性能的分析引擎,这里我们选择的是ClickHouse。我们简单介绍一下,ClickHouse是俄罗斯Yandex公司研发,Yandex相当于美国的谷歌,是全球搜索引擎排名第二名的公司。ClickHouse2009年出现原型,在2012年生产可用,2016年开源,经历了多年时间,现在已经成熟可用。YandexMetrica系统是一款类似GA的分析系统,已经部署将近500个节点,每秒处理2T数据,而且我理解Metrica比谷歌GA还快一点,因为GA需要拿十分之一或者百分之一的数据来进行抽样分析,而Metrica是不需要的。现在ClickHouse在国外已经比较流行,是我目前看到的基于CPU最快的开源OLAP数据库。

在使用ClickHouse过程中,我们发现它的架构非常灵活、性能很好,而且代码优美。我们使用这个ClickHouse引擎,将整个业务流程实现一遍之后,优化了8秒,直接提升至原来的三分之一。当然,我们不满足于这个速度,我们追求是秒级响应。现在我们开始正式针对ClickHouse进行优化。

•  按照用户ID进行分区

 

这是我们刚才看到一个流程,大家可以发现,在前面几步的时候是可以分别在各个节点进行分别计算的。但是到后面几步的时候把数据汇总起到其中一个节点,就是主节点,汇总之后,我们只能用一个节点来算,对我们整个集群不能充分得到利用,如果我们能优化掉,做成完全并行,相信会有非常大的提升空间。我们也是这样做的。我们注意到,在最后面的搜索的时候,相同的用户放在相同的节点,各个节点是完整,相互独立,不需要交流,完全来并行。能做这个优化的前提条件是ClickHouse比较灵活的,支持单独向单个节点表发送查询请求。我们完成并行化之后,我们时间就用了1.6秒,也是一个非常大地提升。

•  使用(uid timestamp)作为主键

 

但我们的目标是0.5秒,后面的每0.1秒都是非常关键的。下一个优化点是主键,这里的主键不是传统关系库的主键,而是数据库内的数据的排列方式,我们这里主要有两种方式。因为Clickhouse只能按照月份来分区, 如果按照右边来进行排序,来查询,615-616日时间段的漏斗不能精准的过滤,就不能太友好。左边可以做到的,但有一点就是压缩率会比较低,我们知道时间戳变化非常大的,如果用ID来排序压缩率比较高。右边是反过来,具体选择哪一种,根据具体的结果来选择,我们结果对比后选择右边这种,就可以把时间优化到1.4秒。

•  数据预排序

 

我们刚才这个流程,中间会有一个排序的步骤。事实上,我们经过上一个优化的时候,已经经过用户ID排序,再进行时间戳的排序,这个排序的步骤是可以省略掉的。但这个要做显示处理,如果不做处理的话,排序算法就不太方便识别了。我们把这部分砍掉了之后,耗时就来到了0.9秒,这个力度也是蛮大的。

 算法优化

 

我们刚才主要说的业务的优化,下面进行一点比较深度的优化。我们知道有序漏斗可以简化成带窗口子序列搜索算法。一般情况下,实现这个算法,是从左到右进行搜索,这是非常显然的。但我们注意到,如果从右到左进行搜索的话,可以剪掉很多分支,为什么呢?我们注意到L这个子串,这里面元素是不会重复的,也就是说,每一个元素自带一个深度,我们搜索的时候找到了一个深度,再遇到比较小的,或者跟他一样的深度是可以直接忽略掉的。我们在S5的已经找到了abc,剩下的位置,只有2位置的d是需要继续分析的,从而可以剪掉许多不用的分支,大大提高效率。我们进行优化的之后,把时间减少到了0.8秒,但离最终目标0.5秒还有一些距离。

•  数据结构优化

 

我们优化了算法,下面是数据结构。在上一个算法中,我们有一个频繁的操作,即从事件ID到数组下标的Index的映射,我们是直接采用的遍历数组的方式,而不使用map,因为在很小的时候,遍历操作非常快的,大家也可以回去做一个实验。第二个,我们在存储事件序列的时候,不使用std::vector,直接原始数组,这样主要是为了控制内存分配策略,可以根据数据量预先分配足够内存,并且在内容使用完了以后,不需要系统去回收,重新利用它,进行小小的优化。除了以上优化点,还有c++的其他常见编码优化方式,大家回去之后参考一下比较流行的C++的优化书籍,都是很全面的。我们经过优化之后,把时间减少到了0.6秒。离我们最终目标0.5秒还有一个0.1秒的距离。

 压缩VS不压缩

 

接下来优化哪一个点呢?事实上数据库来说,包括存储和计算,我们以上都是对计算层的优化,现在来要看看存储上是否有可以优化的点。优化点在这里,首先数据压缩对硬盘是友好的,但是对CPU不太友好,为提高性能,我们可以选择部分字段不压缩。比如说我们用户ID需要压缩的,因为用户ID压缩率是非常高的,它已经排序了;还有时间戳等等,可以选择不压缩,因为压缩率不会很高。最终部分压缩跟全部压缩对比,对业务来说大小差距完全可以接受。我们做性能测试,发现经过这一点优化,我们最终性能达到了目标0.5秒。

 

除了以上优化点之外还有别的点,比如说存储事件属性列用存储的方式也可以拆开,把json拆成多个列,从而提高过滤效率。

 

注:演讲内容基于选手在测试环境下的实践分享。

易观社群

相关文章