一、需求背景

在互聯(lián)網(wǎng)數(shù)據(jù)化運(yùn)營(yíng)實(shí)踐中，有一類數(shù)據(jù)分析應(yīng)用是互聯(lián)網(wǎng)行業(yè)所獨(dú)有的——路徑分析。路徑分析應(yīng)用是對(duì)特定頁(yè)面的上下游進(jìn)行可視化展示并分析用戶在使用產(chǎn)品時(shí)的路徑分布情況。比如：當(dāng)用戶使用某APP時(shí)，是怎樣從【首頁(yè)】進(jìn)入【詳情頁(yè)】的，用戶從【首頁(yè)】分別進(jìn)入【詳情頁(yè)】、【播放頁(yè)】、【下載頁(yè)】的比例是怎樣的，以及可以幫助我們分析用戶離開(kāi)的節(jié)點(diǎn)是什么。

在場(chǎng)景對(duì)應(yīng)到具體的技術(shù)方案設(shè)計(jì)上，我們將訪問(wèn)數(shù)據(jù)根據(jù)session劃分，挖掘出用戶頻繁訪問(wèn)的路徑；功能上允許用戶即時(shí)查看所選節(jié)點(diǎn)相關(guān)路徑，支持用戶自定義設(shè)置路徑的起點(diǎn)或終點(diǎn)，并支持按照業(yè)務(wù)新增用戶/活躍用戶查看不同目標(biāo)人群在同一條行為路徑上的轉(zhuǎn)化結(jié)果分析，滿足精細(xì)化分析的需求。

1.1 應(yīng)用場(chǎng)景

通常用戶在需要進(jìn)行路徑分析的場(chǎng)景時(shí)關(guān)注的主要問(wèn)題：

• 按轉(zhuǎn)換率從高至低排列在APP內(nèi)用戶的主要路徑是什么；
• 用戶在離開(kāi)預(yù)想的路徑后，實(shí)際走向是什么？
• 不同特征的用戶行為路徑有什么差異？

通過(guò)一個(gè)實(shí)際的業(yè)務(wù)場(chǎng)景我們可以看下路徑分析模型是如何解決此類問(wèn)題的；

【業(yè)務(wù)場(chǎng)景】

分析“活躍用戶”到達(dá)目標(biāo)落地頁(yè)[小視頻頁(yè)]的主要行為路徑（日數(shù)據(jù)量為十億級(jí)，要求計(jì)算結(jié)果產(chǎn)出時(shí)間1s左右）

【用戶操作】

1. 選擇起始/結(jié)束頁(yè)面，添加篩選條件“用戶”；
2. 選擇類型“訪問(wèn)次數(shù)”/“會(huì)話次數(shù)”；
3. 點(diǎn)擊查詢，即時(shí)產(chǎn)出結(jié)果。

二、基本概念

在進(jìn)行具體的數(shù)據(jù)模型和工程架構(gòu)設(shè)計(jì)前，先介紹一些基礎(chǔ)概念，幫助大家更好的理解本文。

2.1 路徑分析

路徑分析是常用的數(shù)據(jù)挖據(jù)方法之一， 主要用于分析用戶在使用產(chǎn)品時(shí)的路徑分布情況，挖掘出用戶的頻繁訪問(wèn)路徑。與漏斗功能一樣，路徑分析會(huì)探索用戶在您的網(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ì)話，是指在指定的時(shí)間段內(nèi)在網(wǎng)站上發(fā)生的一系列互動(dòng)。本模型中的Session Time的含義是，當(dāng)兩個(gè)行為間隔時(shí)間超過(guò)Session Time，我們便認(rèn)為這兩個(gè)行為不屬于同一條路徑。

2.3 桑基圖

桑基圖（Sankey diagram），即桑基能量分流圖，也叫桑基能量平衡圖。它是一種特定類型的流程圖，圖中延伸的分支的寬度對(duì)應(yīng)數(shù)據(jù)流量的大小。如圖4.1-1所示，每條邊表示上一節(jié)點(diǎn)到該節(jié)點(diǎn)的流量。一個(gè)完整的桑基圖包括以下幾個(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)造桑基圖可以簡(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è)完整的鄰接表類似于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，訪問(wèn)次數(shù)，本模型中指的是一段時(shí)間內(nèi)訪問(wèn)的次數(shù)；SV即Session View，會(huì)話次數(shù)，本模型中指出現(xiàn)過(guò)該訪問(wèn)路徑的會(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ì)算以及最終得到的桑基圖中路徑的轉(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í)和查詢速度（截止到本文撰寫(xiě)的日期）：

