20 milhões de linhas em 20s

Olá, meu nome é Lucas Wasilewski e recentemente me propus a começar a programar com mais limitações, tanto no sentido de máquina quanto no sentido de programas auxiliares, dito isso, o ecossistema do JDK tem alguns gerenciadores de pacotes muito bem conhecidos como: Gradle e o Maven, porém, como você conecta uma das linguagens mais populares do mundo com um banco de dados sem eles? É isso que eu quis resolver.

JNI e libpq

Bem, como eu não tenho acesso a nenhuma outra biblioteca que faça a conexão ao Postgres, basta eu escrever uma eu mesmo?

Sim, e é bem mais fácil do que parece, o primeiro passo seria eu encontrar uma forma de me conectar ao banco através do Java, me veio a mente que em libs do NodeJs geralmente você especifica os dados necessários em um formato de string, mais ou menos assim:

postgres://usuario:senha@host:port/banco_de_dados

Então logo pensei que deveria ter algo haver com uma conexão de sockets e na verdade o projeto ia virar mais relacionado a redes. Porém, com uma rápida pesquisada na documentação do próprio PostgreSQL vi que eu iria primeiro ter que escrever um client e para isso eu precisava da biblioteca deles: libpq.

Lendo mais um pouco eu vi que só havia implementações em C e então o caminho estava mais claro do que nunca: eu só precisava de uma forma do Java conseguir chamar as funções de outra linguagem e resgatar os dados, isso tem um nome, se chama FFI (Foreign Function Interface) sendo algo muito utilizado devido as limitações das próprias linguagens. Um exemplo disso é o Numpy do Python que usa algumas partes em Fortran devido ao desempenho

Depois de mais uma pesquisada achei o JNI (Java Native Interface), que de acordo com a Oracle: JNI é uma interface que permite ao Java chamar código escrito em outras linguagens, como C ou C++. Basicamente o compilador do Java consegue gerar headers que podem ser depois implementados por essas linguagens usando o <jni.h>.

Claro que o meu objetivo desde o principio era somente conseguir fazer essa conexão e funções suficientes para um mísero CRUD, porém, a criação da lib foi muito rápida e eu queria mais desafios.

20 milhões de linhas

Saiu bem no inicio desse ano (2024) um desafio feito por Gunnar Morling em seu blog chamado de: One Billion Row Challenge, nesse desafio os participantes teriam que dar parse em um arquivo csv com 1 bilhão de linhas, tudo isso feito em Java, essa competição ficou bem famosa e a solução mais rápida foi em 1.5s, isso me deixou muito curioso. Afinal, o arquivo devia ser muito pesado e eles usaram muitos (realmente muitos) conceitos técnicos de memória, processador, sistema operacional e performance.

Um bilhão de linhas é muita coisa para mim ainda, mas talvez eu consiga trabalhar com um número um pouco menor, então após algumas sessões com a nossa LLM favorita criei um script em Python que conseguia criar dois arquivos csv com nome;email;telefone pesando 10mb e 1GB, com 209712 e 20971521 de linhas respectivamente. Agora só bastava por minha framework a maior prova de fogo que eu consegui criar.

Primeira implementação

O primeiro passo é ler o arquivo. Isso pode soar fácil se você estiver na casa das 200 mil linhas, a memória heap da JVM onde geralmente se guarda o conteúdo lido provavelmente suporta essa quantidade de dados, mas você nunca vai conseguir guardar 1 milhão de itens lá dentro. Por isso a sua melhor opção vai ser ler e processar linha a linha do arquivo, assim, você não estoura a memória e linearmente insere todos os itens. Bom, vamos aos testes, todos eles serão feitos em um i5-11400 com 12 threads.

9 minutos.
Esse foi o melhor tempo que consegui com essa implementação e ainda nem chegamos na casa do milhão, o que deu errado? Não era pro Java ser rápido? Melhor reescrever tudo em React...

Segunda implementação

A nossa máquina está acostumada a fazer bilhões de instruções por minuto e o primeiro algoritmo apena lê sequencialmente e insere cada linha uma a uma no banco, ou seja, o tempo aumenta quanto mais linhas existem no arquivo, fora que estamos jogando um tempo de leitura precioso demais aguardando as outras tarefas de dar parse na linha e as de inserção.

