Uso de CPU de 3.200%

• Em uma aplicação Java 17, todos os 32 núcleos ficaram saturados e o uso de CPU disparou até 3.200%; ao ordenar o thread dump por CPU time, foi possível ver várias threads presas em TreeMap.put()
• O código em loop inicialmente suspeito era ineficiente, mas a complexidade O(N lg(M)) e a verificação do tamanho da entrada não explicavam um tempo de execução em nível de incidente
• A causa real foi que várias threads modificavam um TreeMap compartilhado sem proteção, criando um cycle interno na red-black tree e levando buscas e inserções a um loop infinito
• O mesmo comportamento apareceu em código simples de reprodução, com ExecutorService e também em um serviço gRPC, e o pool de threads não expunha o NPE na saída padrão, dificultando ainda mais identificar a causa
• A correção não termina apenas ao trocar para Collections.synchronizedMap ou ConcurrentHashMap; também é preciso adicionar tratamento de exceções no executor, alertas de CPU e NPE, análise estática e testes multithread

---

Sintomas do incidente e a primeira pista

• A máquina ficou tão degradada que quase nem aceitava conexão via ssh, e o uso de CPU chegou a 3.200%
  • Era um estado em que todos os 32 núcleos do host estavam em uso
  • Era um cenário bem diferente de um bug anterior em que apenas 1 núcleo ficava em 100%
• O thread dump do runtime Java 17 incluía CPU time, e ao ordenar por CPU time apareceram várias threads com comportamento semelhante
  • A stack apontava para java.util.TreeMap.put()
  • O ponto no código da aplicação era BusinessLogic.someFunction(BusinessLogic.java:29)

O código inicialmente suspeito e as hipóteses descartadas

• O código no ponto do problema percorria unrelatedObjects, mas no corpo do loop usava apenas relatedObject

for (SomeOtherType unrelatedObject : unrelatedObjects) {
    treeMap.put(relatedObject.a(), relatedObject.b()); // line 29
}

• Esse código poderia ser reduzido a um único put, assim:

treeMap.put(relatedObject.a(), relatedObject.b());

• unrelatedObjects era usado mais adiante na função, então o parâmetro em si não podia ser removido
• Havia a possibilidade de que o uso de unrelatedObject tivesse desaparecido durante um refactoring
• Mesmo aumentando treeMap e unrelatedObjects para 1.000.000 de entradas cada nos testes unitários, não foi possível reproduzir o problema
  • Se o tamanho de unrelatedObjects for N e o de treeMap for M, a complexidade é O(N lg(M))
  • A estimativa foi que, para chegar a tempos de execução na casa de 1 minuto, seriam necessários algo entre 100 milhões e 1 bilhão de entradas
  • Isso também não batia com a suposição de que, na aplicação real, essas duas estruturas nunca passavam de 1.000 elementos

O loop infinito causado por um TreeMap sem proteção

• A definição do campo TreeMap era a seguinte

private final Map<K,V> treeMap = new TreeMap<>();

• Várias threads acessavam esse TreeMap, mas não havia sincronização nem proteção
• O TreeMap do Java é implementado como uma red-black tree, e modificações concorrentes podem corromper os links internos dos nós e criar um cycle
• Ao buscar ou inserir um valor ainda inexistente, a navegação pode seguir esse cycle e cair em loop infinito

Experimento simples de reprodução

• Foi escrito um experimento em que várias threads atualizam aleatoriamente um TreeMap compartilhado

for (int i = 0; i < numThreads; i++) {
    threads.add(new Thread(() -> {
        Random random = new Random();
        for(int j = 0; j < numUpdates; j++) {
            try {
                treeMap.put(random.nextInt(1000), random.nextInt(1000));
            } catch (NullPointerException e) {
                // let it keep going so we can reproduce the issue.
            }
        }
    }));
}

