Errores de concurrencia en Lucene: Cómo corregir fallos de concurrencia optimistas

¿Quieres obtener la certificación de Elastic? ¡Descubre cuándo se realizará la próxima capacitación Elasticsearch Engineer! Puedes iniciar una prueba gratuita en el cloud o prueba Elastic en tu máquina local ahora mismo.

Sí, otro blog para corregir errores. Pero este tiene un giro: un héroe de código abierto aparece y salva el día.

Depurar bugs de concurrencia no es nada fácil, pero vamos a entrar en ello. Entra en escena Fray, un marco determinista de pruebas de concurrencia del laboratorio PASTA de CMU, que convierte fallos irregulares en fallos fiables y reproducibles. Gracias al ingenioso diseño de shadow lock de Fray y su control preciso del hilo, localizamos un bug complicado de Lucene y finalmente lo superamos. Esta entrada explora cómo los héroes y herramientas del código abierto están haciendo que la depuración concurrente sea menos dolorosa—y que el mundo del software sea mucho mejor.

Errores de concurrencia: la maldición de los ingenieros de software

Los errores de concurrencia son los peores. No solo son difíciles de arreglar, sino que simplemente conseguir que fallen de forma fiable es la parte más complicada. Tomemos este fallo de prueba, TestIDVersionPostingsFormat#testGlobalVersions, como ejemplo. Genera múltiples hilos de redacción y actualización de documentos, desafiando el modelo optimista de concurrencia de Lucene. Esta prueba expuso una condición de carrera en el control optimista de concurrencia. Es decir, una operación de documento puede afirmar erróneamente ser la última de una secuencia de operaciones 😱. Es decir, en ciertas condiciones, una operación de actualización o eliminación podría tener éxito cuando debería fallar dadas las limitaciones optimistas de concurrencia.

Disculpas a quienes odian los rastreos de Java Stack. Ten en cuenta que eliminar no significa necesariamente "eliminar". También puede indicar una "actualización" de documento, ya que los segmentos de Lucene son de solo lectura.

Apache Lucene gestiona cada hilo que consiste en escribir documentos a través de la clase DocumentsWriter . Esta clase creará o reutilizará hilos para la redacción de documentos y cada acción de escritura controla su información dentro de la clase DocumentsWriterPerThread (DWPT). Además, el autor lleva un registro de qué documentos se eliminan en el DocumentsWriterDeleteQueue (DWDQ). Estas estructuras mantienen todas las acciones de mutación de los documentos en memoria y periódicamente se vacian, liberando recursos en memoria y estructuras persistentes en disco.

Para evitar bloquear hilos y cerciorar un alto rendimiento en sistemas concurrentes, Apache Lucene intenta sincronizar solo en secciones muy críticas. Aunque esto puede ser bueno en la práctica, como en cualquier sistema concurrente, hay dragones.

Una falsa esperanza

Mi investigación inicial me llevó a un par de secciones críticas que no estaban sincronizadas adecuadamente. Todas las interacciones con un DocumentsWriterDeleteQueue dado están controladas por su DocumentsWriterque encierra . Así que, aunque los métodos individuales pueden no estar adecuadamente sincronizados en el DocumentsWriterDeleteQueue, su acceso al mundo lo es (o debería estar). (No profundicemos en cómo esto confunde la propiedad y el acceso: es un proyecto de larga duración escrito por muchos colaboradores. Ten un poco de margen.)

Sin embargo, encontré un sitio durante un flush que no estaba sincronizado.

Estas acciones no están sincronizadas en una sola operación atómica. Es decir, entre newQueue de creación y llamada a getMaxSeqNo, otro código podría haber ejecutado incrementando el número de secuencia en la clase documentsWriter . ¡Encontré el bicho!

Pero, como ocurre con la mayoría de los bugs complejos, encontrar la causa raíz no fue sencillo. Fue entonces cuando intervino un héroe.

Un héroe en la refriega

Entran en escena nuestro héroe: Ao Li y sus colegas del Laboratorio PATA. Le dejaré explicar cómo salvaron el día con Fray.

