Multiversion Concurrency Control

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

Multiversion concurrency control (abrégé en MCC ou MVCC) est une méthode informatique de contrôle des accès concurrents fréquemment utilisée dans les systèmes de gestion de base de données et les langages de programmation concernant la gestion des caches en mémoire[1].

Le principe de MVCC repose sur un verrouillage dit optimiste contrairement au verrouillage pessimiste qui consiste à bloquer préalablement les objets a des garanties de bonne fin. L'inconvénient logique est qu'une mise à jour peut être annulée du fait d'un "blocage" en fin de traitement.

À cet effet, une base de données ne mettra pas en œuvre des mises à jour par écrasement des anciennes données par les nouvelles, mais plutôt en indiquant que les anciennes données sont obsolètes et en ajoutant une nouvelle "version". Ainsi, plusieurs versions sont stockées, dont une seule est la plus récente. Cela évite en outre à la base de données d'avoir à gérer le remplissage des "trous" en mémoire ou sur le disque mais nécessite (généralement) une purge régulière des données obsolètes. Dans le cas des bases de données orientées document comme CouchDB, cela a aussi pour incidence de réécrire une version complète du document à chaque mise à jour, plutôt que de gérer des mises à jour incrémentales constituées de petits morceaux de document liés entre eux et rangés de manière non contigüe.

MVCC autorise aussi la création de prise de vue "à un instant donné" (cliché ou snapshot en anglais). En réalité, les transactions avec MVCC utilisent une estampille (timestamp en anglais) qui n'a pas de relation avec le temps, mais consiste en une valeur monotone, unique et incrémentée, valuée à chaque transaction pour déterminer l'état de la base à lire. Ce mécanisme permet d'éviter l'usage de verrous pessimiste dans les transactions car les écritures peuvent être virtuellement isolées des opérations de lecture qui s'effectuent sur les anciennes versions dans la base et qui ont été générées par copie et maintenues tant que la transaction est vivante. Ainsi, considérant une requête en lecture ayant un identifiant de transaction donné, toutes ses valeurs sont consistantes car les opérations d'écriture en cours, mais non encore validées, disposent d'un identifiant de transaction plus élevé.

En d'autres termes, MVCC permet à chaque utilisateur connecté de voir une capture de la base. Les modifications apportées ne seront pas visibles par les autres utilisateurs avant que la transaction ne soit validée (commit).

En cas de mise à jour concurrente, la transaction qui est la première à valider les modifications, gagne. Les autres perdent (une annulation est forcée) au moment de reporter les mises à jour de la copie dans la base vivante.

Implémentation[modifier | modifier le code]

MVCC utilise des marqueurs temporels (timestamp - estampille) ou incrémente des identifiants de transaction pour mettre en œuvre des transactions consistantes. MVCC assure qu'une transaction n'aura jamais à attendre la disponibilité d'un objet en gérant plusieurs versions de chaque objet.

Chaque version de ligne dispose d'une estampille et laissera une transaction (Ti) lire la plus récente version d'un objet qui précède l'estampille de la transaction en cours (TS(Ti)).

Si une transaction (Ti) nécessite d'écrire un objet, et qu'une autre transaction (Tk) fait de même, l'estampille de Ti devra précéder celle de Tk (c'est-à-dire TS(Ti) < TS(Tk)) pour que l'opération d'écriture soit un succès. Cela revient à dire qu'une opération d'écriture ne peut pas être effectuée s'il existe une transaction pour le même objet avec une estampille de valeur inférieure.

Chaque objet dispose d'une estampille en lecture, et si une transaction Ti nécessite d'écrire un objet P, et que l'estampille de cette transaction est plus ancien que celle de l'objet en lecture (TS(Ti) < RTS(P)), la transaction Ti est abandonnée et ré exécutée. Dans le cas contraire, Ti crée une nouvelle version de P et définit l'estampille en lecture et écriture de P à la valeur de l'estampille de TS(Ti).

L'avantage est que les lectures ne sont jamais bloquées, et que les écritures ne se bloquent pas entre elles. Il y a donc globalement peu de temps d'attente, donc moins de contention et par conséquent une meilleure concurrence d'accès à la base.

Les inconvénients de ce système sont :

  • l'abandon de certaines transaction, en fin de traitement, si une opération concurrente, portant sur les mêmes informations, a validé ses modifications en premier.
  • le coût du maintien de multiples versions des objets en base (il faut bien les stocker quelque part) qui peut s'avérer très important dans le cas de de bases de données avec de nombreuses transactions fortement concurrentielles;
  • la maintenance éventuelle des versions obsolètes à purger;
  • un nombre accru de possibilité de survenance d'incohérences dans l'état des données de la base, contrairement au verrouillage pessimiste capable de garantir toutes les incohérences. Par exemple une incohérence des données de la base survenant à cause d'un problème d’écriture biaisée (Write Skew Problem).

