Multiversion Concurrency Control

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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ème de gestion de base de données et les langages de programmation concernant la gestion de la mémoire[1].

À 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 l'une seule d'entre elle 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é". En réalité, les transactions avec MVCC utilisent un marqueur temporel (timestamp en anglais) ou un identifiant de transaction pour déterminer l'état de la base à lire. Ce mécanisme permet d'éviter l'usage de verrous dans les transactions car les écritures peuvent être virtuellement isolées des opérations de lecture sur les anciennes versions de la base qui ont été maintenues. 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 disposent d'un identifiant de transaction plus élevé.

En d'autres mots, 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).

Implémentation[modifier | modifier le code]

Cette section doit être recyclée. Une réorganisation et une clarification du contenu sont nécessaires. Discutez des points à améliorer en page de discussion.

MVCC utilise des marqueurs temporel (timestamp) 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 dispose d'un marqueur temporel et laissera une transaction (Ti) lire la plus récente version d'un objet qui précède le marqueur temporel de la transaction (TS(Ti)).

Si une transaction (Ti) nécessite d'écrire un objet, et qu'une autre transaction (Tk) fait de même, le marqueur de temps de Ti devra précéder celui 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 un marqueur temporel inférieur.

Chaque objet dispose d'un marqueur de temps en lecture, et si une transaction Ti nécessite d'écrire un objet P, et que le marqueur temporel de cette transaction est plus ancien que celui 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 les marqueur temporels en lecture et écriture de P à la valeur du marqueur temporel de TS(Ti).

La contrepartie de ce système est le coût du maintien de multiples versions des objets en base. D'un autre coté, les lectures ne sont jamais bloquées, ce qui est crucial car la majorité des accès aux bases de travail sont le plus souvent des accès en lecture. MVCC permet de mettre en œuvre une vraie implémentation de l'isolation, chose que d'autres mécanisme de gestion des accès concurrent ne gèrent que partiellement ou à des coûts élevés.

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 débute une opération en lecture, elle travaillera avec la transaction "t1" et ne verra que cette é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 (à noter cependant que les transactions en écriture nécessitent quant à elles d'utiliser des verrous).

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,‎ 1981
  3. Reed, D.P., « Naming and Synchronization in a Decentralized Computer System », MIT dissertation,‎ September 21, 1978
  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,‎ May 1, 2010
  9. White paper by Roman Rokytsky « Firebird and Multi Version Concurrency Control » (ArchiveWikiwixArchive.isGoogleQue faire ?). Consulté le 2013-04-19
  10. Multi-Version Concurrency Control in the H2 Database Engine
  11. http://community.ingres.com/wiki/MVCC
  12. « InterBase: What Sets It Apart » (ArchiveWikiwixArchive.isGoogleQue faire ?), 2000. Consulté le 4 May 2006
  13. About XtraDB, About XtraDB
  14. MariaDB/Storage Engines, PBXT
  15. About PBXT, About PBXT
  16. MySQL 5.1 Reference Manual, Section 14.2.12: Implementation of Multi-Versioning
  17. ou Maria MySQL 5.1 Reference Manual, Section 14.6.1: Falcon Features
  18. Oracle Database Concepts: Chapter 13 Data Concurrency and Consistency Multiversion Concurency Control
  19. PostgreSQL 9.1 Documentation, Chapter 13: Concurrency Control
  20. RDM Embedded 10.1 Reference Manual, d_trrobegin
  21. [1]
  22. Proposal for MVCC in ZODB
  23. [2]
  24. ehcache site
  25. 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