Uso de CPU del 3,200%

• En una aplicación Java 17, los 32 núcleos quedaron completamente saturados y el uso de CPU se disparó hasta 3,200%; al ordenar el thread dump por tiempo de CPU se confirmó que varios hilos estaban atorados en TreeMap.put()
• El código en bucle que primero se sospechó era ineficiente, pero su complejidad O(N lg(M)) y la verificación del tamaño de entrada no alcanzaban para explicar tiempos de ejecución al nivel de una caída del servicio
• La causa real fue que varios hilos modificaban un TreeMap compartido sin protección, lo que creó un ciclo dentro del árbol red-black y llevó a búsquedas e inserciones a un bucle infinito
• El mismo fenómeno apareció en código de reproducción simple, con ExecutorService y también en un servicio gRPC; además, el pool de hilos no mostraba el NPE en la salida estándar, lo que dificultó todavía más encontrar la causa
• La corrección no termina solo con cambiar a Collections.synchronizedMap o ConcurrentHashMap; también hay que agregar manejo de excepciones del executor, alertas por CPU y NPE, análisis estático y pruebas multihilo

---

Síntomas de la falla y primera pista

• La máquina quedó tan dañada que casi ni siquiera se podía entrar por ssh, y el uso de CPU llegó hasta 3,200%
  • Los 32 núcleos del host estaban todos en uso
  • Era una situación muy distinta de un bug anterior en el que solo 1 núcleo estaba al 100%
• El thread dump del runtime Java 17 incluía tiempo de CPU, y al ordenar por ese criterio aparecieron varios hilos similares
  • El stack apuntaba a java.util.TreeMap.put()
  • La ubicación en el código de la aplicación era BusinessLogic.someFunction(BusinessLogic.java:29)

El código que primero se sospechó y las hipótesis descartadas

• El código del punto problemático recorría unrelatedObjects, pero dentro del cuerpo del bucle solo usaba relatedObject

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

• Ese código podía reducirse a un solo put, así:

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

• unrelatedObjects sí se usaba después en la función, así que no se podía eliminar el parámetro por completo
• Era posible que durante un refactor hubiera desaparecido el uso de unrelatedObject
• Incluso aumentando treeMap y unrelatedObjects a 1,000,000 de entradas cada uno en una prueba unitaria, no se logró reproducir el problema
  • Si el tamaño de unrelatedObjects es N y el de treeMap es M, la complejidad es O(N lg(M))
  • Se estimó que para ver tiempos de ejecución del orden de 1 minuto harían falta entre 100 millones y 1,000 millones de entradas
  • Tampoco cuadraba con la suposición de que, en la aplicación real, ambas estructuras no superaban las 1,000 entradas

El bucle infinito causado por un TreeMap sin protección

• La definición del campo TreeMap era la siguiente

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

• Varios hilos accedían a ese TreeMap sin sincronización ni mecanismo de protección
• TreeMap en Java está implementado como un árbol red-black, y si las modificaciones concurrentes rompen los enlaces internos de sus nodos, puede aparecer un ciclo
• Al buscar o insertar un valor que todavía no existe, el código sigue ese ciclo y cae en un bucle infinito

Experimento simple de reproducción

• Se escribió un experimento donde varios hilos actualizaban aleatoriamente un TreeMap compartido

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.
            }
        }
    }));
}

• El proyecto completo está en SimpleRepro.java
• Al principio parecía que el try/catch era la clave
  • Sin try/catch, algunos hilos morían por NullPointerException y el programa se detenía
  • Después de agregar try/catch, al ejecutarlo unas cuantas veces se observó 500% de uso de CPU
• Una race condition no solo puede causar corrupción de datos o deadlock; también puede romper una estructura de datos de forma que permita un bucle infinito y derive en un problema de rendimiento

Confirmación del ciclo dentro de TreeMap

• Se escribió un experimento que, vía reflection, accedía a los campos root, left, right, key y color de TreeMap para imprimir nodos y colores
• Si durante el recorrido se volvía a encontrar un TreeMap.Entry ya visitado, se consideraba que había un ciclo

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 las restricciones de acceso a módulos de Java, al ejecutar fue necesario este argumento de JVM

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

