近期易觀公司舉辦了一個OLAP大賽，我們隊伍非常幸運地獲得了第一名，成為本次比賽最大黑馬。此篇文章主要是從技術(shù)角度飒房，來分享一下我們是如何解決有序漏斗秒查問題的
比賽地址：2017易觀OLAP算法大賽
參賽情況:? https://www.analysys.cn/media/detail/20018458/
1.? 題目分析：
在以上示例場景下，我們在易觀提供的6億測試數(shù)據(jù)集上媚值，在4臺UCloud云主機(16core狠毯，16G ram)機器下從24s優(yōu)化到了0.5s。而在正式比賽的26億數(shù)據(jù)集上褥芒，使用相同硬件環(huán)境嚼松，耗時1.6s。
2.? 解題分析：
題目描述的有序漏斗問題可以歸結(jié)為 帶滑動時間窗口的最左子序列問題锰扶， 比如我們需要尋找献酗，2017年7月份中，在3小時的時間窗口下坷牛， [A,B,C,D] 漏斗路徑下的轉(zhuǎn)化情況罕偎， 單個用戶只能有? NULL , [a], [A,B], [A,B,C], [A,B,C,D]? 五種轉(zhuǎn)化結(jié)果，對應(yīng)的漏斗深度我們稱之為level京闰，在[A,B,C,D]漏斗路徑下颜及，level的取值可以有[0,1,2,3,4] 四個值，題目的要求即算出所有用戶的滿足條件下最大level匯總結(jié)果蹂楣。
理解問題之后俏站，我們梳理了一下流程圖：
我們將問題解決分為5個步驟：
filter階段 ：根據(jù)時間區(qū)間和事件屬性對數(shù)據(jù)進行過濾
group階段： 根據(jù)用戶Id進行g(shù)roup匯總
sort階段： 按照時間進行排序
algorithm aggregate 階段： 帶時間窗口的子序列搜索
合并結(jié)果
3.? 數(shù)據(jù)庫選型：
根據(jù)以上分析，需要filter捐迫，group乾翔，sort爱葵，aggregate等操作施戴，數(shù)據(jù)庫是必備的核心反浓，而在OLAP領(lǐng)域，開源的數(shù)據(jù)庫選型有很多赞哗，比如：mysql, druid, kylin hdfs + (hive,spark,presto)雷则，imapla, kudu etc。
但在這個場景下肪笋，結(jié)合以往對其他數(shù)據(jù)的深入研究分析對比經(jīng)驗月劈，我們幾乎毫不猶豫就選擇了 ClickHouse (縱然它不支持udaf)，藤乙，我們相信ClickHouse是目前cpu領(lǐng)域最快的olap開源數(shù)據(jù)庫猜揪，它最突出的優(yōu)點就是快，如果你是第一次用坛梁，相信ClickHouse會讓你感到非常驚艷而姐。
ClickHouse 由俄羅斯Yandex開發(fā)，09年原型划咐，12年生產(chǎn)可用拴念，16年開源，目前最大的線上部署實例是 Yandex.Metrica: 472個節(jié)點褐缠，每秒處理2T數(shù)據(jù)政鼠，實時在線分析。ClickHouse 在OLAP上的查詢性能非常彪悍队魏，平均查詢性能幾乎是vertica的三倍公般。
ClickHouse不僅速度快，它系統(tǒng)架構(gòu)靈活胡桨，性能優(yōu)越俐载，代碼優(yōu)雅, 非常適合大數(shù)據(jù)下需要極致性能的應(yīng)用場景。雖然ClickHouse目前暫不支持UDAF登失，但沒關(guān)系遏佣，由于它的架構(gòu)非常好，我們可以通過修改源代碼并重新編譯來實現(xiàn)自定義AggregateFunction (即使我還是一個 c++ 菜鳥 ~~ )揽浙。
以上就是針對漏斗場景的代碼修改情況状婶，可以看出我們只用了不到300行代碼就為ClickHouse加入了漏斗計算（aggregate function path）的功能, 修改的代碼可以在文章末尾看到。
對比官方的presto + hdfs 方案實現(xiàn)的24s速度馅巷，使用ClickHouse之后膛虫，我們在測試環(huán)境下跑的速度達到了8s，這僅僅是一個基礎(chǔ)版本的性能钓猬。
下面開始我們的正式優(yōu)化過程
4. 按照用戶ID分區(qū)：
我們注意到稍刀，漏斗的計算中，每個用戶都是相互獨立的，所以我們可以將數(shù)據(jù)按照uid來分區(qū)账月，這樣就將數(shù)據(jù)分散到了四臺機器上综膀，我們可以分別向每個數(shù)據(jù)庫節(jié)點發(fā)送請求，然后將數(shù)據(jù)進行匯總局齿，得到最終結(jié)果剧劝。
通過這次優(yōu)化，我們在測試環(huán)境下跑的速度達到了1.6s抓歼。
5. 以(uid,timestamp)作為primary key
ClickHouse中primary key代表了數(shù)據(jù)的組織排序方式
左邊的以（timestamp讥此，uid）為主鍵，時間是有序的谣妻，方便做時間精準(zhǔn)過濾萄喳，但uid壓縮率低；右邊的以（uid,timestamp) 為主鍵蹋半，uid壓縮率高取胎，方便做uid group， 但對時間過濾支持不夠好湃窍。
通過測試對比闻蛀，我們發(fā)現(xiàn)以 （uid,timestamp) 作為主鍵性能略快，查詢時間達到了 1.4s您市。
6. 分組預(yù)排序
當(dāng)我們以 （uid,timestamp) 作為primary key后觉痛， 分組內(nèi)的數(shù)據(jù)其實已經(jīng)有序了， 我們可以去掉代碼中的sort方法茵休，來提高性能薪棒，經(jīng)過這個優(yōu)化，查詢時間達到了 0.9s榕莺。
7. 帶時間窗口的子序列搜索優(yōu)化
這里主要是用了一些 剪枝的策略俐芯，當(dāng)我們從左往右去搜索 a,b,c,d 漏斗的時候，我們需要找到最大的深度钉鸯，必須一直去搜索以a開頭的子序列吧史；但我們從右往左搜索時， 我們只要考慮比當(dāng)前結(jié)尾更大的子串即可唠雕， 比如我們找到了 a,b,c贸营， 后面我們只需要考慮以d結(jié)尾的串，這樣減小了搜索的復(fù)雜度岩睁，查詢時間達到了0.8s钞脂。
8. 數(shù)據(jù)結(jié)構(gòu)優(yōu)化
事件ID到數(shù)組下標(biāo)Index的映射，我們直接遍歷了數(shù)組搜索捕儒，而不使用std::unordered_map, 因為在events數(shù)據(jù)量不大的情況下冰啃， 數(shù)組搜索O(1)比O(n)慢。
使用純C++數(shù)組存儲事件序列，不使用std::vector阎毅，去掉了vector的開銷焚刚，靈活控制內(nèi)存分配。
經(jīng)此優(yōu)化净薛，查詢時間達到了0.6s。
9. 部分壓縮
數(shù)據(jù)庫通常會對字段進行壓縮蒲拉，這樣做節(jié)省了硬盤空間肃拜，但卻浪費了cpu計算，為了提供性能雌团，我們對字段進行了部分壓縮燃领，經(jīng)此優(yōu)化，查詢時間達到了最終的0.5s锦援。
uid? => 壓縮
timestamp => 不壓縮
event_id => 不壓縮
event_name => 壓縮
event_tag => 壓縮
date => 不壓縮
最后：
我們已經(jīng)將代碼和PPT開源：https://github.com/analysys/olap
為了滿足通用漏斗的查詢猛蔽，結(jié)合電商分析的場景，新版的 windowFunnel 函數(shù)已提交給ClickHouse 官方灵寺，已被官方采納? Add AggregateFunction windowFunnel? by sundy-li · Pull Request #2352 · yandex/ClickHouse通過這次比賽曼库，0.5s的性能非常突出，但這絕不會是極限略板，如今GPU數(shù)據(jù)庫大道橫行毁枯，技術(shù)變革也愈演愈烈， 前路漫長叮称，預(yù)測未來最好的方法就是自己創(chuàng)造未來种玛，各位技術(shù)大牛們，一起努力Ｈ块堋Ｂ冈稀！
