傳統(tǒng)的客戶端監(jiān)控分析場景中，采用按照具體的 URL 進(jìn)行統(tǒng)計(jì)分析的方法，在面對(duì)一個(gè)應(yīng)用可能會(huì)訪問成千上萬條 URL 時(shí)，結(jié)果就差強(qiáng)人意，不能明顯地標(biāo)識(shí)出應(yīng)用訪問的哪些 URL 存在潛在問題。

MDAP 平臺(tái)在進(jìn)行客戶端監(jiān)控分析時(shí)，通過使用概率統(tǒng)計(jì)和機(jī)器學(xué)習(xí)的方案，將若干條相似的 URL 歸一化成同一條規(guī)則模型，然后基于該規(guī)則模型進(jìn)行相關(guān)統(tǒng)計(jì)分析，從而提高了基于 URL 的客戶端監(jiān)控分析的可用性及準(zhǔn)確性，進(jìn)而提高了 MDAP 用戶對(duì)自己應(yīng)用質(zhì)量的監(jiān)控分析。

1. 引言

URL 作為客戶端監(jiān)控分析的一個(gè)重要元素，傳統(tǒng)的基于 URL 的統(tǒng)計(jì)分析方式直接使用原始 URL 值進(jìn)行統(tǒng)計(jì)分析，比如：

SELECT `url`, count(1) as `cnt` 
    FROM `web_analysis_tab`
    WHERE `app_name` = 'app_1'
    GROUP BY `url`;

使用上述查詢語句進(jìn)行統(tǒng)計(jì)分析的結(jié)果是非常糟糕的，主要表現(xiàn)在以下幾個(gè)方面：

• 應(yīng)用開發(fā)者無法 快速地、準(zhǔn)確地 通過分析結(jié)果定位、發(fā)現(xiàn)潛在的應(yīng)用問題、風(fēng)險(xiǎn)；
• 統(tǒng)計(jì)結(jié)果過于 分散 ，用戶可能會(huì)失去查看統(tǒng)計(jì)分析結(jié)果的興趣；
• 平臺(tái)處理過濾離散數(shù)據(jù)的統(tǒng)計(jì)分析，可能存在較大的 系統(tǒng)開銷 ，包括：查詢效率、網(wǎng)絡(luò)傳輸、頁面展示等。

比如，假設(shè) app_1 訪問過 1,000,000 個(gè)不同值的 URL，而其 URL 規(guī)則模型 不足 100 個(gè) 。

初版的 MDAP （Multi-Dimension Analysis Platform，多維度分析平臺(tái)）用戶和開發(fā)者同樣面對(duì)此類問題的困擾。為了更好地服務(wù) MDAP 用戶，協(xié)助 MDAP 用戶快速、有效地分析自己的應(yīng)用質(zhì)量。MDAP 平臺(tái)基于 概率統(tǒng)計(jì) 理論和 機(jī)器學(xué)習(xí) 技術(shù)，根據(jù)應(yīng)用上報(bào)的 URL， 自動(dòng)學(xué)習(xí) 出相應(yīng)的 URL 模型，利用衍生字段 ??url_pattern?? 而非原始 ??url?? 進(jìn)行統(tǒng)計(jì)分析，從而大幅度減少了基于 URL 統(tǒng)計(jì)分析過于散列的情況，使得統(tǒng)計(jì)分析結(jié)果更加收斂，進(jìn)而更方便用戶使用 MDAP 對(duì)自己的應(yīng)用質(zhì)量進(jìn)行分析查看。

本文剩余部分的結(jié)構(gòu)安排如下：在第 2 節(jié)中，結(jié)合具體例子講解 MDAP 對(duì)解決 URL 歸一化問題的思考。第 3 節(jié)，介紹 MDAP 是如何對(duì) URL 進(jìn)行歸一化處理的總體框架，并在第 4 節(jié)中進(jìn)行詳細(xì)的算法描述。優(yōu)化效果的測試與評(píng)估在第 5 節(jié)中進(jìn)行闡述。最后，在第 6 節(jié)中，進(jìn)行總結(jié)并對(duì)未來進(jìn)行展望。