• O projeto completo está em SimpleRepro.java
• No início, o try/catch parecia ser a peça-chave
  • Sem try/catch, algumas threads morriam com NullPointerException e o programa parava
  • Depois de adicionar o try/catch e executar algumas vezes, foi possível observar 500% de uso de CPU
• Uma race condition pode causar não só corrupção de dados ou deadlock, mas também corromper a estrutura de dados de um jeito que permite loop infinito, resultando em incidente de performance

Confirmando o cycle dentro do TreeMap

• Foi criado um experimento usando reflection para acessar os campos root, left, right, key e color do TreeMap e imprimir os nós e suas cores
• Se durante a travessia um mesmo TreeMap.Entry já visitado fosse encontrado de novo, isso seria tratado como cycle

private void print(
    Object treeMapEntry, String tabs, IdentityHashMap<Object, Object> visited
) throws Exception {
    if (treeMapEntry != null && !visited.containsKey(treeMapEntry)) {
        visited.put(treeMapEntry, treeMapEntry);
        print(treeMapEntryLeft.get(treeMapEntry), tabs + " ", visited);
        System.out.println(tabs + treeMapEntryKey.get(treeMapEntry) + ":"
            + (treeMapEntryColor.getBoolean(treeMapEntry) ? "BLACK" : "RED"));
        print(treeMapEntryRight.get(treeMapEntry), tabs + " ", visited);
    } else if (treeMapEntry != null && visited.containsKey(treeMapEntry)) {
        System.out.println(tabs + treeMapEntryKey.get(treeMapEntry) + ":"
            + (treeMapEntryColor.getBoolean(treeMapEntry) ? "BLACK" : "RED")
            + " CYCLE"
        );
    }
}

• Para abrir as restrições de acesso a módulos do Java, era necessário executar com o seguinte argumento de JVM

--add-opens java.base/java.util=ALL-UNNAMED

Casos anteriores relacionados e o diferencial deste

• Problemas desse mesmo tipo já eram conhecidos
  • writing to a java treemap concurrently can lead to an infinite loop during reads
  • High CPU due to multiple Java threads accessing TreeMap simultaneously da Red Hat
  • Java Process consumes more than 100% CPU
• Este caso também analisa código real de reprodução, tentativas de reprodução em várias linguagens e até ideias de modificação no TreeMap e na red-black tree

Uma reprodução mais realista com ExecutorService

• Ignorar NPE explicitamente pode parecer artificial, mas em ExecutorService as exceções podem não aparecer de forma óbvia

final ExecutorService pool = Executors.newFixedThreadPool(numThreads);
final TreeMap<Integer,Integer> treeMap = new TreeMap<>();
Random random = new Random();

for (int i = 0; i < numThreads*numUpdatesPerThread; i++) {
    pool.submit(() -> {
        treeMap.put(random.nextInt(10000), random.nextInt(10000));
    });
}

• O código completo está em ExecutorUncaughtRepro.java
• Ao executar, o programa trava, e o thread dump mostra threads presas em TreeMap.put()
• Não havia nada na saída padrão
  • O pool de threads engolia o NPE e o sinal do problema não aparecia
  • Era exatamente o que acontecia no caso real
• Se você gerencia o thread pool diretamente, são necessárias as seguintes medidas
  • Registrar um uncaught exception handler via thread factory
  • Tratar o Future retornado e usar future.get() para verificar o NPE encapsulado em ExecutionException

O mesmo problema em um serviço gRPC

• Em um serviço baseado em thread pool como um serviço gRPC, um TreeMap sem proteção pode provocar o mesmo problema

@Override
public void addReceipt(
    ReceiptProcessorServiceOuterClass.AddReceiptRequest req,
    StreamObserver<ReceiptProcessorServiceOuterClass.AddReceiptResponse> responseObserver
) {
    int timestamp = req.getTimestamp();
    int totalPrice = req.getTotalPrice();
    receipts.put(timestamp, totalPrice);
    ReceiptProcessorServiceOuterClass.AddReceiptResponse response =
        ReceiptProcessorServiceOuterClass.AddReceiptResponse.newBuilder().build();
    responseObserver.onNext(response);
    responseObserver.onCompleted();
}

