算法是大数据发展的核心引擎，有序漏斗是技术领域影响计算效率的行业难题。易观举办的2017OLAP算法大赛，从今年7月到10月份，历经四月的比赛角逐，于10月28日在易观A10峰会用户视图主论坛上，正式公布比赛结果并向获奖团队颁发证书及奖金。
其中，来自广州的向量线科技团队，以比主办方提供60分时间提速10倍的优异成绩，获得开源组冠军并收获10万元奖金。
OLAP到底是什么样的多维数据分析？参赛队伍又是如何实现秒级甚至毫秒级的实战分析？以下为向量线科技韦万在论坛现场进行产品演示的演讲实录：
我是向量线科技创始人韦万，非常感谢易观举办了这次OLAP大赛，这次比赛非常有挑战性的，也很荣幸取得本次开源组的第一名。原来易观提供的24秒，我们在相同场景下用了0.5秒。我们是如何实现测试环境下0.5秒这样的速度，下面我将详细讲解我们的优化思路。
首先来简单看一下本次比赛的具体的问题，我们本次比赛具体的产品叫“有序漏斗”，这是一个比较重要的分析场景。比如说我们是一个电商网站，我们运营人员要进行这样的环节，需要分析在某个时间段之内，用户在有序触发事件，从启动、登陆、搜索商品、查看商品、生成订单转化率是多少，流失率是多少，这对整个网站的流程设计是非常有帮助的。在这个场景之下，我们这个测试数据有6亿，正式比赛数据量有26亿，但只可以跑在四台Ucloud云主机上（16核、16G）。我们做了优化，效率提升了几十倍。
以上是对有序漏斗问题的计算流程图
首先我们在查询有序漏斗的时候，需要对时间区间以及事件还有属性进行过滤，经过过滤之后, 将数据按照uid聚合在一起，然后根据时间进行排序，最后对每个用户的事件序列进行搜索, 得出最终的结果。从这个流程可以看出, 由于不同场景的漏斗路径以及时间窗口都是动态的, 所以数据不像多维分析那样可以做预聚合, 必须对原始数据全盘扫描来进行计算, 计算量也非常大。整体来说，这个问题还是非常有挑战性的。
要解决这个问题，首先需要我们选择一个高性能的分析引擎，这里我们选择的是ClickHouse。我们简单介绍一下，ClickHouse是俄罗斯Yandex公司研发，Yandex相当于美国的谷歌，是全球搜索引擎排名第二名的公司。ClickHouse从2009年出现原型，在2012年生产可用，2016年开源，经历了多年时间，现在已经成熟可用。Yandex的Metrica系统是一款类似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只能按照月份来分区， 如果按照右边来进行排序，来查询，6月15日-6月16日时间段的漏斗不能精准的过滤，就不能太友好。左边可以做到的，但有一点就是压缩率会比较低，我们知道时间戳变化非常大的，如果用ID来排序压缩率比较高。右边是反过来，具体选择哪一种，根据具体的结果来选择，我们结果对比后选择右边这种，就可以把时间优化到1.4秒。
• 数据预排序
我们刚才这个流程，中间会有一个排序的步骤。事实上，我们经过上一个优化的时候，已经经过用户ID排序，再进行时间戳的排序，这个排序的步骤是可以省略掉的。但这个要做显示处理，如果不做处理的话，排序算法就不太方便识别了。我们把这部分砍掉了之后，耗时就来到了0.9秒，这个力度也是蛮大的。
• 算法优化
我们刚才主要说的业务的优化，下面进行一点比较深度的优化。我们知道有序漏斗可以简化成带窗口子序列搜索算法。一般情况下，实现这个算法，是从左到右进行搜索，这是非常显然的。但我们注意到，如果从右到左进行搜索的话，可以剪掉很多分支，为什么呢？我们注意到L这个子串，这里面元素是不会重复的，也就是说，每一个元素自带一个深度，我们搜索的时候找到了一个深度，再遇到比较小的，或者跟他一样的深度是可以直接忽略掉的。我们在S为5的已经找到了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拆成多个列，从而提高过滤效率。
注：演讲内容基于选手在测试环境下的实践分享。