Bugs de concurrence dans Lucene : Comment corriger les échecs de concurrence optimiste

Souhaitez-vous recevoir une certification Elastic ? Découvrez quand se déroulera la prochaine formation Elasticsearch Engineer ! Vous pouvez lancer un essai gratuit sur le cloud ou essayer Elastic sur votre machine locale dès maintenant.

Yep, un autre blog sur la correction des bogues. Mais cette fois-ci, c'est un héros de l'open source qui intervient et sauve la situation.

Le débogage des bogues de concurrence n'est pas une sinécure, mais nous allons nous y atteler. C'est là qu'intervient Fray, un cadre de test de concurrence déterministe du laboratoire PASTA de l'Université de Californie du Sud, qui transforme les défaillances en défaillances reproductibles de manière fiable. Grâce à la conception astucieuse du shadow lock de Fray et au contrôle précis des threads, nous avons traqué un bug Lucene délicat et l'avons finalement éliminé. Ce billet explore la façon dont les héros et les outils open-source rendent le débogage de la concurrence moins pénible et le monde du logiciel bien meilleur.

Les bogues de simultanéité : le fléau des ingénieurs en informatique

Les bogues liés à la concomitance sont les pires. Non seulement ils sont difficiles à réparer, mais le plus difficile est de les faire tomber en panne de manière fiable. Prenons l'exemple de l'échec de ce test, TestIDVersionPostingsFormat#testGlobalVersions. Il génère plusieurs fils d'écriture et de mise à jour de documents, ce qui remet en cause le modèle de concurrence optimiste de Lucene. Ce test a mis en évidence une condition de course dans le contrôle optimiste de la concurrence. En d'autres termes, une opération de document peut faussement prétendre être la dernière d'une séquence d'opérations 😱. Cela signifie que, dans certaines conditions, une opération de mise à jour ou de suppression peut réussir alors qu'elle aurait dû échouer compte tenu des contraintes de concurrence optimistes.

Toutes nos excuses à ceux qui détestent les traces de pile Java. Remarque : supprimer ne signifie pas nécessairement "effacer". Il peut également indiquer une "mise à jour" du document, car les segments de Lucene sont en lecture seule.

Apache Lucene gère chaque thread qui écrit des documents par l'intermédiaire de la classe DocumentsWriter. Cette classe crée ou réutilise des fils de discussion pour l'écriture de documents et chaque action d'écriture contrôle ses informations dans la classe DocumentsWriterPerThread (DWPT). En outre, le rédacteur garde la trace des documents supprimés dans le site DocumentsWriterDeleteQueue (DWDQ). Ces structures conservent en mémoire toutes les actions de mutation des documents et se vident périodiquement, libérant ainsi les ressources en mémoire et transférant les structures sur le disque.

Afin d'éviter le blocage des threads et d'assurer un débit élevé dans les systèmes concurrents, Apache Lucene tente de ne se synchroniser que dans les sections très critiques. Bien que cela puisse être une bonne chose dans la pratique, comme dans tous les systèmes concurrents, il y a des dragons.

Un faux espoir

Mon enquête initiale m'a permis d'identifier quelques sections critiques qui n'étaient pas correctement synchronisées. Toutes les interactions avec un site DocumentsWriterDeleteQueue donné sont contrôlées par le site DocumentsWriter qui l'entoure. Ainsi, même si les méthodes individuelles ne sont pas synchronisées de manière appropriée sur le site DocumentsWriterDeleteQueue, leur accès au monde l'est (ou devrait l'être). (Ne nous attardons pas sur la confusion entre propriété et accès - il s'agit d'un projet de longue date rédigé par de nombreux contributeurs. Laissez-lui un peu de répit.)

Cependant, j'ai trouvé un endroit qui n'était pas synchronisé lors d'un rinçage.

Ces actions ne sont pas synchronisées en une seule opération atomique. Cela signifie qu'entre la création de newQueue et l'appel de getMaxSeqNo, un autre code a pu être exécuté, incrémentant le numéro de séquence dans la classe documentsWriter. J'ai trouvé l'insecte !

Mais, comme pour la plupart des bogues complexes, il n'a pas été facile de trouver la cause première. C'est alors qu'un héros est intervenu.

Un héros dans la mêlée

Voici notre héros : Ao Li et ses collègues du laboratoire PASTA. Je le laisserai expliquer comment ils ont sauvé la situation avec Fray.