2. 問題思考

本章節(jié)將解釋這項(xiàng)工作的詳細(xì)動(dòng)機(jī)和思考。針對(duì)三種不同方案進(jìn)行分析，闡述配置/上傳 URL 模型規(guī)則的不可行性；通過一個(gè)具體的例子，展示自底向上的成對(duì)策略如何工作以及何時(shí)失?。徊⒔忉屇Ｊ綐錇楹斡行А?/p>

2.1 用戶配置方案

配置/上傳 URL 模型規(guī)則

為了將 URL 轉(zhuǎn)換成對(duì)應(yīng)的 URL 模型規(guī)則，最先考慮的方案是在平臺(tái)中，允許用戶配置/上傳應(yīng)用相關(guān)的 URL 模型規(guī)則，但隨即我們發(fā)現(xiàn)該方案存在幾點(diǎn)問題：

golang/gin : ??GET http://example.com/users/:user_name?? ；

golang/grpc-gateway : ??GET http://example.com/{name=users/*}?? ，遵守 Google API 設(shè)計(jì)規(guī)范；

java/spring : ??GET http://example.com/users/{user_name}?? 。

• 繁瑣的用戶配置。MDAP 平臺(tái)的宗旨是為了協(xié)助平臺(tái)用戶監(jiān)控、統(tǒng)計(jì)、分析自己的應(yīng)用質(zhì)量。為了進(jìn)行 URL 模型匹配而需要平臺(tái)用戶配置/上傳 URL 模型規(guī)則，無疑增加了平臺(tái)用戶的負(fù)擔(dān)。同時(shí)，平臺(tái)用戶極有可能遺忘進(jìn)行新的 URL 模型規(guī)則變更，從而嚴(yán)重影響 URL 模型匹配效果，進(jìn)而回退到傳統(tǒng)的基于 URL 統(tǒng)計(jì)分析模型。
• 差異化的 URL 模型規(guī)則。不同語言、框架的 URL 路由規(guī)則差異大，巨大的風(fēng)格差異不利于平臺(tái)進(jìn)行 URL 規(guī)則模型的統(tǒng)一管理，比如下面三種獲取某一具體用戶詳情信息的 URL 模型規(guī)則：
• 數(shù)據(jù)巨大的外部 URL。根據(jù) MDAP 平臺(tái)統(tǒng)計(jì)分析，單應(yīng)用訪問非本應(yīng)用服務(wù)的外部 URL 地址數(shù)量平均占比約為 10%-30%。這些外部 URL 多為 Google、Facebook 等網(wǎng)站的路由地址，使用 MDAP 平臺(tái)的用戶在開發(fā)自己應(yīng)用的時(shí)候，并不完全了解外部 URL 的模型規(guī)則，因此無法在 MDAP 平臺(tái)進(jìn)行相關(guān)的配置。

綜上所述，基于用戶自主配置 URL 模型規(guī)則的方案是 不可行的 。因此，MDAP 平臺(tái)需要基于應(yīng)用上報(bào)的 URL 自動(dòng)學(xué)習(xí)對(duì)應(yīng)的 URL 規(guī)則模型。

2.2 機(jī)器學(xué)習(xí)方案

2.2.1 URL 協(xié)議語法介紹

為了幫助讀者更好地理解后續(xù)算法設(shè)計(jì)以及 MDAP 思考解決問題的思路，本文需要對(duì) URL 的語法結(jié)構(gòu)進(jìn)行簡單介紹，如下圖所示：