• O código completo está em GrpcRepro.java
• A definição protobuf está em ReceiptProcessorService.proto
• O thread dump mostra threads grpc-default-executor-* travadas em estado runnable dentro de TreeMap.put()

Hipóteses sobre a causa e experimentos em várias linguagens

• Uma hipótese era que duas threads estivessem rotacionando a árvore em direções opostas de forma independente, ou que escritas intercaladas em rotações sobrepostas criassem o cycle
• Ainda assim, não há prova de qual interleaving exato entre threads produz o cycle
• No início houve a suspeita de que o NPE fosse necessário, mas experimentos posteriores derrubaram essa hipótese
• Houve tentativas de reproduzir o mesmo problema em várias linguagens
  • Java reproduz o problema, já que é a base de todo o caso
  • std::map do C++ também usa red-black tree e, em casos raros, em vez de segfault as threads travam com alto uso de CPU
  • Em Go, ao contrário do esperado, o problema também foi reproduzido; o código está em experimento em Go
  • Em Ruby não foi possível reproduzir, apesar de ser uma linguagem onde NPE pode ser capturado; a hipótese é que o GIL tenha impedido o interleaving necessário
• No experimento em C++, ao contrário do esperado, o loop infinito apareceu sem try/catch nem exceção de ponteiro nulo
  • Às vezes o processo terminava com segmentation fault
  • Muito raramente, ele ficava travado por mais de 10 minutos e o top mostrava SimpleRepro usando 170,8% de CPU
  • Como em C++ uma desreferenciação de ponteiro nulo causa segfault, deve existir um interleaving que não passa por null
• Depois de ver esse resultado, o experimento em Java foi executado novamente 12 vezes sem capturar NPE, e ainda assim foi possível reproduzir o loop infinito em TreeMap.put()

Correção simples e defesa no nível da estrutura de dados

• A correção mais simples é proteger o TreeMap compartilhado
  • Envolvendo-o com Collections.synchronizedMap
  • Ou trocando para ConcurrentHashMap e só aplicando ordenação quando necessário
• Uma defesa mais controversa é rastrear os nós já visitados durante a travessia da red-black tree
  • Se um nó já visitado for encontrado de novo, lança-se ConcurrentModificationException
  • Isso não impede a corrupção dos dados em si
  • Mas pode impedir 100% de uso de CPU causado por loop infinito
  • A memória adicional fica limitada à altura da árvore, isto é, O(lg(n))
  • A altura da red-black tree tem garantia de O(lg(n))
  • A avaliação é que dificilmente a biblioteca padrão adotaria essa abordagem
• O exemplo de modificação registra os nós visitados com IdentityHashMap em getEntry e put

IdentityHashMap<Entry<?,?>, Boolean> visited = new IdentityHashMap<>();

while (p != null) {
    visited.put(p, true);
    int cmp = k.compareTo(p.key);
    if (cmp < 0)
        p = p.left;
    else if (cmp > 0)
        p = p.right;
    else
        return p;

    if (visited.containsKey(p)) {
        throw new ConcurrentModificationException("TreeMap corrupted. Loop detected");
    }
}

• O código completo da modificação está em ProtectedTreeMap.java

Criando várias camadas de defesa

• Erros acontecem, então uma única camada de proteção não basta

• Neste caso, vários erros se acumularam, mas ainda havia monitoramento suficiente para que o problema fosse descoberto

• Alerta de NPE

  • Não existia alerta específico para a ocorrência de NPE
  • Havia apenas alerta de taxa de erro, e esse NPE acontecia apenas uma vez por worker thread do handler da API, então não ultrapassava o limiar da taxa de erro
  • Como o executor tratava isso internamente, também não havia logs de NPE

• Alerta de anomalia no uso de CPU

  • O uso de CPU era monitorado com alerta simples baseado em limiar
  • Quando o uso de CPU ultrapassou esse limiar, concluiu-se que havia comportamento anormal e o alerta disparou; foi por esse caminho que o problema foi encontrado

