# Multiversion concurrency control

El control de concurrencia mediante versiones múltiples (Multiversion concurrency control o MVCC) es un método para control de acceso generalmente usado por SGBDs para proporcionar acceso concurrente a los datos, y en lenguajes de programación para implementar concurrencia.
Aplicado a una base de datos el procedimiento consistiría en implementar las actualizaciones de datos no borrando los datos antiguos y sobreescribiéndolos con los nuevos, sino marcando los antiguos como obsoletos y añadiendo los nuevos. De ese modo habrá en algún momento más de una versión de los mismos datos almacenada, teniendo validez solo la versión más reciente. Se evita así al sistema gestor de la base de datos dedicar tiempo a rellenar huecos en memoria o disco, al precio de tener que recorrer periódicamente la memoria o el disco para eliminar dichos objetos obsoletos. En el caso de una base de datos documental esta estrategia permite optimizar los documentos escribiéndolos en memoria contigua, evitando así tener un documento parcheado o con una lista encadenada de sus piezas en una estructura no contigua.
MVCC también proporciona vistas consistentes en tiempo. La lectura de transacciones en MVCC usan típicamente marca de tiempo o ID de transacción para determinar qué estado de la base de datos leer. Las lecturas se pueden así independizar de las escrituras a merced de la conservación de las versiones con valores antiguos, y se evitan así los procesos de bloqueo o de exclusión mutua. Las escrituras afectan a futuras versiones, pero el ID de transacción en curso garantiza la consistencia ya que las escrituras posteriores se contemplarán más tarde.
Dicho de otro modo, MVCC proporciona a cada usuario conectado a la base de datos una instantánea de la misma para él solo. Cualquier cambio que se haga no será visible a los demás usuarios hasta que la transacción se haya completado.

## Implementación

MVCC usa marcas de tiempo o identificadores de transacción crecientes para conseguir consistencia transaccional. Asegura que ninguna transacción tenga que esperar por un objeto de la base de datos a base de mantener varias versiones de ese objeto. Cada versión tiene asociada su marca de tiempo de escritura por el que permite leer a una transacción hecha en el momento t$_i$ los objetos más recientes que la preceden.
Si una transacción t$_i$ quiere escribir sobre un objeto, y además hay otra transacción t$_k$, la marca de tiempo de t$_i$ debe preceder la marca de tiempo de t$_k$ para que la escritura sea aceptada. Es lo mismo que decir que una escritura no puede completarse si hay transacciones pendientes con una marca de tiempo anterior.
Cada objeto debe tener también una marca de tiempo de lectura, y si una transacción t$_i$ quiere escribir sobre un objeto P, y la marca de tiempo de esa transacción es anterior a la de lectura del objeto, se aborta la transacción t$_i$ y se comienza de nuevo. En caso contrario, t$_i$ crea una nueva versión de P y establece sus marcas de tiempo de lectura y escritura igual a su marca de tiempo.
El inconveniente obvio de este mecanismo está en el coste de almacenar versiones múltiples del mismo objeto. Por otro lado las lecturas nunca se bloquean, lo que favorece aquellas aplicaciones que realizan muchas lecturas de la base de datos. El método MVCC está particularmente adaptado a la toma de instantáneas aisladas, algo que otros métodos de concurrencia no lo hacen bien o a un coste muy alto.

## Ejemplo

El sistema MVCC guarda las distintas versiones de los objetos en la base de datos mientras haya alguien trabajando con alguna de ellas:
| Tiempo | Objeto 1 | Objeto 2 |
| t$_1$ | "Hola" | "Bar" |
| t$_0$ | "Foo" | "Bar" |
Lo que nos indica que el estado actual de la base de datos es Objeto 1="Hola", Objeto 2="Bar", pero previamente Objeto 1 tuvo el valor "Foo", valor que no ha desaparecido ya que la base de datos mantiene versiones múltiples. Ya se borrará cuando no trabaje nadie con ella.
Si una transacción larga inicia una operación de lectura, operará con los valores en t$_1$ y verá siempre ese estado. Si mientras tanto se produjera una actualización durante esa transacción de larga duración que cambiara el valor de Objeto 2 por "Foo-Bar", el estado de la base de datos tendría este aspecto:
| Tiempo | Objeto 1 | Objeto 2 |
| t$_2$ | "Hola" | "Foo-Bar" |
| t$_1$ | "Hola" | "Bar" |
| t$_0$ | "Foo" | "Bar" |
Vemos que ha aparecido una nueva versión en el instante t$_2$. Hay que hacer notar que la transacción de larga duración sigue teniendo acceso a la instantánea coherente en t$_1$, aunque se hayan añadido datos en el instante t$_2$, por lo que la lectura por la transacción de larga duración está aislada de otras que posteriormente modifiquen los datos. De este modo MVCC posibilita lecturas aisladas ACID sin bloqueos (sin embargo, las transacciones con escritura siguen necesitando bloqueos).

## Historia

El mecanismo de control de concurrencia mediante versiones múltiples está descrito en detalle en el artículo de 1981 de Philip Bernstein y Nathan Goodman "Concurrency Control in Distributed Database Systems", por entonces empleados en Computer Corporation of America. El artículo de Bernstein y Goodman cita una disertación de 1978 por David P. Reed que describe claramente MVCC y la reclama como original.
La primera base de datos comercial con MVCC fue VAX Rdb/ELN de Digital. La segunda fue InterBase, todavía activa.