根據(jù)上圖所示，我們可以將 URL 分解為一些通用的 URL 組件： ??schema?? 、 ??authority?? 、 ??path?? 、 ??query?? 及 ??fragment?? ，其通過 ??:?? 、 ??/?? 、 ????? 及 ??#?? 進(jìn)行分割。例如，URL ??http://example.com/books/search?name=go&isbn=1234?? 可以分解成如下幾部分組件：

schema: http
    authority: example.com
    path: {"path0": "books", "path1": "search"}
    query: {"name": "go", "isbn": "1234"}

在稍后的算法設(shè)計(jì)中，本文重點(diǎn)關(guān)注 ??path?? 和 ??query?? 兩部分?jǐn)?shù)據(jù)，將上述 URL 轉(zhuǎn)換成 ??Tuple(authority, Array[Tuple(K, V)])?? 的結(jié)構(gòu)，具體如下：

(
        "example.com",
        [
            ("path0", "books"),
            ("path1", "search"),
            ("name", "go"),
            ("isbn", "1234")
        ]
    )

2.2.2 自底向上結(jié)對(duì)策略思考

如上圖所示，其中存在 8 條不同的 URL，MDAP 采用 2.2.1 將每條 URL 轉(zhuǎn)換成 KV 結(jié)構(gòu)，比如： ??U1 -> {"K1": "a", "K2": "b", "K3": "y", "K4": "c", "K5": "*"}?? 。使用自底向上策略生成 URL 規(guī)則模型的方式，可以清楚地看到 K3 和 K5 應(yīng)該被歸一化為 ??*?? 。其歸一化過程如下：

• U5 + U6 -> P1 ： ??({"K1": "a", "K2": "b", "K3": "y", "K4": "c", "K5": "*"})??
• U7 + U8 -> P2 ： ??({"K1": "a", "K2": "b", "K3": "z", "K4": "c", "K5": "*"})??
• P1 + P2 -> P3 ： ??({"K1": "a", "K2": "b", "K3": "*", "K4": "c", "K5": "*"})??

上述步驟首先基于 U5、U6 和 U7、 U8 分別生成 P1 和 P2，然后基于 P1、P2 生成理想的 URL 模型規(guī)則 P3。但如果 U6 不存在的話，就會(huì)導(dǎo)致 P1 無法生成，進(jìn)一步 P3 也無法生成。此外，在上述示例中 U1 - U4 同樣不適合用來結(jié)對(duì)生成規(guī)則模型。

2.2.3 URL 模式樹

相對(duì)于自底向上策略，模式樹可以充分利用整個(gè)訓(xùn)練集的統(tǒng)計(jì)信息。這樣，學(xué)習(xí)過程變得更加可靠和穩(wěn)健，不再受到隨機(jī)噪聲的影響。對(duì)于 2.2.2 中的示例，即使某些 URL 不存在，仍然可以通過考慮所有其他 URL（包括 U1 ～ U4）。

其次，使用模式樹，可以通過直接基于樹節(jié)點(diǎn)總結(jié)規(guī)則來顯著提高學(xué)習(xí)效率。例如，不再需要 P1 和 P2，可以根據(jù)上述模式直接生成 P3。詳細(xì)的算法描述將在第 4 節(jié)中進(jìn)行闡述。

3. 框架總覽

本章節(jié)將闡述 MDAP 進(jìn)行 URL 模型規(guī)則學(xué)習(xí)和匹配的方法和架構(gòu)。

如上圖所示：

• 首先，MDAP 使用 URL 模型學(xué)習(xí)器，基于應(yīng)用上報(bào)的 URL 數(shù)據(jù)，自動(dòng)學(xué)習(xí)出 URL 規(guī)則模型，并將其進(jìn)行存儲(chǔ)；
• 然后，在 URL 模型匹配器中，MDAP 將 URL 規(guī)則模型作用于應(yīng)用上報(bào)的 URL 數(shù)據(jù)，生成元組 ??Tuple(url, url_pattern)?? 后，將其存入數(shù)據(jù)倉庫之中。

