Erros de concorrência no Lucene: Como corrigir falhas de concorrência otimista

Você deseja obter a certificação da Elastic? Descubra quando será realizado o próximo treinamento do Elasticsearch Engineer! Você pode iniciar um teste gratuito na nuvem ou experimentar o Elastic na sua máquina local agora.

Sim, mais um blog sobre correção de bugs. Mas esta história tem uma reviravolta: um herói do código aberto surge e salva o dia.

Depurar erros de concorrência não é tarefa fácil, mas vamos abordar o assunto. Apresentamos o Fray, uma estrutura de teste de concorrência determinística do PASTA Lab da CMU, que transforma falhas instáveis em falhas reproduzíveis de forma confiável. Graças ao engenhoso design de trava sombreada e ao controle preciso da rosca do Fray, conseguimos localizar e finalmente eliminar um bug complexo do Lucene. Este artigo explora como ferramentas e projetos de código aberto estão tornando a depuração de concorrência menos trabalhosa — e o mundo do software muito melhor.

Erros de concorrência: o pesadelo dos engenheiros de software

Os piores bugs relacionados à concorrência são os seguintes. Além de serem difíceis de consertar, o mais complicado é justamente fazê-los falhar de forma consistente. Tomemos como exemplo esta falha de teste, TestIDVersionPostingsFormat#testGlobalVersions. Isso gera várias threads de escrita e atualização de documentos, desafiando o modelo de concorrência otimista do Lucene. Este teste revelou uma condição de corrida no controle de concorrência otimista. Ou seja, uma operação em um documento pode alegar falsamente ser a última em uma sequência de operações 😱. Ou seja, em certas condições, uma operação de atualização ou exclusão pode, na verdade, ter sucesso quando deveria ter falhado, considerando restrições de concorrência otimistas.

Pedimos desculpas àqueles que detestam rastreamentos de pilha do Java. Note que "excluir" não significa necessariamente "excluir". Também pode indicar uma "atualização" do documento, já que os segmentos do Lucene são somente leitura.

O Apache Lucene gerencia cada thread que está escrevendo documentos através da classe DocumentsWriter . Esta classe criará ou reutilizará threads para escrita de documentos e cada ação de escrita controla suas informações dentro da classe DocumentsWriterPerThread (DWPT). Além disso, o escritor mantém o controle de quais documentos são excluídos no DocumentsWriterDeleteQueue (DWDQ). Essas estruturas mantêm todas as ações de mutação de documentos na memória e são periodicamente liberadas, liberando recursos na memória e persistindo as estruturas em disco.

Na tentativa de evitar o bloqueio de threads e garantir alto desempenho em sistemas concorrentes, o Apache Lucene tenta sincronizar apenas em seções críticas. Embora isso possa ser bom na prática, como em qualquer sistema concorrente, existem problemas.

Uma falsa esperança

Minha investigação inicial apontou para algumas seções críticas que não estavam devidamente sincronizadas. Todas as interações com um dado DocumentsWriterDeleteQueue são controladas pelo seu envolvente DocumentsWriter. Assim, embora os métodos individuais possam não estar devidamente sincronizados no DocumentsWriterDeleteQueue, o seu acesso ao mundo está (ou deveria estar). (Não vamos entrar em detalhes sobre como isso complica as questões de propriedade e acesso — é um projeto de longa data escrito por muitos colaboradores.) Dê um desconto para isso.)

No entanto, encontrei um ponto durante a descarga que não estava sincronizado.

Essas ações não são sincronizadas em uma única operação atômica. Significa que, entre a criação de newQueue e a chamada de getMaxSeqNo, outro código poderia ter sido executado incrementando o número de sequência na classe documentsWriter . Encontrei o bug!

Mas, como acontece com a maioria dos bugs complexos, encontrar a causa raiz não foi simples. Foi então que um herói entrou em cena.

Um herói na batalha

Apresentamos nosso herói: Ao Li e seus colegas do Laboratório PASTA. Deixarei que ele explique como eles salvaram o dia com a ajuda de Fray.

