Control de concurrencia multiversión

Control de concurrencia multiversión (MCC o MVCC), es un método de control de concurrencia comúnmente utilizado por los sistemas de gestión de bases de datos para proporcionar acceso simultáneo a la base de datos y en lenguajes de programación para implementar la memoria transaccional.

Descripción

Sin el control de simultaneidad, si alguien lee de una base de datos al mismo tiempo que otra persona escribe en ella, es posible que el lector vea un dato incoherente o a medio escribir. Por ejemplo, al realizar una transferencia bancaria entre dos cuentas bancarias, si un lector lee el saldo en el banco cuando el dinero se ha retirado de la cuenta original y antes de que se deposite en la cuenta de destino, parecería que el dinero ha desaparecido de la cuenta. 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 y escritura. Se sabe que los bloqueos crean conflictos, especialmente entre transacciones de lectura larga y transacciones de actualización. MVCC tiene como objetivo resolver el problema manteniendo múltiples copias de cada elemento de datos. De esta forma, cada usuario conectado a la base de datos ve una instantánea de la base de datos en un instante particular. Cualquier cambio realizado por un escritor no será visto por otros usuarios de la base de datos hasta que se hayan completado los cambios (o, en términos de base de datos: hasta que se haya confirmado la transacción).

Cuando una base de datos de MVCC necesita actualizar un dato, no sobrescribirá el elemento de datos original con datos nuevos, sino que creará una versión más nueva del elemento de datos. Por lo tanto, hay múltiples versiones almacenadas. La versión que ve cada transacción depende del nivel de aislamiento implementado. El nivel de aislamiento más común implementado con MVCC es el aislamiento de instantáneas. Con el aislamiento de instantáneas, una transacción observa el estado de los datos a partir del momento en que comenzó la transacción.

MVCC proporciona vistas coherentes en un punto en el tiempo. Las transacciones de lectura en MVCC generalmente usan una marca de tiempo o ID de transacción para determinar qué estado de la base de datos leer y leer estas versiones de los datos. Las transacciones de lectura y escritura están así aisladas entre sí sin necesidad de bloqueo. 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 nueva, mientras que las lecturas simultáneas acceden a una versión anterior.

MVCC presenta el desafío de cómo eliminar versiones que se vuelven obsoletas y nunca se leerán. En algunos casos, se implementa un proceso para revisar y eliminar periódicamente las versiones obsoletas. Este es a menudo un proceso de parada del mundo que atraviesa una tabla completa y la vuelve a escribir con la última versión de cada elemento de datos. PostgreSQL puede usar 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 mantiene la última versión confirmada. El registro de deshacer permite la recreación de versiones anteriores de datos. La principal limitación inherente de este último enfoque es que cuando hay cargas de trabajo de actualización intensiva, la parte del registro de deshacer se queda sin espacio y luego las transacciones se abortan porque no se les puede dar su instantánea. Para una base de datos orientada a documentos, también permite que el sistema optimice los documentos al escribir documentos completos en secciones contiguas del disco; cuando se actualiza, el documento completo se puede volver a escribir en lugar de fragmentos cortados o mantenidos en un enlace, no estructura de base de datos contigua.

Implementación

MVCC utiliza marcas de tiempo (TS) y identificadores de transacción crecientes para lograr coherencia transaccional. MVCC asegura 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 en particular T_i lea la versión más reciente del objeto que precede a la Marca de tiempo de lectura RTS(T_i).

Si la transacción T_i quiere Escribir al objeto P, y también hay otra transacción T_k al mismo objeto, la marca de tiempo de lectura RTS(T_i) debe preceder a la marca de tiempo de lectura RTS (T_k), es decir, RTS(T_i) < RTS(T_k), para el objeto Operación de escritura (WTS) para tener éxito. Una escritura no puede completarse si hay otras transacciones pendientes con una marca de tiempo de lectura anterior (RTS) en el mismo objeto. Al igual que hacer cola en la tienda, no puede completar su transacción de pago hasta que los que están frente a usted hayan completado la suya.

Para reafirmar; cada objeto (P) tiene una Timestamp (TS), sin embargo, si la transacción T_i quiere Escribir en un objeto, y la transacción tiene una Marca de tiempo (TS) que es anterior a la actual del objeto Leer marca de tiempo, TS(T_i) < RTS(P), 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, T_i crea una nueva versión del objeto P y establece el lectura/escritura de la marca de tiempo TS de la nueva versión a la marca de tiempo de la transacción TS ← TS(T_i).

La desventaja de este sistema es el costo de almacenar múltiples versiones de objetos en la base de datos. Por otro lado, las lecturas nunca se bloquean, lo que puede ser importante para las cargas de trabajo que involucran principalmente la lectura de valores de la base de datos. MVCC es particularmente hábil para implementar un verdadero aislamiento de instantáneas, algo que otros métodos de control de concurrencia suelen hacer de forma incompleta o con altos costos de rendimiento.

Ejemplos

Lectura y escritura simultáneas

En Time = 1, el estado de una base de datos podría ser:

T0 escribió Objeto 1="Foo" y Objeto 2="Barra". Después de eso, T1 escribió Objeto 1="Hola" dejando el Objeto 2 en su valor original. El nuevo valor del Objeto 1 reemplazará el valor en 0 para todas las transacciones que comiencen después de las confirmaciones de T1, momento en el cual la versión 0 del Objeto 1 puede recolectarse como basura.

Si una transacción de ejecución prolongada T2 inicia una operación de lectura del Objeto 2 y el Objeto 1 después de que T1 se confirma y hay una transacción de actualización simultánea T3 que elimina el Objeto 2 y agrega el Objeto 3 = "Foo-Bar", el estado de la base de datos se verá así en el momento 2:

Hay una nueva versión a partir del tiempo 2 del Objeto 2 que está marcado como eliminado y un nuevo Objeto 3. Dado que T2 y T3 se ejecutan simultáneamente, T2 ve la versión de la base de datos antes de 2, es decir, antes de que T3 confirme las escrituras, como tal T2 lee Objeto 2="Barra" y Objeto 1="Hola". Así es como el control de concurrencia multiversión permite lecturas de aislamiento de instantáneas sin bloqueos.

Historia

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" por Phil Bernstein y Nathan Goodman, entonces empleados por Computer Corporation of America. El artículo de Bernstein y Goodman cita una disertación de 1978 de David P. Reed que describe claramente a MVCC y lo afirma como un trabajo original.

El primer producto de software de base de datos comercial de envío con MVCC fue VAX Rdb/ELN, lanzado en 1984 y creado en Digital Equipment Corporation por Jim Starkey. Starkey pasó a crear la segunda base de datos MVCC comercialmente exitosa: InterBase.