考慮到各應(yīng)用上報(bào)到 MDAP 的 URL 數(shù)據(jù)量巨大，MDAP 平臺(tái)使用 Flink 進(jìn)行 URL 模型規(guī)則學(xué)習(xí)，具體如下：

1. 從數(shù)據(jù)源中讀取 URL 數(shù)據(jù)；
2. 按照 2.2.1 將各 URL 轉(zhuǎn)化成 ??Tuple(authority, Array[Tuple(K, V)])?? 的結(jié)構(gòu)；
3. authority + salt authority salt salt length(Array[Tuple(K, V)])
4. 對(duì)同一分組下的 URL，使用模式樹算法生成 URL 規(guī)則模型；
5. 再按照 ??authority?? 將步驟 4 生成的結(jié)果分組；
6. 合并相同 ??authority?? 下的模型；
7. 保存 URL 規(guī)則模型。

關(guān)于 URL 模型匹配器，MDAP 使用了 ??Trie?? 的衍生變種結(jié)構(gòu)，來提升 URL 模型匹配的效率，在本文中不再贅述，感興趣的讀者可以去了解學(xué)習(xí) Trie 這種數(shù)據(jù)結(jié)構(gòu)。

4. 算法描述

本章節(jié)將闡述如何基于模式樹生成 URL 規(guī)則模型，重點(diǎn)闡述基于熵進(jìn)行節(jié)點(diǎn)分裂及基于高斯分布、馬爾可夫鏈進(jìn)行顯著值、離散值區(qū)分。

如上圖所示，生成 URL 規(guī)則模型的算法包括以下 6 步：

1. 初始化模式樹根節(jié)點(diǎn)，其包含全部 URL；
2. 找出 值 元素 最適合分裂 的 URL 鍵（ ??path_index?? 或 ??query_key?? ）；
3. 區(qū)分出第 2 步找出的 URL 鍵對(duì)應(yīng)的 顯著值 （Salient Value）和 離散值 （Trivial Value）；
4. 將顯著值保留，并將離散值歸一化為 ??*?? ，并基于顯著值和 ??*?? 分裂模式樹；
5. 重復(fù) 2-4 步，直至所有的 URL 鍵都已處理；
6. 遍歷模式樹的葉子節(jié)點(diǎn)，收集各 URL 節(jié)點(diǎn)的模型規(guī)則。

在本算法中，最關(guān)鍵的兩個(gè)步驟為第 2 步和第 3 步。

4.1 找出值元素最適合分裂的 URL 鍵

信息 熵 的概念用來解決如何找出最適合分裂的 URL 鍵。根據(jù)值越隨機(jī)的 URL 鍵，其熵越大。盡可能聚合鍵值變化少的部分，把變化多的部分后置計(jì)算或進(jìn)行通配處理，因此，需要找到可以最小化熵的 URL 鍵。計(jì)算 URL 鍵對(duì)應(yīng)的熵的公式如下：

其中，V 為該 URL 鍵對(duì)應(yīng)的值元素的個(gè)數(shù)，N 為全部元素出現(xiàn)的總次數(shù)，vi 為第 i 個(gè)元素出現(xiàn)的頻次。

根據(jù)上述公式，查找出熵最小的 URL 鍵，并結(jié)合 4.2 區(qū)分出顯著值和離散值，即可進(jìn)行模型樹節(jié)點(diǎn)分裂。

4.2 區(qū)分顯著值和離散值

4.2.1 基于高斯分布區(qū)分顯著值和離散值

根據(jù)對(duì) MDAP 收集的 URL 歷史數(shù)據(jù)的分析結(jié)果，假設(shè) URL 中每個(gè)鍵對(duì)應(yīng)的值列表服從高斯分布：

因此，將熵最小的鍵的值按照其頻次進(jìn)行倒序排序，并對(duì)計(jì)算相鄰的兩個(gè)值之間的頻次下降速度，以下降速度最大的兩個(gè)節(jié)點(diǎn)為界，即可區(qū)分出顯著值和離散值，其中分界點(diǎn)之左為顯著值，之右為離散值，比如：