• Tratamento de exceções no executor

  • Se você envia tarefas para um executor, precisa configurar um uncaught exception handler obrigatoriamente

  thread.setUncaughtExceptionHandler(
      (dyingThread, throwable) -> {
          logger.error("uncaught exception!", throwable);
      }
  );
  

  • Em vez de uma ThreadFactory própria, é possível usar Apache Commons BasicThreadFactory ou Guava ThreadFactoryBuilder
  • Sem esse handler, a exceção é engolida e até o monitoramento de logs pode deixar de detectar o problema

• Code review e análise estática

  • Em code review, alguém poderia ter percebido a combinação de threads com TreeMap, ou sugerido não usar TreeMap quando ordenação não era necessária, mas isso não aconteceu neste caso
  • Ferramentas de análise estática como SpotBugs, JLint e Chord podem encontrar esse tipo de problema de concorrência ainda no build
  • Como referência sobre análise estática, foi citado How Good is Static Analysis at Finding Concurrency Bugs?

• Testes

  • Não havia testes multithread para esse caminho de código
  • Se o código permite acesso concorrente, os testes também precisam cobrir cenários multithread

Conclusão

• Modificações concorrentes sem proteção podem se manifestar não apenas como corrupção de dados, mas também como loop infinito e alto uso de CPU
• Ao permitir que várias threads modifiquem simultaneamente uma estrutura com ponteiros internos, como TreeMap, a estrutura da red-black tree pode acabar formando um cycle
• Escolher estruturas sincronizadas, tratar exceções corretamente, manter alertas, usar análise estática e fazer testes multithread ajuda a prevenir ou detectar esse tipo de problema mais cedo

[GN⁺]

Opiniões no Hacker News

• É bem sabido que as coleções principais do Java não são thread-safe por design, então isso deveria ter sido detectado
  O OP deveria também revisar o restante do código para verificar se há outros pontos em que várias threads possam manipular coleções simultaneamente
  Envolver com Collections.synchronizedMap ou trocar por ConcurrentHashMap torna operações individuais no mapa thread-safe, mas é outra questão se uma sequência de operações também fica segura
  Também é suspeito se o próprio objeto que possui o TreeMap é thread-safe, e modificações como rastrear nós visitados só fazem a coleção continuar insegura e falhar de formas mais sutis
  O ponto central não é um efeito colateral do TreeMap, mas sim a violação do contrato da coleção; mesmo trocando por HashMap, o código ainda estaria errado
  Em código manipulado por várias threads, o mais confiável tem sido tornar imutáveis todos os objetos possíveis e restringir os objetos que não podem ser imutáveis a áreas pequenas, independentes e fortemente controladas

  • Esta parte é realmente importante: mesmo que exista um array dinâmico thread-safe, a combinação de duas operações — verificar o tamanho com size() e depois acessar element(10) — não é atômica
    Se outra thread remover um elemento entre as duas chamadas, pode ocorrer um acesso fora dos limites
    A solução é usar um método atômico que faça as duas coisas juntas, como element_or_null(), ou então usar um array comum e proteger toda a sequência das duas operações com um mutex
  • A disputa de dados surge em estado mutável compartilhado não sincronizado
    Como as três condições são necessárias, há também três soluções: adicionar sincronização, como locks; não compartilhar o acesso mutável, como em um modelo de proprietário único usando canais; ou tornar os dados imutáveis, como sugere a intuição vinda de linguagens puramente funcionais
    Pelo que sei, o Google também investiu bastante nesse modelo no Guava
    Rust permite escolher qual dessas três coisas abrir mão e impede estaticamente que as três condições sejam verdadeiras ao mesmo tempo
  • Meu primeiro pensamento também foi “espera, essa estrutura de dados é thread-safe?”, e no fim parece ser uma escolha de estrutura de dados inadequada para o objetivo
    Tentar encaixar isso à força com um mutex normalmente cria outros problemas e gargalos
    Para usar objetos imutáveis, é preciso usar estruturas de dados imutáveis que aproveitem compartilhamento estrutural, para evitar ou reduzir uma explosão no uso de memória
    Usar estruturas de dados puramente funcionais elimina um lado do problema, mas, se as threads dependerem de versões intermediárias criadas umas pelas outras, surge outro problema complicado e talvez seja necessária outra estrutura de dados
    Se a ideia for manter à força a estrutura de dados mutável já em uso, dá para serializar as tentativas de acesso antes que cheguem à estrutura e agrupar os acessos em transações, permitindo executar apenas transações completas; nesse ponto, acaba parecendo quase implementar um banco de dados
  • Acho que o próprio modelo de threading que tenta fazer execução independente em um ambiente de memória compartilhada é fundamentalmente errado
    Na minha opinião, o esforço para fazer isso funcionar deveria ter sido investido em um modelo de processos melhor