Casos previos relacionados y qué distingue a este

• Este mismo tipo de problema ya se había documentado antes
  • writing to a java treemap concurrently can lead to an infinite loop during reads
  • High CPU due to multiple Java threads accessing TreeMap simultaneously de Red Hat
  • Java Process consumes more than 100% CPU
• Este caso además revisa un código de reproducción real, intentos de reproducción en varios lenguajes y hasta ideas para modificar TreeMap y el árbol red-black

Reproducción más realista con ExecutorService

• Ignorar un NPE en código simple puede parecer poco realista, pero en ExecutorService las excepciones pueden pasar desapercibidas con facilidad

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));
    });
}

• El código completo está en ExecutorUncaughtRepro.java
• Al ejecutarlo, el programa se queda colgado y el thread dump muestra hilos atorados en TreeMap.put()
• En la salida estándar no aparecía nada
  • El pool de hilos se tragaba el NPE y la señal del problema no se veía
  • En la situación real ocurrió exactamente lo mismo
• Si administras directamente un thread pool, hacen falta estas medidas
  • Registrar un uncaught exception handler mediante un thread factory
  • Procesar el Future devuelto y revisar con future.get() el NPE envuelto en ExecutionException

El mismo problema también en un servicio gRPC

• En un servicio basado en thread pool, como uno de gRPC, un TreeMap sin protección puede causar el mismo 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();
}

• El código completo está en GrpcRepro.java
• La definición protobuf está en ReceiptProcessorService.proto
• El thread dump muestra hilos grpc-default-executor-* detenidos en estado runnable dentro de TreeMap.put()

Hipótesis sobre la causa y experimentos en otros lenguajes

• Como posible causa, se sospechó que dos hilos rotaban el árbol en direcciones opuestas de forma independiente, o que escrituras intercaladas durante rotaciones superpuestas producían un ciclo
• Sin embargo, no hay una demostración de qué interleaving exacto de hilos genera ese ciclo
• Al principio se sospechó que el NPE era necesario, pero experimentos posteriores derribaron esa suposición
• Se intentó reproducir el mismo problema en varios lenguajes
  • Java sí lo reproduce, ya que es la base de todo el caso
  • std::map de C++ también usa un árbol red-black y, en raras ocasiones, en vez de segfault deja hilos colgados con alto uso de CPU
  • Go también logró reproducirlo contra lo esperado, y el código está en experimento en Go
  • Ruby no lo reprodujo, a pesar de poder capturar NPE, y es posible que el GIL haya impedido el interleaving que causa el problema
• El experimento en C++ mostró, contra lo esperado, que el bucle infinito podía reproducirse sin try/catch ni excepción por puntero nulo
  • A veces terminaba con segmentation fault
  • Muy rara vez quedaba detenido por más de 10 minutos y top mostraba a SimpleRepro usando 170.8% de CPU
  • Como en C++ una desreferencia de puntero nulo causa segfault, tiene que existir un interleaving que no pasa por null
• Después de ver ese resultado, el experimento en Java se volvió a ejecutar 12 veces sin capturar NPE, y aun así se reprodujo el bucle infinito en TreeMap.put()

Corrección fácil y defensas a nivel de estructura de datos

• La corrección más sencilla es proteger el TreeMap compartido
  • Envolverlo con Collections.synchronizedMap
  • Cambiar a ConcurrentHashMap y ordenar solo cuando realmente haga falta
• Una defensa más discutible es rastrear los nodos visitados durante el recorrido del árbol red-black
  • Si se vuelve a encontrar un nodo ya visitado, se lanza ConcurrentModificationException
  • Eso no evita la corrupción de datos en sí
  • Pero sí puede evitar que un bucle infinito dispare el CPU al 100%
  • La memoria extra queda limitada a la altura del árbol, o sea O(lg(n))
  • La altura de un árbol red-black está garantizada en O(lg(n))
  • Se considera poco probable que la librería estándar adopte este enfoque
• El ejemplo de corrección registra nodos visitados con IdentityHashMap en getEntry y 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");
    }
}

• El código completo de la corrección está en ProtectedTreeMap.java

Varias capas de defensa

