Understanding Java Regex Backtracking and Its Impact on CPU Usage

During a production incident a Java service showed CPU usage close to 100 %; a thread dump revealed that all stack traces were inside a method called validateUrl , which uses a large regular expression to validate URLs.

Running a simple unit test with the original regex shows the Java process spiking to 91 % CPU, confirming that the regex is the culprit.

The regex is composed of three parts: protocol validation, domain validation, and parameter validation. Because the engine used by Java is an NFA (Non‑Deterministic Finite Automaton), it performs backtracking when a pattern is ambiguous or overly greedy.

Backtracking can cause catastrophic performance degradation: the engine tries many possible ways to match the input, and when a later part fails it rewinds and retries, leading to millions of steps.

To illustrate the NFA behavior, the article walks through simple examples (matching "day" in a string, matching "ab{1,3}c" against "abbc", and the effect of lazy vs. greedy quantifiers). It then revisits the problematic URL regex, showing that the domain part uses a greedy pattern that consumes too much, and the parameter part does not allow underscores or percent signs, forcing massive backtracking.

The proposed fix adds the missing characters to the third part (e.g., [_%] ) and changes the second part to a possessive quantifier ( + + ) to prevent backtracking. After the modification the same test prints match!! and runs efficiently.

Additional tips include using online regex debuggers to visualize backtracking steps and preferring possessive or lazy quantifiers to avoid catastrophic performance.

In summary, a seemingly harmless regular expression can cripple CPU performance; developers should be aware of NFA backtracking, greedy quantifiers, and test regexes with realistic data.