• O exemplo simplificado do código no texto original não é exato
  O código original só executa treeMap.put quando unrelatedObjects não está vazio, e essa diferença pode ou não ser o bug
  Também é preciso verificar se a e b retornam sempre os mesmos valores e se treeMap realmente se comporta apenas como um mapa
  Por exemplo, se for um mapa que registra atualizações em log, é preciso avaliar se faz sentido alterá-lo para registrar o log apenas uma vez

  • Correto. Deve ser alterado para um if que verifica se não está vazio

• Também pode surgir um loop infinito se a implementação de Comparator ou Comparable não fornecer uma ordem total consistente: https://stackoverflow.com/questions/62994606/concurrentskips...
  Isso não tem relação com concorrência
  A ocorrência pode depender dos dados concretos processados e da ordem de processamento, então pode parecer normal por muito tempo e depois explodir em produção

  • Fico curioso se alguém já viu isso na prática. Daria um bom post de blog
    Pessoalmente, ainda não encontrei um comparador bugado que não tenha uma ordem total

• Eu achava que condições de corrida só causavam corrupção de dados ou deadlocks, nunca tinha pensado que poderiam causar problemas de desempenho
  Mas, se elas podem corromper dados a ponto de criar um loop infinito, faz sentido
  Por isso, muitas vezes penso que erros, comportamentos anômalos e avisos em um projeto deveriam, por princípio, ser corrigidos. Porque podem causar problemas aparentemente não relacionados
  Só que raramente esse princípio é aceito por quem decide o que fazer

  • É uma boa regra prática, mas é preciso pragmatismo
    Em alguns projetos, o custo de eliminar todos os erros, comportamentos anômalos e avisos pode ser muito maior do que aceitar problemas ocasionais aparentemente não relacionados
    Como é quase impossível prever a probabilidade de um erro específico contribuir para um problema futuro, ou se corrigi-lo antecipadamente sairá mais barato, isso acaba sendo mais uma arte do que ciência
    “Não corrigir nada” é terrível, e “corrigir tudo” geralmente é inviável; então é preciso um modelo de decisão, intuição vinda da experiência e a confiança das partes interessadas
  • No trabalho, tratamos todos os avisos como erros, e não é possível fazer merge de um pull request se todos os pipelines de CI executados automaticamente não passarem
    Exige disciplina, mas, depois que se chega a esse estado, é muito mais fácil manter
  • Também é importante não capturar exceções e ignorá-las
    A menos que você saiba especificamente que é seguro continuar a execução do programa, “capturar e só registrar no log” também é uma má ideia
    É melhor simplesmente propagar a exceção até algum ponto em que seja possível tratá-la de forma útil, como retornar 500 ou exibir uma caixa de diálogo de erro
  • No fim, é preciso escolher suas batalhas
    Em um projeto Rails que eu mantinha, havia um problema em que os logs ficavam cheios de “unsupported parameters”; eu revisava cuidadosamente os controllers e permitia os parâmetros, mas a mensagem continuava aparecendo
    Provavelmente era inofensivo, mas gerava muito ruído nos logs
    Várias pessoas tentaram resolver, mas sempre havia prioridades mais altas, e era difícil justificar gastar muito tempo em algo sem impacto funcional
    É um problema incômodo como hemorroidas. A escolha é fazer uma cirurgia e passar semanas sofrendo bastante, ou simplesmente conviver com aquilo; em geral é benigno, mas também pode piorar e virar um grande problema
    Acho que dá para chamar esse fenômeno de hemorroidas digitais
  • Mesmo sem corrupção, condições de corrida podem fazer o mesmo trabalho ser executado várias vezes e deixar apenas um resultado, causando grandes problemas de desempenho
    Se você concluiu que um aviso é irrelevante, é melhor pelo menos explicar isso em um comentário e, se possível, usar um pragma que desative o aviso no escopo mais estreito possível
    Prefiro eliminar comportamentos anômalos. Já vi código marcado com “não sei por que funciona, mas funciona” parar de funcionar depois; se tivesse sido limpo antes, haveria tempo para consertar com cuidado, mas acabou precisando ser reescrito às pressas