• Los errores ocurren, así que una sola capa de defensa no basta

• En este caso se encadenaron varios errores, pero todavía quedaban algunos mecanismos de observación que permitieron detectar el problema

• Alertas de NPE

  • No existía una alerta específica por ocurrencia de NPE
  • Solo había alerta por tasa de errores, y este NPE ocurría solo una vez por hilo worker del API handler, así que no alcanzaba el umbral
  • Además, por cómo el executor procesaba las tareas, tampoco quedaba log del NPE

• Alertas por anomalías de uso de CPU

  • Sí se monitoreaba el uso de CPU con alertas simples basadas en umbral
  • Cuando el uso de CPU superó el umbral, se interpretó como comportamiento anormal y se disparó la alerta; por esa vía se descubrió el problema

• Manejo de excepciones del executor

  • Si se envían tareas a un executor, hay que configurar sí o sí un uncaught exception handler

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

  • En lugar de una ThreadFactory hecha a mano, se puede usar Apache Commons BasicThreadFactory o Guava ThreadFactoryBuilder
  • Sin ese handler, la excepción se traga y el monitoreo de logs tampoco detecta el problema

• Revisión de código y análisis estático

  • En una revisión de código se pudo haber detectado la combinación de hilos con TreeMap, o sugerido no usar TreeMap si no hacía falta ordenamiento, pero aquí no pasó
  • Herramientas de análisis estático como SpotBugs, JLint y Chord pueden encontrar este tipo de problemas de concurrencia en tiempo de build
  • Como referencia sobre análisis estático se cita How Good is Static Analysis at Finding Concurrency Bugs?

• Pruebas

  • No había pruebas multihilo para esa ruta de código
  • Si un código puede recibir acceso concurrente, sus pruebas también deberían cubrir escenarios multihilo

Conclusión

• Las modificaciones concurrentes sin protección pueden manifestarse no solo como corrupción de datos, sino también como bucles infinitos y alto uso de CPU
• Si varias hebras modifican al mismo tiempo una estructura de datos con punteros internos como TreeMap, la estructura del árbol red-black puede formar un ciclo
• Elegir estructuras sincronizadas, manejar excepciones, configurar alertas, usar análisis estático y agregar pruebas multihilo ayuda a detectar o prevenir antes este tipo de problemas

[GN⁺]

Comentarios de Hacker News

• Es bien sabido que las colecciones principales de Java no son thread-safe por diseño, así que esto debió haberse detectado.
  El OP debería revisar también el resto del código para ver si hay más lugares donde varios hilos puedan estar manipulando colecciones al mismo tiempo.
  Envolverlo con Collections.synchronizedMap o cambiarlo por ConcurrentHashMap hace que las operaciones individuales del mapa sean thread-safe, pero eso es distinto de que también sea segura una secuencia de operaciones.
  También se puede dudar de si el propio objeto que posee el TreeMap es thread-safe, y modificaciones como llevar seguimiento de nodos visitados solo hacen que la colección siga siendo insegura y falle de formas más sutiles.
  El punto clave no es el efecto secundario de TreeMap, sino haber violado el contrato de la colección; incluso si se cambiara por HashMap, seguiría siendo código incorrecto.
  En código manejado por varios hilos, lo más confiable siempre ha sido hacer inmutables todos los objetos posibles, y limitar los que no puedan ser inmutables a zonas pequeñas, aisladas y fuertemente controladas.

  • Esta parte es realmente importante: aunque tengas un arreglo dinámico thread-safe, la combinación de revisar la longitud con size() y luego acceder a element(10) no es atómica.
    Si otro hilo elimina un elemento entre esas dos llamadas, puede ocurrir un acceso fuera de rango.
    La solución es usar un método atómico que haga ambas cosas juntas, por ejemplo element_or_null(), o simplemente usar un arreglo normal y proteger toda la secuencia de ambas operaciones con un mutex.
  • La condición de carrera aparece por estado mutable compartido sin sincronización.
    Como las tres condiciones son necesarias, también hay tres soluciones: agregar sincronización con locks o similares, no compartir el acceso mutable como en un modelo de propietario único con canales, o hacer inmutables los datos, como sugiere la intuición proveniente de los lenguajes puramente funcionales.
    Según entiendo, Google también invirtió bastante en este modelo en Guava.
    Rust te obliga a elegir cuál de esas tres cosas vas a ceder, e impide estáticamente que las tres condiciones se cumplan al mismo tiempo.
  • Mi primera reacción también fue: “a ver, ¿esa estructura de datos es thread-safe?”, y al final parece simplemente una mala elección de estructura de datos para ese propósito.
    Si la fuerzas a encajar con un mutex, normalmente aparecen otros problemas y cuellos de botella.
    Si quieres usar objetos inmutables, necesitas estructuras de datos inmutables con compartición estructural para evitar o reducir una explosión en el uso de memoria.
    Las estructuras de datos puramente funcionales hacen desaparecer una parte del problema, pero si los hilos dependen de versiones intermedias creadas entre sí, entonces puede surgir otro dolor de cabeza y quizá haga falta otra estructura de datos.
    Si quieres salvar a la fuerza la estructura de datos mutable que ya usas, puedes serializar los intentos de acceso antes de que lleguen a la estructura y agruparlos como transacciones para que solo se ejecuten transacciones completas, pero para ese punto ya se siente casi como implementar una base de datos.
  • Creo que el propio modelo de threading de intentar ejecutar cosas de forma independiente en un entorno de memoria compartida está fundamentalmente mal.
    Pienso que el esfuerzo para hacer funcionar eso debería haberse invertido en un mejor modelo de procesos.

