用戶(hù)行為分析模型實(shí)踐(一)—— 路徑分析模型
一、需求背景
在互聯(lián)網(wǎng)數(shù)據(jù)化運(yùn)營(yíng)實(shí)踐中,有一類(lèi)數(shù)據(jù)分析應(yīng)用是互聯(lián)網(wǎng)行業(yè)所獨(dú)有的——路徑分析。路徑分析應(yīng)用是對(duì)特定頁(yè)面的上下游進(jìn)行可視化展示并分析用戶(hù)在使用產(chǎn)品時(shí)的路徑分布情況。比如:當(dāng)用戶(hù)使用某APP時(shí),是怎樣從【首頁(yè)】進(jìn)入【詳情頁(yè)】的,用戶(hù)從【首頁(yè)】分別進(jìn)入【詳情頁(yè)】、【播放頁(yè)】、【下載頁(yè)】的比例是怎樣的,以及可以幫助我們分析用戶(hù)離開(kāi)的節(jié)點(diǎn)是什么。
在場(chǎng)景對(duì)應(yīng)到具體的技術(shù)方案設(shè)計(jì)上,我們將訪(fǎng)問(wèn)數(shù)據(jù)根據(jù)session劃分,挖掘出用戶(hù)頻繁訪(fǎng)問(wèn)的路徑;功能上允許用戶(hù)即時(shí)查看所選節(jié)點(diǎn)相關(guān)路徑,支持用戶(hù)自定義設(shè)置路徑的起點(diǎn)或終點(diǎn),并支持按照業(yè)務(wù)新增用戶(hù)/活躍用戶(hù)查看不同目標(biāo)人群在同一條行為路徑上的轉(zhuǎn)化結(jié)果分析,滿(mǎn)足精細(xì)化分析的需求。
1.1 應(yīng)用場(chǎng)景
通常用戶(hù)在需要進(jìn)行路徑分析的場(chǎng)景時(shí)關(guān)注的主要問(wèn)題:
- 按轉(zhuǎn)換率從高至低排列在APP內(nèi)用戶(hù)的主要路徑是什么;
- 用戶(hù)在離開(kāi)預(yù)想的路徑后,實(shí)際走向是什么?
- 不同特征的用戶(hù)行為路徑有什么差異?
通過(guò)一個(gè)實(shí)際的業(yè)務(wù)場(chǎng)景我們可以看下路徑分析模型是如何解決此類(lèi)問(wèn)題的;
【業(yè)務(wù)場(chǎng)景】
分析“活躍用戶(hù)”到達(dá)目標(biāo)落地頁(yè)[小視頻頁(yè)]的主要行為路徑(日數(shù)據(jù)量為十億級(jí),要求計(jì)算結(jié)果產(chǎn)出時(shí)間1s左右)
【用戶(hù)操作】
- 選擇起始/結(jié)束頁(yè)面,添加篩選條件“用戶(hù)”;
- 選擇類(lèi)型“訪(fǎng)問(wèn)次數(shù)”/“會(huì)話(huà)次數(shù)”;
- 點(diǎn)擊查詢(xún),即時(shí)產(chǎn)出結(jié)果。
二、基本概念
在進(jìn)行具體的數(shù)據(jù)模型和工程架構(gòu)設(shè)計(jì)前,先介紹一些基礎(chǔ)概念,幫助大家更好的理解本文。
2.1 路徑分析
路徑分析是常用的數(shù)據(jù)挖據(jù)方法之一, 主要用于分析用戶(hù)在使用產(chǎn)品時(shí)的路徑分布情況,挖掘出用戶(hù)的頻繁訪(fǎng)問(wèn)路徑。與漏斗功能一樣,路徑分析會(huì)探索用戶(hù)在您的網(wǎng)站或應(yīng)用上逗留的過(guò)程中采取的各項(xiàng)步驟,但路徑分析可隨機(jī)對(duì)多條路徑進(jìn)行研究,而不僅僅是分析一條預(yù)先設(shè)定的路徑。
2.2 Session和Session Time
不同于WEB應(yīng)用中的Session,在數(shù)據(jù)分析中的Session會(huì)話(huà),是指在指定的時(shí)間段內(nèi)在網(wǎng)站上發(fā)生的一系列互動(dòng)。本模型中的Session Time的含義是,當(dāng)兩個(gè)行為間隔時(shí)間超過(guò)Session Time,我們便認(rèn)為這兩個(gè)行為不屬于同一條路徑。
2.3 ?;鶊D
?;鶊D(Sankey diagram),即?;芰糠至鲌D,也叫桑基能量平衡圖。它是一種特定類(lèi)型的流程圖,圖中延伸的分支的寬度對(duì)應(yīng)數(shù)據(jù)流量的大小。如圖4.1-1所示,每條邊表示上一節(jié)點(diǎn)到該節(jié)點(diǎn)的流量。一個(gè)完整的?;鶊D包括以下幾個(gè)內(nèi)容:節(jié)點(diǎn)數(shù)據(jù)及節(jié)點(diǎn)轉(zhuǎn)化率(下圖紅框部分)、邊數(shù)據(jù)及邊轉(zhuǎn)化率(下圖黑框部分)。轉(zhuǎn)化率的計(jì)算詳見(jiàn)【3.5. 轉(zhuǎn)化率計(jì)算】。
2.4 鄰接表
構(gòu)造?;鶊D可以簡(jiǎn)化為一個(gè)圖的壓縮存儲(chǔ)問(wèn)題。圖通常由幾個(gè)部分組成:
- 邊(edge)
- 點(diǎn)(vertex)
- 權(quán)重(weight)
- 度(degree)
本模型中,我們采用鄰接表進(jìn)行存儲(chǔ)。鄰接表是一種常用的圖壓縮存儲(chǔ)結(jié)構(gòu),借助鏈表來(lái)保存圖中的節(jié)點(diǎn)和邊而忽略各節(jié)點(diǎn)之間不存在的邊,從而對(duì)矩陣進(jìn)行壓縮。鄰接表的構(gòu)造如下:
(a)中,左側(cè)為頂點(diǎn)節(jié)點(diǎn),包含頂點(diǎn)數(shù)據(jù)及指向第一條邊的指針;右側(cè)為邊節(jié)點(diǎn),包含該邊的權(quán)重、出入度等邊信息以及指向下一條邊的指針。一個(gè)完整的鄰接表類(lèi)似于Hashmap的結(jié)構(gòu),如圖(b),左側(cè)是一個(gè)順序表,保存的是(a)中的邊節(jié)點(diǎn);每個(gè)邊節(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表存儲(chǔ)與該節(jié)點(diǎn)相連接的邊。頁(yè)面路徑模型中,為了適應(yīng)模型的需要,我們對(duì)頂點(diǎn)節(jié)點(diǎn)和邊節(jié)點(diǎn)結(jié)構(gòu)做了改造,詳情請(qǐng)見(jiàn)【4.1】節(jié)。
2.5 樹(shù)的剪枝
剪枝是樹(shù)的構(gòu)造中一個(gè)重要的步驟,指刪去一些不重要的節(jié)點(diǎn)來(lái)降低計(jì)算或搜索的復(fù)雜度。頁(yè)面路徑模型中,我們?cè)诩糁Νh(huán)節(jié)對(duì)原始數(shù)據(jù)構(gòu)造的樹(shù)進(jìn)行修整,去掉不符合條件的分支,來(lái)保證樹(shù)中每條根節(jié)點(diǎn)到葉節(jié)點(diǎn)路徑的完整性。
2.6 PV和SV
PV即Page View,訪(fǎng)問(wèn)次數(shù),本模型中指的是一段時(shí)間內(nèi)訪(fǎng)問(wèn)的次數(shù);SV即Session View,會(huì)話(huà)次數(shù),本模型中指出現(xiàn)過(guò)該訪(fǎng)問(wèn)路徑的會(huì)話(huà)數(shù)。如,有路徑一:A → B → C → D → A → B和路徑二:A → B → D,那么,A → B的PV為2+1=3,SV為1+1=2。
三、 數(shù)據(jù)模型設(shè)計(jì)
本節(jié)將介紹數(shù)據(jù)模型的設(shè)計(jì),包括數(shù)據(jù)流向、路徑劃分、ps/sv計(jì)算以及最終得到的?;鶊D中路徑的轉(zhuǎn)化率計(jì)算。
3.1 整體數(shù)據(jù)流向
數(shù)據(jù)來(lái)源于統(tǒng)一的數(shù)據(jù)倉(cāng)庫(kù),通過(guò)Spark計(jì)算后寫(xiě)入Clickhouse,并用Hive進(jìn)行冷備份。數(shù)據(jù)流向圖見(jiàn)圖3.1-1。
圖3.1-1
3.2 技術(shù)選型
Clickhouse不是本文的重點(diǎn),在此不詳細(xì)描述,僅簡(jiǎn)要說(shuō)明選擇Clickhouse的原因。
選擇的原因是在于,Clickhouse是列式存儲(chǔ),速度極快??聪聰?shù)據(jù)量級(jí)和查詢(xún)速度(截止到本文撰寫(xiě)的日期):
圖3.2-1
最后得到的千億數(shù)據(jù)查詢(xún)速度是這樣,
圖3.2-2
3.3 數(shù)據(jù)建模
3.3.1 獲取頁(yè)面信息,劃分session
頁(yè)面路徑模型基于各種事件id切割獲取到對(duì)應(yīng)的頁(yè)面id,來(lái)進(jìn)行頁(yè)面路徑分析。Session的概念可見(jiàn)第2.2節(jié),這里不再贅述。目前我們使用更加靈活的Session劃分,使得用戶(hù)可以查詢(xún)到在各種時(shí)間粒度(5,10,15,30,60分鐘)的Session會(huì)話(huà)下,用戶(hù)的頁(yè)面轉(zhuǎn)化信息。
假設(shè)有用戶(hù)a和用戶(hù)b,a用戶(hù)當(dāng)天發(fā)生的行為事件分別為 E1, E2, E3... , 對(duì)應(yīng)的頁(yè)面分別為P1, P2, P3... ,事件發(fā)生的時(shí)間分別為T(mén)1, T2, T3... ,選定的session間隔為tg。如圖所示T4-T3>tg,所以P1,P2,P3被劃分到了第一個(gè)Session,P4,P5被劃分到了第二個(gè)Session,同理P6及后面的頁(yè)面也被劃分到了新的Session。
偽代碼實(shí)現(xiàn)如下:
3.3.2 相鄰頁(yè)面去重
不同的事件可能對(duì)應(yīng)同一頁(yè)面,臨近的相同頁(yè)面需要被過(guò)濾掉,所以劃分session之后需要做的就是相鄰頁(yè)面去重。
圖3.3-2
相鄰頁(yè)面去重后得到的結(jié)果是這樣
圖3.3-3
3.3.3 獲取每個(gè)頁(yè)面的前/后四級(jí)頁(yè)面
然后對(duì)上述數(shù)據(jù)進(jìn)行窗口函數(shù)分析,獲取每個(gè)session中每個(gè)頁(yè)面的前后四級(jí)頁(yè)面,其中sid是根據(jù)用戶(hù)標(biāo)識(shí)ID和session號(hào)拼接而成,比如,針對(duì)上述的用戶(hù)a的第一個(gè)session 0會(huì)生成如下的7條記錄,圖中的page列為當(dāng)前頁(yè)面,空頁(yè)面用-1表示
圖3.3-4
計(jì)算剩下的,會(huì)得到一共7+7+6+4+5=29條記錄。得到全部記錄如下
3.3.4 統(tǒng)計(jì)正負(fù)向路徑的pv/sv
取page和page_id_previous1, page_id_previous2, page_id_previous3 ,page_id_previous4得到負(fù)向五級(jí)路徑(path_direction為2),取page和page_id_next1, page_id_next2, page_id_next3, page_id_next4得到正向五級(jí)路徑(path_direction為1),分別計(jì)算路徑的pv和sv(按照sid去重),得到如下數(shù)據(jù)dfSessions,
直接看上面的數(shù)據(jù)可能比較茫然,所以這里拆出兩條數(shù)據(jù)示例,第一條結(jié)果數(shù)據(jù)
圖3.3-4
這是一條正向的(path_direction為1)路徑結(jié)果數(shù)據(jù),在下圖中就是從左到右的路徑,對(duì)應(yīng)的兩個(gè)路徑如下
圖3.3-5
第二條結(jié)果數(shù)據(jù)
圖3.3-6
也是一條正向的路徑結(jié)果數(shù)據(jù),其中pv為2,對(duì)應(yīng)的兩個(gè)路徑如下,sv為1的原因是這兩條路徑的sid一致,都是用戶(hù)a在S1會(huì)話(huà)中產(chǎn)生的路徑
圖3.3-7
3.3.5 統(tǒng)計(jì)計(jì)算各級(jí)路徑的pv/sv
然后根據(jù)dfSessions數(shù)據(jù),按照page_id_lv1分組計(jì)算pv和sv的和,得到一級(jí)路徑的pv和sv,一級(jí)路徑特殊地會(huì)把path_direction設(shè)置為0
然后類(lèi)似地分別計(jì)算二三四五級(jí)路徑的pv和sv,合并所有結(jié)果得到如下
3.4 數(shù)據(jù)寫(xiě)入
通過(guò)Spark分析計(jì)算的結(jié)果數(shù)據(jù)需要寫(xiě)入Clickhouse來(lái)線(xiàn)上服務(wù),寫(xiě)入Hive來(lái)作為數(shù)據(jù)冷備份,可以進(jìn)行Clickhouse的數(shù)據(jù)恢復(fù)。
Clickhouse表使用的是分布式(Distributed)表結(jié)構(gòu),分布式表本身不存儲(chǔ)任何數(shù)據(jù),而是作為數(shù)據(jù)分片的透明代理,自動(dòng)路由到數(shù)據(jù)到集群中的各個(gè)節(jié)點(diǎn),所以分布式表引擎需要配合其他數(shù)據(jù)表引擎一起使用。用戶(hù)路徑分析模型的表數(shù)據(jù)被存儲(chǔ)在集群的各個(gè)分片中,分片方式使用隨機(jī)分片,在這里涉及到了Clickhouse的數(shù)據(jù)寫(xiě)入,我們展開(kāi)講解下。
有關(guān)于這一點(diǎn),在模型初期我們使用的是寫(xiě)分布式表的方式來(lái)寫(xiě)入數(shù)據(jù),具體的寫(xiě)入流程如下所示:
- 客戶(hù)端和集群中的A節(jié)點(diǎn)建立jdbc連接,并通過(guò)HTTP的POST請(qǐng)求寫(xiě)入數(shù)據(jù);
- A分片在收到數(shù)據(jù)之后會(huì)做兩件事情,第一,根據(jù)分片規(guī)則劃分?jǐn)?shù)據(jù),第二,將屬于當(dāng)前分片的數(shù)據(jù)寫(xiě)入自己的本地表;
- A分片將屬于遠(yuǎn)端分片的數(shù)據(jù)以分區(qū)為單位,寫(xiě)入目錄下臨時(shí)bin文件,命名規(guī)則如:/database@host:port/[increase_num].bin;
- A分片嘗試和遠(yuǎn)端分片建立連接;
- 會(huì)有另一組監(jiān)聽(tīng)任務(wù)監(jiān)聽(tīng)上面產(chǎn)生的臨時(shí)bin文件,并將這些數(shù)據(jù)發(fā)送到遠(yuǎn)端分片,每份數(shù)據(jù)單線(xiàn)程發(fā)送;
- 遠(yuǎn)端分片接收數(shù)據(jù)并且寫(xiě)入本地表;
- A分片確認(rèn)完成寫(xiě)入。
通過(guò)以上過(guò)程可以看出,Distributed表負(fù)責(zé)所有分片的數(shù)據(jù)寫(xiě)入工作,所以建立jdbc連接的節(jié)點(diǎn)的出入流量會(huì)峰值極高,會(huì)產(chǎn)生以下幾個(gè)問(wèn)題:
- 單臺(tái)節(jié)點(diǎn)的負(fù)載過(guò)高,主要體現(xiàn)在內(nèi)存、網(wǎng)卡出入流量和TCP連接等待數(shù)量等,機(jī)器健康程度很差;
- 當(dāng)業(yè)務(wù)增長(zhǎng)后更多的模型會(huì)接入Clickhouse做OLAP,意味著更大的數(shù)據(jù)量,以當(dāng)前的方式來(lái)繼續(xù)寫(xiě)入的必然會(huì)造成單臺(tái)機(jī)器宕機(jī),在當(dāng)前沒(méi)有做高可用的狀況下,單臺(tái)機(jī)器的宕機(jī)會(huì)造成整個(gè)集群的不可用;
- 后續(xù)一定會(huì)做ck集群的高可用,使用可靠性更高的ReplicatedMergeTree,使用這種引擎在寫(xiě)入數(shù)據(jù)的時(shí)候,也會(huì)因?yàn)閷?xiě)分布式表而出現(xiàn)數(shù)據(jù)不一致的情況。
針對(duì)于此數(shù)據(jù)端做了DNS輪詢(xún)寫(xiě)本地表的改造,經(jīng)過(guò)改造之后:
- 用于JDBC連接的機(jī)器的TCP連接等待數(shù)由90下降到25,降低了72%以上;
- 用于JDBC連接的機(jī)器的入流量峰值由645M/s降低到76M/s,降低了88%以上;
- 用于JDBC連接的機(jī)器因分發(fā)數(shù)據(jù)而造成的出流量約為92M/s,改造后這部分出流量清零。
另外,在Distributed表負(fù)責(zé)向遠(yuǎn)端分片寫(xiě)入數(shù)據(jù)的時(shí)候,有異步寫(xiě)和同步寫(xiě)兩種方式,異步寫(xiě)的話(huà)會(huì)在Distributed表寫(xiě)完本地分片之后就會(huì)返回寫(xiě)入成功信息,如果是同步寫(xiě),會(huì)在所有分片都寫(xiě)入完成才返回成功信息,默認(rèn)的情況是異步寫(xiě),我們可以通過(guò)修改參數(shù)來(lái)控制同步寫(xiě)的等待超時(shí)時(shí)間。
3.5 轉(zhuǎn)化率計(jì)算
在前端頁(yè)面選擇相應(yīng)的維度,選中起始頁(yè)面:
后端會(huì)在Clickhouse中查詢(xún),
- 選定節(jié)點(diǎn)深度(node_depth)為1和一級(jí)頁(yè)面(page_id_lv1)是選定頁(yè)面的數(shù)據(jù),得到一級(jí)頁(yè)面及其sv/pv,
- 選定節(jié)點(diǎn)深度(node_depth)為2和一級(jí)頁(yè)面(page_id_lv1)是選定頁(yè)面的數(shù)據(jù),按照sv/pv倒序取前10,得到二級(jí)頁(yè)面及其sv/pv,
- 選定節(jié)點(diǎn)深度(node_depth)為2和一級(jí)頁(yè)面(page_id_lv1)是選定頁(yè)面的數(shù)據(jù),按照sv/pv倒序取前20,得到三級(jí)頁(yè)面及其sv/pv,
- 選定節(jié)點(diǎn)深度(node_depth)為2和一級(jí)頁(yè)面(page_id_lv1)是選定頁(yè)面的數(shù)據(jù),按照sv/pv倒序取前30,得到四級(jí)頁(yè)面及其sv/pv,
- 選定節(jié)點(diǎn)深度(node_depth)為2和一級(jí)頁(yè)面(page_id_lv1)是選定頁(yè)面的數(shù)據(jù),按照sv/pv倒序取前50,得到五級(jí)頁(yè)面及其sv/pv,
轉(zhuǎn)化率計(jì)算規(guī)則:
頁(yè)面轉(zhuǎn)化率:
假設(shè)有路徑 A-B-C,A-D-C,A-B-D-C,其中ABCD分別是四個(gè)不同頁(yè)面
計(jì)算三級(jí)頁(yè)面C的轉(zhuǎn)化率:
(所有節(jié)點(diǎn)深度為3的路徑中三級(jí)頁(yè)面是C的路徑的pv/sv和)÷(一級(jí)頁(yè)面的pv/sv)
路徑轉(zhuǎn)化率
假設(shè)有A-B-C,A-D-C,A-B-D-C,其中ABCD分別是四個(gè)不同頁(yè)面
計(jì)算A-B-C路徑中B-C的轉(zhuǎn)化率:
(A-B-C這條路徑的pv/sv)÷(所有節(jié)點(diǎn)深度為3的路徑中二級(jí)頁(yè)面是B的路徑的pv/sv和)
四、工程端架構(gòu)設(shè)計(jì)
本節(jié)將講解工程端的處理架構(gòu),包括幾個(gè)方面:?;鶊D的構(gòu)造、路徑合并以及轉(zhuǎn)化率計(jì)算、剪枝。
4.1 ?;鶊D的構(gòu)造
從上述原型圖可以看到,我們需要構(gòu)造?;鶊D,對(duì)于工程端而言就是需要構(gòu)造帶權(quán)路徑樹(shù)。
簡(jiǎn)化一下上圖,就可以將需求轉(zhuǎn)化為構(gòu)造帶權(quán)樹(shù)的鄰接表。如下左圖就是我們的鄰接表設(shè)計(jì)。左側(cè)順序列表存儲(chǔ)的是各個(gè)節(jié)點(diǎn)(Vertex),包含節(jié)點(diǎn)名稱(chēng)(name)、節(jié)點(diǎn)代碼(code)等節(jié)點(diǎn)信息和一個(gè)指向邊(Edge)列表的指針;每個(gè)節(jié)點(diǎn)(Vertex)指向一個(gè)邊(Edge)鏈表,每條邊保存的是當(dāng)前邊的權(quán)重、端點(diǎn)信息以及指向同節(jié)點(diǎn)下一條邊的指針。
圖4.1-2
圖4.1-3
圖4.1-2就是我們?cè)谀P椭惺褂玫降泥徑颖怼_@里在2.4中描述的鄰接表上做了一些改動(dòng)。在我們的桑基圖中,不同層級(jí)會(huì)出現(xiàn)相同名稱(chēng)不同轉(zhuǎn)化率的節(jié)點(diǎn),這些節(jié)點(diǎn)作為路徑的一環(huán),并不能按照名稱(chēng)被看作重復(fù)節(jié)點(diǎn),不構(gòu)成環(huán)路。如果整個(gè)?;鶊D用一個(gè)鄰接表表示,那么這類(lèi)節(jié)點(diǎn)將被當(dāng)作相同節(jié)點(diǎn),使得圖像當(dāng)中出現(xiàn)環(huán)路。因此,我們將桑基圖按照層級(jí)劃分,每?jī)杉?jí)用一個(gè)鄰接表表示,如圖4.1-2,Level 1表示層級(jí)1的節(jié)點(diǎn)和指向?qū)蛹?jí)2的邊、Level 2表示層級(jí)2的節(jié)點(diǎn)指向?qū)蛹?jí)3的邊,以此類(lèi)推。
4.2 路徑的定義
首先,我們先回顧一下?;鶊D:
圖4.2-1
觀察上圖可以發(fā)現(xiàn),我們需要計(jì)算四個(gè)數(shù)據(jù):每個(gè)節(jié)點(diǎn)的pv/sv、每個(gè)節(jié)點(diǎn)的轉(zhuǎn)化率、節(jié)點(diǎn)間的pv/sv、節(jié)點(diǎn)間的轉(zhuǎn)化率。那么下面我們給出這幾個(gè)數(shù)據(jù)的定義:
- 節(jié)點(diǎn)pv/sv = 當(dāng)前節(jié)點(diǎn)在當(dāng)前層次中的pv/sv總和
- 節(jié)點(diǎn)轉(zhuǎn)化率 = ( 節(jié)點(diǎn)pv/sv ) / ( 路徑起始節(jié)點(diǎn)pv/sv )
- 節(jié)點(diǎn)間pv/sv = 上一級(jí)節(jié)點(diǎn)流向當(dāng)前節(jié)點(diǎn)的pv/sv
- 節(jié)點(diǎn)間轉(zhuǎn)化率 = ( 節(jié)點(diǎn)間pv/sv ) / ( 上一級(jí)節(jié)點(diǎn)pv/sv )
再來(lái)看下存儲(chǔ)在Clickhouse中的路徑數(shù)據(jù)。先來(lái)看看表結(jié)構(gòu):
上述為路徑表中比較重要的幾個(gè)字段,分別表示節(jié)點(diǎn)深度和各級(jí)節(jié)點(diǎn)。表中的數(shù)據(jù)包含了完整路徑和中間路徑。完整路徑指的是:路徑從起點(diǎn)到退出、從起點(diǎn)到達(dá)指定終點(diǎn),超出5層的路徑當(dāng)作5層路徑來(lái)處理。中間路徑是指數(shù)據(jù)計(jì)算過(guò)程中產(chǎn)生的中間數(shù)據(jù),并不能作為一條完整的路徑。
路徑數(shù)據(jù):
(1)完整路徑
(2)不完整路徑
那么我們需要從數(shù)據(jù)中篩選出完整路徑,并將路徑數(shù)據(jù)組織成樹(shù)狀結(jié)構(gòu)。
4.3 設(shè)計(jì)實(shí)現(xiàn)
4.3.1 整體框架
圖4.3-1
后端整體實(shí)現(xiàn)思路很明確,主要步驟就是讀取數(shù)據(jù)、構(gòu)造鄰接表和剪枝。那么要怎么實(shí)現(xiàn)完整/非完整路徑的篩選呢?我們通過(guò)service層剪枝來(lái)過(guò)濾掉不完整的路徑。以下是描述整個(gè)流程的偽代碼:
4.3.2 Clickhouse連接池
頁(yè)面路徑中我們引入了ClickHouse,其特點(diǎn)在這里不再贅述。我們使用一個(gè)簡(jiǎn)單的Http連接池連接ClickHouse Server。連接池結(jié)構(gòu)如下:
圖4.3-2
4.3.3 數(shù)據(jù)讀取
如2中描述的,我們需要讀取數(shù)據(jù)中的完整路徑。
在上述表結(jié)構(gòu)中可以看到,寫(xiě)入數(shù)據(jù)庫(kù)的路徑已經(jīng)是經(jīng)過(guò)一級(jí)篩選,深度≤5的路徑。我們需要在此基礎(chǔ)上再將完整路徑和不完整路徑區(qū)分開(kāi),根據(jù)需要根據(jù)node_depth和page_id_lvn來(lái)判斷是否為完整路徑并計(jì)算每個(gè)節(jié)點(diǎn)的value。
完整路徑判斷條件:
- node_depth=n, page_id_lvn=pageId (n < MAX_DEPTH)
- node_depth=n, page_id_lvn=pageId || page_id_lvn=EXIT_NODE (n = MAX_DEPTH)
完整路徑的條件我們已經(jīng)知道了,那么讀取路徑時(shí)有兩種方案。方案一:直接根據(jù)上述條件進(jìn)行篩選來(lái)獲取完整路徑,由于Clickhouse及后端性能的限制,取數(shù)時(shí)必須limit;方案二:逐層讀取,可以計(jì)算全量數(shù)據(jù),但是無(wú)法保證取出準(zhǔn)確數(shù)量的路徑。
通過(guò)觀察發(fā)現(xiàn),數(shù)據(jù)中會(huì)存在重復(fù)路徑,并且假設(shè)有兩條路徑:
A → B → C → D → EXIT_NODE
A → B → E → D → EXIT_NODE
當(dāng)有以上兩條路徑時(shí),需要計(jì)算每個(gè)節(jié)點(diǎn)的value。而在實(shí)際數(shù)據(jù)中,我們只能通過(guò)不完整路徑來(lái)獲取當(dāng)前節(jié)點(diǎn)的value。因此,方案一不適用。
那么方案二就可以通過(guò)以下偽代碼逐層讀?。?/p>
讀取出的數(shù)據(jù)如下:
那么,node1_A_val = 10+20,node2_B_val = 9+15 以此類(lèi)推。
4.3.4 剪枝
根據(jù)4.3.3,在取數(shù)階段我們會(huì)分層取出所有原始數(shù)據(jù),而原始數(shù)據(jù)中包含了完整和非完整路徑。如下圖是直接根據(jù)原始數(shù)據(jù)構(gòu)造的樹(shù)(原始樹(shù))。按照我們對(duì)完整路徑的定義:路徑深度達(dá)到5且結(jié)束節(jié)點(diǎn)為退出或其它節(jié)點(diǎn);路徑深度未達(dá)到5且結(jié)束節(jié)點(diǎn)為退出??梢?jiàn),圖中標(biāo)紅的部分(node4_lv1 → node3_lv2)是一條不完整路徑。
另外,原始樹(shù)中還會(huì)出現(xiàn)孤立節(jié)點(diǎn)(綠色節(jié)點(diǎn)node4_lv2)。這是由于在取數(shù)階段,我們會(huì)對(duì)數(shù)據(jù)進(jìn)行分層排序再取出,這樣一來(lái)無(wú)法保證每層數(shù)據(jù)的關(guān)聯(lián)性。因此,node4_lv2節(jié)點(diǎn)在lv2層排序靠前,而其前驅(qū)、后繼節(jié)點(diǎn)排序靠后無(wú)法選中,從而導(dǎo)致孤立節(jié)點(diǎn)產(chǎn)生。
圖4.3-3
因此,在我們?nèi)〕鲈紨?shù)據(jù)集后,還需要進(jìn)行過(guò)濾才能獲取我們真正需要的路徑。
在模型中,我們通過(guò)剪枝來(lái)實(shí)現(xiàn)這一過(guò)濾操作。
在前述的步驟中,我們已經(jīng)獲取了雙向edge列表(父子關(guān)系和子父關(guān)系列表)。因此在上述偽代碼[1]中,借助edge列表即可快速查找當(dāng)前節(jié)點(diǎn)的前驅(qū)和后繼,從而判斷當(dāng)前節(jié)點(diǎn)是否為孤立節(jié)點(diǎn)。
同樣,我們利用edge列表對(duì)不完整路徑進(jìn)行裁剪。對(duì)于不完整路徑,剪枝時(shí)只需要關(guān)心深度不足MAX_DEPTH且最后節(jié)點(diǎn)不為EXIT_NODE的路徑。那么在上述偽代碼[2]中,我們只需要判斷當(dāng)前層的節(jié)點(diǎn)是否存在順序邊(父子關(guān)系)即可,若不存在,則清除當(dāng)前節(jié)點(diǎn)。
五、寫(xiě)在最后
基于平臺(tái)化查詢(xún)中查詢(xún)時(shí)間短、需要可視化的要求,并結(jié)合現(xiàn)有的存儲(chǔ)計(jì)算資源以及具體需求,我們?cè)趯?shí)現(xiàn)中將路徑數(shù)據(jù)進(jìn)行枚舉后分為兩次進(jìn)行合并,第一次是同一天內(nèi)對(duì)相同路徑進(jìn)行合并,第二次是在日期區(qū)間內(nèi)對(duì)路徑進(jìn)行匯總。本文希望能為路徑分析提供參考,在使用時(shí)還需結(jié)合各業(yè)務(wù)自身的特性進(jìn)行合理設(shè)計(jì),更好地服務(wù)于業(yè)務(wù)。
方案中涉及到的Clickhouse在這里不詳細(xì)介紹,感興趣的同學(xué)可以去深入了解,歡迎和筆者一起探討學(xué)習(xí)。