Multiversion Concurrency Control

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 (T_i) lire la plus récente version d'un objet qui précède l'estampille de la transaction en cours (TS(T_i)).

Si une transaction (T_i) nécessite d'écrire un objet, et qu'une autre transaction (T_k) fait de même, l'estampille de T_i devra précéder celle de T_k (c'est-à-dire TS(T_i) < TS(T_k)) 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 T_i 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(T_i) < RTS(P)), la transaction T_i est abandonnée et ré exécutée. Dans le cas contraire, T_i 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(T_i).

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).

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

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 à :

À 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].

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.

• 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)[14] - [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]

• JBoss Cache (v. 3.0) MVCC has landed
• 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]

• (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).