• El ejemplo simplificado de código en el texto original no es exacto.
  En el código original, treeMap.put solo se ejecuta cuando unrelatedObjects no está vacío, y esa diferencia puede o no ser la causa del bug.
  También hay que verificar si a y b devuelven siempre el mismo valor, y si treeMap realmente se comporta solo como un mapa.
  Por ejemplo, si fuera un mapa que registra las actualizaciones en un log, habría que pensar si está bien cambiarlo para que solo registre una vez.

  • Sí, es una observación correcta. Hay que cambiarlo a un if que revise si no está vacío.

• Una implementación de Comparator o Comparable que no proporcione un orden total consistente también puede causar un bucle infinito: https://stackoverflow.com/questions/62994606/concurrentskips...
  Esto no tiene relación con la concurrencia.
  Que ocurra o no puede depender de los datos concretos que se procesen y del orden de procesamiento, así que puede parecer normal durante mucho tiempo y luego explotar en producción.

  • Me pregunto si alguien lo ha visto de primera mano en la práctica. Parece buen material para un post de blog.
    Personalmente todavía no me he topado con un comparador con bug que no tenga orden total consistente.

• Pensaba que las condiciones de carrera solo podían causar corrupción de datos o interbloqueos; no se me había ocurrido que también podían causar problemas de rendimiento
  Pero tiene sentido si la corrupción de datos puede crear un bucle infinito
  Por eso suelo pensar que, en principio, hay que corregir los errores, comportamientos extraños y advertencias de un proyecto, porque pueden provocar problemas aparentemente no relacionados
  Aun así, rara vez quienes deciden qué hacer aceptan ese principio

  • Es una buena regla práctica, pero hace falta sentido práctico
    En algunos proyectos, el costo de eliminar todos los errores, comportamientos extraños y advertencias puede ser mucho mayor que el costo de tolerar problemas ocasionales que parecen no relacionados
    Es casi imposible predecir si cierto error participará en un problema futuro y si será más barato corregirlo por adelantado, así que al final esto se parece más a un arte que a una ciencia
    “No arreglar nada” es terrible y “arreglarlo todo” suele ser poco realista, así que hace falta un marco de decisión o intuición basada en la experiencia, además de la confianza de las partes interesadas
  • En el trabajo tratamos todas las advertencias como errores, y no se puede fusionar un pull request si no pasan todos los pipelines de CI que se ejecutan automáticamente
    Hace falta disciplina, pero una vez que llegas a ese estado es mucho más fácil mantenerlo
  • También es importante no capturar excepciones para ignorarlas
    A menos que sepas específicamente que es seguro seguir ejecutando el programa, incluso “capturar y solo dejar un log” es una mala idea
    Es mejor dejar que la excepción se propague hasta un lugar donde se pueda manejar de forma útil, como devolver un 500 o mostrar un cuadro de diálogo de error
  • Al final hay que elegir bien las batallas
    En un proyecto Rails que mantengo había un problema donde los logs estaban llenos de “unsupported parameters”, y seguía apareciendo aunque revisáramos con cuidado los controladores y los permitiéramos
    Probablemente era inofensivo, pero generaba mucho ruido en los logs
    Varias personas intentaron resolverlo, pero siempre había prioridades más altas y era difícil justificar dedicar tanto tiempo a algo que no afectaba la funcionalidad
    Es una molestia como las hemorroides: o te operas y sufres bastante durante unas semanas, o simplemente aguantas; por lo general es benigno, pero también puede empeorar y volverse un gran problema
    A esto podríamos llamarle hemorroides digitales
  • Incluso sin corrupción, una condición de carrera puede hacer que el mismo trabajo se ejecute varias veces y solo quede un resultado, provocando un gran problema de rendimiento
    Si decidiste que una advertencia no es relevante, al menos conviene explicarlo en un comentario y, si es posible, usar un pragma para desactivarla en el alcance más pequeño posible
    Prefiero eliminar los comportamientos extraños. He tenido código marcado como “no sé por qué funciona, pero funciona” que después dejó de funcionar, y si lo hubiéramos limpiado antes habríamos tenido tiempo de corregirlo con calma, en vez de tener que reescribirlo a las apuradas