Fray é uma estrutura de teste de concorrência determinística desenvolvida por pesquisadores do PASTA Lab, da Universidade Carnegie Mellon. A motivação por trás da criação do Fray surge de uma lacuna notável entre a academia e a indústria: embora os testes de concorrência determinísticos tenham sido amplamente estudados em pesquisas acadêmicas por mais de 20 anos, os profissionais continuam a depender de testes de estresse — um método amplamente reconhecido como não confiável e instável — para testar seus programas concorrentes. Assim, nosso objetivo principal era projetar e implementar uma estrutura de teste de concorrência determinística, tendo como metas a generalidade e a aplicabilidade prática.

A ideia central

Em sua essência, o Fray se baseia em um princípio simples, porém poderoso: a execução sequencial. O modelo de concorrência do Java oferece uma propriedadefundamental: se um programa estiver livre de condições de corrida (data races), todas as execuções parecerão sequencialmente consistentes. Isso significa que o comportamento do programa pode ser representado como uma sequência de instruções do programa.

O Fray funciona executando o programa alvo de forma sequencial: a cada passo, ele pausa todas as threads, exceto uma, permitindo que o Fray controle com precisão o agendamento das threads. Os threads são selecionados aleatoriamente para simular a concorrência, mas as escolhas são registradas para posterior reprodução determinística. Para otimizar a execução, o Fray realiza trocas de contexto apenas quando uma thread está prestes a executar uma instrução de sincronização, como bloqueio ou acesso atômico/volátil. Uma propriedade interessante da ausência de condições de corrida em relação aos dados é que essa troca de contexto limitada é suficiente para explorar todos os comportamentos observáveis devido a qualquer intercalação de threads (nosso artigo contém um esboço da demonstração).

O desafio: controlar o agendamento de threads

Embora a ideia central pareça simples, a implementação do Fray apresentou desafios significativos. Para controlar o agendamento de threads, o Fray precisa gerenciar a execução de cada thread da aplicação. À primeira vista, isso pode parecer simples: substituir primitivas de concorrência por implementações personalizadas. No entanto, o controle de concorrência na JVM é complexo, envolvendo uma combinação de instruções de bytecode, bibliotecas de alto nível e métodos nativos.

Isso acabou se revelando um verdadeiro labirinto:

• Por exemplo, cada instrução MONITORENTER deve ter uma correspondente MONITOREXIT no mesmo método. Se Fray substituir MONITORENTER por uma chamada de método para um stub/mock, também precisará substituir MONITOREXIT.
• Em código que faz uso de object.wait/notify, se MONITORENTER for substituído, o object.wait correspondente também deverá ser substituído. Esta cadeia de substituição estende-se até object.notify e além.
• A JVM invoca certos métodos relacionados à concorrência (por exemplo, object.notify quando uma thread termina) dentro do código nativo. Substituir essas operações exigiria modificar a própria JVM.
• Funções da JVM, como carregadores de classe e threads de coleta de lixo (GC), também usam primitivas de concorrência. Modificar esses elementos primitivos pode criar incompatibilidades com essas funções da JVM.
• A substituição de primitivas de concorrência no JDK frequentemente resulta em falhas da JVM durante sua fase de inicialização.

Esses desafios deixaram claro que uma substituição completa das primitivas de concorrência não era viável.

Nossa solução: design de fechadura sombreada

Para lidar com esses desafios, o Fray utiliza um novo mecanismo de bloqueio sombra para orquestrar a execução de threads sem substituir as primitivas de concorrência. Os bloqueios de sombra atuam como intermediários que orientam a execução das threads. Por exemplo, antes de adquirir um bloqueio, um thread de aplicação deve interagir com seu bloqueio sombra correspondente. O mecanismo de travamento por sombra determina se a rosca consegue obter a trava. Se a thread não puder prosseguir, o bloqueio sombra a bloqueia e permite que outras threads sejam executadas, evitando impasses e permitindo concorrência controlada. Este design permite que o Fray controle o entrelaçamento de threads de forma transparente, preservando a correção da semântica de concorrência. Cada primitiva de concorrência é cuidadosamente modelada dentro da estrutura de bloqueio sombra para garantir solidez e completude. Mais detalhes técnicos podem ser encontrados em nosso artigo.

Além disso, este projeto foi concebido para ser à prova de futuro. Ao exigir apenas a instrumentação de bloqueios de sombra em torno de primitivas de concorrência, garante-se a compatibilidade com versões mais recentes da JVM. Isso é viável porque as interfaces das primitivas de concorrência na JVM são relativamente estáveis e permaneceram inalteradas por anos.

