Multiversion Concurrency Control
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 à 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, valorisée à chaque transaction pour déterminer l'état de la base à lire. Ce mécanisme permet d'éviter l'usage de verrous pessimistes 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
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 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
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
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
- ArangoDB
- Altibase
- Berkeley DB[4]
- Bigdata[5]
- CouchDB
- IBM DB2 depuis IBM DB2 9.7 LUW ("Cobra") avec un niveau d'isolation CS - en mode CURRENTLY COMMITTED[6]
- IBM Cognos TM1 versions 9.5.2 et plus[7]
- Drizzle
- eXtremeDB [8]
- Firebird[9]
- FLAIM
- GE Smallworld Version Managed Data Store
- H2 Database Engine (expérimental depuis la version 1.0.57 du 2007-08-25)[10]
- HSQLDB (depuis la version 2.0)
- Ingres[11]
- InterBase (toutes les versions)[12]
- MariaDB (fork de MySQL) lorsqu'il est utilisé avec XtraDB (développé par Percona Inc., XtraDB est un moteur de stockage qui est un fork d'InnoDB et qui est inclus dans les sources et binaires de MariaDB)[13] ou PBXT (développé par PrimeBase Technologies),[15].
- MarkLogic Server
- Microsoft SQL Server (à partir de SQL Server 2005)
- MongoDB[16] (avec le moteur de stockage WiredTiger à partir de la Version 3.0)
- MySQL utilisé avec InnoDB[17], Falcon[18], ou le moteur de stockage Archive.
- Netezza
- ObjectStore
- Oracle Database toutes les versions depuis Oracle 3[19]
- PostgreSQL[20]
- RDM Embedded[21]
- REAL Server
- SAP HANA
- ScimoreDB
- sones GraphDB [22]
- Sybase SQL Anywhere
- Sybase IQ
- ThinkSQL
- Zope Object Database[23]
Autres logiciels utilisant MVCC
- Infinispan [24]
- EHcache (v. 1.6.0-beta4) [25]
- Clojure language software transactional memory
- Subversion et de nombreux autres gestionnaires de source.
- pojo-mvcc - a lightweight MVCC implementation written in the Java programming language [26]
Notes et références
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Multiversion concurrency control » (voir la liste des auteurs).
- (en) « Refs and Transactions », sur clojure.org (consulté le ).
- Philip Bernstein and Nathan Goodman, « Concurrency Control in Distributed Database Systems », ACM Computing Surveys,
- Reed, D.P., « Naming and Synchronization in a Decentralized Computer System », MIT dissertation,
- Berkeley DB Reference Guide: Degrees of Isolation
- Bigdata Blog
- DB2 Version 9.7 LUW Information Center, Currently committed semantics improve concurrency
- TM1 9.5.2 Information Center, Parallel Interaction
- Graves, Steve, « Multi-Core Software: To Gain Speed, Eliminate Resource Contention », RTC Magazine,
- White paper by Roman Rokytsky « Firebird and Multi Version Concurrency Control »(Archive.org • Wikiwix • Archive.is • Google • Que faire ?) (consulté le )
- Multi-Version Concurrency Control in the H2 Database Engine
- (en) « Hybrid Data Management, Integration & Analytics / Actian », sur Actian (consulté le ).
- Bill Todd, « InterBase: What Sets It Apart » [archive du ], (consulté le )
- About XtraDB, About XtraDB
- About PBXT, About PBXT
- (en) « WiredTiger Storage Engine — MongoDB Manual 3.4 », sur docs.mongodb.com (consulté le )
- MySQL 5.1 Reference Manual, Section 14.2.12: Implementation of Multi-Versioning
- ou Maria MySQL 5.1 Reference Manual, « Section 14.6.1: Falcon Features »(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)
- Oracle Database Concepts: Chapter 13 Data Concurrency and Consistency Multiversion Concurency Control
- PostgreSQL 9.1 Documentation, Chapter 13: Concurrency Control
- RDM Embedded 10.1 Reference Manual, d_trrobegin
- [1]
- Proposal for MVCC in ZODB « Copie archivée » (version du sur Internet Archive)
- [2]
- ehcache site
- pojo-mvcc project home
Voir aussi
Bibliographie
- 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)
Articles connexes
- Timestamp-based concurrency control
- Clojure
- Read-copy-update
- Vector clock