圖3.2-1

最后得到的千億數(shù)據(jù)查詢速度是這樣，

圖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劃分，使得用戶可以查詢到在各種時(shí)間粒度（5,10,15,30,60分鐘）的Session會(huì)話下，用戶的頁(yè)面轉(zhuǎn)化信息。

假設(shè)有用戶a和用戶b，a用戶當(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)如下：

def splitPageSessions(timeSeq: Seq[Long], events: Seq[String], interval: Int)
                     (implicit separator: String): Array[Array[Array[String]]] = {
  // 參數(shù)中的events是事件集合，timeSeq是相應(yīng)的事件發(fā)生時(shí)間的集合
  if (events.contains(separator))
    throw new IllegalArgumentException("Separator should't be in events.")
  if (events.length != timeSeq.length)
    throw new Exception("Events and timeSeq not in equal length.")
  val timeBuf = ArrayBuffer[String](timeSeq.head.toString) // 存儲(chǔ)含有session分隔標(biāo)識(shí)的時(shí)間集合
  val eventBuf = ArrayBuffer[String](events.head) // 存儲(chǔ)含有session分隔標(biāo)識(shí)的事件集合
  if (timeSeq.length >= 2) {
    events.indices.tail.foreach { i =>
      if (timeSeq(i) - timeSeq(i - 1) > interval * 60000) { // 如果兩個(gè)事件的發(fā)生時(shí)間間隔超過(guò)設(shè)置的時(shí)間間隔，則添加分隔符作為后面劃分session的標(biāo)識(shí)
        timeBuf += separator;
        eventBuf += separator
      }
      timeBuf += timeSeq(i).toString;
      eventBuf += events(i)
    }
  }
  val tb = timeBuf.mkString(",").split(s",\\$separator,").map(_.split(",")) // 把集合通過(guò)標(biāo)識(shí)符劃分成為各個(gè)session下的時(shí)間集合
  val eb = eventBuf.mkString(",").split(s",\\$separator,").map(_.split(",")) // 把集合通過(guò)標(biāo)識(shí)符劃分成為各個(gè)session下的事件集合
  tb.zip(eb).map(t => Array(t._1, t._2)) // 把session中的事件和發(fā)生時(shí)間對(duì)應(yīng)zip到一起，并把元組修改成數(shù)組類型，方便后續(xù)處理
}

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ù)用戶標(biāo)識(shí)ID和session號(hào)拼接而成，比如，針對(duì)上述的用戶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一致，都是用戶a在S1會(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

然后類似地分別計(jì)算二三四五級(jí)路徑的pv和sv，合并所有結(jié)果得到如下

3.4 數(shù)據(jù)寫(xiě)入

通過(guò)Spark分析計(jì)算的結(jié)果數(shù)據(jù)需要寫(xiě)入Clickhouse來(lái)線上服務(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ù)表引擎一起使用。用戶路徑分析模型的表數(shù)據(jù)被存儲(chǔ)在集群的各個(gè)分片中，分片方式使用隨機(jī)分片，在這里涉及到了Clickhouse的數(shù)據(jù)寫(xiě)入，我們展開(kāi)講解下。

有關(guān)于這一點(diǎn)，在模型初期我們使用的是寫(xiě)分布式表的方式來(lái)寫(xiě)入數(shù)據(jù)，具體的寫(xiě)入流程如下所示：

1. 客戶端和集群中的A節(jié)點(diǎn)建立jdbc連接，并通過(guò)HTTP的POST請(qǐng)求寫(xiě)入數(shù)據(jù)；
2. A分片在收到數(shù)據(jù)之后會(huì)做兩件事情，第一，根據(jù)分片規(guī)則劃分?jǐn)?shù)據(jù)，第二，將屬于當(dāng)前分片的數(shù)據(jù)寫(xiě)入自己的本地表；
3. A分片將屬于遠(yuǎn)端分片的數(shù)據(jù)以分區(qū)為單位，寫(xiě)入目錄下臨時(shí)bin文件，命名規(guī)則如：/database@host:port/[increase_num].bin；
4. A分片嘗試和遠(yuǎn)端分片建立連接；
5. 會(huì)有另一組監(jiān)聽(tīng)任務(wù)監(jiān)聽(tīng)上面產(chǎn)生的臨時(shí)bin文件，并將這些數(shù)據(jù)發(fā)送到遠(yuǎn)端分片，每份數(shù)據(jù)單線程發(fā)送；
6. 遠(yuǎn)端分片接收數(shù)據(jù)并且寫(xiě)入本地表；
7. A分片確認(rèn)完成寫(xiě)入。