在上圖中，頻次速度下降最大兩個(gè)節(jié)點(diǎn)為 ??videos?? 和 ??0?? ，因此，顯著值包括：

["index", "users", "books", "videos"]

離散值包括：

["0", "12323", "a3df56", "bher43"]

4.2.2 基于馬爾可夫鏈和密度函數(shù)進(jìn)行剪枝

雖然按照 4.2.1 可以區(qū)分顯著值和離散值，但其效果并非總是有效，比如：

在上圖中，如 URL 鍵對(duì)應(yīng)的值服從藍(lán)色線條的高斯分布，則通過 4.2.1 可區(qū)分出顯著值和離散值；但如果 URL 鍵對(duì)應(yīng)的值服從橙色線條甚至是比橙色線條更扁平的高斯分布，則極容易將離散值誤判為顯著值，因此需要輔助算法進(jìn)行剪枝操作。

根據(jù) MDAP 平臺(tái)對(duì) URL 數(shù)據(jù)的分析，發(fā)現(xiàn)離散的 URL 符合以下幾個(gè)特征：

• 數(shù)字，比如： ??/users/123?? 中的 ??123?? ；
• 哈希值，比如： ??/files/12af8712?? 中的 ??12af8712?? ;
• base64，比如： ??/something/aGVsbG8K?? 中的 ??aGVsbG8K?? 等其他非人類語言。

滿足以上特征的（除數(shù)字外）字符串統(tǒng)稱為亂語（Gibberish）。為了對(duì)亂語和數(shù)字類型的 URL 鍵值進(jìn)行剪枝，MDAP 引入馬爾可夫鏈和密度函數(shù)進(jìn)行亂語、數(shù)字識(shí)別，但由于縮略詞（Abbreviate）不屬于人類標(biāo)準(zhǔn)的語言，有極大概率被誤判成亂語，因此需要配置縮略詞表進(jìn)行先驗(yàn)判斷。具體算法步驟如下：

1. 判斷給定字符串是否在縮略詞表，如果是，保留其為顯著值并結(jié)束，否則繼續(xù)后續(xù)步驟；
2. 判斷給定字符串是否為亂語，如果是，將其歸為離散值并結(jié)束，否則繼續(xù)后續(xù)步驟；
3. 判斷給定字符串是否含有大量數(shù)字，如果是，將其歸為離散值，否則保留其為顯著值。

基于馬爾可夫鏈進(jìn)行亂語判別

馬爾可夫鏈在 NLP（自然語言處理）中廣泛使用，MDAP 平臺(tái)使用馬爾可夫鏈的方式比較簡單，通過 ??2-gram?? 的方式進(jìn)行字符串分詞，從而計(jì)算連續(xù)字符串出現(xiàn)的概率，比如：

使用馬爾可夫鏈，將大文本作為訓(xùn)練集，生成相應(yīng)的概率矩陣：

然后，將該矩陣作用于好文本和壞文本，計(jì)算出判斷字符串是否為亂語的閾值：

最后，通過下面的公式判斷給定的字符串是否為亂語：

基于密度函數(shù)進(jìn)行數(shù)字含量判別

考慮到主要版本號(hào)之類的字符串，比如 ??v1?? ，需要保留為顯著值，而像用戶 ID 之類的字符串，比如 ??1234?? ，需要被歸類成離散值，因此需要采用如下的公式，進(jìn)行字符串?dāng)?shù)組含量判斷。

5. 算法優(yōu)化測試與效果展示

本章節(jié)將展示使用模式樹生成 URL 規(guī)則模型的去重效果、URL 匹配度，并展示在 MDAP 平臺(tái)中的實(shí)際效果。

5.1 算法優(yōu)化測試

5.1.1 壓縮率測試

