Protocoles de contrôle de concurrence

Les protocoles de contrôle de concurrence sont les méthodes — verrouillage, ordonnancement par estampille, validation optimiste et multiversion — qui planifient les transactions concurrentes de manière à ce que le résultat soit équivalent à une exécution séquentielle.

Definition

Un protocole de contrôle de concurrence est un ensemble de règles régissant la manière dont les transactions concurrentes accèdent aux données, de sorte que chaque ordonnancement autorisé soit sérialisable (ou satisfasse un niveau d'isolation plus faible choisi), préservant ainsi l'isolation sans obliger les transactions à s'exécuter une par une.

Scope

Ce sujet couvre les protocoles qui garantissent la sérialisabilité en situation de concurrence : le verrouillage à deux phases et sa variante stricte, avec détection et prévention des interblocages ; les protocoles d'ordonnancement par estampille ; le contrôle de concurrence optimiste avec des phases de lecture-validation-écriture ; et le contrôle de concurrence multiversion, incluant l'isolation par instantané. Il examine comment chaque protocole garantit des ordonnancements corrects et les compromis entre le blocage, les annulations et le débit. Il exclut la définition de la sérialisabilité elle-même et les mécanismes de récupération qui complètent le contrôle de concurrence.

Core questions

• Comment le verrouillage à deux phases garantit-il des ordonnancements sérialisables ?
• Comment les interblocages sont-ils détectés, prévenus ou résolus ?
• En quoi les protocoles d'ordonnancement par estampille et optimistes diffèrent-ils du verrouillage ?
• Comment le contrôle de concurrence multiversion permet-il aux lecteurs d'éviter de bloquer les rédacteurs ?
• Quels sont les compromis en termes de débit entre les méthodes pessimistes et optimistes ?

Key concepts

• verrouillage à deux phases
• 2PL strict et rigoureux
• verrous partagés et exclusifs
• détection et prévention des interblocages
• ordonnancement par estampille
• contrôle de concurrence optimiste
• contrôle de concurrence multiversion
• isolation par instantané

Key theories

Verrouillage à deux phases

Si chaque transaction acquiert tous ses verrous avant d'en libérer un seul (une phase de croissance suivie d'une phase de décroissance), tous les ordonnancements résultants sont sérialisables par conflit ; le verrouillage strict à deux phases maintient en outre les verrous d'écriture jusqu'à la validation pour assurer la récupérabilité.

Contrôle de concurrence optimiste

Les transactions s'exécutent sans verrouillage et sont validées au moment de la validation par rapport aux transactions concurrentes ; les transactions en conflit sont annulées et relancées, ce qui fonctionne bien lorsque la contention est faible.

Contrôle de concurrence multiversion

En conservant plusieurs versions de chaque élément de données, le système permet aux lectures d'accéder à un instantané cohérent sans bloquer les écritures ; l'isolation par instantané est un schéma multiversion largement utilisé, bien qu'il puisse permettre certaines anomalies non sérialisables.

Clinical relevance

Les protocoles de contrôle de concurrence déterminent le comportement d'une base de données sous charge : le verrouillage est robuste mais peut entraîner des interblocages et des contentions, les méthodes optimistes et multiversion permettent une concurrence élevée en lecture, et le choix du protocole influence directement le débit et la latence des systèmes transactionnels à fort trafic.

History

Le verrouillage à deux phases et les verrous de prédicat ont été formalisés par Eswaran et ses collègues chez System R en 1976 ; Kung et Robinson ont introduit le contrôle de concurrence optimiste en 1981 ; et la monographie de Bernstein, Hadzilacos et Goodman de 1987 a unifié la théorie. Les méthodes multiversion et l'isolation par instantané sont devenues dominantes par la suite dans les systèmes de bases de données largement utilisés pour leur comportement favorable aux lectures.

Debates

Isolation par instantané versus sérialisabilité

L'isolation par instantané offre une concurrence élevée en permettant aux lecteurs de voir un instantané cohérent, mais elle autorise des anomalies telles que le biais d'écriture (write skew) que la sérialisabilité complète interdit ; les praticiens débattent du moment où sa garantie plus faible est acceptable et du moment où des variantes sérialisables sont nécessaires.

Key figures

• Jim Gray
• Philip Bernstein
• H. T. Kung

Seminal works

• eswaran1976
• kung1981
• bernstein1987

Frequently asked questions

Qu'est-ce qui cause un interblocage et comment est-il géré ?

Un interblocage se produit lorsque deux transactions ou plus détiennent chacune un verrou dont l'autre a besoin, de sorte qu'aucune ne peut progresser. Les systèmes le gèrent soit par détection — en construisant un graphe d'attente, en trouvant un cycle et en annulant une transaction victime — soit par des schémas de prévention qui ordonnent l'acquisition des verrous ou utilisent des estampilles pour décider quelle transaction attend ou est annulée.

Quand le contrôle de concurrence optimiste est-il un bon choix ?

Les méthodes optimistes excellent lorsque les conflits sont rares, car les transactions s'exécutent sans la surcharge du verrouillage et ne échouent et ne sont relancées qu'occasionnellement lors de la validation. En cas de forte contention, elles gaspillent du travail en annulations et relances, de sorte que le verrouillage pessimiste ou les méthodes multiversion sont généralement préférés pour les charges de travail à forte écriture et sujettes aux conflits.