control de concurrencia multiversión

El control de concurrencia multiversión ( MCC o MVCC ) es un método de control de concurrencia sin bloqueo comúnmente utilizado por los sistemas de gestión de bases de datos para proporcionar acceso concurrente a la base de datos y en los lenguajes de programación para implementar memoria transaccional . ^{[ 1 ]}

Sin control de concurrencia, si alguien está leyendo de una base de datos al mismo tiempo que otro está escribiendo en ella, es posible que el lector vea datos incompletos o inconsistentes . Por ejemplo, al realizar una transferencia bancaria entre dos cuentas, si un lector consulta el saldo del banco cuando el dinero se ha retirado de la cuenta original y antes de que se haya depositado en la cuenta de destino, parecería que el dinero ha desaparecido del banco. El aislamiento es la propiedad que proporciona garantías en los accesos concurrentes a los datos. El aislamiento se implementa mediante un protocolo de control de concurrencia . La forma más sencilla es hacer que todos los lectores esperen hasta que el escritor termine, lo que se conoce como bloqueo de lectura/escritura . Se sabe que los bloqueos generan contención , especialmente entre transacciones de lectura largas y transacciones de actualización. MVCC busca resolver este problema manteniendo múltiples copias de cada elemento de datos. De esta manera, cada usuario conectado a la base de datos ve una instantánea de la base de datos en un instante determinado. Los cambios realizados por un escritor no serán visibles para los demás usuarios de la base de datos hasta que se hayan completado (o, en términos de bases de datos: hasta que se haya confirmado la transacción ).

Cuando una base de datos MVCC necesita actualizar un dato, no sobrescribe el dato original con datos nuevos, sino que crea una versión más reciente. Por lo tanto, se almacenan varias versiones. La versión que ve cada transacción depende del nivel de aislamiento implementado. El nivel de aislamiento más común en MVCC es el aislamiento de instantánea . Con este nivel, una transacción observa el estado de los datos tal como estaba cuando se inició.

MVCC proporciona vistas consistentes en un momento dado . Las transacciones de lectura en MVCC suelen usar una marca de tiempo o un ID de transacción para determinar qué estado de la base de datos leer, y leen estas versiones de los datos. De esta forma, las transacciones de lectura y escritura están aisladas entre sí sin necesidad de bloqueos. Sin embargo, a pesar de que los bloqueos son innecesarios, algunas bases de datos MVCC, como Oracle, los utilizan. Las escrituras crean una versión más reciente, mientras que las lecturas concurrentes acceden a una versión anterior.

MVCC plantea el desafío de cómo eliminar las versiones obsoletas que nunca se leerán. En algunos casos, se implementa un proceso para revisar periódicamente y eliminar las versiones obsoletas. Este suele ser un proceso de detención total que recorre una tabla completa y la reescribe con la última versión de cada elemento de datos. PostgreSQL puede utilizar este enfoque con su proceso VACUUM FREEZE . Otras bases de datos dividen los bloques de almacenamiento en dos partes: la parte de datos y un registro de deshacer. La parte de datos siempre conserva la última versión confirmada. El registro de deshacer permite recrear versiones anteriores de los datos. La principal limitación inherente de este último enfoque es que, cuando hay cargas de trabajo intensivas en actualizaciones, el registro de deshacer se queda sin espacio y las transacciones se abortan, ya que no se les puede asignar su instantánea. Para una base de datos orientada a documentos, también permite que el sistema optimice los documentos escribiéndolos completos en secciones contiguas del disco; al actualizarse, se puede reescribir el documento completo en lugar de cortar fragmentos o mantenerlos en una estructura de base de datos vinculada y no contigua.

MVCC utiliza marcas de tiempo ( TS ) e identificadores de transacción incrementales para lograr consistencia transaccional . MVCC garantiza que una transacción ( T ) nunca tenga que esperar para leer un objeto de base de datos ( P ) al mantener varias versiones del objeto. Cada versión del objeto P tiene una marca de tiempo de lectura ( RTS ) y una marca de tiempo de escritura ( WTS ) que permite que una transacción particular T _i lea la versión más reciente del objeto que precede a la marca de tiempo de lectura RTS ( T _i ) de la transacción.