Fray es un marco determinista de pruebas de concurrencia desarrollado por investigadores del PASTA Lab, Universidad Carnegie Mellon. La motivación detrás de la construcción de Fray proviene de una brecha notable entre la academia y la industria: aunque las pruebas de concurrencia deterministas se estudiaron extensamente en la investigación académica durante más de 20 años, los profesionales siguen confiando en las pruebas de estrés —un método ampliamente reconocido como poco fiable e inestable— para poner a prueba sus programas concurrentes. Por ello, queríamos diseñar e implementar un marco determinista de pruebas de concurrencia con generalidad y aplicabilidad práctica como objetivo principal.

La idea central

En esencia, Fray aprovecha un principio sencillo pero poderoso: la ejecución secuencial. El modelo de concurrencia de Java proporciona una propiedadclave: si un programa está libre de carreras de datos, todas las ejecuciones aparecerán secuencialmente consistentes. Esto significa que el comportamiento del programa puede representar como una secuencia de sentencias del programa.

Fray funciona correr el programa destino de forma secuencial: en cada paso, pausa todos los hilos excepto uno, permitiendo a Fray controlar con precisión la planeación de hilos. Los hilos se seleccionan aleatoriamente para simular la concurrencia, pero las elecciones se registran para una posterior repetición determinista. Para optimizar la ejecución, Fray solo realiza cambios de contexto cuando un hilo está a punto de ejecutar una instrucción de sincronización, como el bloqueo o acceso atómico/volátil. Una buena característica de la libertad entre datos y razas es que este cambio limitado de contexto es suficiente para explorar todos los comportamientos observables debidos a cualquier entrelazado de hilos (nuestro artículo tiene un esbozo de demostración).

El reto: controlar la planeación de hilos

Aunque la idea central parece sencilla, implementar Fray presentó desafíos significativos. Para controlar la planeación de hilos, Fray debe gestionar la ejecución de cada hilo de aplicación. A primera vista, esto podría parecer sencillo: reemplazar primitivas de concurrencia por implementaciones personalizadas. Sin embargo, el control de concurrencia en la JVM es complejo, implicando una mezcla de instrucciones de bytecode, bibliotecas de alto nivel y métodos nativos.

Esto resultó ser un agujero de conejo:

• Por ejemplo, cada MONITORENTER instrucción debe tener un MONITOREXIT correspondiente en el mismo método. Si Fray reemplaza MONITORENTER por una llamada a método a un stub/mock, también debe reemplazar MONITOREXIT.
• En el código que emplea object.wait/notify, si MONITORENTER se reemplaza, también debe ser reemplazada la object.wait correspondiente. Esta cadena de reemplazo se extiende hasta object.notify y más allá.
• La JVM invoca ciertos métodos relacionados con la concurrencia (por ejemplo, object.notify cuando termina un hilo) dentro del código nativo. Reemplazar estas operaciones requeriría modificar la propia JVM.
• Las funciones de la JVM, como cargadores de clases e hilos de recogida de basura (GC), también emplean primitivas de concurrencia. Modificar estas primitivas puede crear desajustes con esas funciones de la JVM.
• Reemplazar primitivas de concurrencia en el JDK suele provocar fallos de la JVM durante su fase de inicialización.

Estos desafíos dejaron claro que una sustitución integral de los primitivos de concurrencia no era factible.

Nuestra solución: diseño de cerraduras de sombra

Para abordar estos desafíos, Fray emplea un novedoso mecanismo de bloqueo de sombra para orquestar la ejecución de hilos sin reemplazar primitivas de concurrencia. Los bloqueos sombra actúan como intermediarios que guían la ejecución del hilo. Por ejemplo, antes de adquirir un bloqueo, un hilo de aplicación debe interactuar con su correspondiente bloqueo de sombra. El bloqueo sombra determina si el hilo puede adquirir el bloqueo. Si el hilo no puede continuar, el bloqueo sombra lo bloquea y permite que otros hilos se ejecuten, evitando bloqueos y permitiendo una concurrencia controlada. Este diseño permite a Fray controlar el entrelazado de hilos de forma transparente mientras preserva la corrección de la semántica de concurrencia. Cada primitiva de concurrencia está cuidadosamente modelada dentro del marco de bloqueo de sombra para garantizar la solidez y la completitud. Más detalles técnicos pueden encontrar en nuestro artículo.

Además, este diseño pretende ser a prueba de futuro. Al requerir únicamente la instrumentación de bloqueos de sombra alrededor de primitivas de concurrencia, se garantiza compatibilidad con versiones más recientes de JVM. Esto es factible porque las interfaces de las primitivas de concurrencia en la JVM son relativamente estables y permanecieron sin cambios durante años.

