The regex that never finishes: backtracking and large Kafka messages

You search a topic for a tax code with a regular expression. You write something like:

.*RSS[A-Z]{3}\d\d.*

It looks reasonable: "anything, then the bit I care about, then anything". On thousands of small messages it works fine. Then a single 1 MB message lands in the topic and the search never ends.

In our correctness bench it really happened: a client with a backtracking regex engine had still not finished after 28 minutes, on a topic of 312 messages. With a linear-time engine, the same 3 matches came back at once.

Why it happens

Many regular expression engines, including Java's java.util.regex, work by backtracking: they try one path and, if it fails, go back and try another.

With .* at the start and a match that must cover the whole text, the engine:

1. lets .* swallow the entire message, a million characters;
2. finds there is no RSS after it, gives back one character and tries again;
3. repeats, one character at a time, for every starting position.

The number of attempts grows with the square of the text length. A thousand characters: a million steps, no big deal. A million characters: a million million steps. Hence the hours.

Patterns with nested quantifiers, such as (a+)+, are even worse: there the growth is exponential, and a few dozen characters are enough.

Orders of magnitude, not measurements.

How to write safer patterns

• Drop the .* at the start and the end. If the tool looks for the pattern inside the text (find, not match), RSS[A-Z]{3}\d\d finds the same things and is enormously faster.
• Anchor the pattern when you can. ^ and $ tell the engine where to look.
• Be specific. [A-Z0-9]{16} is better than .+: the engine has fewer paths to try.
• No nested quantifiers like (\w+)* or (a|aa)+.
• Test on a large message before running the search on the whole topic.

Engines that do not have the problem

Some regex engines guarantee linear time in the length of the text: Google's RE2, Rust's regex crate, Go's regexp package. They give up a few features (backreferences like \1 and some lookarounds) and in exchange they can never blow up: a 1 MB message costs roughly a thousand times a 1 KB one, not a million times.

For a tool that runs user-written regexes over data it does not control, such as the messages of a production topic, it is the safest choice.

In Topicup

Topicup's regular-expression search uses Rust's regex crate: linear time, even on the 1 MB message. And patterns with .* at the start and the end still work, with no need to rewrite them.