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

## 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"
de Philip Bernstein et Nathan Goodman alors employés de la société Computer Corporation of America. Le document de Bernstein (en) et Goodman cite une dissertation de 1978 de David P. Reed (en) 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 (en)
* Berkeley DB
* Bigdata
* CouchDB
* IBM DB2 depuis IBM DB2 9.7 LUW ("Cobra") avec un niveau d'isolation CS - en mode CURRENTLY COMMITTED
* IBM Cognos TM1 versions 9.5.2 et plus
* Drizzle (en)
* eXtremeDB (en)
* Firebird
* FLAIM
* GE Smallworld Version Managed Data Store
* H2 Database Engine (expérimental depuis la version 1.0.57 du 2007-08-25)
* HSQLDB (depuis la version 2.0)
* Ingres
* InterBase (toutes les versions)
* MariaDB (fork de MySQL) lorsqu'il est utilisé avec XtraDB (développé par Percona (en) Inc., XtraDB est un moteur de stockage qui est un fork d'InnoDB et qui est inclus dans les sources et binaires de MariaDB) ou PBXT (développé par PrimeBase (en) Technologies)$^,$.
* MarkLogic Server (en)
* Microsoft SQL Server (à partir de SQL Server 2005)
* MongoDB (avec le moteur de stockage WiredTiger à partir de la Version 3.0)
* MySQL utilisé avec InnoDB, Falcon, ou le moteur de stockage Archive.
* Netezza (en)
* ObjectStore
* Oracle Database toutes les versions depuis Oracle 3
* PostgreSQL
* RDM Embedded
* REAL Server (en)
* SAP HANA
* ScimoreDB
* sones GraphDB (en)
* Sybase SQL Anywhere (en)
* Sybase IQ
* ThinkSQL
* Zope Object Database

## Autres logiciels utilisant MVCC

* JBoss Cache (v. 3.0) MVCC has landed
* Infinispan
* EHcache (en) (v. 1.6.0-beta4)
* 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