Consideraciones de las Bases de Datos

Distribuidos

Dr. Fernando Pech Mayauxtecomp@gmail.com

fpech@tamps.cinvestav.mx

August 14, 2019

Abstract

1 Aislamiento en las transacciones

1.1 Introducción

El aislamiento es una de las 4 propiedades ACID (Atomicidad, Consistencia,Aislamiento, Durabilidad) aplicables a una base de datos (BD) transaccional.Esta propiedad que especifica cómo se gestionan los cambios producidos por unaoperación se hacen visibles en la base de datos.

Los sistemas de bases de datos (SBD) presentan múltiples niveles de ais-lamiento, sin embargo, no todos los tipos de bases de datos soportan cada nivelde aislamiento. Algunos proveedores de base de datos utilizan diferentes nom-bres para los niveles de aislamientoque van desde la serialización en el extremosuperior (read committed) hasta lectura comprometida (read committed) o lec-tura no comprometida (read uncommitted) en el extremo inferior. El aislamientoes mas complejo de lo que parece y los niveles exponen a una aplicación a tiposde errores de concurrencia marcadamente diferentes. Normalmente los nivelesde aislamiento más bajos permiten una concurrencia mayor y una menos so-brecarga. Sin embargo, muchos usuarios de bases de datos se apegan al nivelde aislamiento predeterminado de cualquier sistema de base de datos que esténutilizando sin considerar qué nivel de aislamiento es óptimo para su aplicación.

La gran mayoŕıa de los sistemas de bases de datos ampliamente utilizadostales como Oracle, IBM DB2, Microsoft SQL Server, SAP HANA, MySQL yPostgreSQL, no garantizan ningún tipo de serialización por defecto. Los nivelesde aislamiento más débiles pueden provocar errores de concurrencia en unaaplicación y experiencias negativas para el usuario. Por lo tanto, es de granimportancia que los usuarios la

Es muy importante que un usuario de la BD conozca el nivel de aislamientoy qué errores de concurrencia pueden surgir como resultado. Este documentodescribe los niveles de aislamiento de las BD, sus ventajas y los tipos de erroesque pueden producir.

1

Listing 1: Ejemplo de transacción en MySQL

1 START TRANSACTION;

2 SELECT balance FROM checking WHERE customer_id = 10233276;

3 UPDATE checking SET balance = balance -200.00 WHERE

customer_id = 10233276;

4 UPDATE savings SET balance = balance + 200.00 WHERE

customer_id = 10233276

5 COMMIT;

1.2 Niveles de aislamiento

El aislamiento de la base de datos se refiere a la capacidad de una base de datospara permitir que una transacción se ejecute como si no hubiera otras transac-ciones en ejecución simultánea; los resultados de una transacción normalmenteson invisibles para el resto de las transacciones hasta que no se complete. Suobjetivo es evitar las lecturas y escrituras de datos temporales, abortados o in-correctos en las transacciones concurrentes. De esta manera nos aseguramos, deque si se ejecuta el resumen de la cuenta bancaria, después de la ĺınea 3 peroantes de la ĺınea 4 (ver Listin 1), seguirán apareciendo 200 pesos en la cuentabancaria.

Cabe recordar que cada motor de almacenamiento implementa los nivelesde aislamiento de una forma ligeramente diferente y no nesariamente coincidenunos con otros, por lo tanto, es necesario leer los manuales del motor de ais-lamiento que se desee utilizar. Mientras mejor sea el aislamiento, el costo enrendimiento es mayor respecto a la latencia de la transacción (tiempo en quese complete una transacción) o rendimiento (cuántas transacciones por segundopuede completar el sistema).

El estándar SQL define 4 niveles de aislamiento con reglas espećıficas paralos rangos que se visibles o invisibles dentro y fuera de una transacción:

1. READ UNCOMMITED. En este nivel, las transacciones pueden verlos resultados de las transacciones que no se han asignado.

• Inconvenientes. Pueden surgir muchos problemas a no ser que sesepa realmente lo que se está haciendo. Se utiliza poco porque surendimiento es muy pobre. La lectura de datos sin asignación seconoce como lectura sucia (dirty read).

2. READ COMMITED. Es el nivel de aislamiento predeterminado en lamayoŕıa de los SBDDs (a excepción de MySQL). Una transacción sólopuede ver los cambios realizaciones, por las transacciones ya realizadas,cuando empieza y sólo podrá ver los cambios realizados por las transac-ciones que ya se han asignado.

• Inconvenientes. Permite la lectura irrepetible (nonrepeatable read),lo que significa que podemos ejecutar dos veces la misma instruccióny ver datos diferentes.

2

3. REAPETABLE READ. Es el nivel de aislamiento transaccional prede-terminado de MySQL. Resuelve los problemas de READ UNCOMMITEDgarantizando que cualquier fila que lea una transacción será igual en lassiguientes lecturas dentro de la misma transacción.

• Inconvenientes. Permite la (lectura fantasma); esta lectura se pro-duce cuando se selecciona un rango de filas, otra transacción insertauna nueva fila en el rango y después se selecciona de nuevo el mismorango, de esto modo se verá una nueva fila fantasma. Por otra parte,InnoDB y Falcon resuelven el problema de las lecturas fantasma.

4. SERIALIZABLE. Es el máximo nivel de aislamiento, resuelve el prob-lema de la lectura fantasma mediante el forzamiento de las transaccionesa ordenarse para que no exista posibilidad de conflicto; es decir, colocaun bloque en cada fila que lee. En este nivel se pueden producir muchascontenciones de bloqueos y tiempos agotados.

1.3 Anomaĺıas en los niveles de aislamiento

Sin pérdida de generalidad, las anomaĺıas en los niveles de aislamiento se ex-plicarán con un ejemplo muy simple.

Asumamos que un cliente compra un producto online, se ejecuta las sigu-ientes transacciones:

• 1. Leer inventario antiguo

• 2. Escribe un nuevo inventario que sea uno menos de lo que se leyó en elpaso (1)

• 3. Inserte el nuevo pedido correspondiente a esta compra en la tabla depedidos

Si las transacciones anteriores se ejecuta en serie, todo el inventario inicialsiempre se contabilizará.

Si comenzamos con 42 productos, la suma de todo el inventario restante máslos pedidos en la tabla de pedidos será 42.

Pero ¿qué pasa si tales transacciones se ejecutan simultáneamente mediantelos 3 primeros niveles de aislamiento (READ UNCOMMITED, READ COM-MITED, REAPETABLE READ)?

1.3.1 Anomaĺıa de actualización perdida

Supongamos que dos transacciones que se ejecutan simultáneamente leen elmismo inventario inicial (42), y luego ambas intentan escribir el nuevo inven-tario de uno menor que el valor que leyeron (41) además del nuevo pedido.