• La parte de “apenas pude conectarme por ssh” me recordó una situación de mi época de posgrado
  En nuestro laboratorio, un pequeño grupo de unas 8 personas dedicado al procesamiento paralelo y distribuido compartía una máquina que creo que era una Sun UltraSparc 170, con un disco duro de 1 GB y 128 o 256 MB de RAM
  También hay que considerar que las máquinas Sun casi nunca se reiniciaban
  Parece que un estudiante nuevo dividió un archivo de texto grande en 32 o 64 segmentos por número de línea y, en vez de crear archivos separados, ejecutó en paralelo N copias de perl para que cada una procesara su propio rango de líneas
  Para esa época, las N instancias del intérprete perl consumían mucha RAM, y cuando empezó a haber swap, iban haciendo seeks frenéticos a distintas partes del mismo archivo mientras cada proceso intentaba leer unas cuantas líneas más
  Además, es muy probable que el proceso J tuviera que leer J/N del archivo para llegar a su segmento
  Desde la consola ni siquiera se podía obtener el prompt de login, pero por suerte ya había una sesión iniciada, y su mostró el prompt de contraseña después de 20 o 30 minutos
  Tras otros 5 o 10 minutos obtuve la sesión root, confirmé la causa con top, intenté contactar al usuario y maté los procesos problemáticos; entonces el sistema volvió a la normalidad
  La idea en sí no era mala, pero era un caso de no entender en absoluto los límites del sistema, y con un disco duro y tan poca RAM el cuello de botella de I/O era tan severo que probablemente habría sido mucho mejor procesarlo de forma lineal

• Ya sea en Java o en cualquier otro lenguaje, hacer operaciones concurrentes sobre un objeto no seguro para hilos produce algunos de los bugs más interesantes del mundo

  • Por eso, si vas a usar un objeto no seguro para hilos desde varios hilos, tienes que gestionar tú mismo el acceso atómico o usar una versión segura para hilos
    Los errores de multihilo son lo peor de depurar
    En este caso era muy fácil identificarlo desde el diseño, y debieron encenderse todas las alarmas en cuanto se intentó usar un contenedor normal en un entorno multihilo
  • He sufrido bastantes bugs de concurrencia, pero nunca he reproducido de forma intencional la inconsistencia que aparece al quitar el modificador volatile de un campo mutable en Java
    Tal vez la JVM que usé en ese momento estaba demasiado bien hecha
  • Incluso cuando estaba seguro de que podía tolerar las consecuencias de compartir algo no sincronizado, los resultados reales siempre fueron distintos de lo esperado
  • Puede sonar algo extremo, pero por eso prefiero más depurar condiciones de carrera en C/C++
    El lenguaje define una semántica tan loca y prácticamente carente de sentido cuando hay una carrera, pero en la práctica suelen hacerse visibles corrupción de memoria o problemas ruidosos
    Como la mayoría de las carreras son ilegales, se pueden crear herramientas como verificadores de hilos sin tener que cambiar el código fuente para expresar la intención
    En cambio, Java no tiene comportamiento indefinido, pero es fácil que dos campos queden sutilmente desalineados, y eso es mucho más difícil de rastrear
  • Parte de las operaciones de Java Collections, quizá la mayoría, hacen comprobaciones de integridad para advertir sobre estos problemas
    Por ejemplo, un mapa puede lanzar ConcurrentModificationException

