- Publié en 1976, le Two-Phase Locking (2PL) fournit une opacity plus forte que la sérialisabilité, mais près de 50 ans plus tard, il conserve encore des limites en matière de scalabilité en lecture et de garanties de progression
- Grâce à une règle simple d’acquisition et de libération des verrous, il permet de traiter des transactions sur plusieurs enregistrements tout en offrant un fort niveau d’isolation, ce qui explique son usage toujours très répandu dans les bases de données transactionnelles commerciales et les structures de données concurrentes
- Le 2PL traditionnel peut faire entrer en conflit même des lectures entre elles à cause des verrous d’exclusion mutuelle, et même avec un reader-writer lock, une contention sur l’indicateur de lecture apparaît aux points où les lectures se concentrent, comme la racine d’un arbre binaire de recherche
- 2PLSF répartit les indicateurs propres à chaque reader sur plusieurs lignes de cache pour réduire la contention lors de l’acquisition des verrous en lecture, et n’applique fetch_and_add() sur un compteur atomique central qu’aux transactions effectivement en conflit
- Des variantes du 2PL comme No-Wait, Deadlock-detection ou Wait-Or-Die laissent subsister des problèmes de live-lock ou de scalabilité, tandis que 2PLSF vise à la fois la scalabilité en lecture et des transactions sans famine
Pourquoi le 2PL reste important
- Le Two-Phase Locking (2PL) est l’un des premiers contrôles de concurrence généralistes à avoir fourni la sérialisabilité (Serializability) et, en pratique, il offre un niveau d’isolation encore plus fort, l’Opacity
- Le 2PL a été publié en 1976 dans un article de Jim Gray et de ses collègues, même si l’idée elle-même pourrait être antérieure, ce qui en fait une technique vieille de près de 50 ans
- Un contrôle de concurrence généraliste désigne un algorithme qui permet des transactions ayant une sémantique all-or-nothing sur plusieurs éléments de données comme des objets, enregistrements ou tuples
- La force du 2PL tient à sa simplicité et à sa forte isolation
- avant de lire ou d’écrire un enregistrement, on acquiert d’abord le verrou qui protège cet enregistrement
- les verrous acquis sont conservés jusqu’à la fin de la transaction afin de garantir une vue cohérente
Une isolation produite par des règles simples
- En 2PL, chaque accès au cours d’une transaction s’accompagne de l’acquisition d’un verrou, puis tous les verrous sont relâchés à la fin de la transaction, quand celle-ci sait qu’il n’y aura plus d’accès
- À ce moment de fin, tous les verrous sur les données accédées sont détenus, ce qui crée un point de linéarisation (linearization point) pour cette transaction
- Il y a 50 ans, beaucoup de chercheurs en bases de données considéraient qu’on pouvait libérer les verrous juste après avoir terminé l’accès à un enregistrement, mais ce type de contrôle de concurrence n’est pas sérialisable
- Les bases de données transactionnelles commerciales connues utilisent le 2PL ou le T/O, parfois combinés à du MVCC
- Dans le domaine des structures de données concurrentes, la linéarizabilité est proche du standard, et pour écrire de manière cohérente sur plusieurs nœuds, il faut généralement une approche de type 2PL pour les accès en écriture
- l’exception concerne les structures lock-free, mais il est rappelé qu’une implémentation lock-free correcte est difficile
Les goulets d’étranglement du 2PL : scalabilité en lecture et live-lock
- Les grandes faiblesses du 2PL sont le manque de scalabilité en lecture et les garanties de progression en présence de live-lock
- Le 2PL classique est conçu autour de verrous d’exclusion mutuelle, si bien que deux threads qui ne font que lire le même enregistrement peuvent malgré tout entrer en conflit, et l’un ou les deux peuvent être abort puis redémarrer
- Le passage à un reader-writer lock réduit les conflits entre lectures, mais augmente le coût des verrous et l’usage mémoire
- un verrou d’exclusion mutuelle peut être implémenté avec 1 bit indiquant l’état verrouillé/déverrouillé
- un reader-writer lock a besoin, en plus de ce bit, d’un compteur du nombre de readers qui détiennent actuellement le verrou en mode lecture
- par exemple, un compteur sur 7 bits peut représenter jusqu’à 128 threads, et chaque verrou peut alors occuper 1 octet
- avec des milliards d’enregistrements en base, les seuls verrous peuvent déjà nécessiter des milliards d’octets
- Le problème plus sérieux encore est la contention sur le compteur
- dans des workloads read-non-disjoint, beaucoup de lectures se concentrent sur les mêmes données
- la racine d’un arbre binaire de recherche est un cas typique, car toutes les opérations doivent la lire avant de descendre vers les nœuds inférieurs
- en 2PL, chaque accès à la racine exige une acquisition de verrou et, même avec un reader-writer lock, le verrou de la racine subit une forte contention
Approches existantes et read-indicator scalable
- TLRW est une approche présentée par Dave Dice et Nir Shavit à SPAA 2010 ; elle améliore les performances par rapport aux verrous d’exclusion mutuelle grâce à un reader-writer lock, mais reste moins rapide qu’un contrôle de concurrence optimiste
- Comme avec TLRW, si l’on applique à un arbre binaire de recherche AVL relâché basé sur le rang une implémentation où chaque accès en lecture entre en contention sur la variable unique d’un reader-writer lock, la scalabilité devient rapidement plate pour la plupart des transactions, qu’elles soient en lecture ou en écriture
- La contention sur l’indicateur de lecture peut être atténuée par un read-indicator scalable
- l’approche privilégiée consiste à utiliser un reader-writer lock où chaque reader signale son arrivée et son départ sur une ligne de cache distincte
- l’acquisition d’un verrou en lecture ne subit alors plus de contention
- en contrepartie, le thread qui veut obtenir un verrou en écriture doit scanner toutes les lignes de cache pour vérifier s’il peut entrer, ce qui augmente le coût d’acquisition du verrou en écriture
- Les NUMA Aware reader-writer locks décrivent des algorithmes de reader-writer lock qui utilisent cette technique
- parmi les trois algorithmes présentés, deux offrent une forte scalabilité, mais ne sont pas sans famine
Conception du reader-writer lock de 2PLSF
- Two-Phase Locking Starvation-Free (2PLSF) est un contrôle de concurrence implémenté avec un reader-writer lock qui scale bien pour l’acquisition des verrous en lecture et possède des propriétés supplémentaires
- Le reader-writer lock de 2PLSF réserve 1 bit par thread pour le read-lock
- ces bits sont placés sur leurs propres lignes de cache
- ils sont regroupés avec les bits de read-indicator des verrous voisins
- Comme dans l’article sur les reader-writer locks NUMA-aware, le coût est déplacé vers l’acquisition du verrou en écriture
- le verrou en écriture doit scanner plusieurs lignes de cache
- ce n’est pas une solution magique mais bien un compromis
- Ce compromis est utile parce que la plupart des workloads sont dominés par les lectures, et même les workloads intensifs en écriture passent une part significative de leur temps en accès de lecture, notamment lors des phases de recherche d’enregistrements
- Avec ce reader-writer lock amélioré, le 2PL peut mieux scaler même sur des workloads read-non-disjoint, mais le problème du live-lock doit être traité séparément
Les variantes du 2PL laissent subsister des problèmes de garantie de progression
- Le 2PL classique a plusieurs variantes connues selon la manière de gérer les conflits, notamment No-Wait, Deadlock-detection et Wait-Or-Die
-
No-Wait
- lorsqu’un conflit survient, la transaction courante ou la transaction adverse est abort puis retentée
- la nouvelle tentative peut être immédiate ou différée avec un backoff exponentiel
- si une transaction veut modifier l’enregistrement A puis B, tandis qu’une autre veut modifier B puis A, elles peuvent continuer à se heurter et à enchaîner les cycles abort-restart sans jamais commit, ce qui relève d’un live-lock progress
-
Deadlock-detection
- on maintient une liste des threads en attente sur chaque verrou afin de détecter les cycles, c’est-à-dire les deadlocks
- avec un reader-writer lock, chaque reader doit avoir sa propre liste, et chaque liste doit aussi être protégée par un verrou d’exclusion mutuelle
- prendre un verrou en mode lecture impose alors de scanner toutes les listes de readers, ce qui devient coûteux
- en théorie, il serait peut-être possible d’obtenir l’absence de famine, mais cela supposerait un verrou lui-même sans famine, ce qui va à l’encontre de l’objectif puisqu’il n’existe pas de reader-writer lock publié à la fois très scalable et sans famine
- avoir une liste par reader peut aussi augmenter fortement l’usage mémoire
-
Wait-Or-Die
- toutes les transactions reçoivent un ordre et, lors d’un conflit de verrou, on compare le timestamp de la transaction avec celui du détenteur du verrou pour décider d’attendre ou d’abandonner
- avec des verrous d’exclusion mutuelle, le propriétaire peut être stocké directement dans le verrou sous forme d’identifiant de thread unique, ce qui fonctionne bien
- avec un reader-writer lock, la même approche exigerait un thread-id pour chaque reader
- pour supporter 256 threads, il faudrait 8 bits × 256 = 256 octets par reader-writer lock
Le goulet d’étranglement du compteur atomique central et ce qui distingue 2PLSF
- L’obstacle principal de Wait-Or-Die est surtout que toutes les transactions doivent recevoir un identifiant de transaction unique
- par exemple, on peut construire cet ordre en allant chercher un numéro via fetch_and_add() sur une variable atomique centrale
- Sur la plupart des CPU modernes, il est difficile d’effectuer plus de 40 millions de
fetch_and_add()par seconde sur une variable atomique en contention- comparé aux quelque 660 millions de transactions quotidiennes de Visa, cela peut sembler élevé
- mais pour un DBMS in-memory ou des structures de données concurrentes, ce n’est pas forcément suffisant
- sur une machine de test, il était difficile de dépasser 20 millions de
fetch_and_add()par seconde
- Cette opération
fetch_and_add()est nécessaire non seulement pour les transactions d’écriture, mais aussi pour toutes les transactions, y compris celles en lecture, ce qui limite la scalabilité - TL2 permet aux transactions de lecture d’éviter le
fetch_and_add()atomique grâce à des lectures optimistes- du point de vue des transactions de lecture, il peut scaler jusqu’à des centaines de millions de tps
- à l’inverse, un 2PL basé sur Wait-Or-Die ne peut pas dépasser 40M tps/sec
- 2PLSF n’ordonne que les transactions qui entrent effectivement en conflit
- cela réduit le nombre de transactions qui doivent exécuter
fetch_and_add()sur la variable atomique centrale - les transactions sans conflit ne sont donc pas bloquées par le plateau des 40M tps
- à titre d’exemple, on peut avoir 200M tps sans conflit, tandis que seuls 40M tps en conflit restent limités par la barrière du
fetch_and_add() - l’algorithme fournit la starvation-freedom
- cela réduit le nombre de transactions qui doivent exécuter
Ressources et évaluation finale
- L’algorithme 2PLSF lui-même n’est pas détaillé ici, mais il est présenté comme relativement simple pour un algorithme sans famine
- Des références vers l’article et le code source sont fournies
- article : https://zenodo.org/record/7886718
- code source : https://github.com/pramalhe/2PLSF/blob/main/stms/2PLSF.hpp
- 2PLSF est aussi relié à un article de l’ACM et présenté comme un algorithme conçu par Pedro Ramalhete, Andreia et Pascal Felber
- L’objectif de 2PLSF est de se rapprocher des propriétés que le 2PL aurait dû avoir dès le départ
- il scale bien même dans les situations read-non-disjoint où les lectures se recouvrent
- il fournit des transactions sans famine, la forme la plus forte de progression bloquante
- il peut conserver de la scalabilité même dans certaines situations de conflit
- 2PLSF n’est pas parfait, mais il est jugé supérieur à TL2 sur la résolution des conflits, et sa différence avec le 2PL classique est comparée à celle entre une pioche et un marteau-piqueur
1 commentaires
Commentaires sur Hacker News
Dans une architecture de microservices distribuée, je me demande quelles sont les meilleures pratiques du secteur pour synchroniser plusieurs magasins de données, ou les maintenir « cohérents »
Il y a quelques jours, j’ai essayé de résoudre un problème d’incohérence avec un « settled timestamp » : c’est assez proche d’une approche multiversion où, si le temps passe sans rapport d’erreur, on considère l’enregistrement/commit comme valide. Dans un commit en deux phases, la deuxième phase serait en quelque sorte le temps
L’idée était de surveiller les horloges des autres serveurs et, si elles ne sont pas mises à jour, de ne pas faire confiance au settled timestamp de ce serveur ; comme il n’est pas nécessaire d’attendre une réponse à chaque mise à jour, mais seulement la prochaine tranche de timestamp, le but était de faire passer la cohérence à l’échelle de nombreux serveurs
J’ai écrit du code Python multithread et multiprocessus, avec 10 threads qui s’échangent des mises à jour aléatoires, pour tester le non-déterminisme : https://replit.com/@Chronological/InconsistencySimulation#ma...
Dans cette simulation, une lecture correspond au minimum de tous les timestamps rapportés par tous les serveurs ; si, au bout de 10 secondes, on demande la valeur du compteur à chaque thread, il arrive qu’ils renvoient tous la même valeur, mais assez souvent on se retrouve en situation de split-brain
Je sais que, dans les systèmes distribués, les timestamps d’horloge murale ne conviennent pas pour déterminer l’ordre, et qu’il faut utiliser des horloges logiques ou des horloges vectorielles
Ce serait bien si, à n’importe quel moment, la simulation pouvait faire en sorte que tous rapportent le même nombre. Bloomlang cherche à résoudre, dans l’eventual consistency, le problème où une valeur arrivée tardivement affecte le résultat et empêche la linéarisabilité
Je m’intéresse surtout à la mise à l’échelle tout en conservant la cohérence, mais cela semble être un problème assez difficile
Plusieurs systèmes écrivent séquentiellement dans le journal central, et le journal reçoit les requêtes comme un magasin clé-valeur. Ce journal est répliqué sur tous les nœuds, qui le lisent pour exécuter la logique complexe demandée
Kubernetes utilise etcd, donc, comme magasin clé-valeur à forte cohérence, cela passe plutôt bien à l’échelle
Comme vous parlez de « plusieurs magasins de données », je suppose que les données sont hétérogènes et qu’une option comme CockroachDB n’est pas adaptée
Si vous débutez, le faire vous-même est risqué. https://aphyr.com/ est une sorte de référence pour les tests et c’est aussi excellent à des fins pédagogiques. On peut tester des systèmes distribués avec Jepsen, mais il vaut mieux utiliser un magasin de données dont Kyle a montré la robustesse
Je ne suis pas très familier de ces techniques, mais quand j’ai étudié les bases de données, SSI était présenté comme une sorte de « meilleure » version future du verrouillage en deux phases. Je me demande en quoi SSI diffère de 2PLSF, et pourquoi il n’est pas mentionné ici
Mais pour les effets distribués, il faut toujours des verrous, des transactions en deux phases, etc. Personnellement, je vois cela davantage comme des fonctionnalités complémentaires que comme des substituts
Pour une structure de données en mémoire, c’est naturel, mais si vous manipulez une base de données externe ou une autre ressource externe partagée, il peut exister une meilleure approche
On peut souvent traiter les requêtes par lots afin d’accéder à la ressource externe avec une concurrence plus faible et des charges utiles plus grandes. Si cette ressource gère bien les lots, la concurrence et le verrouillage nécessaires diminuent beaucoup
Par exemple, si vous utilisez Postgres, cela peut réduire le nombre de connexions et vous éviter d’ajouter PgBouncer, qui accroît la complexité
Cela dit, le traitement par lots des requêtes s’accorde mal avec la plupart des langages de programmation. Les langages optimisés pour une forte concurrence, comme les channels de Go ou les processus d’Elixir, peuvent très bien s’en sortir, mais dans les langages où tout passe par des threads, cela peut être pénible
Pour les sites qui ne peuvent pas être mis à niveau vers HTTPS, un avertissement s’affiche ; pour ceux qui prennent en charge les deux, on est directement redirigé vers la version HTTPS
Et si le lien HTTP porte sur un bon algorithme de concurrence, je le lirai quand même
fetch_and_addpour obtenir un ID de transaction ? Je me demande même si un ID de transaction est nécessaire au départL’objectif semble être d’établir entre les transactions actives un ordre arbitraire mais cohérent, afin qu’en cas de conflit elles puissent se mettre d’accord sur qui attend et qui « meurt ». Dans ce cas, pourquoi ne pas utiliser l’ID du thread ?
Un nombre aléatoire pourrait aussi convenir. Si l’on traite les égalités comme une « mort », dans le pire des cas les deux transactions sont interrompues inutilement et réessayent simplement avec un nouveau nombre aléatoire.
Ce n’est pas mentionné, mais il semble qu’on veuille donner la priorité aux transactions anciennes pour éviter qu’une transaction longue ne soit affamée par des transactions courtes. Par exemple, si une longue transaction entre en conflit en moyenne avec trois transactions courtes, et que le gagnant de chaque conflit est en pratique aléatoire, la probabilité que la longue transaction gagne les trois fois et puisse committer n’est que de 1/8.
Mais pour éviter la famine, il n’est pas nécessaire de donner à chaque fois la priorité à la transaction la plus ancienne ; il suffit que ce soit le cas la plupart du temps. C’est encore plus vrai si elle n’est que très légèrement plus ancienne.
Ainsi, même avec des écarts d’horloge entre threads ou d’autres imprécisions, quelque chose comme un timestamp ou un cycle counter peut bien fonctionner. Les égalités peuvent être départagées par l’ID du thread, ou bien, là encore, en interrompant les deux côtés.
Cela convient bien à ce cas et à beaucoup d’autres.
Le commit en deux phases est comparable à Paxos, et les deux relèvent des protocoles de consensus.
Le verrouillage en deux phases est un mécanisme de contrôle de concurrence.
Quand le premier message de verrouillage disparaît, le problème est de savoir comment déterminer que ce n’est pas le message de réponse qui a été perdu.
Dans les cas simples, comme GitHub ou Dropbox, on peut simplement continuer et gérer les conflits plus tard. Pour une base de données, il faut espérer avoir de la chance ; pour une banque, encore plus.
Dans une transaction en lecture seule, TL2 n’a qu’à échantillonner la version globale, puis vérifier, pour toutes les lectures, que la version locale est inférieure ou égale à la version échantillonnée.
Dans ce cas, il est difficile de comprendre pourquoi le graphe est sous-linéaire, et pourquoi TL2 n’est pas aussi rapide que les autres implémentations STM.
Par exemple, supposons qu’il y ait typiquement 1 000 tâches et 10 à 100 threads matériels.
On crée une liste triée unique des 1 000 tâches, puis une copie pour chaque thread, dont l’ordre est randomisé à chaque fois.
Chaque thread peut alors lire sa propre liste et exécuter les tâches, puis s’abonner à une liste implémentée comme une file multithread non bloquante.
Dans le pire des cas, certains threads peuvent exécuter plusieurs fois une même tâche.
Avec cette approche, les opérations atomiques pourraient scaler jusqu’à 1 000 fois.