Exemple[modifier | modifier le code]

Au moment = "t1", l'état de la base pourrait être:

Temps Objet 1 Objet 2
t1 "Hello" "Bar"
t0 "Foo" "Bar"

Cela indique que le jeu de données actuel dans cette base est Objet 1="Hello", Objet 2="Bar". Auparavant, l'objet 1 était « Foo » mais cette valeur a été surchargée. Elle n'a pas été supprimée car la base contient plusieurs versions, mais finira par l'être.

Si une transaction longue commence une opération en lecture, elle travaillera avec la transaction « t1 » et ne verra que cet état. Si une mise à jour concurrente est effectuée (durant la longue transaction en lecture) qui supprime Objet 2 et ajoute Objet 3="Foo-Bar", l'état de la base de données ressemblera à :

Temps Objet 1 Objet 2 Objet 3
t2 "Hello" (deleted) "Foo-Bar"
t1 "Hello" "Bar"
t0 "Foo" "Bar"

À présent, il y a une nouvelle version avec un identifiant de transaction "t2". À noter que la transaction "t1" continue d'avoir accès à une prise de vue cohérente du système, même si la transaction "t2" a ajouté des données. La transaction "t1" a donc effectué une lecture de donnée isolée de l'écriture de la transaction "t2". C'est ainsi que MVCC gère des accès ACID isolés, sans mettre en œuvre de mécanisme de verrou [la gestion des dépendances entre transactions permet d'éviter les verrous en modification].

Historique[modifier | modifier le code]

Multiversion concurrency control est décrit en détail dans le document de 1981 "Concurrency Control in Distributed Database Systems" [2] de Philip Bernstein et Nathan Goodman alors employés de la société Computer Corporation of America. Le document de Bernstein et Goodman cite une dissertation de 1978[3] de David P. Reed qui décrit clairement le mécanisme MVCC et qui proclame être l'auteur original de ce travail.

Bases de données employant MVCC[modifier | modifier le code]

Autres logiciels utilisant MVCC[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Références[modifier | modifier le code]

  1. http://clojure.org/refs
  2. Philip Bernstein and Nathan Goodman, « Concurrency Control in Distributed Database Systems », ACM Computing Surveys,
  3. Reed, D.P., « Naming and Synchronization in a Decentralized Computer System », MIT dissertation,
  4. Berkeley DB Reference Guide: Degrees of Isolation
  5. Bigdata Blog
  6. DB2 Version 9.7 LUW Information Center, Currently committed semantics improve concurrency
  7. TM1 9.5.2 Information Center, Parallel Interaction
  8. Graves, Steve, « Multi-Core Software: To Gain Speed, Eliminate Resource Contention », RTC Magazine,
  9. White paper by Roman Rokytsky « Firebird and Multi Version Concurrency Control »(ArchiveWikiwixArchive.isGoogleQue faire ?) (consulté le 19 avril 2013)
  10. Multi-Version Concurrency Control in the H2 Database Engine
  11. http://community.ingres.com/wiki/MVCC
  12. Bill Todd, « InterBase: What Sets It Apart » [archive du ], (consulté le 4 mai 2006)
  13. About XtraDB, About XtraDB
  14. MariaDB/Storage Engines, PBXT
  15. About PBXT, About PBXT
  16. (en) « WiredTiger Storage Engine — MongoDB Manual 3.4 », sur docs.mongodb.com (consulté le 3 octobre 2017)
  17. MySQL 5.1 Reference Manual, Section 14.2.12: Implementation of Multi-Versioning
  18. ou Maria MySQL 5.1 Reference Manual, « Section 14.6.1: Falcon Features »(ArchiveWikiwixArchive.isGoogleQue faire ?)
  19. Oracle Database Concepts: Chapter 13 Data Concurrency and Consistency Multiversion Concurency Control
  20. PostgreSQL 9.1 Documentation, Chapter 13: Concurrency Control
  21. RDM Embedded 10.1 Reference Manual, d_trrobegin
  22. [1]
  23. Proposal for MVCC in ZODB « Copie archivée » (version du 6 février 2012 sur l'Internet Archive)
  24. [2]
  25. ehcache site
  26. pojo-mvcc project home

Pour voir plus loin[modifier | modifier le code]

  • Gerhard Weikum, Gottfried Vossen, Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery, Morgan Kaufmann, 2002, (ISBN 1-55860-508-8)