关于客户端:机器学习在基于-URL-的客户端监控分析中的优化和实践

本文首发于微信公众号“Shopee 技术团队”

传统的客户端监控剖析场景中，采纳依照具体的 URL 进行统计分析的办法，在面对一个利用可能会拜访成千上万条 URL 时，后果就差强人意，不能显著地标识出利用拜访的哪些 URL 存在潜在问题。

MDAP 平台在进行客户端监控剖析时，通过应用概率统计和机器学习的计划，将若干条类似的 URL 归一化成同一条规定模型，而后基于该规定模型进行相干统计分析，从而进步了基于 URL 的客户端监控剖析的可用性及准确性，进而进步了 MDAP 用户对本人利用品质的监控剖析。

这是 MDAP 系列的第二篇文章，前文回顾：《MDAP：可观测性数据分析平台设计与实际》

URL 作为客户端监控剖析的一个重要元素，传统的基于 URL 的统计分析形式间接应用原始 URL 值进行统计分析，比方：

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

应用上述查问语句进行统计分析的后果是十分蹩脚的，次要体现在以下几个方面：

利用开发者无奈 疾速地、精确地 通过剖析后果定位、发现潜在的利用问题、危险；
统计后果过于扩散，用户可能会失去查看统计分析后果的趣味；
平台解决过滤离散数据的统计分析，可能存在较大的 零碎开销，包含：查问效率、网络传输、页面展现等。

比方，假如 app_1 拜访过 1,000,000 个不同值的 URL，而其 URL 规定模型 有余 100 个。

初版的 MDAP（Multi-Dimension Analysis Platform，多维度剖析平台）用户和开发者同样面对此类问题的困扰。为了更好地服务 MDAP 用户，帮助 MDAP 用户疾速、无效地剖析本人的利用品质。MDAP 平台基于 概率统计 实践和 机器学习 技术，依据利用上报的 URL，主动学习 出相应的 URL 模型，利用衍生字段 url_pattern 而非原始 url 进行统计分析，从而大幅度缩小了基于 URL 统计分析过于散列的状况，使得统计分析后果更加收敛，进而更不便用户应用 MDAP 对本人的利用品质进行剖析查看。

本文残余局部的构造安顿如下：在第 2 节中，联合具体例子解说 MDAP 对解决 URL 归一化问题的思考。第 3 节，介绍 MDAP 是如何对 URL 进行归一化解决的总体框架，并在第 4 节中进行具体的算法形容。优化成果的测试与评估在第 5 节中进行论述。最初，在第 6 节中，进行总结并对将来进行瞻望。

本章节将解释这项工作的具体动机和思考。针对三种不同计划进行剖析，论述配置 / 上传 URL 模型规定的不可行性；通过一个具体的例子，展现自底向上的成对策略如何工作以及何时失败；并解释模式树为何无效。

为了将 URL 转换成对应的 URL 模型规定，最先思考的计划是在平台中，容许用户配置 / 上传利用相干的 URL 模型规定，但随即咱们发现该计划存在几点问题：

繁琐的用户配置。MDAP 平台的主旨是为了帮助平台用户监控、统计、剖析本人的利用品质。为了进行 URL 模型匹配而须要平台用户配置 / 上传 URL 模型规定，无疑减少了平台用户的累赘。同时，平台用户极有可能忘记进行新的 URL 模型规定变更，从而重大影响 URL 模型匹配成果，进而回退到传统的基于 URL 统计分析模型。
差异化的 URL 模型规定。不同语言、框架的 URL 路由规定差别大，微小的格调差别不利于平台进行 URL 规定模型的对立治理，比方上面三种获取某一具体用户详情信息的 URL 模型规定：
- golang/gin: GET http://example.com/users/:user_name；
- golang/grpc-gateway: GET http://example.com/{name=users/*}，恪守 Google API 设计规范；
- java/spring: GET http://example.com/users/{user_name}。
数据微小的内部 URL。依据 MDAP 平台统计分析，单利用拜访非本应用服务的内部 URL 地址数量均匀占比约为 10%-30%。这些内部 URL 多为 Google、Facebook 等网站的路由地址，应用 MDAP 平台的用户在开发本人利用的时候，并不齐全理解内部 URL 的模型规定，因而无奈在 MDAP 平台进行相干的配置。