• También he visto el mismo fenómeno en producción con C#
  Los síntomas eran iguales y, al revisar el volcado del proceso, había un diccionario corrupto
  Yo pensaba que todo usaba ConcurrentDictionary, pero el problema venía de uno que llegaba desde una librería
  En ese momento usábamos .NET Framework y, según recuerdo, .NET Core tiene código para detectar modificaciones concurrentes
  No conozco la implementación, pero con solo un contador de versión debería ser posible
  Es raro lo obsesionados que están con que el NPE sea el ingrediente clave. No parece formar parte del patrón original, y no hay motivo para pensar que en C este tipo de bug no existe solo porque no haya excepciones
  La clave está en el invariante de clase. En general, mientras se ejecuta un modificador el invariante no se cumple, y solo se restaura al final
  Si ejecutas otro modificador antes de que el invariante se restaure, la estructura de datos se corrompe. Si no empiezas desde un estado válido, es poco probable que termines en uno válido

  • Al final era por una lógica incorrecta
    Tuvimos la mala suerte de no poder reproducirlo con un NPE no capturado, así que concluimos erróneamente que un NPE no capturado era una condición necesaria

• También he visto algo parecido en un java.util.HashMap sin suficiente sincronización
  Fue por ahí de 2009, pero hasta donde sé todavía puede pasar
  Según recuerdo, HashMap usa encadenamiento para resolver colisiones, y creo que probablemente se formó un ciclo dentro de la cadena
  Pero en vez de meterme a fondo para verificarlo, me enfoqué en eliminar por completo el código problemático
  En entrevistas suelen preguntar mucho sobre concurrencia; si piensas que una condición de carrera es un problema menor, difícilmente darás una buena impresión, y este caso es la razón

  • No sabía que algo así también podía pasar en HashMap
    ¿Tiene que ver con la lista enlazada que se usa para manejar colisiones?

• Me pregunto si una forma sería poner un contador incremental para detectar ciclos y lanzar una excepción si supera la profundidad del árbol o el tamaño de la colección
  A diferencia del enfoque con conjunto hash que propuso el autor, casi no tendría sobrecarga de memoria ni de CPU, y parece más probable que lo acepten
  Aun así, en más de 10 años usando C# nunca dejé de considerar el acceso concurrente a estructuras de datos en situaciones concurrentes

  • No es una mala idea, pero en general es bastante difícil agregar precondiciones útiles en una situación con condiciones de carrera
    Hay muchas otras formas en que un árbol puede corromperse
  • Buena idea. Antes lo hice en búsqueda binaria y estructuras de árbol
    Si se puede, evita los bucles infinitos, y los casos en que no se puede son bastante raros
    No es una corrección, pero sí una buena estrategia de mitigación
    Los bucles infinitos son uno de los bugs más infernales. En el depurador son fáciles de encontrar, pero como en la situación del OP, donde “apenas entraba por ssh”, el resultado puede ser muy poco amigable
    En particular, los bucles infinitos dentro de código de librería son todavía más desagradables
  • Eso es mucho mejor. Solo usa memoria constante
    Está garantizado que la cantidad de nodos no supera la altura del árbol

• Las excepciones dentro de un hilo son realmente letales
  Hay una terrible historia de rastreo de bugs con C++, select() y un hilo que iba lanzando excepciones como protagonista: https://news.ycombinator.com/item?id=42532979

  • Recuerdo haber leído ese texto, pero no lo entendí porque me faltan conocimientos de esa área
    Debería volver a leerlo