Para reduzir esse problema podemos introduzir o multi-threading, fazendo com que usemos todos os nossos núcleos do processador e aumentando o número de "atores" para resolver o problema. Então nessa implementação adicionei uma queue, a thread principal lia o arquivo sequencialmente da forma mais rápida que podia e ia jogando em pedaços as linhas para que alguma outra thread pudesse puxar esse valor e fazer a inserção. Vamos aos testes:

Opa, uma melhoria de 55,56%, já começou a ficar bem mais legal, até mesmo conseguimos processar o arquivo de 1Gb, porém, por algum motivo essa implementação fica presa nas 1.200.000 linhas.

Terceira implementação

Ok, as threads ajudam muito, mas, meu conhecimento em Java não é dos maiores, então eu usei um método que eu conhecia em outras linguagens: Eu pegava a linha inteira, usava o .split para separar por ; e então usava o .format para criar uma query de inserção, ao pesquisar por soluções melhores achei em um blog que o .format era o mais lento dentre todas as funções de string no Java e que isso era o que provavelmente estava causando essa enorme lentidão, então comecei a usar o StringBuilder:

StringBuilder sb = new StringBuilder();
sb.append("INSERT INTO users VALUES ");
for(String line : lines) {
    String[] split = line.split(";");
    sb.append("('"+ split[0] + "','" + split[1] +"'," + split[2]  +"),");
}
sb.setCharAt(sb.length() - 1, ';');
connection.query(sb.toString());

Nos testes isso realmente se provou ser um grande gargalo do algoritmo:

😲 essa foi minha reação quando eu fiz o primeiro teste, uma melhora de 99,83%. Tão rápido que eu mesmo não estava acreditando que no que estava acontecendo. Claro que o StringBuilder não foi a única solução adicionada, se você olhar com um pouco mais de atenção dá para perceber que junto todos os inserts das linhas e faço a query de uma vez só, assim reduzindo a quantidade de comandos realizados.

Um último suspiro

Eu ainda estava querendo mais, queria pelo menos algo em torno de 15 segundos (ia ficar bem no título, pensei comigo), então adicionei uma última carta na manga, as threadpools, elas são um número de threads que são criadas em conjunto e conseguem receber tarefas igualmente, assim reduzo o tempo de criação e também melhoro a forma de distribuir as tarefas:

Aqui, começo a identificar os gargalos nas minhas implementações. Nessa última tentativa, além da pool de threads, utilizei outros métodos que encontrei para extrair o máximo de desempenho possível. Porém não consegui passar dos 20 segundos.

Conclusões

Esse projeto foi com certeza o mais técnico que fiz nos últimos tempos, apesar de não chegar no tempo que eu queria eu fiquei muito animado quando descobria cada nova forma de melhorar uma única linha (mesmo que eu provavelmente fosse ganhar no máximo 0.001 segundos).

Ainda sim fiquei pensando o quanto eu conseguiria extrair dessa única framework de 3 funções, vale ressaltar que no desafio do bilhão de linhas eles somente tinham que processar o arquivo e escrever na tela, assim, não levavam em conta o tempo de espera das querys (embora eu acredite que isso não seria um impedimento para eles).

Em conclusão, o meu pequeno desafio de ter mais impedimentos do que ajudas foi o pontapé para eu estudar e aprender mais sobre muita coisa que eu não conhecia, isso fora as que eu não quis entrar, como os métodos unsafe do java que iria me permitir mexer com ponteiros e endereços de memória.

Caso você queira olhar o que eu fiz de certo, ou provavelmente de muito errado, por favor dê uma olhada no projeto pelo github: Ant. Rumo aos 2 bilhões de linhas.

C is quirky, flawed, and an enormous success - Dennis Ritchie

Refêrencias

https://docs.oracle.com/javase/8/docs/technotes/guides/jni/

https://en.wikipedia.org/wiki/Foreign_function_interface

https://www.postgresql.org/docs/17/libpq.html

https://www.baeldung.com/java-read-lines-large-file

https://github.com/gunnarmorling/1brc

https://www.youtube.com/watch?v=EFXxXFHpS0M&t=1836s