综上所述，基于用户自主配置 URL 模型规定的计划是 不可行的。因而，MDAP 平台须要基于利用上报的 URL 主动学习对应的 URL 规定模型。

为了帮忙读者更好地了解后续算法设计以及 MDAP 思考解决问题的思路，本文须要对 URL 的语法结构进行简略介绍，如下图所示：

依据上图所示，咱们能够将 URL 合成为一些通用的 URL 组件：schema、authority、path、query 及 fragment，其通过 :、/、? 及 # 进行宰割。例如，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"}

在稍后的算法设计中，本文重点关注 path 和 query 两局部数据，将上述 URL 转换成 Tuple(authority, Array[Tuple(K, V)])的构造，具体如下：

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

如上图所示，其中存在 8 条不同的 URL，MDAP 采纳 2.2.1 将每条 URL 转换成 KV 构造，比方：U1 -> {"K1": "a", "K2": "b", "K3": "y", "K4": "c", "K5": "*"}。应用自底向上策略生成 URL 规定模型的形式，能够分明地看到 K3 和 K5 应该被归一化为 *。其归一化过程如下：

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 模型规定 P3。但如果 U6 不存在的话，就会导致 P1 无奈生成，进一步 P3 也无奈生成。此外，在上述示例中 U1 – U4 同样不适宜用来结对生成规定模型。

绝对于自底向上策略，模式树能够充分利用整个训练集的统计信息。这样，学习过程变得更加牢靠和持重，不再受到随机噪声的影响。对于 2.2.2 中的示例，即便某些 URL 不存在，依然能够通过思考所有其余 URL（包含 U1 ∼ U4）。

其次，应用模式树，能够通过间接基于树节点总结规定来显着进步学习效率。例如，不再须要 P1 和 P2，能够根据上述模式间接生成 P3。具体的算法形容将在第 4 节中进行论述。

本章节将论述 MDAP 进行 URL 模型规则学习和匹配的办法和架构。

如上图所示：

首先，MDAP 应用 URL 模型学习器，基于利用上报的 URL 数据，主动学习出 URL 规定模型，并将其进行存储；
而后，在 URL 模型匹配器中，MDAP 将 URL 规定模型作用于利用上报的 URL 数据，生成元组 Tuple(url, url_pattern) 后，将其存入数据仓库之中。

思考到各利用上报到 MDAP 的 URL 数据量微小，MDAP 平台应用 Flink 进行 URL 模型规则学习，具体如下：

从数据源中读取 URL 数据；
依照 2.2.1 将各 URL 转化成 Tuple(authority, Array[Tuple(K, V)])的构造；
依照 authority + salt 将步骤 2 生成的后果分组，其中 authority 定义参考 2.2.1，salt 用来解决大数据计算时的数据歪斜问题，可依据理论状况抉择不同的数据作为 salt，比方：length(Array[Tuple(K, V)])；
对同一分组下的 URL，应用模式树算法生成 URL 规定模型；
再依照 authority 将步骤 4 生成的后果分组；
合并雷同 authority 下的模型；
保留 URL 规定模型。

对于 URL 模型匹配器，MDAP 应用了 Trie 的衍生变种构造，来晋升 URL 模型匹配的效率，在本文中不再赘述，感兴趣的读者能够去理解学习 Trie 这种数据结构。

本章节将论述如何基于模式树生成 URL 规定模型，重点论述基于熵进行节点决裂及基于高斯分布、马尔可夫链进行显著值、离散值辨别。

如上图所示，生成 URL 规定模型的算法包含以下 6 步：

初始化模式树根节点，其蕴含全副 URL；
找出值元素 最适宜决裂 的 URL 键（path_index 或 query_key）；
辨别出第 2 步找出的 URL 键对应的 显著值 （Salient Value）和 离散值（Trivial Value）；
将显著值保留，并将离散值归一化为 *，并基于显著值和 * 决裂模式树；
反复 2-4 步，直至所有的 URL 键都已解决；
遍历模式树的叶子节点，收集各 URL 节点的模型规定。

