个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
25
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章一个正则表达式导致CPU 利用率居高不下由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
前几天线上一个项目监控信息突然报告异常，上到机器上后查看相关资源的使用情况，发现 CPU 利用率将近 100%。通过 Java 自带的线程 Dump 工具，我们导出了出问题的堆栈信息.
藏在正则表达式里的陷阱，一个正则表达式导致CPU 利用率居高不下 。
我们可以看到所有的堆栈都指向了一个名为 validateUrl 的方法，这样的报错信息在堆栈中一共超过 100 处。通过排查代码，我们知道这个方法的主要功能是校验 URL 是否合法.
很奇怪，一个正则表达式怎么会导致 CPU 利用率居高不下。为了弄清楚复现问题，我们将其中的关键代码摘抄出来，做了个简单的单元测试.
|
1
2
3
4
5
6
7
8
9
|
public static void main(String[] args) {
String badRegex =
"^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\/])+$"
;
String bugUrl =
"http://www.fapiao.com/dddp-web/pdf/download?request=6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf"
;
if
(bugUrl.matches(badRegex)) {
System.out.println(
"match!!"
);
}
else
{
System.out.println(
"no match!!"
);
}
}
|
当我们运行上面这个例子的时候，通过资源监视器可以看到有一个名为 java 的进程 CPU 利用率直接飙升到了 91.4% .
藏在正则表达式里的陷阱，一个正则表达式导致CPU 利用率居高不下 。
看到这里，我们基本可以推断，这个正则表达式就是导致 CPU 利用率居高不下的凶手！ 。
于是，我们将排错的重点放在了那个正则表达式上:
|
1
|
^([hH][tT]{2}[pP]:
//
|[hH][tT]{2}[pP][sS]:
//
)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\/])+$
|
这个正则表达式看起来没什么问题，可以分为三个部分:
第一部分匹配 http 和 https 协议，第二部分匹配 www. 字符，第三部分匹配许多字符。我看着这个表达式发呆了许久，也没发现没有什么大的问题.
其实这里导致 CPU 使用率高的关键原因就是： Java 正则表达式使用的引擎实现是 NFA 自动机，这种正则表达式引擎在进行字符匹配时会发生回溯（backtracking）。 而一旦发生回溯，那其消耗的时间就会变得很长，有可能是几分钟，也有可能是几个小时，时间长短取决于回溯的次数和复杂度.
看到这里，可能大家还不是很清楚什么是回溯，还有点懵。没关系，我们一点点从正则表达式的原理开始讲起 。
正则表达式引擎 。
正则表达式是一个很方便的匹配符号，但要实现这么复杂，功能如此强大的匹配语法，就必须要有一套算法来实现，而实现这套算法的东西就叫做正则表达式引擎。简单地说，实现正则表达式引擎的有两种方式： DFA 自动机 （Deterministic Final Automata 确定型有穷自动机）和 NFA 自动机 （Non deterministic Finite Automaton 不确定型有穷自动机）.
对于这两种自动机，他们有各自的区别，这里并不打算深入将它们的原理。简单地说，DFA 自动机的时间复杂度是线性的，更加稳定，但是功能有限。而 NFA 的时间复杂度比较不稳定，有时候很好，有时候不怎么好，好不好取决于你写的正则表达式。但是胜在 NFA 的功能更加强大，所以包括 Java 、.NET、Perl、Python、Ruby、PHP 等语言都使用了 NFA 去实现其正则表达式.
那 NFA 自动机到底是怎么进行匹配的呢？我们以下面的字符和表达式来举例说明.
|
1
|
text=
"Today is a nice day."
regex=
"day"
|
要记住一个很重要的点，即：NFA 是以正则表达式为基准去匹配的。也就是说，NFA 自动机会读取正则表达式的一个一个字符，然后拿去和目标字符串匹配，匹配成功就换正则表达式的下一个字符，否则继续和目标字符串的下一个字符比较。或许你们听不太懂，没事，接下来我们以上面的例子一步步解析.
上面这个匹配过程就是 NFA 自动机的匹配过程，但实际上的匹配过程会比这个复杂非常多，但其原理是不变的.
NFA自动机的回溯 。
了解了 NFA 是如何进行字符串匹配的，接下来我们就可以讲讲这篇文章的重点了：回溯。为了更好地解释回溯，我们同样以下面的例子来讲解.
|
1
|
text=
"abbc"
regex=
"ab{1,3}c"
|
上面的这个例子的目的比较简单，匹配以 a 开头，以 c 结尾，中间有 1-3 个 b 字符的字符串。NFA 对其解析的过程是这样子的:
首先，读取正则表达式第一个匹配符 a 和 字符串第一个字符 a 比较，匹配了。于是读取正则表达式第二个字符。 读取正则表达式第二个匹配符 b{1,3} 和字符串的第二个字符 b 比较，匹配了。但因为 b{1,3} 表示 1-3 个 b 字符串，以及 NFA 自动机的贪婪特性（也就是说要尽可能多地匹配），所以此时并不会再去读取下一个正则表达式的匹配符，而是依旧使用 b{1,3} 和字符串的第三个字符 b 比较，发现还是匹配。于是继续使用 b{1,3} 和字符串的第四个字符 c 比较，发现不匹配了。此时就会发生回溯。 发生回溯是怎么操作呢？发生回溯后，我们已经读取的字符串第四个字符 c 将被吐出去，指针回到第三个字符串的位置。之后，程序读取正则表达式的下一个操作符 c，读取当前指针的下一个字符 c 进行对比，发现匹配。于是读取下一个操作符，但这里已经结束了。 下面我们回过头来看看前面的那个校验 URL 的正则表达式:
|
1
|
^([hH][tT]{2}[pP]:
//
|[hH][tT]{2}[pP][sS]:
//
)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\/])+$
|
出现问题的 URL 是:
|
1
|
http:
//www
.fapiao.com
/dzfp-web/pdf/download
?request=6e7JGm38jfjghVrv4ILd-kEn64HcUX4qL4a4qJ4-CHLmqVnenXC692m74H5oxkjgdsYazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf
|
我们把这个正则表达式分为三个部分:
我们可以发现正则表达式校验协议 http:// 这部分是没有问题的，但是在校验 www.fapiao.com 的时候，其使用了 xxxx. 这种方式去校验。那么其实匹配过程是这样的:
这是这个正则表达式存在的第一个问题.
另外一个问题是在正则表达式的第三部分，我们发现出现问题的 URL 是有下划线（_）和百分号（%）的，但是对应第三部分的正则表达式里面却没有。这样就会导致前面匹配了一长串的字符之后，发现不匹配，最后回溯回去.
这是这个正则表达式存在的第二个问题.
解决方案 。
明白了回溯是导致问题的原因之后，其实就是减少这种回溯，你会发现如果我在第三部分加上下划线和百分号之后，程序就正常了.
|
1
2
3
4
5
6
7
8
9
|
public static void main(String[] args) {
String badRegex =
"^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~_%\\/])+$"
;
String bugUrl =
"http://www.fapiao.com/dddp-web/pdf/download?request=6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf"
;
if
(bugUrl.matches(badRegex)) {
System.out.println(
"match!!"
);
}
else
{
System.out.println(
"no match!!"
);
}
}
|
运行上面的程序，立刻就会打印出match!!.
但这是不够的，如果以后还有其他 URL 包含了乱七八糟的字符呢，我们难不成还再修改一遍。肯定不现实嘛！ 。
其实在正则表达式中有这么三种模式： 贪婪模式、懒惰模式、独占模式.
在关于数量的匹配中，有 + ? * {min,max} 四种两次，如果只是单独使用，那么它们就是贪婪模式.
如果在他们之后加多一个 ? 符号，那么原先的贪婪模式就会变成懒惰模式，即尽可能少地匹配。但是懒惰模式还是会发生回溯现象的。例如下面这个例子:
|
1
|
text=
"abbc"
regex=
"ab{1,3}?c"
|
正则表达式的第一个操作符 a 与 字符串第一个字符 a 匹配，匹配成功。于是正则表达式的第二个操作符 b{1,3}? 和 字符串第二个字符 b 匹配，匹配成功。因为最小匹配原则，所以拿正则表达式第三个操作符 c 与字符串第三个字符 b 匹配，发现不匹配。于是回溯回去，拿正则表达式第二个操作符 b{1,3}? 和字符串第三个字符 b 匹配，匹配成功。于是再拿正则表达式第三个操作符 c 与字符串第四个字符 c 匹配，匹配成功。于是结束.
如果在他们之后加多一个 + 符号，那么原先的贪婪模式就会变成独占模式，即尽可能多地匹配，但是不回溯.
于是乎，如果要彻底解决问题，就要在保证功能的同时确保不发生回溯。我将上面校验 URL 的正则表达式的第二部分后面加多了个 + 号，即变成这样:
|
1
2
3
|
^([hH][tT]{2}[pP]:
//
|[hH][tT]{2}[pP][sS]:
//
)
(([A-Za-z0-9-~]+).)++ --->>> （这里加了个+号）
([A-Za-z0-9-~_%\/])+$
|
这样之后，运行原有的程序就没有问题了.
最后推荐一个网站，这个网站可以检查你写的正则表达式和对应的字符串匹配时会不会有问题.
Online regex tester and debugger: PHP, PCRE, Python, Golang and JavaScript 。
例如我本文中存在问题的那个 URL 使用该网站检查后会提示：catastrophic backgracking（灾难性回溯）.
藏在正则表达式里的陷阱，一个正则表达式导致CPU 利用率居高不下 。
当你点击左下角的「regex debugger」时，它会告诉你一共经过多少步检查完毕，并且会将所有步骤都列出来，并标明发生回溯的位置.
藏在正则表达式里的陷阱，一个正则表达式导致CPU 利用率居高不下 。
本文中的这个正则表达式在进行了 11 万步尝试之后，自动停止了。这说明这个正则表达式确实存在问题，需要改进.
但是当我用我们修改过的正则表达式进行测试，即下面这个正则表达式.
|
1
|
^([hH][tT]{2}[pP]:
//
|[hH][tT]{2}[pP][sS]:
//
)(([A-Za-z0-9-~]+).)++([A-Za-z0-9-~\/])+$
|
工具提示只用了 58 步就完成了检查.
总结 。
以上所述是小编给大家介绍的一个正则表达式导致CPU 利用率居高不下,希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我网站的支持！ 如果你觉得本文对你有帮助，欢迎转载，烦请注明出处，谢谢！ 。
原文链接：https://studygolang.com/articles/21308 。
最后此篇关于一个正则表达式导致CPU 利用率居高不下的文章就讲到这里了,如果你想了解更多关于一个正则表达式导致CPU 利用率居高不下的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
25
4
0
我知道使用事件监视器我们可以看到 CPU 利用率。但我想通过脚本获取远程系统的这些信息。 top 命令对我没有帮助。请评论我任何其他方式来获得它。 最佳答案 在日志模式下对 top 的反对是什么？ t
我一直在使用 NVML 库来获取图形和内存利用率的值 Rodinia 基准套件。我观察到，对于不同的频率，同一应用程序的利用率显示出不同的值。来自维基链接http://en.wikipedia.org
我们计划使用 Locust 进行性能测试。我已经在 Kubernetes 上以分布式模式启动了 Locust，有 800 个用户持续了 5 分钟。孵化率也是100。几分钟后，我可以在工作日志中看到以下
关闭。这个问题是off-topic .它目前不接受答案。 想改进这个问题？ Update the question所以它是on-topic对于堆栈溢出。 10年前关闭。 Improve this qu
我正在使用java 8并行流将数据插入数据库。以下是代码 customers.parallelStream().forEach(t->{ UserTransaction userTra
我有一个基准测试程序，可以计算时间(以毫秒和滴答为单位)，以持久化到 Entity Framework 4.0。有没有办法计算 CPU 负载？我猜我需要查询 Windows 来找出我的 CPU 频率、
我正在处理一个与网络相关的守护进程:它接收数据，处理数据，然后将数据吐出。我想通过分析它并降低它的 CPU 使用率来提高这个守护进程的性能。我可以在 Linux 上使用 gprof 轻松完成此操作。但
考虑到下面的 C 代码，我预计 CPU 利用率会上升到 100%，因为处理器会尝试完成分配给它的作业(在这种情况下是无限的)。在运行可执行文件 5 分钟后，我发现 CPU 达到了最大值。的 48%。我
我想修改以下脚本，使其仅在进程/pid 号使用超过 50% 的 CPU 时运行。有人知道如何获取该信息吗？如果特定 pid 的 cpu 利用率超过 50%，我只想使用 jstack 创建线程转储。 #
我在 Python 3.4 中工作，对内存中的分区数据执行简单搜索，并尝试 fork 进程以利用所有可用的处理能力。我说天真，因为我确信还有其他额外的事情可以提高性能，但这些潜力超出了手头问题的范围。
我的多线程应用程序 (c++) 使用 pthreads。该应用程序自动生成线程并按需重新使用它们，并允许在线程空闲时间过长时将其取消。 我放入了一个“特殊线程”来捕获统计数据，以查看应用程序在不同情况
是否有一种标准方法来获取 GPU 上的当前负载？我正在寻找类似于显示 CPU% 的任务管理器的东西。 GPU-Z 等实用程序会显示此值，但我不确定它是如何获得此值的。我目前对 AMD 显卡特别感兴趣，
在运行时如何控制 cpu 利用率是明智的？ 轮询 CPU 负载并插休眠眠？ 最佳答案 我会推荐操作系统功能。 Windows 上有性能计数器和 WinAPI 函数。 这是一个使用来自 BCL Team
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 这个问题似乎不是关于 a specific programming problem, a softwar
我有一个运行 Linux 的 ARM 平台，其中 L1 行长 64 字节。 我决定用另一个 malloc 替换 malloc(通过 LD_PRELOAD)，其中无论分配给 malloc 的大小如何，内
在 Linux 中是否有命令或任何其他方法来获取当前或平均 CPU 利用率(对于多处理器环境)？ 我在一个小型系统中使用嵌入式 Linux。基本上，我需要确定 CPU 利用率，如果它很高，我可以将一个
我有一个计算CPU利用率的任务，我有4个进程 P1 30% 的时间在等待 I/O。 P2 40% 的时间在等待 I/O。 P3 等待 I/0 20% 的时间。 P4 等待 I/0 50% 的时间。 我
我正在训练一个模型，当我在 Google Cloud Platform 控制台中打开 TPU 时，它会向我显示 CPU 利用率(我想是在 TPU 上)。它真的非常非常低(比如 0.07%)，所以也许是
我在 redhat 6 上执行了以下代码片段: #include int main(int argc, char *argv[]) { while(true) { #ifdef S
我有一个程序可以通过将大文件分成 block 来对大文件进行排序，对 block 进行排序并将它们合并到最终排序的文件中。应用程序运行一个线程来从文件加载数据/将数据保存到文件 - 只有一个线程执行
我是一名优秀的程序员,十分优秀！