Testando Fray

Após a construção do Fray, o próximo passo foi a avaliação. Felizmente, muitas aplicações, como o Apache Lucene, já incluem testes de concorrência. Esses testes de concorrência são testes JUnit regulares que criam várias threads, executam algum trabalho e, em seguida (geralmente), esperam que essas threads terminem para então verificar alguma propriedade. Na maioria das vezes, esses testes são aprovados porque utilizam apenas uma intercalação. Pior ainda, alguns testes falham apenas ocasionalmente no ambiente CI/CD, como descrito anteriormente, tornando essas falhas extremamente difíceis de depurar. Ao executarmos os mesmos testes com o Fray, descobrimos inúmeros bugs. Notavelmente, Fray redescobriu bugs relatados anteriormente que permaneceram sem correção devido à falta de uma reprodução confiável, incluindo o foco deste blog: TestIDVersionPostingsFormat.testGlobalVersions. Felizmente, com o Fray, podemos reproduzi-los de forma determinística e fornecer aos desenvolvedores informações detalhadas, permitindo que eles reproduzam e corrijam o problema de forma confiável.

Próximos passos para Fray

Estamos muito satisfeitos em saber, por parte dos desenvolvedores da Elastic, que o Fray tem sido útil na depuração de bugs de concorrência. Continuaremos trabalhando no Fray para torná-lo disponível para mais desenvolvedores.

Nossos objetivos de curto prazo incluem aprimorar a capacidade do Fray de reproduzir deterministicamente a programação, mesmo na presença de outras operações não determinísticas, como um gerador de valores aleatórios ou o uso de object.hashcode. Nosso objetivo também é melhorar a usabilidade do Fray, permitindo que os desenvolvedores analisem e depurem testes de concorrência existentes sem qualquer intervenção manual. E, mais importante ainda, se você estiver enfrentando dificuldades para depurar ou testar problemas de concorrência em seu programa, gostaríamos muito de ouvir sua opinião. Por favor, não hesite em criar uma issue no repositório do Fray no Github.

Hora de corrigir o bug de concorrência

Graças a Ao Li e ao laboratório PASTA, agora temos uma instância confiável que falha neste teste! Finalmente podemos resolver isso. A questão principal residia em como DocumentsWriterPerThreadPool permitia a reutilização de threads e recursos.

Aqui podemos ver cada thread sendo criada, fazendo referência à fila de exclusão inicial na geração 0.

Então, o avanço da fila ocorrerá no momento do flush, visualizando corretamente as 7 ações anteriores na fila.

Mas, antes que todas as threads terminem de ser processadas, duas são reutilizadas para um documento adicional:

Esses valores incrementarão o seqNo acima do máximo assumido, que foi calculado durante o flush como 7. Observe o numDocsInRAM adicional para os segmentos _3 e _0

Isso faz com que o Lucene contabilize incorretamente a sequência de ações do documento durante um flush, acionando essa falha no teste.

Como toda boa correção de bugs, a solução em si consiste em cerca de 10 linhas de código. Mas dois engenheiros levaram vários dias para descobrir:

Nem todos os heróis usam capas.

Sim, é clichê, mas é verdade.

A depuração de programas concorrentes é extremamente importante. Esses bugs de concorrência complexos levam uma quantidade excessiva de tempo para serem depurados e resolvidos. Embora novas linguagens como Rust possuam mecanismos integrados para ajudar a prevenir condições de corrida como essa, a maior parte do software no mundo já está escrita, e escrita em alguma linguagem diferente de Rust. Java, mesmo depois de todos esses anos, ainda é uma das linguagens mais utilizadas. A melhoria da depuração em linguagens baseadas na JVM torna o mundo da engenharia de software melhor. E considerando que algumas pessoas acreditam que o código será escrito por Grandes Modelos de Linguagem, talvez nosso trabalho como engenheiros acabe sendo apenas depurar código LLM ruim, em vez de apenas nosso próprio código ruim. Mas, independentemente do futuro da engenharia de software, a depuração de programas concorrentes continuará sendo fundamental para a manutenção e o desenvolvimento de software.

Obrigado, Ao Li, e seus colegas do PASTA Lab, por tornarem tudo ainda melhor.

Perguntas frequentes