• A parte de “mal consegui conectar por ssh” me lembrou uma situação da época da pós-graduação
  Nosso laboratório era um pequeno grupo de umas 8 pessoas trabalhando com processamento paralelo e distribuído, e compartilhávamos uma máquina que acho que era uma Sun UltraSparc 170, com HD de 1 GB e 128 ou 256 MB de RAM
  Também é preciso considerar que máquinas Sun quase nunca eram reiniciadas
  Um aluno novo aparentemente pegou um arquivo de texto grande, dividiu por número de linhas em 32 ou 64 faixas e, sem criar arquivos separados, executou N cópias de perl em paralelo para que cada uma processasse sua própria faixa de linhas
  Para os padrões da época, N interpretadores perl consumiam muita RAM; quando começava a usar swap, o sistema ficava buscando freneticamente diferentes trechos do mesmo arquivo enquanto cada processo tentava ler mais algumas linhas
  Além disso, é muito provável que o processo J precisasse ler J/N do arquivo só para chegar à sua própria faixa
  No console, nem dava para obter um prompt de login, mas felizmente havia uma sessão já logada, e o su exibiu o prompt de senha depois de 20 a 30 minutos
  Depois de mais 5 a 10 minutos, consegui uma sessão root, identifiquei a causa com top, tentei contatar o usuário e matei os processos problemáticos, fazendo o sistema voltar ao normal
  A ideia em si estava certa, mas era um caso de total falta de compreensão dos limites do sistema; por causa do HD e da pouca RAM, o gargalo de I/O era tão severo que teria sido muito melhor simplesmente processar de forma linear

• Seja em Java ou em outra linguagem, executar operações concorrentes em objetos que não são thread-safe produz alguns dos bugs mais interessantes do mundo

  • Por isso, ao usar objetos não thread-safe em várias threads, é preciso gerenciar manualmente o acesso atômico ou usar uma versão thread-safe
    Erros de multithreading são os piores de depurar
    Neste caso, teria sido muito fácil identificar isso na fase de projeto, e a luz de alerta deveria ter acendido no momento em que se tentou usar um container comum em um ambiente multithread
  • Já lidei com bastantes bugs de concorrência, mas nunca reproduzi intencionalmente a inconsistência que surge ao remover o modificador volatile de um campo mutável em Java
    Talvez a JVM que eu usava na época fosse bem demais
  • Mesmo quando eu tinha certeza de que podia aceitar as consequências de compartilhar algo sem sincronização, o resultado real era sempre inesperado
  • É uma ideia um pouco radical, mas por esse motivo prefiro depurar corridas em C/C++
    A linguagem até define semânticas absurdas, praticamente sem sentido, quando ocorre uma corrida, mas na prática muitas vezes aparecem corrupção de memória ou problemas barulhentos
    Como a maioria das corridas é ilegal, dá para criar ferramentas como verificadores de threads sem precisar alterar o código-fonte para indicar a semântica
    Já em Java não há comportamento indefinido, mas é fácil dois campos ficarem sutilmente desalinhados, e isso é muito mais difícil de rastrear
  • Algumas, talvez a maioria, das operações em Java Collections fazem verificações de integridade para alertar sobre esse tipo de problema
    Por exemplo, um map lança ConcurrentModificationException