En tal caso, el estado final es un inventario de 41, sin embargo, hay dosnuevos pedidos en la tabla de pedidos (para un total de 43 productos contabi-lizados).

3

¡Creamos un producto de la nada!. Claramente, esto es un error.

1.3.2 Anomaĺıa de escritura sucia

Como otro ejemplo, supongamos que estas mismas dos transacciones se ejecutansimultáneamente, pero esta vez la segunda transacción comienza entre los pasos(2) y (3) de la primera. En este caso, la segunda transacción lee el valor delinventario después de que se ha disminuido, es decir, lee el valor de 41 y lodisminuye a 40, y escribe el pedido. Mientras tanto, la primera transacción secanceló al escribir el pedido (por ejemplo, debido a un rechazo de la tarjeta decrédito).

En tal caso, durante el proceso de cancelación, la primera transacción vuelveal estado de la base de datos antes de comenzar (cuando el inventario era 42).Por lo tanto, el estado final es un inventario de 42 y una orden escrita (de lasegunda transacción).

De nuevo, ¡creamos un producto de la nada! Esto se conoce como la anomaĺıade escritura sucia (porque la segunda transacción sobrescribió el valor de laescritura de la primera transacción antes de decidir si se confirmaŕıa o anulaŕıa).

1.3.3 Anomaĺıa de lectura sucia

Como tercer ejemplo, supongamos que una transacción por separado realiza unalectura tanto del inventario como de la tabla de pedidos, para hacer un recuentode todos los productos que alguna vez existieron. Si se ejecuta entre los pasos(2) y (3) de una transacción de compra, verá un estado temporal de la basede datos en la que el widget ha desaparecido del inventario, pero aún no haaparecido como un pedido.

Parece que se ha perdido un producto, otro error en nuestra aplicación. Estose conoce como la anomaĺıa de lectura sucia, ya que a la transacción contable sele permitió leer el estado temporal (incompleto) de la transacción de compra.

1.3.4 Anomaĺıa de lectura no repetible

Como cuarto ejemplo, supongamos que una transacción separada verifica elinventario y adquiere más productos si quedan menos de 10 productos:

1 SI (LEER (Inventario) = (10 OR 11 OR 12))

2 Enviar algunos productos nuevos para reabastecer el inventario a través del envı́o estándar

