Consistencia causal

La consistencia causal es uno de los principales modelos de consistencia de memoria. En la programación concurrente, donde procesos concurrentes acceden a una memoria compartida, un modelo de consistencia restringe qué accesos son legales. Esto resulta útil para definir estructuras de datos correctas en la memoria compartida distribuida o en transacciones distribuidas.

La consistencia causal está “disponible bajo partición”, lo que significa que un proceso puede leer y escribir en la memoria (la memoria está disponible) incluso cuando no hay una conexión de red en funcionamiento (la red está particionada) entre procesos; es un modelo asincrónico. A diferencia de los modelos de consistencia fuerte, como la consistencia secuencial o la linealización, que no pueden ser seguros y funcionar bajo partición, y responden con lentitud porque requieren sincronización.

La consistencia causal se propuso en la década de 1990 como un modelo de consistencia más débil para los modelos de memoria compartida. La consistencia causal está estrechamente relacionada con el concepto de transmisión causal en los protocolos de comunicación. En estos modelos, una ejecución distribuida se representa como un orden parcial, basado en el concepto de causalidad potencial de "sucedió antes" de Lamport.

La consistencia causal es un modelo de consistencia útil porque coincide con las intuiciones de los programadores sobre el tiempo, está más disponible que los modelos de consistencia fuerte y, sin embargo, proporciona garantías más útiles que la consistencia eventual. Por ejemplo, en bases de datos distribuidas, la consistencia causal respalda el ordenamiento de las operaciones, en contraste con la consistencia eventual. Además, la consistencia causal ayuda con el desarrollo de tipos de datos abstractos, como colas o contadores.

Dado que el tiempo y el orden son tan fundamentales para nuestra intuición, es difícil razonar sobre un sistema que no impone la coherencia causal. Sin embargo, muchas bases de datos distribuidas carecen de esta garantía, incluso las que ofrecen serialización. Spanner garantiza la coherencia causal, pero también impone una coherencia fuerte, evitando así la disponibilidad bajo partición. Las bases de datos más disponibles que garantizan la coherencia causal incluyen MongoDB y AntidoteDB.

La coherencia causal captura las posibles relaciones causales entre operaciones y garantiza que todos los procesos observen operaciones causalmente relacionadas en un orden común. En otras palabras, todos los procesos del sistema están de acuerdo en el orden de las operaciones causalmente relacionadas. Pueden estar en desacuerdo en el orden de las operaciones que no están causalmente relacionadas.

Definamos la siguiente relación. Si algún proceso realiza una operación de escritura A, y algún proceso (el mismo u otro) que observó A realiza luego una operación de escritura B, entonces es posible que A sea la causa de B; decimos que A “causa potencialmente” o “precede causalmente” a B. La consistencia causal garantiza que si A precede causalmente a B, entonces cada proceso en el sistema observa A antes de observar B. Por el contrario, se dice que dos operaciones de escritura C y D son concurrentes, o causalmente independientes, si ninguna precede causalmente a la otra. En este caso, un proceso puede observar C antes que D, o D antes que C. La relación de precedencia causal en la memoria compartida está relacionada con la relación de "ocurrió antes" en la comunicación basada en mensajes.

Por lo tanto, un sistema proporciona coherencia causal si se cumple la siguiente condición: las operaciones de escritura que están relacionadas por causalidad potencial son vistas por cada proceso del sistema en su orden de precedencia causal. Diferentes procesos pueden observar escrituras concurrentes en diferentes órdenes.

El modelo de consistencia causal es más débil que el de consistencia secuencial, que garantiza que todos los procesos observen todas las operaciones de escritura en un orden común, ya sea que estén relacionadas causalmente o no. Sin embargo, la consistencia causal es más fuerte que la consistencia PRAM, que requiere que solo las operaciones de escritura que realiza un solo proceso sean observadas en un orden común por todos los demás procesos. De ello se deduce que cuando un sistema es secuencialmente consistente, también es causalmente consistente. Además, la consistencia causal implica consistencia PRAM, pero no viceversa.

A continuación se muestra un ejemplo de coherencia causal.

En la siguiente secuencia de eventos se respetan las relaciones causales:

El proceso P2 observa y lee la escritura anterior W(x)1 realizada por el proceso P1. Por lo tanto, las dos escrituras W(x)1 y W(x)2 están relacionadas causalmente. En condiciones de coherencia causal, cada proceso observa primero W(x)1, antes de observar W(x)2. Observe que las dos operaciones de escritura W(x)2 y W(x)3, sin operaciones de lectura intermedias, son concurrentes, y los procesos P3 y P4 las observan (leen) en órdenes diferentes.

El modelo de consistencia causal se puede refinar en cuatro garantías de sesión, que se pueden resumir de la siguiente manera:

• Lea sus escritos: Si un proceso realiza una escritura, el mismo proceso observa más adelante el resultado de su escritura.

• Monotonic Lees: el conjunto de escritos observados (leer) por un proceso está garantizado para ser monotonicamente no-disminución.

• Escribir Sigue Lecturas: si algún proceso realiza una lectura seguida de una escritura, y otro proceso observa el resultado de la escritura, entonces también puede observar la lectura (a menos que haya sido sobrescrito).

• Monotonic Writes: Si algún proceso realiza un escrito, seguido algún tiempo más tarde por otro escrito, otros procesos los observarán en el mismo orden.

Daudjee y Salem presentan garantías de sesión transaccional para serialización y aislamiento de instantáneas.

El sistema se abstrae como un conjunto de procesos que se comunican. Cuando un proceso escribe en la memoria compartida, la implementación envía este evento a los demás procesos (a través de la memoria compartida o como un mensaje). Debido a la concurrencia y a las fallas, un proceso puede recibir eventos en cualquier orden. La implementación entrega un evento, es decir, lo hace visible para el proceso, solo si todos los eventos que lo preceden causalmente se han entregado. Esto requiere que la implementación mantenga metadatos que representen las relaciones causales entre los accesos a la memoria.

En resumen, la implementación incluye los siguientes pasos: (1) Mantener metadatos de contexto causal en cada proceso para resumir qué actualizaciones preceden causalmente al estado actual. (2) Cuando un proceso actualiza la memoria, etiquetar el evento de actualización con el contexto causal de ese proceso, para resumir qué actualizaciones preceden causalmente a esta actualización. (3) Un proceso que ha recibido algún evento de actualización puede entregarlo sólo si la etiqueta del evento precede causalmente al contexto causal del proceso receptor. (Como efecto secundario de la entrega, agregar el nuevo evento al contexto causal del proceso receptor). De lo contrario, la actualización se recibió demasiado pronto y debe permanecer almacenada en el búfer hasta que el evento coincida con el contexto. Mientras tanto, la implementación espera pasivamente para recibir los eventos faltantes o los recupera activamente de su fuente.

Este enfoque permite la disponibilidad bajo partición.

Existen dos representaciones comunes para los metadatos del contexto causal. Una es mantener un gráfico de dependencia explícita de la relación de dependencia causal. Debido a que un gráfico de este tipo puede crecer arbitrariamente, un evento a menudo se etiqueta solo con sus predecesores inmediatos; determinar sus predecesores transitivos requiere un recorrido de gráfico distribuido. La otra es mantener un reloj vectorial, con una entrada por proceso (o grupo de procesos), que cuente la cantidad de eventos generados por el proceso o grupo. Esta representación tiene un tamaño fijo y el orden de los eventos se puede inferir mediante una simple comparación de los vectores.

Para determinar con precisión qué eventos son dependientes y cuáles son concurrentes en un sistema totalmente peer-to-peer, el tamaño de los metadatos es al menos proporcional al número de escritores activos. Sin embargo, una determinación precisa de la concurrencia es generalmente excesiva. La consistencia causal requiere solamente que los eventos causalmente dependientes se entreguen en orden; no importa si dos eventos concurrentes terminan siendo ordenados. Por lo tanto, el tamaño se puede reducir arbitrariamente utilizando técnicas de aproximación segura. En el límite, un único escalar (un reloj Lamport) es suficiente, a costa de eliminar cualquier concurrencia. El tamaño de los metadatos también se puede reducir restringiendo la topología de comunicación; por ejemplo, en una topología en estrella, árbol o lineal, un único escalar es suficiente.

La búsqueda de implementaciones eficientes de la consistencia causal es un área de investigación muy activa.