• Já vi o mesmo fenômeno em C# em produção
  Os sintomas eram os mesmos e, ao olhar o dump do processo, havia um dicionário corrompido
  Eu achava que tudo usava ConcurrentDictionary, mas o problema era um que vinha de uma biblioteca
  Na época era .NET Framework, e, se me lembro bem, o .NET Core tem código para detectar modificações concorrentes
  Não sei como é a implementação, mas só um contador de versão já tornaria isso possível
  É estranho a obsessão com NPE como se fosse o ingrediente essencial. Na forma como o problema originalmente ocorria, isso não parecia existir, e o simples fato de não haver exceções não é motivo para dizer que esse tipo de bug não existe em C
  O ponto central é o invariante da classe. Em geral, enquanto um mutador está em execução, o invariante não é válido e só é restaurado no final
  Se outro mutador for executado antes que o invariante seja restaurado, a estrutura de dados será corrompida. Se ela não começa em um estado válido, é improvável que termine em um estado válido

  • No fim, foi por causa de uma lógica incorreta
    Tive o azar de não conseguir reproduzir com uma NPE não capturada, então concluí erroneamente que uma NPE não capturada era uma condição necessária

• Já vi a mesma coisa acontecer em java.util.HashMap com sincronização insuficiente
  Foi por volta de 2009, mas, até onde sei, ainda é possível hoje
  Pelo que me lembro, HashMap usa encadeamento para resolver colisões, e provavelmente acabou surgindo um ciclo dentro da cadeia
  Mas, em vez de me aprofundar para verificar, foquei em remover o código problemático por completo
  Conhecimento sobre concorrência costuma ser perguntado em entrevistas, e é difícil causar uma boa impressão se você trata corridas de dados como um problema menor; este caso mostra o motivo

  • Eu não sabia que isso podia acontecer também em HashMap
    Tem a ver com a lista ligada usada no tratamento de colisões?

• Acho que uma opção seria manter um contador incremental para detectar ciclos e lançar uma exceção se ele ficar maior que a profundidade da árvore ou o tamanho da coleção
  Diferentemente da abordagem com conjunto hash sugerida pelo autor, isso quase não teria overhead de memória ou CPU e parece ter mais chance de ser aceito
  Dito isso, em mais de 10 anos usando C#, nunca deixei de considerar o acesso concorrente a estruturas de dados em situações concorrentes

  • Não é uma má ideia, mas geralmente é bem difícil adicionar uma pré-condição útil numa situação em que há corrida de dados
    Há muitas outras formas de uma árvore se corromper além desta
  • Boa ideia. Já fiz isso antes com busca binária e estruturas de árvore
    Evite loops infinitos quando possível, e os casos em que não dá para evitar são bem raros
    Não é uma correção, mas é uma boa estratégia de mitigação
    Loops infinitos são um dos bugs mais terríveis. No depurador são fáceis de achar, mas o resultado pode ser muito hostil, como na situação do OP em que “até o ssh mal funcionava”
    Loops infinitos em código de biblioteca são especialmente desagradáveis
  • Isso é muito melhor. Basta usar memória constante
    Há a garantia de que o número de nós é menor ou igual à altura da árvore

• Exceções dentro de threads são realmente devastadoras
  Há uma história horrível de depuração de bug envolvendo C++, select() e uma thread que ficava disparando exceções: https://news.ycombinator.com/item?id=42532979

  • Lembro de ter lido aquele post, mas não entendi por falta de conhecimento na área
    Vou ter que reler