Probando la batalla

Luego de construir Fray, el siguiente paso fue la evaluación. Afortunadamente, muchas aplicaciones, como Apache Lucene, ya incluyen pruebas de concurrencia. Estas pruebas de concurrencia son pruebas JUnit regulares que generan múltiples hilos, realizan algo de trabajo, luego (normalmente) esperan a que terminen esos hilos y luego afirman alguna propiedad. La mayoría de las veces, estas pruebas se aprueban porque solo hacen un entrecalado. Peor aún, algunas pruebas solo fallan ocasionalmente en el entorno CI/CD, como se describió antes, lo que hace que estos fallos sean extremadamente difíciles de depurar. Cuando ejecutamos las mismas pruebas con Fray, descubrimos numerosos errores. Cabe destacar que Fray redescubrió errores previamente reportados que no fueron corregidos debido a la falta de una reproducción fiable, incluyendo el enfoque de este blog: TestIDVersionPostingsFormat.testGlobalVersions. Por suerte, con Fray, podemos reproducirlos de forma determinista y proporcionar a los desarrolladores información detallada, permitiéndoles reproducir y solucionar el problema de forma fiable.

Próximos pasos para Fray

Nos entusiasma escuchar de los desarrolladores de Elastic que Fray fue útil para depurar errores de concurrencia. Seguiremos trabajando en Fray para que esté disponible para más desarrolladores.

Nuestros objetivos a corto plazo incluyen mejorar la capacidad de Fray para reproducir determinísticamente el calendario, incluso en presencia de otras operaciones no deterministas como un generador de valores aleatorios o el uso de object.hashcode. También pretendemos mejorar la usabilidad de Fray, permitiendo a los desarrolladores analizar y depurar pruebas de concurrencia existentes sin intervención manual. Lo más importante es que, si tienes dificultades para depurar o probar problemas de concurrencia en tu programa, nos encantaría saber de ti. Por favor, no dudes en crear un problema en el repositorio Fray Github.

Hora de arreglar el bug de la concurrencia

¡Gracias a Ao Li y al laboratorio de PATA, ahora tenemos un caso fiable que suspende esta prueba! Por fin podemos arreglar esto. El problema clave residía en cómo DocumentsWriterPerThreadPool permitía la reutilización de hilos y recursos.

Aquí podemos ver cada hilo creado, haciendo referencia a la cola inicial de eliminación en la generación 0.

Después, el avance de cola ocurrirá al encajar la cola y se verán correctamente las 7 acciones anteriores en la cola.

Pero, antes de que todos los hilos terminen de enjuagar, dos se reutilizan para un documento adicional:

Estos incrementarán el seqNo por encima del máximo asumido, que se calculó durante el flush como 7. Notar el numDocsInRAM adicional para los segmentos _3 y _0

Lo que provoca que Lucene tenga en cuenta incorrectamente la secuencia de acciones del documento durante un vaciado y activa este fallo de prueba.

Como todas las buenas correcciones de errores, la corrección real tiene unas 10 líneas de código. Pero dos ingenieros tardaron varios días en entenderlo realmente:

No todos los héroes llevan capa

Sí, es un cliché, pero es verdad.

La depuración concurrente de programas es increíblemente importante. Estos complicados errores de concurrencia requieren una cantidad desproporcionada de tiempo para depurar y resolver. Aunque nuevos lenguajes como Rust tienen mecanismos incorporados para ayudar a prevenir condiciones raciales como esta, la mayoría del software del mundo ya está escrito, y escrito en algo distinto a Rust. Java, incluso luego de todos estos años, sigue siendo uno de los lenguajes más empleados. Mejorar la depuración en lenguajes basados en JVM mejora el mundo de la ingeniería de software. Y dado que algunos piensan que el código será escrito por grandes modelos de lenguaje, quizá nuestro trabajo como ingenieros acabe siendo simplemente depurar código malo de LLM en lugar de solo nuestro propio código malo. Pero, sea cual sea el futuro de la ingeniería de software, la depuración concurrente de programas seguirá siendo fundamental para el mantenimiento y desarrollo de software.

Gracias a Ao Li y a sus colegas del PASTA Lab por hacerlo aún mejor.

Preguntas frecuentes