本文實踐了對於千萬級別的使用者，操作總數達萬級別，每日幾十億操作流水的留存分析工具秒級別查詢的資料構建方案。同時，除了留存分析，對於使用者群分析，事件分析等也可以嘗試用此方案來解決。

背景

你可能聽說過Growingio、神策等資料分析平臺，本文主要介紹實現留存分析工具相關的內容。

留存分析是一種用來分析使用者參與情況/活躍程度的分析模型，可考查進行初始行為後的使用者中，有多少人會進行後續行為，這是衡量產品對使用者價值高低的重要指標。如，為評估產品更新效果或渠道推廣效果，我們常常需要對同期進入產品或同期使用了產品某個功能的使用者的後續行為表現進行評估 [1]。大部分資料分析平臺主要包括如圖的幾個功能（以神策為例）：

本文主要介紹留存分析工具的優化方案（只涉及資料儲存和查詢的方案設計，不涉及平臺）。

我想每個資料/產品同學在以往的取數分析過程中，都曾有一個痛點，就是每次查詢留存相關的資料時，都要等到天荒地老，慢！而最近採用優化方案的目的也是為了提高查詢的效率和減少資料的儲存，可以幫助產品快速地查詢/分析留存相關的資料。

優化方案的核心是在Clickhouse中使用Roaringbitmap對使用者進行壓縮，將留存率的計算交給高效率的點陣圖函式，這樣既省空間又可以提高查詢速度。

希望本實踐方案可以給你帶來一些幫助和啟示。下面主要分3個部分詳細介紹：Roaringbitmap簡介、思路與實現、總結與思考。

Roaringbitmap簡介

下面先簡單介紹一下高效的點陣圖壓縮方法Roaringbitmap。先來看一個問題:

給定含有40億個不重複的位於[0,2^32-1]區間內的整數集合，如何快速判定某個數是否在該集合內？ 

顯然，如果我們將這40億個數原樣儲存下來，需要耗費高達14.9GB的記憶體，這是難以接受的。所以我們可以用點陣圖(bitmap)來儲存，即第0個位元表示數字0，第1個位元表示數字1，以此類推。如果某個數位於原集合內，就將它對應的點陣圖內的位元置為1，否則保持為0，這樣就能很方便地查詢得出結果了，僅僅需要佔用512MB的記憶體，不到原來的3.4% [3]。但是這種方式也有缺點：比如我需要將1~5000w這5000w個連續的整數儲存起來，用普通的bitmap同樣需要消耗512M的儲存，顯然，對於這種情況其實有很大的優化空間。

2016年由S. Chambi、D. Lemire、O. Kaser等人在論文《Better bitmap performance with Roaring bitmaps》與《Consistently faster and smaller compressed bitmaps with Roaring》中提出了roaringbitmap，主要特點就是可以極大程度地節約儲存及提供了快速的點陣圖計算，因此考慮用它來做優化。對於前文提及的儲存連續的5000w個整數，只需要幾十KB。

它的主要思路是：將32位無符號整數按照高16位分桶，即最多可能有2^16 =65536個桶，論文內稱為container。儲存資料時，按照資料的高16位找到container（找不到就會新建一個），再將低16位放入container中。也就是說，一個roaringbitmap就是很多container的集合 [3]，具體細節可以自行檢視文末的參考文章 。

思路與實現

我們的原始資料主要分為：

1.使用者操作行為資料table_oper_raw 包括時間分割槽(ds)、使用者標識id(user_id)和使用者操作行為名稱(oper_name)，如：20200701|6053002|點選首頁banner 表示使用者6053002在20200701這天點選了首頁banner（同一天中同一個使用者多次操作了同一個行為只保留一條）。實踐過程中，此表每日記錄數達幾十億行。2.使用者屬性資料table_attribute_raw 表示使用者在產品/畫像中的屬性，包括時間分割槽(ds)、使用者標識(user_id)及各種使用者屬性欄位（可能是使用者的新進渠道、所在省份等），如20200701|6053002|小米商店|廣東省。實踐過程中，此表每日有千萬級的使用者數，測試屬性在20+個。

現在我們需要根據這兩類資料，求出某天操作了某個行為的使用者在後續的某一天操作了另一個行為的留存率，比如，在20200701這天操作了“點選banner”的使用者有100個，這部分使用者在20200702這天操作了“點選app簽到”的有20個，那麼對於分析時間是20200701，且“點選banner”的使用者在次日“點選app簽到”的留存率是20%。同時，還需要考慮利用使用者屬性對留存比例進行區分，例如只考慮廣東省的使用者的留存率，或者只考慮小米商店使用者的留存率，或者在廣東的小米商店的使用者的留存率等等。

一般來說，求留存率的做法就是兩天的使用者求交集，例如前文說到的情況，就是先獲取出20200701的所有操作了“點選banner”的使用者標識id集合假設為S1，然後獲取20200702的所有操作了“點選app簽到”的使用者標識id集合假設為S2，最後求解S1和S2的交集：

可以看到，當s1和s2的集合中使用者數都比較大的時候，join的速度會比較慢。

在此我們考慮前文說到的bitmap，假若每一個使用者都可以表示成一個32位的無符號整型，用bitmap的形式去儲存，S1和S2的求交過程就是直接的一個位比較過程，這樣速度會得到巨大的提升。而Roaringbitmap對資料進行了壓縮，其求交的速度在絕大部分情況下比bitmap還要快，因此這裡我們考慮使用Roaringbitmap的方法來對計算留存的過程進行優化。

1.資料構建