通過(guò)以上過(guò)程可以看出，Distributed表負(fù)責(zé)所有分片的數(shù)據(jù)寫(xiě)入工作，所以建立jdbc連接的節(jié)點(diǎn)的出入流量會(huì)峰值極高，會(huì)產(chǎn)生以下幾個(gè)問(wèn)題：

1. 單臺(tái)節(jié)點(diǎn)的負(fù)載過(guò)高，主要體現(xiàn)在內(nèi)存、網(wǎng)卡出入流量和TCP連接等待數(shù)量等，機(jī)器健康程度很差；
2. 當(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è)集群的不可用；
3. 后續(xù)一定會(huì)做ck集群的高可用，使用可靠性更高的ReplicatedMergeTree，使用這種引擎在寫(xiě)入數(shù)據(jù)的時(shí)候，也會(huì)因?yàn)閷?xiě)分布式表而出現(xiàn)數(shù)據(jù)不一致的情況。

針對(duì)于此數(shù)據(jù)端做了DNS輪詢寫(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ì)在Distributed表寫(xiě)完本地分片之后就會(huì)返回寫(xiě)入成功信息，如果是同步寫(xiě)，會(huì)在所有分片都寫(xiě)入完成才返回成功信息，默認(rèn)的情況是異步寫(xiě)，我們可以通過(guò)修改參數(shù)來(lái)控制同步寫(xiě)的等待超時(shí)時(shí)間。

def splitPageSessions(timeSeq: Seq[Long], events: Seq[String], interval: Int)
                     (implicit separator: String): Array[Array[Array[String]]] = {
  // 參數(shù)中的events是事件集合，timeSeq是相應(yīng)的事件發(fā)生時(shí)間的集合
  if (events.contains(separator))
    throw new IllegalArgumentException("Separator should't be in events.")
  if (events.length != timeSeq.length)
    throw new Exception("Events and timeSeq not in equal length.")
  val timeBuf = ArrayBuffer[String](timeSeq.head.toString) // 存儲(chǔ)含有session分隔標(biāo)識(shí)的時(shí)間集合
  val eventBuf = ArrayBuffer[String](events.head) // 存儲(chǔ)含有session分隔標(biāo)識(shí)的事件集合
  if (timeSeq.length >= 2) {
    events.indices.tail.foreach { i =>
      if (timeSeq(i) - timeSeq(i - 1) > interval * 60000) { // 如果兩個(gè)事件的發(fā)生時(shí)間間隔超過(guò)設(shè)置的時(shí)間間隔，則添加分隔符作為后面劃分session的標(biāo)識(shí)
        timeBuf += separator;
        eventBuf += separator
      }
      timeBuf += timeSeq(i).toString;
      eventBuf += events(i)
    }
  }
  val tb = timeBuf.mkString(",").split(s",\\$separator,").map(_.split(",")) // 把集合通過(guò)標(biāo)識(shí)符劃分成為各個(gè)session下的時(shí)間集合
  val eb = eventBuf.mkString(",").split(s",\\$separator,").map(_.split(",")) // 把集合通過(guò)標(biāo)識(shí)符劃分成為各個(gè)session下的事件集合
  tb.zip(eb).map(t => Array(t._1, t._2)) // 把session中的事件和發(fā)生時(shí)間對(duì)應(yīng)zip到一起，并把元組修改成數(shù)組類型，方便后續(xù)處理
}

3.5 轉(zhuǎn)化率計(jì)算

在前端頁(yè)面選擇相應(yīng)的維度，選中起始頁(yè)面：

后端會(huì)在Clickhouse中查詢，

• 選定節(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è)方面：桑基圖的構(gòu)造、路徑合并以及轉(zhuǎn)化率計(jì)算、剪枝。

4.1 桑基圖的構(gòu)造

