乐趣区

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

jiezi

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

摘要

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

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

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

1. 引言

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 节中，进行总结并对将来进行瞻望。

2. 问题思考

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

2.1 用户配置计划

配置 / 上传 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 规定模型。

2.2 机器学习计划

2.2.1 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")
        ]
    )

2.2.2 自底向上结对策略思考

如上图所示，其中存在 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.3 URL 模式树

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

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

3. 框架总览

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

如上图所示：

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

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

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

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

4. 算法形容

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

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

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

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

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

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

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

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

4.2 辨别显著值和离散值

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

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

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

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

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

离散值包含：

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

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

尽管依照 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）不属于人类规范的语言，有极大概率被误判成乱语，因而须要配置缩略词表进行先验判断。具体算法步骤如下：

  1. 判断给定字符串是否在缩略词表，如果是，保留其为显著值并完结，否则持续后续步骤；
  2. 判断给定字符串是否为乱语，如果是，将其归为离散值并完结，否则持续后续步骤；
  3. 判断给定字符串是否含有大量数字，如果是，将其归为离散值，否则保留其为显著值。
基于马尔可夫链进行乱语判断

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

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

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

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

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

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

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

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

5.1 算法优化测试

5.1.1 压缩率测试

首先，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.2 匹配度测试

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

5.1.3 测试论断

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

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

5.2 成果展现

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

6. 总结与瞻望

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 团队。

退出移动版