本文首发于微信大众号“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
• github.com/rrenaud/Gib…
• en.wikipedia.org/wiki/URL

本文作者

Daniel，MDAP 联合项目团队后端工程师，来自 Shopee Engineering Infrastructure 团队。

称谢

感谢 Content Services、Digital Purchase & Local Services、Financial Products、Marketplace、Merchant Services、ShopeeFood 等团队的支撑和奉献。