在传统的客户端监控分析场景中，采用的是基于特定URL进行统计分析的方法，一个应用可能会访问几千个，而只有几个URLs，结果并不令人满意，应用程序访问哪些URLs可能存在问题并不明显。MDAP平台在进行客户端监控分析时，利用概率统计和机器学习方案，将多个相似的URL归一化为同一个规则模型，然后基于规则模型进行相关统计分析，从而提高基于URL的可用性和准确性。客户端监控分析，提高MDAP用户对自身应用质量的监控分析。1.简介URL是客户端监控分析的重要元素。传统的基于URL的统计分析方法直接使用原始URL值进行统计分析，例如：SELECT`url`,count(1)as`cnt`FROM`web_analysis_tab`WHERE`app_name`='app_1'GROUPBY`url`;使用上述查询语句统计分析的结果非常糟糕，主要表现在以下几个方面：应用开发者无法通过分析结果快速准确定位，发现潜在的应用问题和风险；统计结果过于分散，用户可能失去查看统计分析结果的兴趣；平台处理和过滤离散数据统计分析，可能有较大的系统开销，包括：查询效率、网络传输、页面显示等。例如，假设app_1访问了具有1,000,000个不同值的URL，但其URL规则模型具有较少超过100个。第一版MDAP（Multi-DimensionAnalysisPlatform，多维分析平台）的用户和开发者也被这样的问题所困扰。为了更好的服务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模型规则，但后来发现这种方案存在几个问题：golang/gin:GEThttp://example.com/users/:user_name;golang/grpc-gateway:GEThttp://example.com/{name=users/*}，符合GoogleAPI设计规范；java/spring:GEThttp://example.com/users/{user_name}。繁琐的用户配置。MDAP平台的目的是协助平台用户监控、统计和分析自身的应用质量。要求平台用户配置/上传URL模型规则进行URL模型匹配，这无疑增加了平台用户的负担。同时，平台用户极有可能忘记更改新的URL模型规则，这将严重影响URL模型匹配效果，进而退回到传统的基于URL的统计分析模型。区分URL模型规则。不同语言和框架的URL路由规则差异很大，巨大的风格差异不利于平台统一管理URL规则模型。比如下面三种获取特定用户详细信息的URL模型规则：海量数据的外部URL。根据MDAP平台统计分析，单个应用对非应用服务访问的外部URL地址平均占比约10%-30%。这些外部URL大多是Google、Facebook等网站的路由地址。使用MDAP平台的用户在开发自己的应用时，并没有完全理解外部URL的模型规则，因此无法在MDAP平台上进行相关配置。综上所述，基于用户配置的URL模型规则的方案是不可行的。因此，MDAP平台需要根据应用上报的URL自动学习相应的URL规则模型。2.2机器学习方案2.2.1URL协议语法介绍为了帮助读者更好地理解后续的算法设计和MDAP思维及解题思路，本文需要简单介绍一下URL语法结构，如下图所示：根据上图，我们可以将URL分解为一些常见的URL组件：schema,authority,path,query和fragment，其中通过:,/,?和#拆分。例如，URLhttp://example.com/books/search?name=go&isbn=1234可以分解为以下部分：schema:httpauthority:example.compath:{"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":"*"})U??7+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生成理想的URL模型规则P3和P2。但是如果U6不存在，则无法生成P1，进而无法生成P3。此外，上述示例中的U1-U4也不适合对生成规则模型。2.2.3URL模式树与自下而上的策略相比，模式树可以充分利用整个训练集的统计信息。这样，学习过程变得更加可靠和鲁棒，不再受到随机噪声的影响。对于2.2.2中的例子，即使某些URL不存在，其他所有URL（包括U1～U4）仍然可以考虑。其次，利用模式树，直接基于树节点总结规则可以显着提高学习效率。比如P1和P2已经不需要了，直接按照上面的schema生成P3即可。详细的算法描述将在第4节中进行阐述。3.框架概述本章将描述MDAP用于URL模型规则学习和匹配的方法和体系结构。如上图所示：首先，MDAP使用URL模型学习器，根据应用上报的URL数据自动学习URL规则模型，并存储；然后，在URL模型匹配器中，MDAP将URL规则模型应用于Apply上报的URL数据，生成元组Tuple(url,url_pattern)，存入数据仓库。考虑到每个应用向MDAP上报的URL数据量巨大，MDAP平台使用Flink学习URL模型规则，具体如下：从数据源中读取URL数据；将每个URL转换成一个Tuple(authority,Array[Tuple(K,V)]的结构)；authority+saltauthoritysaltsaltlength(Array[Tuple(K,V)])使用模式树算法为同一组下的URL生成URL规则模型；然后根据权限对第4步生成的结果进行分组；在同一权限下合并模型；保存URL规则模型。关于URL模型匹配器，MDAP利用Trie派生的变体结构来提高URL模型匹配的效率，本文不再赘述。有兴趣的读者可以了解一下Trie的数据结构。4.算法描述本章将讲解如何基于模式树生成URL规则模型，重点介绍基于熵的节点分裂以及基于高斯分布和马尔可夫链的区分显着值和离散值。如上图所示，生成URL规则模型的算法包括以下6个步骤：初始化模式树的根节点，其中包含所有的URL；找出value元素最适合拆分的URLkey（path_indexorquery_key）；区分第2步找到的URLkey对应的显着值（SalientValue）和离散值（TrivialValue）；保留显着值，并将离散值归一化为*，并根据显着值和*拆分模式树；重复步骤2-4，直到处理完所有URL键；遍历模式树的叶子节点，收集每个URL节点的模型规则。在该算法中，最关键的两个步骤是第2步和第3步。4.1找出最适合拆分值元素的URLkey利用信息熵的概念来解决如何找到最适合拆分的URLkey。具有更多随机值的URL键具有更高的熵。尽可能聚合键值变化少的部分，对变化多的部分进行后计算或通配处理。因此，需要找到能使熵最小的URLkey。URLkey对应的熵的计算公式如下：其中V为URLkey对应的值元素个数，N为所有元素出现的总次数，vi为第i个元素出现的频率。根据上式，找到熵值最小的URLkey，结合4.2区分显着值和离散值，即可对模型树节点进行分裂。4.2区分显着值和离散值4.2.1基于高斯分布区分显着值和离散值根据MDAP收集的历史URL数据分析结果，假设对应的值列表URL中的每个key服从高斯分布：因此，熵最小化keys的值按照频率倒序排列，计算两个相邻值之间的频率下降率，将两个节点丢弃率最大的点作为分界线来区分显着值和离散值，其中分界线点的左边是显着值，右边是离散值。例如：在上图中，频率和速度下降最大的两个节点是videos和0，因此，显着值包括：["index","users","books","videos"]离散值包括：["0","12323","a3df56","bher43"]4.2.2基于马尔可夫链和密度函数的剪枝虽然根据4.2.1可以区分显着值和离散值，但其效果并不总是有效。例如：上图中，如果URLkey对应的值服从蓝线的高斯分布，那么4.2.1可以区分显着值和离散值；但如果URLkey对应的值服从橙线甚至比橙线更平坦的高斯分布，则很容易将离散值误判为显着值，因此需要辅助算法进行剪枝。根据MDAP平台对URL数据的分析，发现离散的URL满足以下特征：数字，如：/users/123中的123；hash值，如：/files/12af8712in12af8712；base64，例如：/something/aGVsbG8K中的aGVsbG8K等非人类语言。满足上述特征的字符串（数字除外）统称为Gibberish。为了修剪乱码和数字类型的URL键值，MDAP引入了马尔可夫链和密度函数来进行乱码和数字识别，但是由于缩写（Abbreviate）不属于人类标准语言，所以有很大概率被误判为乱码，所以需要配置一个缩写列表，以便事先判断。具体算法步骤如下：判断给定的字符串是否在缩写列表中，如果是，则保留为有效值并结束，否则继续后续步骤；判断给定的字符串是否为乱码，如果是，则将其归类为离散值并结束，否则继续下一步；判断给定的字符串是否包含大量数字，如果是，则将其归类为离散值，否则保留为显着值。基于马尔可夫链的乱码判别马尔可夫链广泛应用于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进行去重，得到10-16000个URL，如下图：最后，原始URL经过第4节的算法处理后，生成的URL规则模型条目数为1-85，如下图所示：通过对比URL去重和URL规则模型的统计效果图，可以明显的发现，通过模式树生成的URL模型规则数量远小于patterntreesimpledistinct的去重结果。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规则模型进行统计分析，可以大大提高统计分析结果的收敛性；匹配度随训练时间和匹配时间的范围而变化，时间差越近，匹配度越好。5.2效果展示MDAP平台目前采用T+1方式进行URL规则模型匹配。根据平台数据监测统计，模型规则的平均匹配失败率约为0.3%。使用模型下的规则基于URL统计分析的页面显示效果如下，第一张图是基于去重后不同URL的统计分析（约8110条），第二张图是基于URL规则模型的统计分析（约60项）。6.总结与展望MDAP平台基于模型树构建实现了URL规范化处理，提高了基于规范化结果的基于URL的统计分析能力和准确性。但是仍然存在一些不足，主要有两个方面：规则学习周期比较长，处理准实时数据的能力较差；模型迭代功能尚未完善，存在一定的缺陷。因此，后续MDAP平台将在这两方面进一步优化，以提高MDAP在基于URL统计分析方面的数据质量。本文作者为MDAP联合项目组后端工程师Daniel，来自ShopeeEngineeringInfrastructure团队。
