Control de concurrencia multiversion - Multiversion concurrency control

El control de concurrencia de múltiples versiones ( MCC o MVCC ), es un método de control de concurrencia comúnmente utilizado por los sistemas de administración de bases de datos para proporcionar acceso concurrente a la base de datos y en lenguajes de programación para implementar la memoria transaccional .

Descripción

Sin control de concurrencia, si alguien está leyendo de una base de datos al mismo tiempo que otra persona está escribiendo en ella, es posible que el lector vea un dato a medio escribir o inconsistente . 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 haya depositado 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 contención, 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 manera, cada usuario conectado a la base de datos ve una instantánea de la base de datos en un instante particular en el tiempo. Los demás usuarios de la base de datos no verán los cambios realizados por un escritor hasta que se hayan completado (o, en términos de la base de datos: hasta que se haya confirmado la transacción ).

Cuando una base de datos 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 tanto, hay varias 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 un estado de los datos como cuando comenzó la transacción.

MVCC proporciona vistas coherentes en un momento determinado . Las transacciones de lectura en MVCC suelen utilizar una marca de tiempo o un 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 quedan 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 barrer y eliminar periódicamente las versiones obsoletas. A menudo, este es un proceso de parada del mundo que atraviesa 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 la recreación de versiones anteriores de datos. La principal limitación inherente de este último enfoque es que cuando hay cargas de trabajo intensivas en actualizaciones, la parte del registro de deshacer se queda sin espacio y luego las transacciones se cancelan porque no se les puede dar su instantánea. Para una base de datos orientada a documentos , también permite que el sistema optimice documentos escribiendo documentos completos en secciones contiguas del disco; cuando se actualiza, el documento completo se puede reescribir en lugar de recortar partes o mantenerlas en un enlace, no estructura de base de datos contigua.

Implementación

MVCC utiliza marcas de tiempo ( TS ) e identificadores de transacciones en aumento para lograr la coherencia transaccional . MVCC asegura que una transacción ( T ) nunca tenga que esperar para leer un objeto de base de datos ( P ) manteniendo varias versiones del objeto. Cada versión del objeto P tiene tanto una marca de tiempo de lectura ( RTS ) como 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 sucediendo en el 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 que el objeto Write Operation ( WTS ) tenga éxito. No se puede completar una escritura si hay otras transacciones pendientes con una marca de tiempo de lectura ( RTS ) anterior al 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 marca de tiempo ( 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 marca de tiempo de lectura actual del objeto, TS ( T _i ) < RTS ( P ), la transacción se cancela 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 la marca de tiempo de lectura / escritura TS de la nueva versión en la marca de tiempo de la transacción TS ← TS ( T _i ).

El inconveniente 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 cargas de trabajo que involucran principalmente valores de lectura de la base de datos. MVCC es particularmente experto en implementar un verdadero aislamiento de instantáneas , algo que otros métodos de control de concurrencia frecuentemente hacen de manera incompleta o con altos costos de rendimiento.

Ejemplos de

Lectura y escritura simultánea

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

T0 escribió Object 1 = "Foo" y Object 2 = "Bar". 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 que T1 se confirme, momento en el que la versión 0 del Objeto 1 se puede recolectar como basura.

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

Hay una nueva versión a partir del momento 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 el Objeto 2 = "Barra" y Objeto 1 = "Hola". Así es como el control de simultaneidad de múltiples versiones permite lecturas de aislamiento de instantáneas sin ningún bloqueo.

Historia

El control de concurrencia de múltiples versiones se describe con cierto detalle en el artículo de 1981 "Control de concurrencia en sistemas de bases de datos distribuidos" por Phil Bernstein y Nathan Goodman, entonces empleado por Computer Corporation of America . El artículo de Bernstein y Goodman cita una disertación de 1978 de David P. Reed que describe con bastante claridad MVCC y afirma que es un trabajo original.

El primer producto de software de base de datos comercial 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 .

Ver también

• Lista de bases de datos que utilizan MVCC
• Leer-copiar-actualizar
• Control de simultaneidad basado en marcas de tiempo
• Reloj de vector
• Sistema de control de versiones

Referencias

Otras lecturas

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