用戶行為分析是數據分析中非常重要的一項內容，在統計活躍用戶，分析留存和轉化率，改進產品體驗、推動用戶增長等領域有重要作用。美團點評每天收集的用戶行為日誌達到數百億條，如何在海量數據集上實現對用戶行為的快速靈活分析，成為一個巨大的挑戰。為此，我們提出並實現了一套面向海量數據的用戶行為分析解決方案，將單次分析的耗時從小時級降低到秒級，極大的改善了分析體驗，提升了分析人員的工作效率。
本文以有序漏斗的需求為例，詳細介紹了問題分析和思路設計，以及工程實現和優化的全過程。本文根據2017年12月ArchSummit北京站演講整理而成，略有刪改。
問題分析
下圖描述了轉化率分析中一個常見場景，對訪問路徑“首頁-搜索-菜品-下單-支付”做分析，統計按照順序訪問每層節點的用戶數，得到訪問過程的轉化率。
統計上有一些維度約束，比如日期，時間窗口（整個訪問過程在規定時間內完成，否則統計無效），城市或操作系統等，因此這也是一個典型的OLAP分析需求。此外，每個訪問節點可能還有埋點屬性，比如搜索頁上的關鍵詞屬性，支付頁的價格屬性等。從結果上看，用戶數是逐層收斂的，在可視化上構成了一個漏斗的形狀，因此這一類需求又稱之為“有序漏斗”。
這類分析通常是基於用戶行為的日誌表上進行的，其中每行數據記錄了某個用戶的一次事件的相關信息，包括髮生時間、用戶ID、事件類型以及相關屬性和維度信息等。現在業界流行的通常有兩種解決思路。
基於Join的SQL
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 = '首頁') t1left join(select uuid id2, timestamp ts2 from data where timestamp >= 1510329600 and timestamp < 1510416000 and page = '搜索' and keyword = '中餐') t2on t1.id1 = t2.id2 and t1.ts1 < t2.ts2 and t2.ts2 - t1.ts1 < 3600left join(select uuid id3, timestamp ts3 from data where timestamp >= 1510329600 and timestamp < 1510416000 and page = '菜品') t3on t1.id1 = t3.id3 and t2.ts2 < t3.ts3 and t1.ts1 < t3.ts3 and t3.ts3 - t1.ts1 < 360012345678
基於UDAF(User Defined Aggregate Function)的SQL
selectfunnel(timestamp, 3600, '首頁') stage0,funnel(timestamp, 3600, '首頁', '搜索', keyword = '中餐') stage1, funnel(timestamp, 3600, '首頁', '搜索', '菜品') stage2from datawhere timestamp >= 1510329600 and timestamp < 1510416000 group by uuid12345
對於第一種解法，最大的問題是需要做大量join操作，而且關聯條件除了ID的等值連接之外，還有時間戳的非等值連接。當數據規模不大時，這種用法沒有什麼問題。但隨著數據規模越來越大，在幾百億的數據集上做join操作的代價非常高，甚至已經不可行。
第二種解法有了改進，通過聚合的方式避免了join操作，改為對聚合後的數據通過UDAF做數據匹配。這種解法的問題是沒有足夠的篩選手段，這意味著幾億用戶對應的幾億條數據都需要遍歷篩選，在性能上也難以接受。
那麼這個問題的難點在哪裡？為什麼上述兩個解法在實際應用中變得越來越不可行？主要問題有這麼幾點。
1. 事件匹配有序列關係。如果沒有序列關係就非常容易，通過集合的交集並集運算即可。
2. 時間窗口約束。這意味著事件匹配的時候還有最大長度的約束，所以匹配算法的複雜度會進一步提升。
3. 屬性和維度的需求。埋點SDK提供給各個業務線，每個頁面具體埋什麼內容，完全由業務決定，而且取值是完全開放的，因此目前屬性基數已經達到了百萬量級。同時還有幾十個維度用於篩選，有些維度的基數也很高。
4. 數據規模。目前每天收集到的用戶行為日誌有幾百億條，對資源和效率都是很大的挑戰。
基於上述難點和實際需求的分析，可以總結出幾個實際困難，稱之為“壞消息”。
1. 漏斗定義完全隨機。不同分析需求對應的漏斗定義完全不同，包括具體包含哪些事件，這些事件的順序等，這意味著完全的預計算是不可能的。
2. 附加OLAP需求。除了路徑匹配之外，還需要滿足屬性和維度上一些OLAP的上卷下鑽的需求。
3. 規模和性能的矛盾。一方面有幾百億條數據的超大規模，另一方面又追求秒級響應的交互式分析效率，這是一個非常激烈的矛盾衝突。
另一方面，還是能夠從問題的分析中得到一些“好消息”, 這些也是在設計和優化中可以利用的點。
1. 計算需求非常單一。這個需求最終需要的就是去重計數的結果，這意味著不需要一個大而全的數據引擎，在設計上有很大的優化空間。
2. 併發需求不高。漏斗分析這類需求一般由運營或者產品同學手動提交，查詢結果用於輔助決策，因此併發度不會很高，這樣可以在一次查詢時充分調動整個集群的資源。
3. 數據不可變。所謂日誌即事實，用戶行為的日誌一旦收集進來，除非bug等原因一般不會再更新，基於此可以考慮一些索引類的手段來加速查詢。
4. 實際業務特點。最後是對實際業務觀察得出的結論，整個漏斗收斂非常快，比如首頁是幾千萬甚至上億的結果，到了最下層節點可能只有幾千，因此可以考慮一些快速過濾的方法來降低查詢計算和數據IO的壓力。
如果用一句話總結這個問題的核心本質，那就是“多維分析和序列匹配基礎上的去重計數”。具體來說，最終結果就是每層節點符合條件的UUID有多少個，也就是去重後的計數值。這裡UUID要符合兩個條件，一是符合維度的篩選，二是事件序列能匹配漏斗的定義。去重計數是相對好解的問題，那麼問題的重點就是如果快速有效的做維度篩選和序列匹配。
算法設計
下圖是部分行為日誌的數據，前面已經提到，直接在這樣的數據上做維度篩選和序列匹配都是很困難的，因此考慮如何對數據做預處理，以提高執行效率。
很自然的想法是基於UUID做聚合，根據時間排序，這也是前面提到的UDAF的思路，如下圖所示。這裡的問題是沒有過濾的手段，每個UUID都需要遍歷，成本很高。
再進一步，為了更快更方便的做過濾，考慮把維度和屬性抽出來構成Key，把對應的UUID和時間戳組織起來構成value。如果有搜索引擎經驗的話，很容易看出來這非常像倒排的思路。
這個數據結構還是存在問題。比如說要拿到某個Key對應的UUID列表時，需要遍歷所有的value才可以。再比如做時間序列的匹配，這裡的時間戳信息被打散了，實際處理起來更困難。因此還可以在此基礎上再優化。
可以看到優化後的Key內容保持不變，value被拆成了UUID集合和時間戳序列集合這兩部分，這樣的好處有兩點：一是可以做快速的UUID篩選，通過Key對應的UUID集合運算就可以達成；二是在做時間序列匹配時，對於匹配算法和IO效率都是很友好的，因為時間戳是統一連續存放的，在處理時很方便。
基於上述的思路，最終的索引格式如下圖所示。這裡每個色塊對應了一個索引的block，其中包括三部分內容，一是屬性名和取值；二是對應的UUID集合，數據通過bitmap格式存儲，在快速篩選時效率很高；三是每個UUID對應的時間戳序列，用於序列匹配，在存儲時使用差值或變長編碼等一些編碼壓縮手段提高存儲效率。
在實際應用中，通常會同時指定多個屬性或維度條件，通過AND或OR的條件組織起來。這在處理時也很簡單，通過語法分析可以把查詢條件轉為一顆表達樹，樹上的葉子節點對應的是單個索引數據，非葉子節點就是AND或OR類型的索引，通過並集或交集的思路做集合篩選和序列匹配即可。
上面解決的是維度篩選的問題，另一個序列匹配的問題相對簡單很多。基於上述的數據格式，讀取UUID對應的每個事件的時間戳序列，檢查是否能按照順序匹配即可。需要注意的是，由於存在最大時間窗口的限制，匹配算法中需要考慮回溯的情況，下圖展示了一個具體的例子。在第一次匹配過程中，由於第一層節點的起始時間戳為100，並且時間窗口為10，所以第二層節點的時間戳101符合要求，但第三層節點的時間戳112超過了最大截止時間戳110，因此只能匹配兩層節點，但通過回溯之後，第二次可以完整的匹配三層節點。
通過上述的討論和設計，完整的算法如下圖所示。其中的核心要點是先通過UUID集合做快速的過濾，再對過濾後的UUID分別做時間戳的匹配，同時上一層節點輸出也作為下一層節點的輸入，由此達到快速過濾的目的。
工程實現和優化
有了明確的算法思路，接下來再看看工程如何落地。
首先明確的是需要一個分佈式的服務，主要包括接口服務、計算框架和文件系統三部分。其中接口服務用於接收查詢請求，分析請求並生成實際的查詢邏輯；計算框架用於分佈式的執行查詢邏輯；文件系統存儲實際的索引數據，用於響應具體的查詢。
這裡簡單談一下架構選型的方法論，主要有四點：簡單、成熟、可控、可調。
1.簡單。不管是架構設計，還是邏輯複雜度和運維成本，都希望儘可能簡單。這樣的系統可以快速落地，也比較容易掌控。
2.成熟。評估一個系統是否成熟有很多方面，比如社區是否活躍，項目是否有明確的發展規劃並能持續落地推進？再比如業界有沒有足夠多的成功案例，實際應用效果如何？一個成熟的系統在落地時的問題相對較少，出現問題也能參考其它案例比較容易的解決，從而很大程度上降低了整體系統的風險。
3.可控。如果一個系統持續保持黑盒的狀態，那隻能是被動的使用，出了問題也很難解決。反之現在有很多的開源項目，可以拿到完整的代碼，這樣就可以有更強的掌控力，不管是問題的定位解決，還是修改、定製、優化等，都更容易實現。
4.可調。一個設計良好的系統，在架構上一定是分層和模塊化的，且有合理的抽象。在這樣的架構下，針對其中一些邏輯做進一步定製或替換時就比較方便，不需要對代碼做大範圍的改動，降低了改造成本和出錯概率。
基於上述的選型思路，服務的三個核心架構分別選擇了Spring，Spark和Alluxio。其中Spring的應用非常廣泛，在實際案例和文檔上都非常豐富，很容易落地實現；Spark本身是一個非常優秀的分佈式計算框架，目前團隊對Spark有很強的掌控力，調優經驗也很豐富，這樣只需要專注在計算邏輯的開發即可；Alluxio相對HDFS或HBase來說更加輕量，同時支持包括內存在內的多層異構存儲，這些特性可能會在後續優化中得到利用。
在具體的部署方式上，Spring Server單獨啟動，Spark和Alluxio都採用Standalone模式，且兩個服務的slave節點在物理機上共同部署。Spring進程中通過SparkContext維持一個Spark長作業，這樣接到查詢請求後可以快速提交邏輯，避免了申請節點資源和啟動Executor的時間開銷。
上述架構通過對數據的合理分區和資源的併發利用，可以實現一個查詢請求在幾分鐘內完成。相對原來的幾個小時有了很大改觀，但還是不能滿足交互式分析的需求，因此還需要做進一步的優化。
1. 本地化調度。存儲和計算分離的架構中這是常見的一種優化手段。以下圖為例，某個節點上task讀取的數據在另外節點上，這樣就產生了跨機器的訪問，在併發度很大時對網絡IO帶來了很大壓力。如果通過本地化調度，把計算調度到數據的同一節點上執行，就可以避免這個問題。實現本地化調度的前提是有包含數據位置信息的元數據，以及計算框架的支持，這兩點在Alluxio和Spark中都很容易做到。
2. 內存映射。常規實現中，數據需要從磁盤拷貝到JVM的內存中，這會帶來兩個問題。一是拷貝的時間很長，幾百MB的數據對CPU時間的佔用非常可觀；二是JVM的內存壓力很大，帶來GC等一系列的問題。通過mmap等內存映射的方式，數據可以直接讀取，不需要再進JVM，這樣就很好的解決了上述的兩個問題。
3. Unsafe調用。由於大部分的數據通過ByteBuffer訪問，這裡帶來的額外開銷對最終性能也有很大影響。Java lib中的ByteBuffer訪問接口是非常安全的，但安全也意味著低效，一次訪問會有很多次的邊界檢查，而且多層函數的調用也有很多額外開銷。如果訪問邏輯相對簡單，對數據邊界控制很有信心的情況下，可以直接調用native方法，繞過上述的一系列額外檢查和函數調用。這種用法在很多系統中也被廣泛採用，比如Presto和Spark都有類似的優化方法。
下圖是對上述優化過程的對比展示。請注意縱軸是對數軸，也就是說圖中每格代表了一個數據級的優化。從圖中可以看到，常規的UDAF方案一次查詢需要花幾千秒的時間，經過索引結構的設計、本地化調度、內存映射和Unsafe調用的優化過程之後，一次查詢只需要幾秒的時間，優化了3~4個數據級，完全達到了交互式分析的需求。
這裡想多談幾句對這個優化結果的看法。主流的大數據生態系統都是基於JVM系語言開發的，包括Hadoop生態的Java，Spark的Scala等等。由於JVM執行機制帶來的不可避免的性能損失，現在也有一些基於C++或其它語言開發的系統，有人宣稱在性能上有幾倍甚至幾十倍的提升。這種嘗試當然很好，但從上面的優化過程來看，整個系統主要是通過更高效的數據結構和更合理的系統架構達到了3個數量級的性能提升，語言特性只是在最後一步優化中有一定效果，在整體佔比中並不多。
有一句雞湯說“以大多數人的努力程度而言，根本沒有到拼天賦的地步”，套用在這裡就是“以大多數系統的架構設計而言，根本沒有到拼語言性能的地步”。語言本身不是門檻，代碼大家都會寫，但整個系統的架構是否合理，數據結構是否足夠高效，這些設計依賴的是對問題本質的理解和工程上的權衡，這才是更考量設計能力和經驗的地方。
總結
上述方案目前在美團點評內部已經實際落地，穩定運行超過半年以上。每天的數據有幾百億條，活躍用戶達到了上億的量級，埋點屬性超過了百萬，日均查詢量幾百次，單次查詢的TP95時間小於5秒，完全能夠滿足交互式分析的預期。
整個方案從業務需求的實際理解和深入分析出發，抽象出了維度篩選、序列匹配和去重計數三個核心問題，針對每個問題都給出了合理高效的解決方案，其中結合實際數據特點對數據結構的優化是方案的最大亮點。在方案的實際工程落地和優化過程中，秉持“簡單、成熟、可控、可調”的選型原則，快速落地實現了高效架構，通過一系列的優化手段和技巧，最終達成了3~4個數量級的性能提升。
閱讀更多 果動科技 的文章