Si la transacción T _i quiere escribir en el objeto P , y también hay otra transacción T _k en curso sobre el mismo objeto, la marca de tiempo de lectura ( RTS) de T _i debe preceder a la marca de tiempo de lectura ( RTS ) de T _k , es decir, RTS ( T _i ) < RTS ( T _k ) , para que la operación de escritura ( WTS ) sobre el objeto tenga éxito. Una escritura no puede completarse si hay otras transacciones pendientes con una marca de tiempo de lectura ( RTS ) anterior sobre el mismo objeto. Al igual que las personas que hacen fila en una tienda, no pueden completar su transacción de pago hasta que quienes están delante completen la suya.

En resumen, cada objeto ( P ) tiene una marca de tiempo ( TS ). Sin embargo , si la transacción Ti _quiere escribir en un objeto y su marca de tiempo ( TS ) es anterior a la marca de tiempo de lectura actual del objeto, TS ( Ti ₎ < RTS ( P ), entonces la transacción se aborta y se reinicia. (Esto se debe a que una transacción posterior ya depende del valor anterior). De lo contrario, Ti crea una nueva versión del objeto P y establece la marca de tiempo de lectura/escritura TS de la nueva versión a la marca de tiempo de la _transacción TS ← TS ( Ti ₎ . ^{[ 2 ]}

La desventaja de este sistema radica en el costo de almacenar múltiples versiones de objetos en la base de datos. Por otro lado, las lecturas nunca se bloquean, lo cual puede ser importante para cargas de trabajo que implican principalmente la lectura de valores de la base de datos. MVCC destaca por su capacidad para implementar un verdadero aislamiento de instantáneas , algo que otros métodos de control de concurrencia suelen hacer de forma incompleta o con un alto costo en términos de rendimiento.

Una estructura para almacenar un registro ( fila ) para una base de datos usando MVCC podría verse así en Rust .

struct Record { /// Inserta el identificador de transacción stamp. insert_transaction_id : u32 ,/// Eliminar el sello de identificador de transacción. delete_transaction_id : u32 ,/// La longitud de los datos. data_length : u16 ,/// El contenido del registro. datos : Vec <u8> , }

Insertar identificador de transacción : 32 bits

El identificador de transacción MVCC para la inserción.

Eliminar identificador de transacción : 32 bits

El identificador de transacción MVCC para eliminar.

Longitud de los datos : 16 bits

La longitud de los datos.

Datos : Variable

El contenido almacenado en el registro.

El control de concurrencia multiversión se describe con cierto detalle en el artículo de 1981 "Control de concurrencia en sistemas de bases de datos distribuidas " ^{[ 3 ]} de Phil Bernstein y Nathan Goodman, quienes entonces trabajaban para Computer Corporation of America . El artículo de Bernstein y Goodman cita una tesis doctoral de 1978 ^{[ 4 ]} de David P. Reed que describe con bastante claridad el MVCC y lo presenta como un trabajo original.

El primer producto de software de base de datos comercial que incorporaba MVCC fue VAX Rdb/ELN , lanzado en 1984, ^{[ 5 ]} y creado en Digital Equipment Corporation por Jim Starkey . Starkey continuó ^{[ 6 ]} creando la segunda base de datos MVCC de éxito comercial: InterBase . ^{[ 7 ]}

• Lista de bases de datos que utilizan MVCC
• Leer-copiar-actualizar
• Control de concurrencia basado en marcas de tiempo
• Reloj vectorial
• Control de versiones

• Gerhard Weikum, Gottfried Vossen, Sistemas de información transaccionales: teoría, algoritmos y práctica del control y la recuperación de la concurrencia , Morgan Kaufmann, 2002, ISBN 1-55860-508-8