在本算法中，最要害的两个步骤为第 2 步和第 3 步。

信息熵的概念用来解决如何找出最适宜决裂的 URL 键。依据值越随机的 URL 键，其熵越大。尽可能聚合键值变动少的局部，把变动多的局部后置计算或进行通配解决，因而，须要找到能够最小化熵的 URL 键。计算 URL 键对应的熵的公式如下：

其中，V 为该 URL 键对应的值元素的个数，N 为全副元素呈现的总次数，vi 为第 i 个元素呈现的频次。

根据上述公式，查找出熵最小的 URL 键，并联合 4.2 辨别出显著值和离散值，即可进行模型树节点决裂。

依据对 MDAP 收集的 URL 历史数据的剖析后果，假如 URL 中每个键对应的值列表遵从高斯分布：

因而，将熵最小的键的值依照其频次进行倒序排序，并对计算相邻的两个值之间的频次降落速度，以降落速度最大的两个节点为界，即可辨别出显著值和离散值，其中分界点之左为显著值，之右为离散值，比方：

在上图中，频次速度降落最大两个节点为 videos 和 0，因而，显著值包含：

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

离散值包含：

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

尽管依照 4.2.1 能够辨别显著值和离散值，但其成果并非总是无效，比方：

在上图中，如 URL 键对应的值遵从蓝色线条的高斯分布，则通过 4.2.1 可辨别出显著值和离散值；但如果 URL 键对应的值遵从橙色线条甚至是比橙色线条更扁平的高斯分布，则极容易将离散值误判为显著值，因而须要辅助算法进行剪枝操作。

依据 MDAP 平台对 URL 数据的剖析，发现离散的 URL 合乎以下几个特色：

数字，比方：/users/123 中的 123；
哈希值，比方：/files/12af8712 中的 12af8712;
base64，比方：/something/aGVsbG8K 中的 aGVsbG8K 等其余非人类语言。

满足以上特色的（除数字外）字符串统称为乱语（Gibberish）。为了对乱语和数字类型的 URL 键值进行剪枝，MDAP 引入马尔可夫链和密度函数进行乱语、数字辨认，但因为缩略词（Abbreviate）不属于人类规范的语言，有极大概率被误判成乱语，因而须要配置缩略词表进行先验判断。具体算法步骤如下：

判断给定字符串是否在缩略词表，如果是，保留其为显著值并完结，否则持续后续步骤；
判断给定字符串是否为乱语，如果是，将其归为离散值并完结，否则持续后续步骤；
判断给定字符串是否含有大量数字，如果是，将其归为离散值，否则保留其为显著值。

基于马尔可夫链进行乱语判断

马尔可夫链在 NLP（自然语言解决）中宽泛应用，MDAP 平台应用马尔可夫链的形式比较简单，通过 2-gram 的形式进行字符串分词，从而计算间断字符串呈现的概率，比方：

应用马尔可夫链，将大文本作为训练集，生成相应的概率矩阵：

而后，将该矩阵作用于好文本和坏文本，计算出判断字符串是否为乱语的阈值：

最初，通过上面的公式判断给定的字符串是否为乱语：

基于密度函数进行数字含量判断

思考到次要版本号之类的字符串，比方 v1，须要保留为显著值，而像用户 ID 之类的字符串，比方 1234，须要被归类成离散值，因而须要采纳如下的公式，进行字符串数组含量判断。

本章节将展现应用模式树生成 URL 规定模型的去重成果、URL 匹配度，并展现在 MDAP 平台中的实际效果。

首先，MDAP 收集一部分来自生产环境的数据作为训练集来生成 URL 规定模型，其中各域名蕴含 100,000 - 2,000,000 原始 URL 数据，具体如下图所示：

而后，将原始 URL 进行 distinct 去重后失去 10 - 16,000 条 URL，具体如下图所示：