Fray est un cadre de test de concurrence déterministe développé par des chercheurs du PASTA Lab de l'Université Carnegie Mellon. La motivation derrière la création de Fray provient d'un écart notable entre le monde universitaire et l'industrie : alors que les tests déterministes de concurrence ont été largement étudiés dans la recherche universitaire depuis plus de 20 ans, les praticiens continuent de s'appuyer sur les tests de stress - une méthode largement reconnue comme peu fiable et peu fiable - pour tester leurs programmes simultanés. C'est pourquoi nous avons voulu concevoir et mettre en œuvre un cadre de test de concurrence déterministe dont l'objectif principal est la généralité et l'applicabilité pratique.

L'idée maîtresse

Fray s'appuie sur un principe simple mais puissant : l'exécution séquentielle. Le modèle de concurrence de Java offre une propriétéessentielle: si un programme est exempt de course aux données, toutes les exécutions sembleront cohérentes d'un point de vue séquentiel. Cela signifie que le comportement du programme peut être représenté comme une séquence d'instructions.

Fray exécute le programme cible de manière séquentielle : à chaque étape, il met en pause tous les threads sauf un, ce qui permet à Fray de contrôler précisément l'ordonnancement des threads. Les fils sont sélectionnés au hasard pour simuler la concurrence, mais les choix sont enregistrés en vue d'une relecture déterministe ultérieure. Pour optimiser l'exécution, Fray n'effectue des changements de contexte que lorsqu'un thread est sur le point d'exécuter une instruction de synchronisation telle que le verrouillage ou l'accès atomique/volatile. Une propriété intéressante de la liberté de la course aux données est que ce changement de contexte limité est suffisant pour explorer tous les comportements observables dus à l'entrelacement des threads(notre article contient une esquisse de preuve).

Le défi : contrôler l'ordonnancement des threads

Bien que l'idée de base semble simple, la mise en œuvre de Fray a présenté des défis importants. Pour contrôler l'ordonnancement des threads, Fray doit gérer l'exécution de chaque thread d'application. À première vue, cela peut sembler simple : remplacer les primitives de concurrence par des implémentations personnalisées. Cependant, le contrôle de la concurrence dans la JVM est complexe et implique un mélange d'instructions de bytecode, de bibliothèques de haut niveau et de méthodes natives.

Il s'est avéré qu'il s'agissait d'un trou de lapin :

