Optimistic Lock Coupling : synchroniser les arbres binaires sans contention
Sommaire
En bref
- Le Lock Coupling classique crée une contention physique sur le nœud racine lors de lectures concurrentes, limitant la scalabilité même sans conflit sémantique.
- L'Optimistic Lock Coupling laisse les lecteurs lire sans verrouiller, en validant une version avant et après chaque accès : aucune écriture par les lecteurs, donc pas de contention.
- La technique est performante mais fragile : lire une valeur avant de la valider crée une condition de concurrence. L'article propose d'encoder cette validation dans le système de types C++ via des types `unvalidated<T>` pour la rendre obligatoire à la compilation.
Ce que dit la source
L'auteur explique que les structures de données concurrentes protégées par des verrous souffrent de contention sur les nœuds fréquemment accédés (notamment la racine). Le Lock Coupling classique, bien qu'il libère les verrous au fur et à mesure, crée une contention physique sur les locks eux-mêmes : chaque lecture traverse la racine et doit acquérir son verrou, même si aucun écrivain n'accède réellement au nœud. L'Optimistic Lock Coupling résout ce problème en supprimant les acquisitions de verrou côté lecteur : les lecteurs ne font que lire et valider les versions, ce qui n'implique aucune écriture sur les locks.
- L'article mesure l'impact sur un 9950X3D 16-core/32-thread : le Lock Coupling classique plafonne beaucoup plus tôt que l'Optimistic Lock Coupling à mesure que le nombre de cœurs croît.
- Les lecteurs lisent un numéro de version avant d'accéder aux données, relit le contenu, puis re-valident la version ; si elle a changé ou si un verrou est actif, la lecture recommence.
- L'implémentation naïve est dangereuse : oublier une validation entre la lecture d'une valeur et son utilisation crée une condition de concurrence réelle, même si la technique est sémantiquement correcte.
- La solution proposée utilise un type `unvalidated<T>` pour encapsuler les valeurs lues, accessible uniquement via la méthode `validate()` du verrou : le compilateur force donc la validation avant tout usage.
- La classe `OptimisticPtr` expose les membres du nœud via une `OptimisticView` qui retourne toujours des `unvalidated<T>`, rendant impossible l'accès direct sans validation.
Dans les commentaires
Débat limité mais sérieux. Les commentaires relevés soulignent une faiblesse majeure non traitée dans l'article : la gestion de la durée de vie et la prévention des use-after-free. Le texte reconnaît que les lecteurs peuvent déréférencer des nœuds libérés par l'écrivain ; l'article n'évoque ni RCU ni Hazard pointers, ce qui rend la technique incomplète pour un arbre qui doit vraiment dealloquer.
- Un commentateur souligne que le design n'adresse pas la libération de mémoire : rien n'empêche un lecteur en train de valider de déréférencer un nœud que l'écrivain a entretemps supprimé. Fixer cela exige RCU ou Hazard pointers, techniques non mentionnées ici.
- Un autre pointe que la technique repose sur la sécurité des lectures de mises à jour décousues (torn updates), ce qui est techniquement un comportement indéfini en C++.
- Une question sur pourquoi ne pas simplement utiliser RwLock (Rust) qui permet aussi plusieurs lecteurs et un écrivain : pas de réponse comparant les performances réelles entre les deux approches.
Notre lecture
L'article est une bonne explication pédagogique d'une technique réelle d'optimisation, avec une excellente présentation du problème de contention et une solution ingénieuse de typage pour forcer la validation. Mais il y a une lacune critique : le problème de la durée de vie des nœuds n'est pas résolu et rend la technique dangereuse en pratique pour des arbres qui deallouent. Intéressant pour comprendre comment le compilateur peut polir les bords d'une stratégie de verrouillage audacieuse, mais pas prêt pour la production sans protection mémoire explicite (RCU ou Hazard pointers).