最初，将原始 URL 通过第 4 节的算法解决后，生成的 URL 规定模型条数为 1 - 85 条，具体如下图所示：

通过比照去重 URL 和 URL 规定模型的统计效果图，能够显著发现，通过模式树生成的 URL 模型规定的数量远小于简略 distinct 去重的后果。

将 5.1.1 生成的 URL 规定模型在两个不同的测试集之间进行验证，其中测试集 1（Test-1）为与训练集同日但不同时间段的数据，测试集 2（Test-2）为间隔测试集 1 一周之后的数据。如上图所示，测试集 1 的数据匹配规定模型的命中率很高（大于等于 99.99%），测试集 2 的命中率绝对较差（80.89% – 100%）。

通过 5.1.1 和 5.1.2 的测试后果，能够得出以下论断：

基于模式树生成的 URL 规定模型进行统计分析，能够极大地统计分析后果的收敛度；
URL 与模型规定的匹配度随训练工夫与匹配工夫的范畴变动而变动，相差工夫越近，匹配度越好。

MDAP 平台目前应用 T + 1 的形式进行 URL 规定模型匹配，基于平台数据监测统计后果，模型规定的均匀匹配失败率约为 0.3%。
应用模型下规定基于 URL 统计分析的页面展现成果如下，其中第一张图为基于 distinct 去重后的 URL 进行统计分析（约 8110 条），第二张图为基于 URL 规定模型进行统计分析（约 60 条）。

MDAP 平台基于模型树构建实现了 URL 归一化解决，并基于归一化的后果进步了基于 URL 进行统计分析的能力和准确性。

但目前依然存在肯定缺点，次要包含两方面：

规则学习周期绝对较长，对于准实时数据处理能力较差；
模型迭代性能尚未欠缺，存在肯定缺点。

因而，后续 MDAP 平台将在此两方面进行进一步优化，从而进步 MDAP 在基于 URL 进行统计分析时的数据品质。

A pattern tree-based approach to learning URL normalization rules
https://github.com/rrenaud/Gibberish-Detector
https://en.wikipedia.org/wiki/URL

本文作者

Daniel，后端工程师，来自 Shopee Engineering Infrastructure 团队。

关于客户端:机器学习在基于-URL-的客户端监控分析中的优化和实践

摘要

1. 引言

2. 问题思考

2.1 用户配置计划

配置 / 上传 URL 模型规定

2.2 机器学习计划

2.2.1 URL 协定语法介绍

2.2.2 自底向上结对策略思考

2.2.3 URL 模式树

3. 框架总览

4. 算法形容

4.1 找出值元素最适宜决裂的 URL 键

4.2 辨别显著值和离散值

4.2.1 基于高斯分布辨别显著值和离散值

4.2.2 基于马尔可夫链和密度函数进行剪枝

基于马尔可夫链进行乱语判断

基于密度函数进行数字含量判断

5. 算法优化测试与成果展现

5.1 算法优化测试

5.1.1 压缩率测试

5.1.2 匹配度测试

5.1.3 测试论断

5.2 成果展现

6. 总结与瞻望

🔗 参考资料

Just My Socks（注册教程内含优惠码）

关于客户端:机器学习在基于-URL-的客户端监控分析中的优化和实践

摘要

1. 引言

2. 问题思考

2.1 用户配置计划

配置 / 上传 URL 模型规定

2.2 机器学习计划

2.2.1 URL 协定语法介绍

2.2.2 自底向上结对策略思考

2.2.3 URL 模式树

3. 框架总览

4. 算法形容

4.1 找出值元素最适宜决裂的 URL 键

4.2 辨别显著值和离散值

4.2.1 基于高斯分布辨别显著值和离散值

4.2.2 基于马尔可夫链和密度函数进行剪枝

基于马尔可夫链进行乱语判断

基于密度函数进行数字含量判断

5. 算法优化测试与成果展现

5.1 算法优化测试

5.1.1 压缩率测试

5.1.2 匹配度测试

5.1.3 测试论断

5.2 成果展现

6. 总结与瞻望

🔗 参考资料

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）