• Par exemple, chaque instruction MONITORENTER doit avoir un correspondant MONITOREXIT dans la même méthode. Si Fray remplace MONITORENTER par un appel de méthode à un stub/mock, il doit également remplacer MONITOREXIT.
• Dans le code qui utilise object.wait/notify, si MONITORENTER est remplacé, le object.wait correspondant doit également être remplacé. Cette chaîne de remplacement s'étend jusqu'à object.notify et au-delà.
• La JVM invoque certaines méthodes liées à la concurrence (par exemple, object.notify lorsqu'un thread se termine) dans le code natif. Le remplacement de ces opérations nécessiterait de modifier la JVM elle-même.
• Les fonctions de la JVM, telles que les chargeurs de classes et les threads de collecte de déchets (GC), utilisent également des primitives de concurrence. La modification de ces primitives peut créer des incohérences avec ces fonctions de la JVM.
• Le remplacement des primitives de concurrence dans le JDK entraîne souvent des plantages de la JVM pendant sa phase d'initialisation.

Ces défis ont clairement montré qu'un remplacement complet des primitives de concurrence n'était pas réalisable.

Notre solution : la conception d'une serrure à l'abri des regards

Pour relever ces défis, Fray utilise un nouveau mécanisme de verrouillage fictif pour orchestrer l'exécution des threads sans remplacer les primitives de concurrence. Les Shadow locks agissent comme des intermédiaires qui guident l'exécution des threads. Par exemple, avant d'acquérir un verrou, un thread d'application doit interagir avec le verrou fantôme correspondant. Le verrou fantôme détermine si le thread peut acquérir le verrou. Si le thread ne peut pas continuer, le verrou fantôme le bloque et permet à d'autres threads de s'exécuter, ce qui évite les blocages et permet une concurrence contrôlée. Cette conception permet à Fray de contrôler l'entrelacement des threads de manière transparente tout en préservant l'exactitude de la sémantique de la concurrence. Chaque primitive de concurrence est soigneusement modélisée dans le cadre du verrouillage fictif afin d'en garantir la solidité et l'exhaustivité. Plus de détails techniques peuvent être trouvés dans notre document.

En outre, cette conception est conçue pour être à l'épreuve du temps. En n'exigeant que l'instrumentation des verrous fantômes autour des primitives de concurrence, il garantit la compatibilité avec les versions plus récentes de la JVM. Cela est possible parce que les interfaces des primitives de concurrence dans la JVM sont relativement stables et sont restées inchangées depuis des années.

Test Fray

Après la construction de Fray, l'étape suivante a été l'évaluation. Heureusement, de nombreuses applications, comme Apache Lucene, intègrent déjà des tests de concurrence. Ces tests de concurrence sont des tests JUnit classiques qui génèrent plusieurs threads, effectuent un certain travail, attendent (généralement) que ces threads se terminent, puis affirment une certaine propriété. La plupart du temps, ces tests réussissent parce qu'ils n'exercent qu'un seul entrelacement. Pire encore, certains tests n'échouent qu'occasionnellement dans l'environnement CI/CD, comme décrit précédemment, ce qui rend ces échecs extrêmement difficiles à déboguer. Lorsque nous avons exécuté les mêmes tests avec Fray, nous avons découvert de nombreux bogues. Notamment, Fray a redécouvert des bogues précédemment signalés qui n'avaient pas été corrigés en raison de l'absence d'une reproduction fiable, y compris l'objet de ce blog : TestIDVersionPostingsFormat.testGlobalVersions. Heureusement, avec Fray, nous pouvons les rejouer de manière déterministe et fournir aux développeurs des informations détaillées, ce qui leur permet de reproduire et de résoudre le problème de manière fiable.

Prochaines étapes pour Fray

Nous sommes ravis d'entendre les développeurs d'Elastic dire que Fray a été utile pour déboguer les bogues de concurrence. Nous continuerons à travailler sur Fray afin de le rendre accessible à un plus grand nombre de développeurs.

Nos objectifs à court terme sont d'améliorer la capacité de Fray à rejouer le programme de manière déterministe, même en présence d'autres opérations non déterministes telles qu'un générateur de valeurs aléatoires ou l'utilisation de object.hashcode. Nous visons également à améliorer la facilité d'utilisation de Fray, en permettant aux développeurs d'analyser et de déboguer les tests de concurrence existants sans aucune intervention manuelle. Plus important encore, si vous rencontrez des difficultés pour déboguer ou tester les problèmes de concurrence dans votre programme, nous aimerions avoir de vos nouvelles. N'hésitez pas à créer un problème dans le dépôt Github de Fray.

Il est temps de corriger le bogue de la concurrence

Grâce à Ao Li et au laboratoire PASTA, nous disposons désormais d'une instance de ce test qui échoue de manière fiable ! Nous pouvons enfin réparer cette chose. Le principal problème réside dans la manière dont DocumentsWriterPerThreadPool permet la réutilisation des fils et des ressources.

Ici, nous pouvons voir la création de chaque thread, qui fait référence à la file d'attente de suppression initiale de la génération 0.

Ensuite, l'avance dans la file d'attente se produira au moment de l'effacement, en voyant correctement les 7 actions précédentes dans la file d'attente.

Mais avant que tous les fils ne puissent finir de se vider, deux d'entre eux sont réutilisés pour un document supplémentaire :

Ces derniers incrémenteront alors le site seqNo au-delà du maximum supposé, qui a été calculé lors de la chasse d'eau comme étant 7. Notez le site supplémentaire numDocsInRAM pour les segments _3 et _0

Lucene tient donc compte de manière incorrecte de la séquence d'actions des documents au cours d'une vidange et déclenche l'échec de ce test.

Comme toutes les bonnes corrections de bogues, la correction proprement dite se résume à une dizaine de lignes de code. Mais il a fallu plusieurs jours à deux ingénieurs pour trouver la solution :

Tous les héros ne portent pas de capes

Oui, c'est un cliché, mais c'est vrai.

Le débogage de programmes simultanés est extrêmement important. Ces bogues de concurrence délicats prennent un temps fou à déboguer et à résoudre. Bien que les nouveaux langages comme Rust intègrent des mécanismes permettant d'éviter de telles conditions de course, la majorité des logiciels dans le monde sont déjà écrits, et écrits dans un autre langage que Rust. Java, même après toutes ces années, reste l'un des langages les plus utilisés. L'amélioration du débogage sur les langages basés sur la JVM permet d'améliorer le monde du génie logiciel. Et étant donné que certains pensent que le code sera écrit par de grands modèles de langage, peut-être que notre travail d'ingénieur consistera finalement à déboguer du mauvais code LLM au lieu de notre propre mauvais code. Mais quel que soit l'avenir du génie logiciel, le débogage simultané des programmes restera essentiel pour la maintenance et la création de logiciels.

Merci à Ao Li et à ses collègues du laboratoire PASTA de l'avoir rendu encore meilleur.

Questions fréquentes