從上述原型圖可以看到，我們需要構(gòu)造桑基圖，對(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)名稱（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è)谀Ｐ椭惺褂玫降泥徑颖怼＿@里在2.4中描述的鄰接表上做了一些改動(dòng)。在我們的桑基圖中，不同層級(jí)會(huì)出現(xiàn)相同名稱不同轉(zhuǎn)化率的節(jié)點(diǎn)，這些節(jié)點(diǎn)作為路徑的一環(huán)，并不能按照名稱被看作重復(fù)節(jié)點(diǎn)，不構(gòu)成環(huán)路。如果整個(gè)桑基圖用一個(gè)鄰接表表示，那么這類節(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的邊，以此類推。

4.2 路徑的定義

首先，我們先回顧一下桑基圖：

圖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)：

(
  `node_depth` Int8 COMMENT '節(jié)點(diǎn)深度，共5個(gè)層級(jí)深度，枚舉值1-2-3-4-5' CODEC(T64, LZ4HC(0)),
  `page_id_lv1` String COMMENT '一級(jí)頁(yè)面，起始頁(yè)面' CODEC(LZ4HC(0)),
  `page_id_lv2` String COMMENT '二級(jí)頁(yè)面' CODEC(LZ4HC(0)),
  `page_id_lv3` String COMMENT '三級(jí)頁(yè)面' CODEC(LZ4HC(0)),
  `page_id_lv4` String COMMENT '四級(jí)頁(yè)面' CODEC(LZ4HC(0)),
  `page_id_lv5` String COMMENT '五級(jí)頁(yè)面' CODEC(LZ4HC(0))
)

上述為路徑表中比較重要的幾個(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è)流程的偽代碼：

// 1-1: 分層讀取原始數(shù)據(jù)
// 1-1-1: 分層構(gòu)造Clickhouse Sql
    for( int depth = 1; depth <= MAX_DEPTH; depth ++){
        sql.append(select records where node_depth = depth)
    }
// 1-1-2: 讀取數(shù)據(jù)
    clickPool.getClient();
    records = clickPool.getResponse(sql);
// 2-1: 獲取節(jié)點(diǎn)之間的父子、子父關(guān)系（雙向edge構(gòu)造）
    findFatherAndSonRelation(records);
    findSonAndFathRelation(records);
// 3-1: 剪枝
// 3-1-1: 清除孤立節(jié)點(diǎn)
    for(int depth = 2; depth <= MAX_DEPTH; depth ++){
        while(hasNode()){
            node = getNode();
            if node does not have father in level depth-1:
                cut out node;
        }
    }
// 3-1-2: 過(guò)濾不完整路徑
    for(int depth = MAX_DEPTH - 1; depth >= 1; depth --){
        cut out this path;
    }
// 3-2: 構(gòu)造鄰接表
    while(node.hasNext()){
        sumVal = calculate the sum of pv/sv of this node until this level;
        edgeDetails = get the details of edges connected to this node and the end point connected to the edges;
        sortEdgesByEndPoint(edgeDetails);
        path = new Path(sumVal, edgeDetails);
    }

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ù)中的完整路徑。

(
  `node_depth` Int8 COMMENT '節(jié)點(diǎn)深度，枚舉值',
  `page_id_lv1` String COMMENT '一級(jí)頁(yè)面，起始頁(yè)面',
  `page_id_lv2` String COMMENT '二級(jí)頁(yè)面',
  `page_id_lv3` String COMMENT '三級(jí)頁(yè)面',
  `page_id_lv4` String COMMENT '四級(jí)頁(yè)面',
  `page_id_lv5` String COMMENT '五級(jí)頁(yè)面',
  `val` Int64 COMMENT '全量數(shù)據(jù)value'
)

在上述表結(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ò)以下偽代碼逐層讀取：

for(depth = 1; depth <= MAX_DEPTH; depth++){
    select
        node_depth as nodeDepth,
        ...,
        sum(sv) as val
    from
        table_name
    where
        ...
        AND (toInt16OrNull(pageId1) = 45)
        AND (node_depth = depth)
        ...
    group by
        node_depth,
        pageId1,
        pageId2,
        ...
    ORDER BY
        ...
    LIMIT
        ...
}

讀取出的數(shù)據(jù)如下：

那么，node1_A_val = 10+20，node2_B_val = 9+15 以此類推。

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ò)濾操作。

// 清除孤立節(jié)點(diǎn)
    for(int depth = 2; depth <= MAX_DEPTH; depth ++){
        while(hasNode()){
            node = getNode();
            if node does not have any father and son: // [1]
                cut out node;
        }
    }
// 過(guò)濾不完整路徑
    for(int depth = MAX_DEPTH - 1; depth >= 1; depth --){
        cut out this path; // [2]
    }

在前述的步驟中，我們已經(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)化查詢中查詢時(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í)。