En informática , un modelo de consistencia especifica un contrato entre el programador y un sistema, en el que el sistema garantiza que si el programador sigue las reglas para las operaciones en la memoria, la memoria será consistente y los resultados de la lectura, escritura o actualización de la memoria serán predecibles. Los modelos de consistencia se utilizan en sistemas distribuidos como sistemas de memoria compartida distribuida o almacenes de datos distribuidos (como sistemas de archivos , bases de datos , sistemas de replicación optimista o almacenamiento en caché web ). La consistencia es diferente de la coherencia, que ocurre en sistemas con o sin caché, y es la consistencia de los datos con respecto a todos los procesadores. La coherencia se ocupa de mantener un orden global en el que las escrituras en una sola ubicación o variable única sean vistas por todos los procesadores. La consistencia se ocupa del ordenamiento de las operaciones en múltiples ubicaciones con respecto a todos los procesadores.
Los lenguajes de alto nivel , como C++ y Java , mantienen el contrato de consistencia traduciendo las operaciones de memoria en operaciones de bajo nivel de una manera que preserva la semántica de la memoria , reordenando algunas instrucciones de memoria y encapsulando la sincronización requerida con llamadas a bibliotecas como pthread_mutex_lock(). [1]
Supongamos que ocurre el siguiente caso: [2]
El modelo de consistencia determina si el cliente B definitivamente verá la escritura realizada por el cliente A, definitivamente no lo verá o no puede depender de ver la escritura.
Los modelos de consistencia definen reglas para el orden aparente y la visibilidad de las actualizaciones, y son un continuo con compensaciones. [2] Hay dos métodos para definir y categorizar los modelos de consistencia: problemas y vistas.
Por ejemplo, un modelo de consistencia puede definir que un proceso no puede ejecutar una operación hasta que se completen todas las operaciones ejecutadas anteriormente. Los distintos modelos de consistencia imponen distintas condiciones. Un modelo de consistencia puede considerarse más fuerte que otro si requiere todas las condiciones de ese modelo y más. En otras palabras, un modelo con menos restricciones se considera un modelo de consistencia más débil.
Estos modelos definen cómo se debe distribuir el hardware y, en un nivel alto, cómo debe codificar el programador. El modelo elegido también afecta la forma en que el compilador puede reordenar las instrucciones. En general, si se ordenan las dependencias de control entre instrucciones y si se escribe en la misma ubicación, el compilador puede reordenarlas según sea necesario. Sin embargo, con los modelos que se describen a continuación, algunos pueden permitir que se reordenen las escrituras antes de las cargas, mientras que otros no.
La consistencia estricta es el modelo de consistencia más sólido. Según este modelo, cualquier acción de escritura en una variable por parte de cualquier procesador debe ser vista instantáneamente por todos los procesadores.
El diagrama de modelo estricto y los diagramas de modelo no estrictos describen la restricción de tiempo: instantánea. Se puede entender mejor como si existiera un reloj global en el que cada escritura debería reflejarse en todas las memorias caché del procesador al final de ese período de reloj. La siguiente operación debe ocurrir solo en el siguiente período de reloj.
En el siguiente diagrama, P significa "proceso" y el valor del reloj global está representado en la columna Secuencia.
Este es el modelo más rígido. En este modelo, el resultado esperado por el programador se recibirá siempre. Es determinista. Su relevancia práctica se limita a un experimento mental y al formalismo, porque el intercambio instantáneo de mensajes es imposible. No ayuda a responder la pregunta de la resolución de conflictos en escrituras concurrentes en el mismo elemento de datos, porque supone que las escrituras concurrentes son imposibles.
El modelo de consistencia secuencial fue propuesto por Lamport (1979). Es un modelo de memoria más débil que el modelo de consistencia estricta. [3] Una escritura en una variable no tiene por qué ser vista instantáneamente, sin embargo, las escrituras en las variables por diferentes procesadores tienen que ser vistas en el mismo orden por todos los procesadores. La consistencia secuencial se cumple si "el resultado de cualquier ejecución es el mismo que si las operaciones (de lectura y escritura) de todos los procesos en el almacén de datos se ejecutaran en algún orden secuencial, y las operaciones de cada procesador individual aparecen en esta secuencia en el orden especificado por su programa". [3] [4] Adve y Gharachorloo, 1996 [5] definen dos requisitos para implementar la consistencia secuencial: orden del programa y atomicidad de la escritura.
En la coherencia secuencial, no existe la noción de tiempo ni de operaciones de escritura más recientes. Hay algunas operaciones que se intercalan de la misma manera para todos los procesos. Un proceso puede ver las operaciones de escritura de todos los procesos, pero solo puede ver sus propias operaciones de lectura. Se debe mantener el orden del programa dentro de cada procesador y el orden secuencial de las operaciones entre procesadores. Para preservar el orden secuencial de ejecución entre procesadores, todas las operaciones deben parecer ejecutarse de manera instantánea o atómica con respecto a todos los demás procesadores.
Estas operaciones sólo necesitan "aparentar" que se completaron porque es físicamente imposible enviar información instantáneamente. Por ejemplo, en un sistema que utiliza un único bus compartido globalmente, una vez que se envía una línea de bus con información, se garantiza que todos los procesadores verán la información al mismo tiempo. Por lo tanto, al pasar la información a la línea de bus se completa la ejecución con respecto a todos los procesadores y parece que se ha ejecutado. Las arquitecturas sin caché o las arquitecturas con caché con redes de interconexión que no son instantáneas pueden contener una ruta lenta entre los procesadores y las memorias. Estas rutas lentas pueden dar lugar a una inconsistencia secuencial, porque algunas memorias reciben los datos transmitidos más rápido que otras.
La coherencia secuencial puede producir resultados no deterministas. Esto se debe a que la secuencia de operaciones secuenciales entre procesadores puede ser diferente durante distintas ejecuciones del programa. Todas las operaciones de memoria deben realizarse en el orden del programa.
La linealizabilidad [6] (también conocida como consistencia atómica o memoria atómica) [7] se puede definir como la consistencia secuencial con una restricción de tiempo real, considerando un tiempo de inicio y un tiempo de finalización para cada operación. Una ejecución es linealizable si cada operación se lleva a cabo en un orden linealizable colocando un punto entre su tiempo de inicio y su tiempo de finalización y garantizando la consistencia secuencial.
La verificación de la consistencia secuencial a través de la comprobación de modelos es indecidible en general, incluso para protocolos de coherencia de caché de estados finitos . [8]
La consistencia causal [4] definida por Hutto y Ahamad, 1990, [9] es un debilitamiento del modelo de consistencia secuencial al categorizar los eventos en aquellos causalmente relacionados y aquellos que no lo están. Define que solo las operaciones de escritura que están causalmente relacionadas deben ser vistas en el mismo orden por todos los procesos. Por ejemplo, si un evento b tiene efecto a partir de un evento anterior a, la consistencia causal garantiza que todos los procesos vean el evento b después del evento a. Tanenbaum et al., 2007 proporcionan una definición más estricta, que establece que un almacén de datos se considera causalmente consistente bajo las siguientes condiciones: [4]
Este modelo relaja la coherencia secuencial en las escrituras simultáneas realizadas por un procesador y en las escrituras que no están relacionadas causalmente. Dos escrituras pueden volverse causalmente relacionadas si una escritura en una variable depende de una escritura anterior en cualquier variable si el procesador que realiza la segunda escritura acaba de leer la primera. Las dos escrituras podrían haber sido realizadas por el mismo procesador o por diferentes procesadores.
Al igual que en la consistencia secuencial, las lecturas no necesitan reflejar los cambios instantáneamente, sin embargo, necesitan reflejar todos los cambios en una variable secuencialmente.
W(x)2 ocurre después de W(x)1 debido a la lectura hecha por P2 a x antes de W(x)2, por lo tanto, este ejemplo es causalmente consistente según la definición de Hutto y Ahamad (aunque no según la de Tanenbaum et al., porque W(x)2 y W(x)3 no se ven en el mismo orden para todos los procesos). Sin embargo, R(x)2 y R(x)3 ocurren en un orden diferente en P3 y P4, por lo tanto, este ejemplo es secuencialmente inconsistente . [10]
Para mantener la coherencia de los datos y lograr sistemas de procesadores escalables en los que cada procesador tenga su propia memoria, se derivó el modelo de coherencia de procesadores . [10] Todos los procesadores deben ser coherentes en el orden en el que ven las escrituras realizadas por un procesador y en la forma en que ven las escrituras de diferentes procesadores en la misma ubicación (se mantiene la coherencia). Sin embargo, no necesitan ser coherentes cuando las escrituras las realizan diferentes procesadores en diferentes ubicaciones.
Cada operación de escritura se puede dividir en varias subescrituras en todas las memorias. Una lectura de una de esas memorias puede ocurrir antes de que se complete la escritura en esta memoria. Por lo tanto, los datos leídos pueden estar obsoletos. Por lo tanto, un procesador en una PC puede ejecutar una carga más reciente cuando se necesita detener una memoria más antigua. En este modelo, se conserva el orden de lectura antes de escritura, lectura después de lectura y escritura antes de escritura.
El modelo de consistencia del procesador [11] es similar al modelo de consistencia PRAM con una condición más fuerte que define que todas las escrituras en la misma ubicación de memoria deben ser vistas en el mismo orden secuencial por todos los demás procesos. La consistencia del procesador es más débil que la consistencia secuencial pero más fuerte que el modelo de consistencia PRAM.
El sistema multiprocesador Stanford DASH implementa una variación de la consistencia del procesador que no tiene parangón (ni es más débil ni más fuerte) con las definiciones de Goodman. [12] Todos los procesadores deben ser consistentes en el orden en el que ven las escrituras de un procesador y en la forma en que ven las escrituras de diferentes procesadores en la misma ubicación. Sin embargo, no necesitan ser consistentes cuando las escrituras son de diferentes procesadores en diferentes ubicaciones.
Lipton y Sandberg presentaron en 1988 [13] la consistencia RAM segmentada (consistencia PRAM) como uno de los primeros modelos de consistencia descritos. Debido a su definición informal, existen de hecho al menos dos implementaciones sutilmente diferentes, [12] una de Ahamad et al. y otra de Mosberger.
En la coherencia PRAM, todos los procesos ven las operaciones de un único proceso en el mismo orden en que fueron emitidas por ese proceso, mientras que las operaciones emitidas por diferentes procesos pueden verse en un orden diferente desde diferentes procesos. La coherencia PRAM es más débil que la coherencia del procesador. PRAM relaja la necesidad de mantener la coherencia en una ubicación en todos sus procesadores. Aquí, las lecturas de cualquier variable se pueden ejecutar antes de las escrituras en un procesador. En este modelo, se conserva el orden de lectura antes de escritura, lectura después de lectura y escritura antes de escritura.
La consistencia de la memoria caché [11] [14] requiere que todas las operaciones de escritura en la misma ubicación de memoria se realicen en un orden secuencial. La consistencia de la memoria caché es más débil que la consistencia del procesador y no es comparable con la consistencia de la PRAM.
En la consistencia lenta, [14] si un proceso lee un valor escrito previamente en una ubicación de memoria, no puede leer posteriormente ningún valor anterior de esa ubicación. Las escrituras realizadas por un proceso son inmediatamente visibles para ese proceso. La consistencia lenta es un modelo más débil que la consistencia de PRAM y caché.
Ejemplo: El diagrama de memoria lenta muestra un ejemplo de consistencia lenta. El primer proceso escribe 1 en la ubicación de memoria X y luego escribe 1 en la ubicación de memoria Y. El segundo proceso lee 1 de Y y luego lee 0 de X, aunque X se escribió antes que Y.
Hutto, Phillip W. y Mustaque Ahamad (1990) [9] ilustran que, mediante una programación adecuada, la memoria lenta (consistencia) puede ser expresiva y eficiente. Mencionan que la memoria lenta tiene dos propiedades valiosas: localidad y apoyo a la reducción de la memoria atómica. Proponen dos algoritmos para presentar la expresividad de la memoria lenta.
Estos cuatro modelos de consistencia se propusieron en un artículo de 1994. Se centran en las garantías en la situación en la que sólo un único usuario o aplicación realiza modificaciones de datos. [15]
Si un proceso lee el valor de un elemento de datos x, cualquier operación de lectura sucesiva en x por parte de ese proceso siempre devolverá ese mismo valor o un valor más reciente. [4]
Una operación de escritura realizada por un proceso sobre un elemento de datos X se completa antes de cualquier operación de escritura sucesiva sobre X realizada por el mismo proceso. [4]
Un valor escrito por un proceso en un elemento de datos X siempre estará disponible para una operación de lectura sucesiva realizada por el mismo proceso en el elemento de datos X. [4]
Se garantiza que una operación de escritura realizada por un proceso sobre un elemento de datos x después de una operación de lectura previa sobre x realizada por el mismo proceso se realizará sobre el mismo valor o sobre un valor más reciente de x que se leyó. [4]
Los siguientes modelos requieren una sincronización específica por parte de los programadores.
El orden débil clasifica las operaciones de memoria en dos categorías: operaciones de datos y operaciones de sincronización . Para hacer cumplir el orden del programa, un programador necesita encontrar al menos una operación de sincronización en un programa. Las operaciones de sincronización le indican al procesador que se asegure de que ha completado y visto todas las operaciones anteriores realizadas por todos los procesadores. El orden y la atomicidad del programa se mantienen solo en las operaciones de sincronización y no en todas las lecturas y escrituras. Esto se derivó de la comprensión de que ciertas operaciones de memoria, como las realizadas en una sección crítica, no necesitan ser vistas por todos los procesadores hasta que se completen todas las operaciones en la sección crítica. Supone que reordenar las operaciones de memoria a las regiones de datos entre operaciones de sincronización no afecta el resultado del programa. Esto explota el hecho de que los programas escritos para ser ejecutados en un sistema multiprocesador contienen la sincronización requerida para asegurarse de que no se produzcan carreras de datos y que los resultados de SC se produzcan siempre. [16]
En este modelo, la coherencia no se relaja. Una vez que se cumplen estos requisitos, se pueden reordenar todas las demás operaciones de "datos". La forma en que esto funciona es que un contador registra la cantidad de operaciones de datos y, hasta que este contador llegue a cero, no se emite la operación de sincronización. Además, no se emiten más operaciones de datos a menos que se completen todas las sincronizaciones anteriores. Las operaciones de memoria entre dos variables de sincronización se pueden superponer y reordenar sin afectar la corrección del programa. Este modelo garantiza que siempre se mantenga la atomicidad de la escritura, por lo que no se requiere una red de seguridad adicional para el ordenamiento débil.
Para mantener un orden débil, las operaciones de escritura anteriores a una operación de sincronización deben realizarse globalmente antes de la operación de sincronización. Las operaciones posteriores a una operación de sincronización también deben realizarse solo después de que se complete la operación de sincronización. Por lo tanto, los accesos a las variables de sincronización son secuencialmente consistentes y cualquier lectura o escritura debe realizarse solo después de que se hayan completado las operaciones de sincronización anteriores.
El programa depende en gran medida de la sincronización explícita. En el caso de los modelos de ordenación débil, el programador debe utilizar instrucciones de bloqueo atómico, como test-and-set, fetch-and-op, store conditional, load linked o debe etiquetar las variables de sincronización o utilizar vallas.
El modelo de consistencia de liberación relaja el modelo de consistencia débil al distinguir la operación de sincronización de entrada de la operación de sincronización de salida. En el orden débil, cuando se debe ver una operación de sincronización, todas las operaciones en todos los procesadores deben ser visibles antes de que se realice la operación de sincronización y el procesador continúe. Sin embargo, en el modelo de consistencia de liberación, durante la entrada a una sección crítica, denominada como "adquisición", todas las operaciones con respecto a las variables de memoria local deben completarse. Durante la salida, denominada como "liberación", todos los cambios realizados por el procesador local deben propagarse a todos los demás procesadores. La coherencia aún se mantiene.
La operación de adquisición es una operación de carga/lectura que se realiza para acceder a la sección crítica. Una operación de liberación es una operación de almacenamiento/escritura que se realiza para permitir que otros procesadores utilicen las variables compartidas.
Entre las variables de sincronización, se puede mantener la coherencia secuencial o la coherencia del procesador. Con SC, todas las variables de sincronización que compiten deben procesarse en orden. Sin embargo, con PC, un par de variables que compiten solo deben seguir este orden. Se puede permitir que las adquisiciones más recientes se realicen antes de las versiones más antiguas. [ cita requerida ]
Existen dos tipos de consistencia de versión: consistencia de versión con consistencia secuencial (RCsc) y consistencia de versión con consistencia de procesador (RCpc). El último tipo indica qué tipo de consistencia se aplica a las operaciones que se nominan a continuación como especiales.
Existen operaciones de memoria especiales (cf. operaciones ordinarias), que consisten en dos clases de operaciones: operaciones de sincronización o nsync . Las últimas son operaciones que no se utilizan para la sincronización; las primeras sí, y consisten en operaciones de adquisición y liberación . Una adquisición es efectivamente una operación de lectura de memoria que se utiliza para obtener acceso a un determinado conjunto de ubicaciones compartidas. La liberación, por otro lado, es una operación de escritura que se realiza para otorgar permiso para acceder a las ubicaciones compartidas.
Para la consistencia secuencial (RCsc), las restricciones son:
Para la consistencia del procesador (RCpc), el orden de escritura y lectura del programa se relaja y tiene las siguientes restricciones:
Nota: la notación anterior A → B, implica que si la operación A precede a B en el orden del programa, entonces se aplica el orden del programa.
Esta es una variante del modelo de consistencia de liberación. También requiere el uso de instrucciones de adquisición y liberación para indicar explícitamente una entrada o salida a una sección crítica. Sin embargo, bajo la consistencia de entrada, a cada variable compartida se le asigna una variable de sincronización específica para ella. De esta manera, solo cuando la adquisición es para la variable x, todas las operaciones relacionadas con x deben completarse con respecto a ese procesador. Esto permite que se produzcan operaciones concurrentes de diferentes secciones críticas de diferentes variables compartidas. La concurrencia no se puede ver para operaciones críticas en la misma variable compartida. Este modelo de consistencia será útil cuando se puedan procesar diferentes elementos de la matriz al mismo tiempo.
En la consistencia local, [14] cada proceso realiza sus propias operaciones en el orden definido por su programa. No hay ninguna restricción en el orden en el que parecen realizarse las operaciones de escritura de otros procesos. La consistencia local es el modelo de consistencia más débil en los sistemas de memoria compartida.
En términos generales, [17] todas las copias de una ubicación de memoria son eventualmente idénticas después de que se completan las escrituras de todos los procesos.
Una consistencia eventual [4] es un modelo de consistencia débil en un sistema con falta de actualizaciones simultáneas. Define que si ninguna actualización tarda mucho tiempo, todas las réplicas eventualmente se vuelven consistentes.
La mayoría de las bases de datos descentralizadas compartidas tienen un modelo de consistencia eventual, ya sea BASE: básicamente disponible; estado blando; eventualmente consistente, o una combinación de ACID y BASE a veces llamada SALT: secuencial; acordado; registrado; resistente a la manipulación, y también simétrico; sin administración; registrado; y consensual en el tiempo. [18] [19] [20]
Se pueden definir diferentes modelos de consistencia relajando uno o más requisitos de la consistencia secuencial, denominados modelos de consistencia relajada. [7] Estos modelos de consistencia no proporcionan consistencia de memoria a nivel de hardware. De hecho, los programadores son responsables de implementar la consistencia de memoria aplicando técnicas de sincronización. Los modelos anteriores se clasifican en función de cuatro criterios y se detallan más adelante.
Hay cuatro comparaciones para definir la consistencia relajada:
La consistencia secuencial tiene dos requisitos: orden del programa y atomicidad de la escritura. Se pueden obtener diferentes modelos de consistencia relajada relajando estos requisitos. Esto se hace para que, junto con las restricciones relajadas, el rendimiento aumente, pero el programador es responsable de implementar la consistencia de la memoria aplicando técnicas de sincronización y debe tener un buen conocimiento del hardware.
Posibles relajaciones:
Un método para mejorar el rendimiento a nivel de hardware consiste en relajar el orden de ejecución de una escritura seguida de una lectura, lo que oculta de forma eficaz la latencia de las operaciones de escritura. La optimización en la que se basa este tipo de relajación es que permite que las lecturas posteriores se realicen en un orden relajado con respecto a las escrituras anteriores del procesador. Debido a esta relajación, algunos programas como XXX pueden no ofrecer resultados de SC debido a esta relajación, mientras que se espera que programas como YYY ofrezcan resultados consistentes debido a la aplicación de las restricciones de orden de programa restantes.
Tres modelos entran en esta categoría. El modelo IBM 370 es el modelo más estricto. Una lectura puede completarse antes de una escritura anterior en una dirección diferente, pero tiene prohibido devolver el valor de la escritura a menos que todos los procesadores hayan visto la escritura. El modelo de orden de almacenamiento total (TSO) SPARC V8 relaja parcialmente el modelo IBM 370, ya que permite que una lectura devuelva el valor de la escritura de su propio procesador con respecto a otras escrituras en la misma ubicación, es decir, devuelve el valor de su propia escritura antes de que otros lo vean. De manera similar al modelo anterior, este no puede devolver el valor de la escritura a menos que todos los procesadores hayan visto la escritura. El modelo de consistencia del procesador (PC) es el más relajado de los tres modelos y relaja ambas restricciones de modo que una lectura puede completarse antes de una escritura anterior incluso antes de que se haga visible para otros procesadores.
En el ejemplo A, el resultado es posible solo en IBM 370 porque read(A) no se emite hasta que se completa write(A) en ese procesador. Por otro lado, este resultado es posible en TSO y PC porque permiten las lecturas de los indicadores antes de las escrituras de los indicadores en un solo procesador.
En el ejemplo B, el resultado solo es posible con PC, ya que permite que P2 devuelva el valor de una escritura incluso antes de que sea visible para P3. Esto no será posible en los otros dos modelos.
Para garantizar la coherencia secuencial en los modelos anteriores, se utilizan redes de seguridad o vallas para aplicar manualmente la restricción. El modelo IBM370 tiene algunas instrucciones de serialización especializadas que se colocan manualmente entre las operaciones. Estas instrucciones pueden consistir en instrucciones de memoria o instrucciones que no son de memoria, como las bifurcaciones. Por otro lado, los modelos TSO y PC no proporcionan redes de seguridad, pero los programadores pueden seguir utilizando operaciones de lectura-modificación-escritura para que parezca que el orden del programa se mantiene entre una escritura y una lectura siguiente. En el caso de TSO, PO parece mantenerse si la R o W que ya forma parte de una R-modificación-W se reemplaza por una R-modificación-W, esto requiere que la W en la R-modificación-W sea un "dummy" que devuelva el valor leído. De manera similar, para PC, PO parece mantenerse si la lectura se reemplaza por una escritura o ya forma parte de una R-modificación-W.
Sin embargo, no es posible optimizar el compilador después de aplicar esta relajación únicamente. Las optimizaciones del compilador requieren la flexibilidad total de reordenar dos operaciones cualesquiera en el PO, por lo que la capacidad de reordenar una escritura con respecto a una lectura no es lo suficientemente útil en este caso.
Algunos modelos relajan aún más el orden del programa al relajar incluso las restricciones de orden entre escrituras en diferentes ubicaciones. El modelo de orden de almacenamiento parcial (PSO) SPARC V8 es el único ejemplo de un modelo de este tipo. La capacidad de canalizar y superponer escrituras en diferentes ubicaciones desde el mismo procesador es la optimización clave del hardware habilitada por PSO. PSO es similar a TSO en términos de requisitos de atomicidad, en el sentido de que permite que un procesador lea el valor de su propia escritura y evita que otros procesadores lean la escritura de otro procesador antes de que la escritura sea visible para todos los demás procesadores. El orden del programa entre dos escrituras se mantiene mediante PSO mediante una instrucción STBAR explícita. La STBAR se inserta en un búfer de escritura en implementaciones con búferes de escritura FIFO. Se utiliza un contador para determinar cuándo se han completado todas las escrituras antes de la instrucción STBAR, lo que desencadena una escritura en el sistema de memoria para incrementar el contador. Un acuse de recibo de escritura disminuye el contador y, cuando el contador se convierte en 0, significa que se han completado todas las escrituras anteriores.
En los ejemplos A y B, PSO permite ambos resultados no secuencialmente consistentes. La red de seguridad que proporciona PSO es similar a la de TSO: impone un orden de programa desde una escritura hasta una lectura y refuerza la atomicidad de la escritura.
Al igual que los modelos anteriores, las relajaciones permitidas por PSO no son lo suficientemente flexibles como para ser útiles para la optimización del compilador, que requiere una optimización mucho más flexible.
En algunos modelos, todas las operaciones en diferentes ubicaciones se relajan. Una lectura o escritura se puede reordenar con respecto a una lectura o escritura diferente en una ubicación diferente. El orden débil se puede clasificar en esta categoría y dos tipos de modelos de consistencia de versiones (RCsc y RCpc) también se incluyen en este modelo. También se proponen tres arquitecturas comerciales en esta categoría de relajación: los modelos Digital Alpha, SPARC V9 de orden relajado de memoria (RMO) y IBM PowerPC.
Estas tres arquitecturas comerciales presentan instrucciones de valla explícitas como sus redes de seguridad. El modelo Alpha proporciona dos tipos de instrucciones de valla, barrera de memoria (MB) y barrera de memoria de escritura (WMB). La operación MB se puede utilizar para mantener el orden del programa de cualquier operación de memoria antes de la MB con una operación de memoria después de la barrera. De manera similar, la WMB mantiene el orden del programa solo entre escrituras. El modelo SPARC V9 RMO proporciona una instrucción MEMBAR que se puede personalizar para ordenar lecturas y escrituras anteriores con respecto a futuras operaciones de lectura y escritura. No es necesario utilizar lectura-modificación-escrituras para lograr este orden porque la instrucción MEMBAR se puede utilizar para ordenar una escritura con respecto a una lectura posterior. El modelo PowerPC utiliza una única instrucción de valla denominada instrucción SYNC. Es similar a la instrucción MB, pero con una pequeña excepción: las lecturas pueden ocurrir fuera del orden del programa incluso si se coloca una SYNC entre dos lecturas en la misma ubicación. Este modelo también difiere de Alpha y RMO en términos de atomicidad. Permite que una escritura se vea antes de que se complete una lectura. Puede ser necesaria una combinación de operaciones de lectura, modificación y escritura para crear una ilusión de atomicidad de escritura.
RMO y PowerPC permiten reordenar las lecturas en la misma ubicación. Estos modelos violan el orden secuencial de los ejemplos A y B. Una relajación adicional permitida en estos modelos es que las operaciones de memoria posteriores a una operación de lectura se pueden superponer y reordenar con respecto a la lectura. Alpha y RMO permiten que una lectura devuelva el valor de la escritura temprana de otro procesador. Desde la perspectiva de un programador, estos modelos deben mantener la ilusión de atomicidad de la escritura aunque permitan al procesador leer su propia escritura temprana.
El modelo de memoria transaccional [7] es la combinación de los modelos de coherencia de caché y consistencia de memoria como modelo de comunicación para sistemas de memoria compartida soportados por software o hardware; un modelo de memoria transaccional proporciona tanto coherencia de memoria como coherencia de caché. Una transacción es una secuencia de operaciones ejecutadas por un proceso que transforma datos de un estado consistente a otro. Una transacción se confirma cuando no hay conflicto o se cancela. En las confirmaciones, todos los cambios son visibles para todos los demás procesos cuando se completa una transacción, mientras que las cancelaciones descartan todos los cambios. En comparación con los modelos de consistencia relajada, un modelo transaccional es más fácil de usar y puede proporcionar un mayor rendimiento que un modelo de consistencia secuencial.
Algunos otros modelos de consistencia son los siguientes:
Se han concebido otros modelos de consistencia para expresar restricciones con respecto al orden o la visibilidad de las operaciones, o para abordar supuestos de fallas específicas. [24]
Tanenbaum et al., 2007 [4] define dos razones principales para la replicación: confiabilidad y rendimiento. La confiabilidad se puede lograr en un sistema de archivos replicado al cambiar a otra réplica en el caso de que falle la réplica actual. La replicación también protege los datos de ser dañados al proporcionar múltiples copias de datos en diferentes réplicas. También mejora el rendimiento al dividir el trabajo. Si bien la replicación puede mejorar el rendimiento y la confiabilidad, puede causar problemas de consistencia entre múltiples copias de datos. Las múltiples copias son consistentes si una operación de lectura devuelve el mismo valor de todas las copias y una operación de escritura como una sola operación atómica (transacción) actualiza todas las copias antes de que se realice cualquier otra operación. Tanenbaum, Andrew y Maarten Van Steen, 2007 [4] se refieren a este tipo de consistencia como consistencia estricta proporcionada por la replicación sincrónica. Sin embargo, aplicar sincronizaciones globales para mantener todas las copias consistentes es costoso. Una forma de disminuir el costo de la sincronización global y mejorar el rendimiento puede ser debilitando las restricciones de consistencia.
Tanenbaum et al., 2007 [4] define el modelo de consistencia como un contrato entre el software (procesos) y la implementación de la memoria (almacén de datos). Este modelo garantiza que si el software sigue ciertas reglas, la memoria funciona correctamente. Dado que, en un sistema sin un reloj global, definir la última operación entre escrituras es difícil, se pueden aplicar algunas restricciones sobre los valores que pueden devolverse mediante una operación de lectura. El objetivo de los modelos de consistencia centrados en los datos es proporcionar una vista consistente sobre un almacén de datos donde los procesos pueden realizar actualizaciones concurrentes.
Algunos modelos de consistencia, como los modelos de consistencia secuencial y causal, se ocupan del orden de las operaciones en datos replicados compartidos para proporcionar coherencia. En estos modelos, todas las réplicas deben concordar en un orden global coherente de las actualizaciones.
En la operación de agrupamiento, los accesos a las variables de sincronización son secuencialmente consistentes. Se permite que un proceso acceda a una variable de sincronización si se han completado todas las operaciones de escritura anteriores. En otras palabras, no se permiten los accesos a las variables de sincronización hasta que se hayan realizado por completo todas las operaciones en las variables de sincronización. [4]
En los sistemas distribuidos, es esencial mantener la coherencia secuencial para controlar las operaciones concurrentes. En algunos almacenes de datos especiales sin actualizaciones simultáneas, los modelos de coherencia centrados en el cliente pueden solucionar las incoherencias de una manera menos costosa. Los siguientes son algunos modelos de coherencia centrados en el cliente: [4]
La implementación de un modelo de consistencia se define mediante un protocolo de consistencia. Tanenbaum et al., 2007 [4] ilustra algunos protocolos de consistencia para modelos centrados en datos.
Consistencia continua introducida por Yu y Vahdat (2000). [25] En este modelo, la semántica de consistencia de una aplicación se describe mediante el uso de conits en la aplicación. Dado que los requisitos de consistencia pueden diferir según la semántica de la aplicación, Yu y Vahdat (2000) [25] creen que un modelo de consistencia uniforme predefinido puede no ser un enfoque apropiado. La aplicación debe especificar los requisitos de consistencia que satisfacen la semántica de la aplicación. En este modelo, una aplicación especifica cada requisito de consistencia como un conit (abreviatura de unidades de consistencia). Un conit puede ser una consistencia física o lógica y se utiliza para medir la consistencia. Tanenbaum et al., 2007 [4] describe la noción de un conit dando un ejemplo.
Hay tres inconsistencias que las aplicaciones pueden tolerar.
Si los tres límites de desviación se establecen en cero, el modelo de consistencia continua es el de consistencia fuerte.
Los protocolos basados en datos primarios [4] pueden considerarse como una clase de protocolos de consistencia que son más simples de implementar. Por ejemplo, el ordenamiento secuencial es un modelo de consistencia popular cuando se considera el ordenamiento consistente de las operaciones. El ordenamiento secuencial puede determinarse como un protocolo basado en datos primarios. En estos protocolos, hay un primario asociado para cada elemento de datos en un almacén de datos para coordinar las operaciones de escritura en ese elemento de datos.
En el protocolo primario más simple que admite la replicación, también conocido como protocolo de respaldo primario, las operaciones de escritura se reenvían a un solo servidor y las operaciones de lectura se pueden realizar localmente.
En los protocolos de escritura local basados en el servidor primario, [4] la copia del servidor primario se mueve entre procesos que desean realizar una actualización. Para actualizar un elemento de datos, un proceso primero lo mueve a su ubicación. Como resultado, en este enfoque, las operaciones de escritura sucesivas se pueden realizar localmente mientras cada proceso puede leer su copia local de los elementos de datos. Una vez que el servidor primario termina su actualización, la actualización se reenvía a otras réplicas y todas realizan la actualización localmente. Este enfoque sin bloqueo puede conducir a una mejora. El diagrama del protocolo de escritura local representa el enfoque de escritura local en protocolos basados en el servidor primario. Un proceso solicita una operación de escritura en un elemento de datos x. El servidor actual se considera como el nuevo servidor primario para un elemento de datos x. La operación de escritura se realiza y cuando la solicitud finaliza, el servidor primario envía una solicitud de actualización a otros servidores de respaldo. Cada respaldo envía un acuse de recibo al servidor primario después de finalizar la operación de actualización.
En los protocolos de escritura replicada, [4] a diferencia del protocolo basado en primario, todas las actualizaciones se llevan a cabo en todas las réplicas.
En la replicación activa, [4] hay un proceso asociado con cada réplica para realizar la operación de escritura. En otras palabras, las actualizaciones se envían a cada réplica en forma de una operación para que se ejecuten. Todas las actualizaciones deben realizarse en el mismo orden en todas las réplicas. Como resultado, se requiere un mecanismo de multidifusión totalmente ordenado. Existe un problema de escalabilidad en la implementación de un mecanismo de multidifusión de este tipo en grandes sistemas distribuidos. Existe otro enfoque en el que cada operación se envía a un coordinador central (secuenciador). El coordinador primero asigna un número de secuencia a cada operación y luego reenvía la operación a todas las réplicas. El segundo enfoque tampoco puede resolver el problema de escalabilidad.
La votación puede ser otro enfoque en los protocolos de escritura replicada. En este enfoque, un cliente solicita y recibe permiso de varios servidores para leer y escribir datos replicados. Como ejemplo, supongamos que en un sistema de archivos distribuido, un archivo se replica en N servidores. Para actualizar un archivo, un cliente debe enviar una solicitud a al menos N/2 + 1 para que acepten realizar una actualización. Después del acuerdo, se aplican los cambios en el archivo y se asigna un nuevo número de versión al archivo actualizado. De manera similar, para leer un archivo replicado, un cliente envía una solicitud a N/2 + 1 servidores para recibir el número de versión asociado de esos servidores. La operación de lectura se completa si todos los números de versión recibidos son la versión más reciente. [4]
En un sistema de archivos replicado, un protocolo de coherencia de caché [4] proporciona la coherencia de la caché, mientras que las cachés generalmente están controladas por los clientes. En muchos enfoques, la coherencia de la caché la proporciona el hardware subyacente. Algunos otros enfoques en sistemas distribuidos basados en middleware aplican soluciones basadas en software para proporcionar la coherencia de la caché.
Los modelos de consistencia de caché pueden diferir en sus estrategias de detección de coherencia que definen cuándo ocurren las inconsistencias. Existen dos enfoques para detectar la inconsistencia: soluciones estáticas y dinámicas. En la solución estática, un compilador determina qué variables pueden causar la inconsistencia de caché. Por lo tanto, el compilador aplica una instrucción para evitar el problema de inconsistencia. En la solución dinámica, el servidor verifica si hay inconsistencias en tiempo de ejecución para controlar la consistencia de los datos almacenados en caché que han cambiado después de que se almacenaron en caché.
La estrategia de aplicación de la coherencia es otro protocolo de coherencia de caché. Define cómo proporcionar coherencia en las cachés mediante el uso de las copias ubicadas en el servidor. Una forma de mantener la coherencia de los datos es no almacenar nunca en caché los datos compartidos. Un servidor puede conservar los datos y aplicar algún protocolo de coherencia, como los protocolos basados en primarios, para garantizar la coherencia de los datos compartidos. En esta solución, los clientes solo pueden almacenar en caché los datos privados. En el caso de que se almacenen en caché los datos compartidos, existen dos enfoques para aplicar la coherencia de la caché.
En el primer enfoque, cuando se actualizan los datos compartidos, el servidor reenvía la invalidación a todos los cachés. En el segundo enfoque, se propaga una actualización. La mayoría de los sistemas de almacenamiento en caché aplican estos dos enfoques o eligen dinámicamente uno de ellos.
Un modelo de consistencia determina las reglas de visibilidad y orden aparente de las actualizaciones. Ejemplo: * La fila X se replica en los nodos M y N * El cliente A escribe la fila X en el nodo N * Transcurre un período de tiempo t. * El cliente B lee la fila X del nodo M * ¿El cliente B ve la escritura del cliente A? La consistencia es un continuo con compensaciones