Similaridade de Strings em Big Data
Quando estudamos sobre programação aprendemos que as operações com strings são consideradas complexas devido ao fato de os computadores serem programados para entender números e não letras. Google e Yahoo foram as empresas que quebraram o paradigma dos mecanismos de buscas com palavras e foram capazes de desenvolver os maiores sites de busca. Todo mundo já fez uma pesquisa no Google e notou que mesmo quando ocorre um erro de digitação em determinada palavra ou se troca uma palavra em uma sentença, o mecanismo de busca é capaz de encontrar/adivinhar o que você quis dizer e te entregar o resultado desejado. Isso é possível graças aos algoritmos de similaridade de strings, sendo a distância de Levenshtein e o Jaro-Winkler os mais conhecidos.
A distância de Levenshtein calcula quantas mudanças (inserções, remoções ou substituições) devem ser feitas em uma string para que ela se torne a outra que está sendo comparada. Essa medida é um número que independe da quantidade de caracteres que a string possui, logo, palavras como AME e AMA, AMENDOIM e AMENDOIN, possuem a mesma distância de Levenshtein, pois em ambos os casos é necessária apenas 1 mudança para transformar uma string na outra. Caso queiramos construir uma versão score dessa distância, basta dividir pela quantidade de caracteres, com isso AME e AMA ficam com score de 67 em similaridade e AMENDOIM e AMENDOIN com score de 88.
Já o método de Jaro-Winkler calcula a similaridade entre duas strings. Esse algoritmo é a combinação do algoritmo de Jaro, que considera quantos caracteres em comum as duas strings possuem, o número de transposições necessárias e a quantidade de caracteres que elas possuem. Já a variante Winkler adiciona um peso aos primeiros caracteres, tornando-o mais adequado para comparar strings menores. Para os mesmos exemplos anteriores, a similaridade de Jaro-Winkler entre AME e AMA é 82 e entre AMENDOIM e AMENDOIN é de 95.
Além dos algoritmos de similaridade de string, existe também o Soundex que converte uma string a uma outra string referente à sua fonética. Caso queira fazer a comparação em fonética, basta aplicar o Soundex e em seguida um algoritmo de similaridade de strings.
O Spark, nosso grande amigo quando se fala em Big Data, já possui integrado as funções de Levenshtein e Soundex, o que é uma grande vantagem. Caso queiram implementar o Jaro-Winkler é necessário fazer através de uma UDF que por si só compromete um pouco o desempenho em Spark.
Realizar o cálculo de similaridade de strings em pequenas bases é até uma tarefa bem simples e não se percebe tanto os problemas de performance. Entretanto, me deparei com um problema onde eu precisava calcular a similaridade entre milhões de strings com uma lista na faixa de milhares de strings. Multiplicando milhões por milhares, encaramos um dataset que possui trilhões de possibilidades para computação. E aí começou o desafio.
A arquitetura Spark é composta de clusters que executam o processo em paralelo. Existe um cluster principal chamado de head ou driver que faz o papel de gerente e envia os trabalhos para os clusters workers executarem. Durante o processo, aprendi que um cluster worker precisa ter mais capacidade de processamento do que de memória e o cluster driver o inverso, mais memória do que processamento, justamente pelo objetivo que cada um foi desenvolvido. Uma boa distribuição nos dados e nas tarefas fazem com que os cluster workers trabalhem o tempo inteiro em paralelo e o driver fique apenas enviando informações de um para o outro e apontando as tarefas.
Em computação existem tarefas que necessariamente precisam ser realizadas sequenciais enquanto outras podem ser executadas em paralelo, o famoso dividir para conquistar. O Spark foi desenvolvido pensando exatamente nas tarefas em paralelo e a melhor forma de usar todo o seu desempenho é desenvolver o código pensando em execução de tarefas na horizontal, ou seja, particionar o dataset horizontalmente e distribuir as tarefas de forma que os workers não precisam trocar tanta informação entre si, os famosos shuffles.
As tarefas que são facilmente paralelizadas são aquelas onde a mesma operação precisa ser realizada diversas vezes e onde uma operação não depende da anterior para continuar. Esse era exatamente o caso que estava encarando, onde a mesma operação (execução de algoritmos de similaridade de strings) precisava ser aplicado em cada linha do dataset.
Como eu tinha uma base muito grande para fazer multiplicação cruzada com uma base pequena, para facilitar o trabalho dos workers, o cross join foi feito usando o artifício de hint (‘broadcast’) na base menor. As tarefas de joins demandam muito do Spark, pois o dataset está particionado com os workers e eles precisam trocar informação entre si para construir a tabela final. O broadcast ajuda nessa etapa fazendo com que a base seja copiada em cada worker evitando os shuffles e melhorando a performance. Mas lembre-se que os workers são máquinas com pouca memória, então as bases com o broadcast precisam ser pequenas para conseguirem ser absorvidas pelos workers.
Além do broadcast na base menor durante o join, a base maior foi reparticionada para ter a mesma quantidade de partições que a quantidade de dados na base menor. Afinal, o cross join é uma execução de N (milhões de registros) vezes M (milhares de registro), então ao forçar o dataset ter M partições permitiu uma melhor distribuição dos dados entre os workers e melhorou muito o tempo de processamento do código.
Para um melhor resultado final, foi necessário combinar o Levenshtein e o Jaro-Winkler aplicados tanto na versão original das strings que estava comparando, como na sua representação fonética fornecida pelo Soundex. Como o Jaro-Winkler não era nativo do Spark e foi criado através de uma UDF, nesse caso para executá-lo foi preciso persistir os dados, ou seja, salvá-los em um repositório temporário após a execução do primeiro algoritmo e continuar lendo a partir desse repositório. A persistência dos dados é bastante útil quando se tem muito processamento sequencial em uma única execução. Caso não seja possível, é possível realizar um ajuste fino nos pesos do Levenshtein aplicado ao Soundex e conseguir um resultado similar e garantir o desempenho.
Não é todo dia que se tem um desafio de trabalhar com trilhões de dados. Mas esse desafio me permitiu aprender demais como funciona o ambiente Spark e como aproveitar melhor os seus recursos.