3 SI (LEER (Inventario)

1.3.5 Anomaĺıa de lectura fantasma

Como quinto ejemplo, imagine una transacción que escanea la tabla de pedidospara calcular el precio máximo de un pedido y luego lo escanea nuevamente paraencontrar el precio promedio del pedido. Entre estos dos escaneos, se inserta unpedido extremadamente costoso que sesga tanto el promedio que se vuelve másalto que el precio máximo encontrado en el escaneo anterior.

Esta transacción devuelve un precio promedio que es mayor que el preciomáximo, una imposibilidad clara y un error que nunca sucedeŕıa en un sistemaserializable. Este error es ligeramente diferente de la anomaĺıa de lectura norepetible ya que cada valor que la transacción leyó permaneció igual entre losdos escaneos; la fuente del error es que se insertaron registros adicionales entreestos dos escaneos.

1.3.6 Anomaĺıa de inclinación de escritura

Como último ejemplo, suponga que la aplicación permite que el precio del pro-ducto cambie según el inventario. Por ejemplo, muchas aeroĺıneas aumentan elprecio del boleto a medida que disminuye el inventario de un vuelo. Supongaque la aplicación usa una fórmula para limitar la forma en que estas dos vari-ables se interrelacionan, por ejemplo:10I + P> = $500

donde I es inventario y P es el precio.

Antes de permitir que una compra tenga éxito, la transacción de compradebe verificar tanto el inventario como el precio para asegurarse de que no seviole la restricción anterior.

Si no se viola la restricción, puede continuar la actualización del inventariopor esa transacción de compra.

Del mismo modo, una transacción separada que implementa descuentos pro-mocionales especiales puede verificar tanto el inventario como el precio paraasegurarse de que no se viole la restricción al actualizar el precio como parte deuna promoción. Si no se viola, el precio puede actualizarse.

Ahora bien: imagine que estas dos transacciones se ejecutan al mismo tiempo:

• ambas leen el valor anterior de I y P y deciden independientemente quesus actualizaciones de inventario y precio respectivamente no violarán larestricción.

• Por lo tanto, proceden con sus actualizaciones.

¡Desafortunadamente, esto puede resultar en un nuevo valor de I y P queviola la restricción! Si uno se hubiera ejecutado antes que el otro, el primerohabŕıa tenido éxito y el otro habŕıa léıdo el valor de I y P después de que elprimero terminara y detectara que su actualización violaŕıa la restricción y, porlo tanto, no continuaŕıa.

5

Table 1: Niveles de aislamiento ANSI SQL.

Nivel Lecturassucias

Lecturasir-repetibles

Lecturasfantasmas

Lectura debloqueo

READ UNCOMMITED Śı Śı Śı NoREAD COMMITED No Śı Śı NoREPEATABLE READ No No Śı NoSERIALIZABLE No No No Śı

Pero como se estaban ejecutando simultáneamente, ambos ven el valor ante-rior y deciden incorrectamente que pueden continuar con la actualización. Esteerror se llama anomaĺıa de inclinación de escritura porque ocurre cuando dostransacciones leen los mismos datos pero actualizan subconjuntos disjuntos delos datos que se leyeron.

1.3.7 Anomaĺıas en SQL

En la Tabla 1 se resume los niveles de aislamiento de SQL y los tipos deanomaĺıas que presentan. A continuación se describen algunos inconvenientesen la descripción de las anomaĺıas en SQL.

1. Problema 1. En estándar SQL (como se aprecia en la Tabla 1) sólo definetres tipos de anomaĺıas. Sin embargo, a nivel práctico pueden presentarseotros tipos de errores de concurrencia en las transacciones ( los 6 citadosanteriormente), estos tipos de errores presentados en SQL están poco doc-umentados, lo que puede generar confusión y errores impredecibles duranteel desarrollo y ejecución de la aplicación.

2. Problema 2. No proporciona una definición precisa de los posibles estadosde la BD que se puede presentar en cualquier transacción. En la Tesisdoctoral de Atul Adya’s 1 describe con detalle la descripción de cada unade las anomaĺıas en los niveles de aislamiento. En un art́ıculo publicadopor Natacha Crooks et al [2] describe, desde el punto de vista del usuario,las anomaĺıas en el aislamiento.

3. Problema 3. El estándar no define ni proporciona restricciones de cor-rección en uno de los niveles de aislamiento reducido más populares uti-lizados en la práctica: el aislamiento de instantáneas (ni ninguna desus muchas variantes: PSI, NMSI, Read Atomic, etc.). Debido a esto hansurgido diferencias en las vulnerabilidades de concurrencia permitidas porel aislamiento de instantánea en todos los sistemas.

El aislamiento de instantáneas realiza todas las lecturas de datos a partirde una instantánea particular del estado de la base de datos que contienesolo datos confirmados. Esta instantánea se mantiene constante durante

1http://pmg.csail.mit.edu/papers/adya-phd.pdf

6

toda la vida de la transacción, por lo que se garantiza que todas las lec-turas sean repetibles (además de ser solo de datos confirmados). Además,las transacciones simultáneas que escriben los mismos datos detectan con-flictos entre śı y generalmente resuelven este conflicto abortando una delas transacciones en conflicto. Esto evita la anomaĺıa de la actualizaciónperdida. Sin embargo, los conflictos solo se detectan si las transaccionesen conflicto escriben un conjunto de datos superpuestos. Si los conjun-tos de escritura son disjuntos, estos conflictos no se detectarán. Por lotanto, el aislamiento de instantáneas es vulnerable a la anomaĺıa de incli-nación de escritura. Algunas implementaciones también son vulnerablesa la anomaĺıa de lectura fantasma.

4. Problema 4. El estándar SQL aparentemente da dos definiciones diferentesdel nivel de aislamiento SERIALIZABLE. Para el estándar SERIALIZABLEsignifica que el resultado final debe ser equivalente a un resultado quepodŕıa haber ocurrido si no hubiera concurrencia. Luego en la docu-mentación presenta la Tabla 1donde indica que el aislamiento SERIALIZABLEno permita lecturas sucias, lecturas no repetibles o lecturas fantasmas.Esta información es ambigua y, de hecho, ORACLE ha aprovechado estaambigüedad para justificar llamar a su implementación de aislamiento deinstantánea SERIALIZABLE.

Con lo anteriormente dicho, podemos concluir que es casi imposible dardefiniciones claras de los diferentes niveles de aislamiento disponibles paralos desarrolladores de aplicaciones, porque la vaguedad y las ambigüedadesen el estándar SQL ha llevado a diferencias semánticas entre implementa-ciones/sistemas.

1.3.8 Elegir el nivel de aislamiento

Cuando se desarrollan aplicaciones, quizás se ha tenido la duda sobre qué nivelde aislamiento elegir. Lo que se puede asegurar, es que los niveles de aislamientoreducido son peligrosos. Es muy complicado determinar qué errores de concur-rencia pueden presentarse.

Si cada sistema definió sus niveles de aislamiento utilizando la metodoloǵıa deCrooks et al. [2] al menos tendŕıa una definición precisa y formal de sus garant́ıasasociadas. Desafortunadamente, el formalismo del documento de Crooks es de-masiado avanzado para la mayoŕıa de los usuarios de BD, por lo que es pocoprobable que los proveedores de bases de datos adopten estos formalismos en sudocumentación en el corto plazo. Mientras tanto, la definición de niveles reduci-dos de aislamiento sigue siendo vaga en la práctica y riesgosa de usar. Además,incluso si pudiera saber exactamente qué errores de concurrencia son posiblespara un nivel de aislamiento en particular, escribir una aplicación de maneraque estos errores no sucedan en la práctica (o si lo hacen, que no causarán expe-riencias negativas para los usuarios de la aplicación) también es muy desafiante.

Si su SBD le da una opción, la opción correcta generalmente es evitar nivelesde aislamiento más bajos que el aislamiento serializable (para la gran mayoŕıade los sistemas de bases de datos, ¡realmente tiene que cambiar los valorespredeterminados para lograr esto!). Sin embargo, hay tres advertencias:

7

1. Es importante recordar que algunos sistemas definen el aislamiento SERIALIZABLEde manera incorrecta. Algunos le dan un significado algo más débil queel verdadero aislamiento serializable. Desafortunadamente, esto significaque simplemente elegir el nivel de aislamiento SERIALIZABLE en suSBD puede no ser suficiente para garantizar la serialización. Debe veri-ficar la documentación, del SBD a elegir, para asegurarse de que defineSERIALIZABLE de la siguiente manera: que el estado visible de la basede datos siempre es equivalente a un estado que podŕıa haber ocurrido sino hubiera concurrencia. De lo contrario, su aplicación probablementeserá vulnerable a la anomaĺıa de inclinación de escritura.

2. Como se mencionó anteriormente, el nivel de aislamiento serializable vienecon un costo de rendimiento. Dependiendo de la calidad de la arquitec-tura del sistema, el costo de rendimiento de la serialización puede sergrande o pequeño. En un trabajo de investigación de Faleiro y Heller-stein [3], demostraron que en un sistema bien diseñado, la diferencia derendimiento entre SERIALIZABLE y READ COMMITTED puede ser insignifi-cante. En algunos casos es posible que el nivel de aislamiento SERIALIZ-ABLE supera el nivel de aislamiento de manera sorprendente respecto aREAD COMMITTED. Si encuentra que el costo del aislamiento serializable ensu sistema es prohibitivo, probablemente debeŕıa considerar usar un SBDdiferente antes de considerar conformarse con un nivel de aislamiento re-ducido.

En los sistemas distribuidos, hay anomaĺıas importantes que pueden surgir(y lo hacen) incluso dentro de la clase de niveles de aislamiento serializ-ables. Para tales sistemas, es importante comprender las diferencias sutilesentre los elementos de la clase de aislamiento serializable (se sabe que laserialización estricta es la más segura).

1.4 Corrección de las anomaĺıas en el aislamiento serializ-able

La mayoŕıa de los SBD admiten múltiples niveles de aislamiento que permitena sus usuarios compensar la exposición a varios tipos de anomaĺıas y erroresde aplicación. Como hemos mencionado anteriormente, el nivel más alto decorrección sin errores ofrecido por los sistemas de bases de datos comercialesfue el aislamiento SERIALIZABLE en el que el sistema de la base de datos eje-cuta transacciones en paralelo, pero de una manera equivalente a como si seestuvieran ejecutando una tras otra. Este nivel de aislamiento se considerabaperfecto porque permit́ıa a los usuarios escribir código en la parte superior deun sistema de base de datos para evitar tener que razonar sobre los errores quepodŕıan surgir debido a la concurrencia. Siempre que el código de transacciónparticular sea correcto en el sentido de que si no se está ejecutando nada más almismo tiempo, la transacción llevará el estado actual de la base de datos de unestado correcto a otro estado correcto (donde ”correcto” se define como no vio-lar ninguna semántica de una aplicación), el aislamiento serializable garantizaráque la presencia de transacciones simultáneas no causará ningún tipo de condi-ciones de carrera que puedan permitir que la base de datos llegue a un estadoincorrecto. En otras palabras, el aislamiento serializable generalmente permite a

8

un desarrollador de aplicaciones evitar tener que razonar sobre la concurrencia,y solo enfocarse en corregir el código de un solo subproceso.

En tiempos antaños, tener un servidor de base de datos alojado en una sólamáquina f́ısica, el aislamiento serializable era suficiente; los proveedores de basesde datos nunca intentaron vender software de bases de datos con garant́ıas decorrección más fuertes que SERIALIZABLE. Sin embargo, a medida que lossistemas de bases de datos distribuidos y replicados han comenzado a prolif-erar en las últimas décadas, han comenzado a aparecer anomaĺıas y errores enlas aplicaciones incluso cuando se ejecutan sobre un sistema de base de datosque garantiza el aislamiento serializable. Como consecuencia, los proveedoresde sistemas de bases de datos comenzaron a lanzar sistemas con garant́ıas decorrección más fuertes que el aislamiento serializable, que prometen una faltade vulnerabilidad a estas nuevas anomaĺıas.

1.4.1 Serialización en un Sistema Distribuido

El aislamiento serializable es una garant́ıa de que aunque un sistema de base dedatos puede ejecutar transacciones en paralelo, el resultado final es equivalentea como si se estuvieran ejecutando uno tras otro.En un sistema replicado, la garant́ıa debe fortalecerse para evitar las anomaĺıasque solo ocurriŕıan en niveles más bajos de aislamiento en sistemas no repli-cados. Por ejemplo, supongamos que el saldo de la cuenta corriente de Alicia($50) se replica para que el mismo valor se almacene en los centros de datos enEuropa y Estados Unidos. Muchos sistemas no replican datos sincrónicamente adistancias tan grandes. Más bien, una transacción se completará primero en unaregión, y su actualización del sistema de base de datos puede replicarse después.Si se realiza un retiro de $20 simultáneamente en los Estados Unidos y Europa,se lee el saldo anterior ($ 50) en ambos lugares, se eliminan $ 20 y el nuevo saldo($ 30) se devuelve en ambos lugares y se replica en el otro centro de datos Estesaldo final es claramente incorrecto —- debeŕıa ser $ 10 — y fue causado porla ejecución simultánea de transacciones. El mismo resultado podŕıa ocurrir silas transacciones fueran en serie (una después de la otra) siempre y cuando lareplicación no se incluya como parte de la transacción (sino que ocurra después).Por lo tanto, se produce un error de concurrencia a pesar de la equivalencia aun pedido en serie.Rony Attar et al [1] expandieron el concepto de serialización para definir lacorrección en el contexto de los sistemas replicados.La idea básica es que todas las réplicas de un elemento de datos se comportencomo un único elemento de datos lógicos. Cuando se dice que una ejecuciónconcurrente de transacciones es equivalente a procesarlas en un orden en se-rie particular, esto implica que siempre que se lea un elemento de datos, elvalor devuelto será la escritura más reciente en ese elemento de datos por unatransacción previa en el orden de serie (equivalente). En este contexto, la escrit-ura más reciente significa la escritura por la transacción más cercana (anterior)en ese orden en serie. En nuestro ejemplo anterior, el retiro en Europa o elretiro en los EE. UU. Se ordenarán primero en el pedido en serie equivalente.Cualquiera que sea la segunda transacción, cuando lee el saldo, debe leer elvalor escrito por la primera transacción. Ronn Attar et al.[1] denominaron aesta garant́ıa serialización de una copia o 1SR debido la garant́ıa de aislamiento

9

es equivalente a la serialización en un sistema no replicado con una copia decada elemento de datos.

1.4.2 Anomaĺıas en la serializabilidad

Como se mencionó anteriormente, la serialización de una copia en sistemasreplicados es la garant́ıa de aislamiento idéntica a la serialización en sistemasno replicados.Existe una gran cantidad de de bases de datos que ofrecen un nivel de aislamientollamado serializability, pero muy pocos sistemas de bases de datos replica-dos ofrecen un nivel de aislamiento llamado serialización una copia.Para entenderlo mejor, es necesario explicar algunos desaf́ıos al escribir progra-mas libres de errores sobre sistemas que sólo garantizan la serialización.

Un sistema serializable solo garantiza que las transacciones se procesarán demanera equivalente a un pedido en serie. La garant́ıa de serialización por śısola no impone restricciones sobre cuál es este pedido en serie. En teoŕıa, unatransacción puede ejecutarse y comprometerse. Puede aparecer otra transacción,un largo peŕıodo de tiempo después de que la primera se comprometa, y proce-sarse de tal manera que el pedido en serie equivalente resultante coloque latransacción posterior antes de la anterior. En cierto sentido, la transacción pos-terior en el tiempo en el tiempo, y se procesa de modo que el estado final de labase de datos sea equivalente a la transacción que se ejecuta antes de las transac-ciones que se completaron antes de cuando comenzó. Un sistema serializable noevita esto. Tampoco un sistema serializable de una copia. No obstante, en lossistemas de servidor único, es fácil y conveniente evitar el viaje en el tiempo.Por lo tanto, la gran mayoŕıa de los sistemas de servidor único que garantizanla serialización también evitan los viajes en el tiempo. De hecho, era tan trivialevitar el viaje en el tiempo que la mayoŕıa de los sistemas serializables comer-ciales no lo consideraban lo suficientemente notable como para documentar suprevención de este comportamiento.

Por el contrario, en los sistemas distribuidos y replicados, es mucho menostrivial garantizar una falta de viaje en el tiempo, y muchos sistemas permitenalgunas formas de viaje en el tiempo en su comportamiento de procesamientode transacciones.

Existen distintas anomaĺıas de viaje en el tiempo (time-travel) que ocurrenen sistemas distribuidos y / o replicados aśı como errores de aplicación quepueden causar. Todas estas anomaĺıas son posibles bajo un sistema que sologarantiza la serialización de una copia. Por lo tanto, los proveedores suelendocumentar cuáles de estas anomaĺıas permiten y no permiten, lo que garantizaun nivel de corrección mayor que la serialización de una copia. A continuaciónse mencionan las anomaĺıas.

1. Escritura inmortal. Supongamos que el usuario de una aplicación ac-tualmente tiene un nombre a mostrar Daniel y decide cambiarlo a Danny.Accede a la interfaz de la aplicación y cambia su nombre para mostrar.Luego lee su perfil para asegurarse de que el cambio surta efecto y con-firma que śı. Dos semanas más tarde, cambia de opinión nuevamente ydecide que quiere cambiar su nombre para mostrar a Danger. Él va a la

10

Historial Ahora

Escribe nombre:Daniel

Escribe nombre:Danny

Escribe nombre:Danger

Retrocede en el tiempo

Las lecturas sólo ven el valor de la escritura final en orde serial

Escribe nombre:Daniel

Escribe nombre:Danny

Escribe nombre:Danger

Figure 1: Ejemplo de escritura inmortal

interfaz y cambia su nombre para mostrar, el sistema indica que el cambiofue exitoso. Pero cuando realiza una lectura en su perfil, todav́ıa muestrasu nombre como Danny. Puede regresar y cambiar su nombre un millónde veces. Cada vez, le dicen que el cambio fue exitoso, pero el valor de sunombre para mostrar en el sistema sigue siendo Danny (ver Figura 1).

Lo que sucedió es que, todas las escrituras viajaron en el tiempo en ordenserial de manera directa antes de que la transación cambiara el nombrea Danny. Por lo atnto, la transacción Danny sobrescribió el valor escritopor todas estas otras transacciones, a pesar de que ocurrió mucho antesque estas otras transacciones en tiempo real.El sistema decidió que el orden en serie al que estaba garantizando la equiv-alencia tiene la transacción Danny después de todas las otras transaccionesde cambio de nombre

Cuando la transacción Danny y/o las otras transacciones de cambio denombre también realizan una lectura en la base de datos, como parte dela misma transacción que la escritura en el nombre, la capacidad de viajaren el tiempo sin violar la serialización se vuelve mucho más dif́ıcil. Peropara las transacciones de escritura a ciegas, como estos ejemplos, el viajeen el tiempo es fácil de lograr.

En los sistemas de bases de datos replicados de forma aśıncrona multi-maestro, donde se permite que las escrituras ocurran en cualquiera de lasréplicas, es posible que ocurran escrituras conflictivas entre las réplicas.En tal escenario, es tentador aprovechar el viaje en el tiempo para crearuna escritura ciega inmortal, que permite la resolución de conflictos sinviolar la garant́ıa de serialización.

2. Lecturas obsoletas. El tipo más común de anomaĺıa que aparece ensistemas replicados, pero no en sistemas serializables de servidor único, esla anomaĺıa de lectura obsoleta.

Supongamos que Carlos tiene una cuenta bancaria con $50 restantes en lacuenta. Acude al cajero automático y retira $50. Luego, pide un recibocon su saldo bancario actual. El recibo (incorrectamente) indica que le

11

Historial Ahora

Escribe balance:$ 50

Escribe balance:$ 0 Lee balance:

Retrocede en el tiempo

Figure 2: Anomaĺıa de lectura obsoleta.

quedan $50 en su cuenta (cuando, en realidad ya no le queda dinero).Como resultado, Carlos se queda con una impresión incorrecta de cuántodinero tiene, y puede cometer errores de comportamiento en la vida real.Esta anomaĺıa ocurrió como resultado de una lectura obsoleta: su cuentaciertamente teńıa $50. Pero cuando el cajero automático realizó una solic-itud de lectura en la base de datos del banco para obtener su saldo actual,esta solicitud de lectura no reflejó la escritura en su saldo que ocurrió unossegundos antes cuando retiró dinero de su cuenta.

La anomaĺıa de lectura obsoleta es extremadamente común en los sistemasde bases de datos replicados asincrónicamente (como las réplicas de lecturaen MySQL o Amazon Aurora). La escritura (la actualización del saldo deCarlos) se dirige a una copia, que no se replica inmediatamente a la otracopia (ver Figura 2). Si la lectura se dirige a la otra copia antes de que lanueva escritura se haya replicado, verá un valor obsoleto.

La lectura obsoleta no viola la serialización. El sistema simplemente viajaen el tiempo para mantenerse en un punto de tiempo equivalente a un or-den serial de la transacción antes de que los nuevos datos escritos ocurran.Por lo tanto, los sistemas de base de datos replicados aśıncronos puedenpermiten lecturas obsoletas sin renunciar a su garant́ıa de serealización.

En un sistema de servidor único, hay poca motivación para leer algo apartedel valor más reciente de un elemento de datos. Por el contrario, en un sis-tema replicado, los retrasos en la red, debido a la replicación sincrónica, re-quieren mucho tiempo y son costosos. Esto motiva a hacer una replicaciónasincrónica, ya que las lecturas pueden ocurrir desde réplicas aśıncronasde sólo lectura sin violar la serialización (siempre que los datos replicadossean visibles en el mismo orden que el original).

3. Anomaĺıa causal inversa. A diferencia de la anomaĺıa de lectura obso-leta, la anomaĺıa causal inversa puede ocurrir en cualquier sistema de basede datos distribuida y es independiente de cómo se realiza la replicación(śıncrona o aśıncrona).

En la anomaĺıa causal inversa, una escritura posterior que fue causada poruna escritura anterior, viaja en el tiempo a un punto en el orden serialantes de la escritura anterior. En general, estas dos escrituras pueden serelementos de datos totalmente diferentes. Las lecturas que se producen en

12

Historial Ahora

Escribe cuenta A:balance:$ 0

Escribe cuenta B:balance: $ 10,000

Retrocede en el tiempo

Lee el balance de la cuenta A y la cuenta B

Equivalencia en orden serial

Escribe cuenta B:balance: $ 10,000

Lee balance de lacuenta A y B

Escribe cuenta A:balance: $ 0

Figure 3: Anomaĺıa de lectura obsoleta.

el orden en serie entre estas dos escrituras pueden observar el efecto sin lacausa, lo que puede provocar errores en la aplicación.

Como ejemplo, la mayoŕıa de los bancos no intercambian dinero entrecuentas en una sola transacción de base de datos. En cambio, el dinero seelimina de una cuenta a la cuenta bancaria en una transacción.

Una segunda transacción mueve el dinero de la cuenta bancaria a la cuentadestinada como destino para esta transferencia. La segunda transacciónes causada por la primera (ver Figura 3). Si la primera transacción notuvo éxito por alguna razón, la segunda transacción nunca se emitirá.

Supongamos que se transfieren $10,000 de la cuenta A (que actualmentetiene $10,000 y le quedarán $0 después de esta transferencia) a la cuenta B(que actualmente tiene $ 0 y tendrá $10,000 después de la transferencia).Digamos que la cuenta A y la cuenta B son propiedad de la misma entidad, yesta entidad desea obtener un préstamo considerable que requiera $20,000como anticipo.Para ver si este cliente es elegible para el préstamo, el prestamista emiteuna transacción de lectura que lee los valores de las cuentas A y B y toma lasuma del saldo de esas dos cuentas. Si esta transacción de lectura ocurreen el pedido en serie antes de la transferencia de $10,000 de A a B, seobservará un total de $ 10,000 en todas las cuentas.Si esta transacción de lectura ocurre después de la transferencia de $10,000de A a B, todav́ıa se observará un total de $ 10,000 en todas las cuentas. Siesta transacción de lectura ocurre entre las dos transacciones involucradasen la transferencia de $10,000 de A a B que describimos anteriormente, seobservará un total de $0 en todas las cuentas.En los tres casos posibles, a la entidad se le negará (correctamente) elpréstamo debido a la falta de fondos necesarios para el pago inicial.

Si una segunda transacción involucrada en la transferencia (la que agrega$ 10,000 a la cuenta B) viaja en el tiempo antes de la transacción quecausó su existencia en primer lugar (la que resta $ 10,000 de la cuenta

13

A), es posible que una transacción de lectura, que ocurre entre estas dosescrituras, muestre un saldo en las cuentas de $ 20,000 y, por lo tanto,permitir a la entidad asegurar el préstamo.Dado que la transferencia se realizó en dos transacciones separadas, esteejemplo no viola la serialización. El pedido en serie equivalente es:

(a) La transacción que realiza la segunda parte de la transferencia

(b) La transacción de lectura y

(c) La transacción que realiza la primera parte de la transferencia. Sinembargo, este ejemplo muestra el potencial de errores devastadores enel código de la aplicación si se permite que las transacciones causalesviajen en el tiempo hasta un punto en el tiempo antes de su causa.

Un ejemplo de un sistema de base de datos distribuido que permite elreverso causal es CockroachDB 2 (también conocido como CRDB).

CockroachDB particiona una base de datos de manera que cada particiónconfirma escrituras y replica sincrónicamente datos por separado de otrasparticiones. Cada escritura recibe una marca de tiempo basada en el relojlocal en uno de los servidores dentro de esa partición. En general, esimposible sincronizar perfectamente los relojes en una gran cantidad demáquinas, por lo que CockroachDB permite un sesgo de reloj máximo.Sin embargo, (a diferencia de Google Spanner) CockroachDB no espera aque pase el sesgo de reloj máximo antes de realizar una transacción. Porlo tanto, es posible en CockroachDB que se confirme una transacción yque se produzca una transacción posterior (que escribe datos en una par-tición diferente), que fue causada por la anterior (que comenzó despuésde que finalizó la anterior) y aún recibe una marca de tiempo anterior ala transacción anterior. Esto permite una lectura (en el caso de Cock-roachDB, esta lectura debe enviarse al sistema antes de las dos transac-ciones de escritura) para ver potencialmente la escritura de la transacciónposterior, pero no la anterior.

Si el ejemplo de las transacciones bancarias se implementa en CockroachDB,la entidad que desea asegurar el préstamo podŕıa simplemente hacer la so-licitud del préstamo repetidamente y luego transferir dinero entre las cuen-tas A y B hasta que aparezca la anomaĺıa causal inversa, y se aprueba elpréstamo. Obviamente, una aplicación bien escrita debeŕıa ser capaz dedetectar las repetidas solicitudes de préstamos y evitar que ocurra estehack. Pero en general, es dif́ıcil predecir todos los posibles hacks y escribircódigo de aplicación defensivo para evitarlos. Además, los bancos general-mente no pueden reclutar programadores de aplicaciones de élite, lo queconduce a algunas vulnerabilidades alucinantes en aplicaciones del mundoreal3.

2https://www.cockroachlabs.com/3https://www.theverge.com/2019/2/5/18212902/huaxia-bank-qin-qisheng-atm-loophole-

hack-china

14

1.4.3 Cómo evitar las anomaĺıas en el viaje del tiempo

Todas las anomaĺıas discutidas (la escritura inmortal, la lectura obsoleta y elreverso causal) explotan la permisibilidad del viaje en el tiempo en la garant́ıade serialización y, por lo tanto, introducen errores en el código de la aplicación.Para evitar estos errores, el sistema debe garantizar que no se permite que lastransacciones viajen en el tiempo, además de garantizar la serialización.

Como mencionamos anteriormente, los sistemas de servidor único general-mente hacen esta garant́ıa de viaje en el tiempo sin anunciarla, ya que la imple-mentación de esta garant́ıa es trivial en un servidor único. En los sistemas debases de datos distribuidos y replicados, esta garant́ıa adicional de no viajar enel tiempo además de las otras garant́ıas de serialización no es trivial, no obstante,ha sido lograda por varios sistemas como FaunaDB/Calvin4, FoundationDB5 ySpanner6. Este alto nivel de corrección se llama serialización estricta.

La serialización estricta ofrece todas las garant́ıas de serialización de unacopia que discutimos anteriormente. Además, garantiza que si una transacciónX se completa antes de que comience la transacción Y (en tiempo real), X secolocará antes de Y en el orden en serie al que el sistema garantiza la equivalencia.

Clasificación de sistemas serializables Los sistemas que garantizan unaserialización estricta eliminan todo tipo de anomaĺıas en el viaje en el tiempo.En el otro extremo del espectro, los sistemas que garantizan la serialización desolo una copia son vulnerables a todas las anomaĺıas que hemos discutido eneste documento, a pesar de que son inmunes a las anomaĺıas de aislamiento.También existen sistemas que garantizan una versión de serialización entre es-tos dos extremos.

Un ejemplo son los sistemas de serialización de sesión fuerte que garantizanla estricta serialización de las transacciones dentro de la misma sesión, peropor lo demás solo la serialización de una copia. Otra clase bien conocida detales sistemas son los sistemas de réplica de solo lectura donde todas lastransacciones de actualización van a la réplica maestra que las procesa conuna serialización estricta. Estas actualizaciones se replican asincrónicamente enréplicas de solo lectura en el orden en que se procesaron en el maestro.

Las lecturas de las réplicas pueden ser obsoletas, pero aún son serializables.Llamamos a esto serializabilidad asincrónica. Otra clase de sistemas son los sis-temas particionados en los que las escrituras dentro de una partición se replicansincrónicamente, pero no se realiza ninguna coordinación entre particiones paraescrituras disjuntas. Llamamos a esto serializabilidad particionada. En laTabla 2 se resume los diferentes niveles de serialización y las anomaĺıas a lasque son vulnerables.

4https://fauna.com/5https://www.foundationdb.org/6https://cloud.google.com/spanner/

15

Table 2: Niveles de serialización y sus anomaĺıas.

Garant́ıa del sistema Escritura inmor-tal

Lectura ob-soleta

Causal inversa

ONE COPY SERI-ALIZABLE

Posible Posible Posible

STRONG SESSIONSERIALIZABLE

Posible (perono dentro de lamisma sesión)

Posible (perono dentrode la mismasesión)

Posible (perono dentro de lamisma sesión)

ASYNCHRONOUSSERIALIZABLE

No Posible No

PARTITIONED SE-RIALIZABLE

No No Posible

STRICT SERIALIZ-ABLE

No No No

2 Consistencia en las bases de datos

Los sistemas de bases de datos generalmente brindan a los usuarios la capaci-dad de intercambiar la corrección por el rendimiento: esto se traduce como losniveles de aislamiento de la base de datos.En los sistemas distribuidos, existe una categoŕıa completamente diferente paracompensar la corrección por el rendimiento: esto son los niveles de consisten-cia. Hay un número creciente de sistemas de bases de datos distribuidas queofrecen a sus usuarios múltiples niveles de consistencia diferentes para elegir,lo que permite al usuario especificar qué garant́ıas de consistencia se necesitandel sistema para una aplicación en particular. Similar a los niveles de ais-lamiento: los niveles de consistencia más débiles generalmente vienen con unmejor rendimiento y, por lo tanto, vienen con los mismos tipos de tentacionesque los niveles de aislamiento reducidos.

2.0.1 Niveles de consistencia

La Consistencia depende fundamentalmente del contexto. Se refiere a la ca-pacidad de un sistema para garantizar que cumple (sin falta) con un conjuntopredefinido de reglas. Sin embargo, este conjunto de reglas cambia según elcontexto. Por ejemplo, la C de ACID y la C de CAP se refieren a la consisten-cia. Sin embargo, el conjunto de reglas implicadas por estos dos contextos sontotalmente diferentes:

• En ACID, las reglas se refieren a la semántica definida por la aplicación.Un sistema que garantiza la C de ACID asegura que el procesamientode una transacción no viola las restricciones de integridad referencial, lasrestricciones de clave externa y cualquier otra restricción espećıfica de laaplicación (por ejemplo cada usuario debe tener un nombre).

• En CAP se refiere a las reglas relacionadas con hacer que un sistema dis-tribuido concurrente parezca un sistema centralizado de un solo subpro-

16

ceso. Las lecturas en un momento determinado solo tienen un resultadoposible: deben reflejar la escritura completada más reciente (en tiemporeal) de ese elemento de datos, sin importar qué servidor procesó esa es-critura.

Con lo anteriormente mencionado, el nivel de consistencia no se usa t́ıpicamenteen el contexto de consistencia de ACID. Esto se debe a que la C de ACID escasi completamente responsabilidad del desarrollador de la aplicación.Sólo el desarrollador puede asegurarse de que el código que colocan dentro deuna transacción no viole la semántica de la aplicación cuando se ejecuta deforma aislada. ACID es realmente un nombre inapropiado –realmente debeŕıaser AID, ya que sólo esos tres (atomicidad, aislamiento y durabilidad) están enel ámbito de las garant́ıas del sistema.

Cuando hablamos de niveles de consistencia, realmente nos referimos alaC de CAP. En este contexto, la consistencia perfecta se conoce como consis-tencia estricta, esto implicaŕıa que el sistema garantiza que todas las lecturasreflejen todas las escrituras anteriores, sin importar dónde se realizaron esasescrituras.

Cualquier nivel de consistencia por debajo de la consistencia perfecta permiteque ocurran situaciones en las que una lectura no devuelve la escritura másreciente de un elemento de datos.

Según la arquitectura de un sistema en particular, la consistencia perfectase vuelve más fácil o más dif́ıcil de lograr. En sistemas mal diseñados, lograr laperfección conlleva un costo prohibitivo de rendimiento y disponibilidad, y losusuarios de dichos sistemas deben aceptar garant́ıas significativamente inferioresa la perfección. Sin embargo, incluso en sistemas bien diseñados, a menudo seobtiene un beneficio de rendimiento no trivial al aceptar garant́ıas por debajode la perfección.

Según algunos investigadores sobre sistemas multiprocesadores de memoriacompartida [4], los niveles de consistencia se pueden dividir en 3:

• Consistencia secuencial. Todas las escrituras, sin importar en qué hilofue realizado y qué elemento de datos se escribieron, están ordenados glob-almente. Cada hilo de ejecución debe ver las escrituras que ocurren en esteorden. Por ejemplo, si un hilo vio que los datos X se actualizaban a 5, yluego que Y se actualizaba a 10, cada hilo debe ver la actualización de Xantes de la actualización de Y. Si algún hilo ve el nuevo valor de Y pero elantiguo valor de X, se violaŕıa la coherencia secuencial (ver Figura 4). Enesta Figura 4, el tiempo avanza a medida que se mueve hacia la derecha;hay 4 hilos de ejecución: P1, P2, P3 y P4. Cada subproceso (que lee X yY) ve la actualización de X de 0 a 5 antes de la actualización de Y desde0 a 10.Los subprocesos P1 y P2 escriben X y Y respectivamente, pero no leenninguno.El subproceso P3 ve el nuevo valor de X y posteriormente ve el valor an-terior de Y. Esto solo es posible si la actualización a X ocurrió antes dela actualización a Y. El subproceso P4 solo ve los nuevos valores de X y

17

P1: W: x=5

P2: W: y=10

P3: R: x=5 R: y=0 R: y=10

P4: R: y=10 R: x=5

Figure 4: Ejemplo de planificación con consistencia secuencial y causal, nolinealizable o estricta. El valor inicial de X y Y = 0.

P1: W: x=5

P2: W: y=10

P3: R: y=10 R: x=0

P4: R: y=10 R: x=5

Figure 5: Ejemplo de planificación con consistencia secuencial y causal pero nolinealizable o estricta. El valor inicial de X y Y = 0.

Y, por lo que no ve cuál sucedió primero. Por lo tanto, todos los hiloscoinciden en que es posible que la actualización de X ocurriera antes de laactualización de Y.

En general, la consistencia secuencial no impone ningún requisito sobrecómo ordenar las escrituras. En nuestro ejemplo, la escritura en X sucedióen tiempo real antes de la escritura en Y. Sin embargo, siempre que cadahilo acepte ver que la escritura en Y sucede antes de la escritura en X,la coherencia secuencial permite que la historia oficial sea diferente. loque ocurrió según el tiempo real (la única restricción es que las escriturasy lecturas que se originan en el mismo hilo de ejecución no se puedenreordenar). En la Figura 5 se aprecia el ejemplo.

• Consistencia estricta. A diferencia de la coherencia secuencial, la co-herencia estricta impone requisitos en tiempo real sobre cómo ordenar lasescrituras. Se supone que siempre es posible saber qué hora es actual-mente con cero errores, es decir, que cada subproceso de ejecución está deacuerdo con la hora actual precisa.El orden de las escrituras, en el orden secuencial, debe ser igual al tiemporeal en que se emitieron estas escrituras. Además, cada operación de lec-tura debe leer el valor de la escritura más reciente en tiempo real, sin im-portar qué hilo de ejecución haya iniciado esa escritura. A nivel práctico,

18

P1: W: x=5

P2: W: y=10

P3: R: x=5 R: y=10

P4: R: y=10 R: x=5

Figure 6: Ejemplo de planificación con consistencia estricta, linearizable, se-cuencial y causal. El valor inicial de X y Y = 0.

en un sistema distribuido (e incluso en sistemas de servidor único multi-procesador) es imposible tener un acuerdo global sobre el tiempo actualpreciso, lo que hace que la consistencia estricta sea principalmente de in-terés teórico.

La Figura 4 no satisface una consistencia estricta porque contiene unalectura de x = 0 o una lectura de y = 0 después de que el valor de x o yse haya escrito en un nuevo valor.

En la Figura 6 satisface una consistencia estricta ya que todas las lecturasreflejan la escritura más reciente en tiempo real.

• Consistencia atómica o linealizable. Es el nivel de consistencia másalto que se puede obtener en un sistema distribuido/replicado, don lasescrituras y las lecturas pueden originarse en cualquier parte. La lineal-ización es muy similar a la consistencia estricta: ambas son extensionesde consistencia secuencial que imponen restricciones en tiempo real a lasescrituras. La diferencia es que el modelo de linealización reconoce quehay un peŕıodo de tiempo entre el momento en que se env́ıa una operaciónal sistema y cuando el sistema responde con un reconocimiento de que secompletó.

En un sistema distribuido, el env́ıo de la solicitud de escritura a las ubi-caciones correctas, que puede incluir la replicación, puede ocurrir duranteeste peŕıodo de tiempo. Una garant́ıa de linealización no impone restric-ciones de orden en las operaciones que se producen con la superposición delas horas de inicio y finalización. La única restricción de ordenamiento espara operaciones que no se superponen en el tiempo; solo en esos casos, laescritura anterior debe verse antes de la escritura posterior. En la Figura6 se muestra un ejemplo de planificación con consistencia causal, secuen-cial, estricta y linealizable/atómica; en la Figura 7 se muestra un ejemplode una consistencia linealizable, pero no estrictamente consistente. No esestrictamente consistente ya que la lectura de X, por parte de P3,se inicia(y regresa) un poco después de la escritura de X por parte de P1, peroaún ve el valor anterior. Sin embargo, es linealizable porque la lectura deX por P3 y la escritura de X por P1 se superponen en el tiempo, y por

19

P1: W: x=5

P2: W: y=10

P3: R: x=0 R: y=10

P4: R: y=10 R: x=5

Figure 7: Ejemplo de planificación con consistencia linearizable, secuencial,causal pero no estricta. El valor inicial de X y Y = 0.

P1: W: x=5

P2: W: y=10

P3: R: x=5 R: y=0 R: y=10

P4: R: y=10 R: x=0

Figure 8: Ejemplo de planificación con consistencia causal pero no linealizable,estricta o secuencial. El valor inicial de X y Y = 0.

lo tanto la linealización no requiere la lectura de X por P3 para ver elresultado de la escritura de X por P1.

Si bien la linealización y la consistencia estricta son más fuertes que laconsistencia secuencial, la consistencia secuencial es en śı misma un nivelmuy alto de consistencia, y existen muchos niveles de consistencia por de-bajo.

• Consistencia causal. Es un nivel de consistencia popular y útil que estáligeramente por debajo de la consistencia secuencial. En la consistenciasecuencial, todas las escrituras deben estar ordenadas globalmente, inclusosi no están relacionadas entre śı. La coherencia causal no impone órdenesde escrituras no relacionadas. Sin embargo, si un hilo de ejecución realizauna lectura de algún elemento de datos (llámelo X) y luego escribe eseı́tem de datos o uno diferente (llámelo Y), se supone que la lectura pos-terior puede haber sido causada por la lectura. Por lo tanto, impone elorden de X y Y, todos los hilos de ejecución deben observar la escriturade Y después de la escritura de X.

En la la Figura 9 se aprecia un ejemplo de planificación sin consistencia

20

P1: W: x=5

P2: W: y=10

P3: R: x=5 R: y=0

P4: R: y=10 R: x=0

R: x=5

R: y=10

Figure 9: Ejemplo de planificación sin consistencia causal, linealizable, estrictao secuencial. El valor inicial de X y Y = 0.

causal, linealizable, estricta o secuencial. Si se compara con la Figura8, se puede apreciar que en la Figura 8, P3 vio la escritura en X antesde la escritura en Y, pero P4 vio la escritura en Y antes de la escrituraen X. Esto viola la consistencia secuencial, pero no consistencia causal.Sin embargo, en la Figura 9, P2 lee la escritura en X antes de realizar laescritura en Y. Eso coloca una restricción causal entre la escritura en X yY. Por lo tanto, cuando P4 ve la escritura en Y sin escribir en X, se violala consistencia causal.

• Consistencia eventual. Es la consistencia más débil, incluso las escrit-uras causalmente dependientes pueden volverse visibles fuera de orden.Viola cualquier otra garant́ıa de consistencia que hemos discutido hastaahora. La única garant́ıa en la consistencia eventual es que si no hay escrit-uras durante un peŕıodo de tiempo largo (donde la definición de ”largo”depende del sistema), cada hilo de ejecución acordará el valor de la últimaescritura. Por lo tanto, siempre que P4 vea el nuevo valor de X (5) enalgún momento posterior (no se muestra en la Figura 6), se mantendrá laconsistencia eventual. La Figura 9 no necesariamente viola la consistenciaeventual.

References

[1] Rony Attar, Philip A. Bernstein, and Nathan Goodman. Site initialization,recovery, and backup in a distributed database system. IEEE Transactionson Software Engineering, SE-10(6):645–650, November 1984.

[2] Natacha Crooks, Youer Pu, Lorenzo Alvisi, and Allen Clement. Seeing isbelieving: A client-centric specification of database isolation. In Proceedingsof the ACM Symposium on Principles of Distributed Computing, PODC ’17,pages 73–82, New York, NY, USA, 2017. ACM.

[3] Jose M. Faleiro, Daniel J. Abadi, and Joseph M. Hellerstein. High per-formance transactions via early write visibility. Proc. VLDB Endow.,10(5):613–624, January 2017.

21

[4] Seth Gilbert and Nancy Lynch. Brewer’s conjecture and the feasibilityof consistent, available, partition-tolerant web services. SIGACT News,33(2):51–59, June 2002.

22