La regex che non finisce mai: backtracking e messaggi Kafka grandi

Cerchi un codice fiscale in un topic con un'espressione regolare. Scrivi qualcosa come:

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

Sembra ragionevole: «qualsiasi cosa, poi il pezzo che mi interessa, poi qualsiasi cosa». Su migliaia di messaggi piccoli va benissimo. Poi nel topic arriva un solo messaggio da 1 MB e la ricerca non finisce più.

Nel nostro banco di correttezza è successo davvero: un client con un motore regex a backtracking non aveva ancora finito dopo 28 minuti, su un topic di 312 messaggi. Con un motore a tempo lineare, gli stessi 3 risultati sono arrivati subito.

Perché succede

Molti motori di espressioni regolari, fra cui java.util.regex di Java, funzionano a backtracking: provano una strada, e se non va tornano indietro e ne provano un'altra.

Con .* all'inizio e un controllo che deve coprire tutto il testo, il motore:

1. fa mangiare a .* l'intero messaggio, un milione di caratteri;
2. scopre che dopo non c'è RSS, quindi restituisce un carattere e riprova;
3. ripete, un carattere alla volta, per ogni posizione di partenza.

Il numero di tentativi cresce con il quadrato della lunghezza del testo. Mille caratteri: un milione di passi, niente di grave. Un milione di caratteri: un milione di milioni di passi. Ecco le ore.

Pattern con quantificatori annidati, come (a+)+, fanno anche di peggio: lì la crescita è esponenziale, e bastano poche decine di caratteri.

Ordini di grandezza, non misure.

Come scrivere pattern più sicuri

• Togli .* all'inizio e alla fine. Se lo strumento cerca il pattern dentro il testo (find, non match), RSS[A-Z]{3}\d\d trova le stesse cose ed è enormemente più veloce.
• Ancora il pattern quando puoi. ^ e $ dicono al motore dove guardare.
• Sii specifico. [A-Z0-9]{16} è meglio di .+: il motore ha meno strade da provare.
• Niente quantificatori annidati come (\w+)* o (a|aa)+.
• Prova su un messaggio grande prima di lanciare la ricerca su tutto il topic.

I motori che non hanno il problema

Esistono motori regex che garantiscono un tempo lineare nella lunghezza del testo: RE2 di Google, il crate regex di Rust, il pacchetto regexp di Go. Rinunciano a qualche funzione (i backreference come \1 e alcune lookaround) e in cambio non possono mai esplodere: un messaggio da 1 MB costa più o meno mille volte uno da 1 KB, non un milione di volte.

Per uno strumento che lancia regex scritte dall'utente su dati che non controlla, come i messaggi di un topic di produzione, è la scelta più sicura.

In Topicup

La ricerca per espressione regolare di Topicup usa il crate regex di Rust: tempo lineare, anche sul messaggio da 1 MB. E i pattern con .* all'inizio e alla fine funzionano lo stesso, senza bisogno di riscriverli.