Expressões regulares são mesmo lentas?

No mundo da computação, expressões regulares são bastante utilizadas e chegam a parecer mágica!

Já resolvi muitas coisas com elas, mas somente quando comecei a desenvolver com Go é que descobri que elas são bem lentas. Primeiramente, preciso dizer que se você vai executar uma regex poucas vezes, isso não será um problema de desempenho, mas se você vai executar milhares ou milhões de vezes, já deve começar a pensar em outras opções. Mostrarei um exemplo prático mais a frente.

Algumas expressões afetam tanto o desempenho de uma aplicação ou script, que são exploradas por atacantes com a intenção de derrubar serviços e até servidores. São os ataques de ReDoS. Esses acontecem quando usamos expressões regulares de complexidade alta para processar dados que vem do usuário. Evitar o uso de ‘*’ e ‘+’ pode ajudar a evitar esses ataques. No nosso exemplo não teremos essa preocupação, pois apenas analisaremos arquivos de log.

O exemplo que usarei foi tirado de um caso real. Eu costumava cuidar de um servidor de e-mails e ainda ajudo quando a galera que assumiu precisa. Na ocasião, eles precisavam analisar os logs do servidor para tentar detectar quando uma conta fosse usada para SPAM. Para isso, criaram um script que era executado a cada 5 minutos, ele fazia a contagem de envios de cada conta e bloqueava quem passasse de uma certa quota. O problema é que, num dia normal, um log acumulava pouco mais de 100 mil linhas, mas num dia de caos, chegavam a alguns milhões! Com isso, o tempo de processamento poderia durar mais do que os 5 minutos. Percebem a “bola de neve” e a avalanche chegando?

Se não me engano, o arquivo de log que usei de exemplo (1.4Gb referente a um único dia) estava demorando mais de 1 hora para ser processado no servidor. Copiando para a minha máquina, o processo era um pouco mais rápido. Acredito que por diferenças de hardware (meu SSD vs HD do servidor).

Para começar, percebi que o script deles (em bash) estava fazendo loops desnecessários. Ele lia o arquivo todo, do começo ao fim, para fazer a contagem de cada usuário individualmente, inclusive de usuários que nem eram citados. Resolvi isso usando um script em AWK que fazia todo o trabalho com uma única leitura:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#!/usr/bin/gawk -f

# segundo argumento serve para filtrar valores iguais ou acima de "quota"
BEGIN { quota = 1; if (ARGV[2]) quota = ARGV[2]; delete ARGV[2] }

match($0, /; from=<([^>]+)> to=</, arr) { list[arr[1]]++ }

END {
    for (i in list) {
        if (list[i] >= quota) print list[i] "\t" i
    }
}

Se fosse algo que recebesse entradas diretamente dos usuários, poderíamos ter problemas. Deixarei essa explicação pro final. O fato é que, na minha máquina, esse script estava levando 12 segundos para processar algo perto de 10 milhões de registros. Ainda precisaria processar a saída dele com um sort -nr para ordernar a lista de forma decrescente.

Depois descobri que adicionando uma condição mais simples antes, o script ficaria um pouco mais rápido (o tempo caiu para 9s). Então a linha 6 ficou assim:

6

/; from=</ && match($0, /; from=<([^>]+)> to=</, arr) { list[arr[1]]++ }

Meus colegas acharam que já estava bom, mas esses números são de um servidor modesto que tem cerca de 800 usuários (nem todos ativos). Um único domínio. Imaginem se fosse um ambiente maior e o chefe chegasse pedindo a contagem do mês inteiro! Eu me senti desafiado a estar preparado para situações piores. Foi então que resolvi fazer uma versão em Go para tentar melhorar o desempenho e já ter a saída ordenada definitiva. Na minha primeira tentativa, o programa já conseguiu executar a tarefa em 3,6s, usando a mesma regex “; from=<([^>]+)> to=<”.

Eu sabia que dava para melhor porque o limite ainda estava muito longe do que eu considerava o limite do IO (ler tudo e jogar fora com um “cat mail.log >> /dev/null” levava 110ms). Você pode ver essa primeira versão aqui.

Decidi então usar outra abordagem, evitando o uso de regex. Usando uma função da própria standard library: bytes.Cut(). Sem entrar em muitos detalhes, para cada linha do arquivo o programa ignorava um prefixo de 21 caracteres (timestamp) e depois buscava pelo trecho “; from=<”, cortando em partes “antes e depois”. Com a segunda parte, ele fazia outra busca por “> to=” e cortava novamente, dessa vez eu ficava com a primeira parte. Tudo isso parece bem mais complicado e eu pensei que todos esses if's poderiam ficar pesados. Eis que para a minha surpresa, o tempo de processamento caiu bastante, chegando numa média de 600ms!!

Por enquanto, essa é a versão final.