機(jī)器學(xué)習(xí)在基于 URL 的客戶端監(jiān)控分析中的優(yōu)化和實(shí)踐

作者：MDAP Team 2022-04-15 10:52:50

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

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

MDAP 平臺(tái)在進(jìn)行客戶端監(jiān)控分析時(shí)，通過(guò)使用概率統(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`;

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

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

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

初版的 MDAP （Multi-Dimension Analysis Platform，多維度分析平臺(tái)）用戶和開(kāi)發(fā)者同樣面對(duì)此類問(wèn)題的困擾。為了更好地服務(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ì)分析過(guò)于散列的情況，使得統(tǒng)計(jì)分析結(jié)果更加收斂，進(jìn)而更方便用戶使用 MDAP 對(duì)自己的應(yīng)用質(zhì)量進(jìn)行分析查看。

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

2. 問(wèn)題思考

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

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)問(wè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ī)則，無(wú)疑增加了平臺(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ī)則。不同語(yǔ)言、框架的 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)用訪問(wèn)非本應(yīng)用服務(wù)的外部 URL 地址數(shù)量平均占比約為 10%-30%。這些外部 URL 多為 Google、Facebook 等網(wǎng)站的路由地址，使用 MDAP 平臺(tái)的用戶在開(kāi)發(fā)自己應(yīng)用的時(shí)候，并不完全了解外部 URL 的模型規(guī)則，因此無(wú)法在 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é)議語(yǔ)法介紹

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

根據(jù)上圖所示，我們可以將 URL 分解為一些通用的 URL 組件： ??schema?? 、 ??authority?? 、 ??path?? 、 ??query?? 及 ??fragment?? ，其通過(guò) ??:?? 、 ??/?? 、 ????? 及 ??#?? 進(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)該被歸一化為 ??*?? 。其歸一化過(guò)程如下：

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 無(wú)法生成，進(jìn)一步 P3 也無(wú)法生成。此外，在上述示例中 U1 - U4 同樣不適合用來(lái)結(jié)對(duì)生成規(guī)則模型。

2.2.3 URL 模式樹(shù)

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

其次，使用模式樹(shù)，可以通過(guò)直接基于樹(shù)節(jié)點(diǎn)總結(jié)規(guī)則來(lái)顯著提高學(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ù)倉(cāng)庫(kù)之中。

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

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

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

4. 算法描述

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

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

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

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

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

信息熵的概念用來(lái)解決如何找出最適合分裂的 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)行模型樹(shù)節(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)色線條的高斯分布，則通過(guò) 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?? 等其他非人類語(yǔ)言。

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

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

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

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

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

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

最后，通過(guò)下面的公式判斷給定的字符串是否為亂語(yǔ)：

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

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

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

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

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

5.1.1 壓縮率測(cè)試

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

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

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

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

5.1.2 匹配度測(cè)試

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

5.1.3 測(cè)試結(jié)論

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

基于模式樹(shù)生成的 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)測(cè)統(tǒng)計(jì)結(jié)果，模型規(guī)則的平均匹配失敗率約為 ??0.3%?? 。使用模型下規(guī)則基于 URL 統(tǒng)計(jì)分析的頁(yè)面展示效果如下，其中第一張圖為基于 ??distinct?? 去重后的 URL 進(jìn)行統(tǒng)計(jì)分析（約 ??8110?? 條），第二張圖為基于 URL 規(guī)則模型進(jìn)行統(tǒng)計(jì)分析（約 ??60?? 條）。