整個過程主要是：首先對初始的兩張表——使用者操作資料表table_oper_raw和使用者篩選維度資料表table_attribute_raw中的user_id欄位進行編碼，將每個使用者對映成唯一的id（32位的無符號整型），分別得到兩個新表table_oper_middle和table_attribute_middle。再將他們匯入clickhouse，使用roaringbitmap的方法對使用者進行壓縮儲存，最後得到壓縮後的兩張表table_oper_bit和table_attribute_bit，即為最終的查詢表。流程圖如下：

同 樣的，在clickhouse中 建立表table_attribute_middle_ch。 然後用spark將這兩份資料分別匯入這 兩張表。 這一步匯入很快，幾十億的資料大概10分多鐘 就可以完成。

(4).Roaringbitmap壓縮 對於使用者操作流水資料，我們先建一個可以存放bitmap的表table_oper_bit，建表語句如下：使用者屬性資料table_attribute_bit也類似：這裡索引粒度可設定小值，接著用聚合函式groupBitmapState對使用者id進行壓縮：這樣，對於使用者操作資料表，原本幾十億的資料就壓縮成了幾萬行的資料，每行包括操作名稱和對應的使用者id形成的bitmap：同樣的，使用者屬性的資料也可以這樣處理，得到table_attribute_bit表，每行包括某個屬性的某個屬性值對應的使用者的id形成的bitmap：至此，資料壓縮的過程就這樣完成了。2. 查詢過程

首先，簡要地介紹下方案中常用的bitmap函式（詳細見文末的參考資料）：

1.bitmapCardinality 返回一個UInt64型別的數值，表示bitmap物件的基數。用來計算不同條件下的使用者數，可以粗略理解為count(distinct)

2.bitmapAnd 為兩個bitmap物件進行與操作，返回一個新的bitmap物件。可以理解為用來滿足兩個條件之間的and，但是引數只能是兩個bitmap

3.bitmapOr 為兩個bitmap物件進行或操作，返回一個新的bitmap物件。可以理解為用來滿足兩個條件之間的or，但是引數也同樣只能是兩個bitmap。如果是多個的情況，可以嘗試使用groupBitmapMergeState

# 返回5

select bitmapCardinality ( user_bit )

from tddb . table_oper_bit

where ds = 20200701 AND oper_name =

又如果20200701從小米商店新進的使用者是[1,3,8,111,2000,100000]，則有：

# 返回3,因為兩者的重合使用者只有1,3,8這3個使用者

select bitmapCardinality ( bitmapAnd (

( SELECT user_bit

FROM tddb . table_oper_bit

( SELECT user_bit

FROM tddb . table_attribute_bit

WHERE ds = 20200701 and ( attr_id = 'first_channel' ) and ( attr_value IN ( '小米商店'

)))))

有了以上的資料生成過程和bitmap函式，我們就可以根據不同的條件使用不同的點陣圖函式來快速查詢，具體來說，主要是以下幾種情況：

a. 操作了某個行為的使用者在後續某一天操作了另一個行為的留存：如“20200701點選了banner的使用者在次日點選app簽到的留存人數”，就可以用以下的sql快速求解:b. 操作了某個行為並且帶有某個屬性的使用者在後續的某一天操作了另一個行為的留存：如“20200701點選了banner且來自廣東/江西/河南的使用者在次日點選app簽到的留存人數”：c. 操作了某個行為並且帶有某幾個屬性的使用者在後續的某一天操作了另一個行為的留存：如“20200701點選了banner、來自廣東且新進渠道是小米商店的使用者在次日點選app簽到的留存人數”：

3. 實踐效果

根據這套方案做了實踐，對每日按時間分割槽、使用者、操作名稱去重後包括幾十億的操作記錄，其中包含千萬級別的使用者數，萬級別的運算元。最後實現了：

儲存 原本每日幾十G的操作流水資料經壓縮後得到的表table_oper_bit為4GB左右/天。而使用者屬性表table_attribute_bit為500MB左右/天查詢速度 clickhouse叢集現狀：12核125G記憶體機器10臺。clickhouse版本:20.4.7.67。查詢的表都存放在其中一臺機器上。測試了查詢在20200701操作了行為oper_name_1(使用者數量級為3000+w)的使用者在後續7天內每天操作了另一個行為oper_name_2(使用者數量級為2700+w)的留存資料(使用者重合度在1000w以上)，耗時0.2秒左右反饋 最後和前端打通，效果也是有了明顯的優化，麻麻再也不用擔心我會轉暈~總結與思考

總的來說，本方案的優點是：

儲存小，極大地節約了儲存；查詢快，利用bitmapCardinality、bitmapAnd、bitmapOr等點陣圖函式快速計算使用者數和滿足一些條件的查詢，將緩慢的join操作轉化成點陣圖間的計算；適用於靈活天數的留存查詢；便於更新，使用者操作資料和使用者屬性資料分開儲存，便於後續屬性的增加和資料回滾。

另外，根據本方案的特點，除了留存分析工具，對於使用者群分析，事件分析等工具也可以嘗試用此方案來解決。

參考文獻：

[1] 解析常見的資料分析模型——留存分析：https://www.sensorsdata.cn/blog/jie-xi-chang-jian-de-shu-ju-fen-xi-mo-xing-liu-cun-fen-xi/

[2] RoaringBitmap資料結構及原理： https://blog.csdn.net/yizishou/article/details/78342499

[3] 高效壓縮點陣圖RoaringBitmap的原理與應用： https://www.jianshu.com/p/818ac4e90daf

[4] 論文：Better bitmap performance with Roaring bitmaps： /file/2020/08/19/20200819160448_1613.jpg.6407v9 Clickhouse文件-點陣圖函式： https://clickhouse.tech/docs/zh/sql-reference/functions/bitmap-functions/

原文地址:https://mp.weixin.qq.com/s?__biz=MjM5ODYwMjI2MA==&mid=2649748113&idx=1&sn=2f0ea3ba734f29e0c3df8a88fb73058d