首先，MDAP 收集一部分來自生產(chǎn)環(huán)境的數(shù)據(jù)作為訓(xùn)練集來生成 URL 規(guī)則模型，其中各域名包含 ??100,000 - 2,000,000?? 原始 URL 數(shù)據(jù)，具體如下圖所示：

然后，將原始 URL 進(jìn)行 ??distinct?? 去重后得到 ??10 - 16,000?? 條 URL，具體如下圖所示：

最后，將原始 URL 經(jīng)過第 4 節(jié)的算法處理后，生成的 URL 規(guī)則模型條數(shù)為 ??1 - 85?? 條，具體如下圖所示：

通過對(duì)比去重 URL 和 URL 規(guī)則模型的統(tǒng)計(jì)效果圖，可以明顯發(fā)現(xiàn)， 通過模式樹生成的 URL 模型規(guī)則的數(shù)量遠(yuǎn)小于簡單 ??distinct?? 去重的結(jié)果 。

5.1.2 匹配度測試

將 5.1.1 生成的 URL 規(guī)則模型在兩個(gè)不同的測試集之間進(jìn)行驗(yàn)證，其中測試集 1（Test-1）為與訓(xùn)練集同日但不同時(shí)間段的數(shù)據(jù)，測試集 2（Test-2）為距離測試集 1 一周之后的數(shù)據(jù)。如上圖所示，測試集 1 的數(shù)據(jù)匹配規(guī)則模型的命中率很高（大于等于 99.99%），測試集 2 的命中率相對(duì)較差（80.89% - 100%）。

5.1.3 測試結(jié)論

通過 5.1.1 和 5.1.2 的測試結(jié)果，可以得出以下結(jié)論：

• 基于模式樹生成的 URL 規(guī)則模型進(jìn)行統(tǒng)計(jì)分析，可以極大地統(tǒng)計(jì)分析結(jié)果的收斂度；
• URL 與模型規(guī)則的匹配度隨訓(xùn)練時(shí)間與匹配時(shí)間的范圍變化而變化，相差時(shí)間越近，匹配度越好。

5.2 效果展示

MDAP 平臺(tái)目前使用 ??T + 1?? 的方式進(jìn)行 URL 規(guī)則模型匹配，基于平臺(tái)數(shù)據(jù)監(jiān)測統(tǒng)計(jì)結(jié)果，模型規(guī)則的平均匹配失敗率約為 ??0.3%?? 。使用模型下規(guī)則基于 URL 統(tǒng)計(jì)分析的頁面展示效果如下，其中第一張圖為基于 ??distinct?? 去重后的 URL 進(jìn)行統(tǒng)計(jì)分析（約 ??8110?? 條），第二張圖為基于 URL 規(guī)則模型進(jìn)行統(tǒng)計(jì)分析（約 ??60?? 條）。

6. 總結(jié)與展望

MDAP 平臺(tái)基于模型樹構(gòu)建實(shí)現(xiàn)了 URL 歸一化處理，并基于歸一化的結(jié)果提高了基于 URL 進(jìn)行統(tǒng)計(jì)分析的能力和準(zhǔn)確性。

但目前仍然存在一定缺陷，主要包括兩方面：

• 規(guī)則學(xué)習(xí)周期相對(duì)較長，對(duì)于準(zhǔn)實(shí)時(shí)數(shù)據(jù)處理能力較差；
• 模型迭代功能尚未完善，存在一定缺陷。

因此，后續(xù) MDAP 平臺(tái)將在此兩方面進(jìn)行進(jìn)一步優(yōu)化，從而提高 MDAP 在基于 URL 進(jìn)行統(tǒng)計(jì)分析時(shí)的數(shù)據(jù)質(zhì)量。

本文作者

Daniel，MDAP 聯(lián)合項(xiàng)目團(tuán)隊(duì)后端工程師，來自 Shopee Engineering Infrastructure 團(tuán)隊(duì)。