Consistencia de datos
En Informática, en un sistema distribuido, tales como una memoria compartida distribuida o almacenes de datos distribuido, tales como una base de datos, sistema de archivos, caché web o sistemas de replicación optimista, hay una serie de posibles modelos de consistencia de datos. Se dice que un sistema soporta un determinado modelo, si las operaciones en memoria siguen normas específicas. La consistencia de los datos es definida entre el programador y el sistema, que garantiza que si el programador sigue las reglas, la memoria será consistente y el resultado de las operaciones de memoria será predecible.
Los lenguajes de alto nivel, tales como C, C++ y Java, respetan parcialmente este modelo traduciendo operaciones de memoria en operaciones de bajo nivel para preservar la memoria semántica. Para mantener el modelo, los compiladores pueden reordenar algunas instrucciones de memoria, y las llamadas a las bibliotecas como "pthread_mutex_lock()", encapsular la sincronización necesaria.
A continuación se muestran los distintos tipos, ordenados según la fuerza de la consistencia que ofrecen:
Modelos de consistencia fuerte[editar]
Consistencia linealizable[editar]
Los sistemas con consistencia linealizable presentan las características de garantía de ejecución de operaciones a tiempo real, respetando su orden, siendo que este orden también se debe preservar de manera global en las operaciones que hacen overlapping. Las ventajas que posee sobre la secuencialidad es que mantiene la ordenación a tiempo real de las operaciones, lo que se asemeja más al concepto de atomicidad. Además, esta consistencia se mantiene si se combinan implementaciones linealizables separadas de dos objetos.
Las operaciones de lectura siempre devolverán lo último escrito en memoria, independientemente de cuando se haya solicitado. Las siguientes peticiones de lectura devolverán el mismo resultado siempre que no se haya vuelto a escribir en memoria, independientemente del cliente.
La consistencia linealizable es una forma de consistencia secuencial con restricción de tiempo real.[1]
Consistencia secuencial[editar]
Se produce consistencia secuencial cuando todas las operaciones de datos de diferentes sistemas aparentan ser atómicos, como si ocurriesen todas en un sistema uniprocesador ejecutadas de manera secuencia,con un orden que esté en concordancia con aquel visto en los procesos individuales.[2]
En varios sistemas, es decir diferentes procesadores, esto puede dejar de cumplirse ya que el acceso puede ocurrir en diferente orden.
La consistencia secuencial trata de corregir esto para que las operaciones aparenten atomicidad.
Para obtener la consistencia secuencial, se requiere que las operaciones de memoria estén completadas antes de acceder a la siguiente instrucción según el orden del programa. Es también necesaria la serialización de las escrituras a memoria: las escrituras deberán estar finalizadas, y su valor no podrá ser devuelto por una lectura hasta que la escritura sea visible para todos los sistemas[3].
La consistencia secuencial de una implementación de dos objetos con consistencia secuencial no es garantizada,sin embargo se puede obtener una concurrencia elevada y mayor rendimiento que en la consistencia linealizable
La consistencia secuencial puede producir una pérdida de optimización al no forzar el orden estricto.
En todo caso, se debe respetar siempre el orden aparente de programa para el usuario en contra del tiempo real de ejecución.
Consistencia de causalidad[editar]
La consistencia de causalidad es un modelo de consistencia más fuerte que otros modelos como la consistencia eventual, pero más débil que los modelos secuenciales o los modelos linealizables. Es el modelo de consistencia más fuerte posible en sistemas distribuidos tolerantes a fallos.[4] Los modelos más fuertes traen consigo unas mayores garantías de seguridad en el orden de los procesos, a cambio de una notable pérdida de rendimiento, demostrado por el teorema CAP, el cual prueba que es imposible garantizar simultáneamente de consistencia y disponibilidad o latencia en un sistema distribuido.
La consistencia de causal permite una mayor eficiencia al ser posible más ejecuciones, manteniendo un modelo viable para los programadores.[5]
En la consistencia causal no se podrá leer un dato hasta que todas las operaciones que hayan llevado a su escritura o actualización sean visibles. Un sistema será consistente de manera cual, pues, si siguen el principio de causalidad, tal que si se cumple la operación de escritura a, y lectura b, a→b, b obtendrá el dato escrito por a.
Modelos de consistencia débil[editar]
Consistencia débil[editar]
El modelo de consistencia débil presenta un mayor potencial de rendimiento. Los sistemas con este modelo dependen de la sincronización en el hardware para garantizar el orden de las operaciones iniciadas por los diferentes procesadores.
Un sistema con consistencia débil cumple con una serie de propiedades:
- Definición formal de la relación entre elementos software y hardware y del cumplimiento de los requerimientos.
- Simpleza del modelo hardware para el programador.
- El diseño hardware facilita implementaciones paralelas de alto rendimiento.
Por lo tanto, un sistema que cumpla las propiedades anteriores será consistentemente débil. Dicho de otro modo, existirá consistencia débil si se aparenta ser secuencialmente consistente para el programador, obedeciendo todo el software un modelo de sincronización.[6]
Un sistema de este tipo presenta las complicaciones de no ser secuencial, lo que dificulta el entendimiento para el programador si se vuelve complejo.También se pueden presentar restricciones al software para conseguir la sincronización, dificultando a veces detectar que tareas son las productoras de esta sincronización.
Consistencia liberada[editar]
La consistencia liberada es un modelo de consistencia débil creado con el objetivo de reducir la latencia en sistemas distribuidos. Su funcionamiento se basa en retrasar los accesos a memoria compartida hasta que otros accesos especiales definidos para el modelo ocurran.
Las características de un sistema con consistencia liberada son:
- Antes de que un acceso ordinario a memoria se permita, todos los accesos a zonas de exclusión mutua hechos anteriormente se deben finalizar.
- Antes de liberar la zona, se deben finalizar todas las lecturas y escrituras previas.
- Los accesos especiales son secuencialmente consistentes respecto el uno del otro.[7]
Las lecturas se realizan respecto a otro procesador o sistema cuando una escritura por ese sistema no puede volver a afectar el valor devuelto por la lectura. Las escrituras respecto a otro procesador se realizan cuando este ha devuelto el nuevo valor escrito. Los accesos se harán respecto a todos los procesadores.[8]
La consistencia liberada presenta una modificación, conocida como consistencia liberada vaga, que asume que el hilo en posesión de la zona de exclusión mútua no requiere de los valores escritos por otros hilos.
Consistencia eventual[editar]
La consistencia liberada es un modelo de consistencia débil tal que cumple lo siguiente: el sistema garantiza que todos los accesos a zonas de exclusión mútua donde se obtenga un valor, cada acceso obtendrá el mismo valor devuelto mientras no se haya hecho ninguna actualización a este.[9] En otras palabras, una cierta operación deberá ser finalmente visible para todos los sistemas. La consistencia eventual es suficiente para crear programas clientes.[10]
Un sistema con únicamente este modelo puede presentar una serie de inconsistencias:
- Lectura de escrituras propias: este tipo de consistencia no garantiza que, en una misma sesión, un usuario no pueda leer el mismo dato que ha escrito
- Lectura monótona: solicitar varias lecturas en una misma sesión no tiene porqué aumentar el número de lecturas totales.
Se pueden evitar estas anomalías añadiendo garantías de seguridad de orden de operaciones.[11]
Es utilizado frecuentemente con los DNS.
Consistencia delta[editar]
También conocida como consistencia-δ, es un modelo de consistencia débil. Se caracteriza por poseer un tipo de dato conocido como CDRT, de las siglas en inglés Conflict-Free Replicated Data Type, o tipo de datos replicado libre de conflicto.
La caracterítisca principal de los sistemas con este modelo es que las actualizaciones a los datos se propagarán por los sistemas y serán visibles a todos ellos después de un intervalo de tiempo δ: las réplicas de un mismo tipo de dato pueden divergir, pero se asegurá que después de un cierto periodo de tiempo todas estas réplicas convergeran al mismo valor.[12]
Consistencia PRAM[editar]
La consistencia PRAM (de Pipelined Random Access Memory), también se conoce como consistencia FIFO es un modelo de consistencia.
Es uno de los primeros modelos de consistencia surgidos, pensado para poder permitir la escalabilidad en los sistemas distribuidos sin pérdida de rendimiento.[13]
Se basa en una relajación de la coherencia de la memoria existente para permitir una mayor concurrencia y rendimiento: esto lo consigue haciendo que cada sistema o procesador tenga visión de la memoria compartida entre el conjunto de sistemas en su memoria local. Las lecturas se realizan de forma normal, leyendo la memoria local. Las escrituras se realizan tanto de forma local como iniciando una acción global: se escribe en su propia memoria, y se envía un mensaje a los demás sistemas. Una vez llegan estos mensajes a los otros sistemas, estos realizan la misma operación y escriben en su propia memoria local.[14]
Este envío de mensajes no es confirmado por los demás procesadores. Además, este tipo de consistencia no tiene porqué respetar la secuencialidad.
Consistencia vector-campo[editar]
La consistencia vector-campo es un modelo reciente de consistencia.[15] A diferencia del modelo delta, este sí permite la divergencia de los objetos o de los datos, concretamente permite divergencia conectada.
Este tipo especial de divergencia se caracteriza por ser variable y dinámica: de esta manera se puede modificar la consistencia en los sistemas, aumentándola o disminuyéndola según el estado de ejecución del programa.
Uno de sus principales usos en es los videojuegos, específicamente los videojuego multijugador. La medida de consistencia será propia para cada elemento, tal que posee una función de consistencia basada en la distancia al elemento, con los elementos a sus alrededor siendo forzados a tener la misma consistencia.
La consistencia se describe como un vector 3-dimensional representando:
- el tiempo de actualización de consistencia.
- Número máximo de réplicas pérdidas o modificadas.
- Valor de diferencia relativa máxima permitida.
Con esto se facilita el desarrollo de videojuegos multijugador distribuidos permitiendo una notable mejora en el rendimiento y reduciendo el coste en las comunicaciones inalámbricas.
| Control de autoridades |
|
|---|
Datos: Q5163219
- ↑ Herlihy, Maurice P.; Wing, Jeannette M. (1 de julio de 1990). «Linearizability: a correctness condition for concurrent objects». ACM Transactions on Programming Languages and Systems 12 (3): 463-492. ISSN 0164-0925. doi:10.1145/78969.78972. Consultado el 10 de mayo de 2023.
- ↑ Lamport (1979-09). «How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs». IEEE Transactions on Computers. C-28 (9): 690-691. ISSN 1557-9956. doi:10.1109/TC.1979.1675439. Consultado el 10 de mayo de 2023.
- ↑ Adve, Sarita V. (1-9-1995). «Shared Memory Consistency Models: A Tutorial». WRL Reasearch report. Consultado el 7-5-2023.
- ↑ Camilleri, Carl; Vella, Joseph G.; Nezval, Vitezslav (2023). Hameurlain, Abdelkader, ed. D-Thespis: A Distributed Actor-Based Causally Consistent DBMS (en inglés). Springer. pp. 126-165. ISBN 978-3-662-66863-4. doi:10.1007/978-3-662-66863-4_6?fbclid=iwar2z279grm0autvqgm29arfdt4_nbadeuzcohp_ssv7b4uw29m7djdkkah8. Consultado el 11 de mayo de 2023.
- ↑ Ahamad, Mustaque; Neiger, Gil; Kohli, Prince; Burns, James E.; Hutto, Phillip W. (1993). Causal Memory: Definitions, Implementation, and Programming (en inglés estadounidense). Consultado el 4 de mayo de 2023.
- ↑ Sarita V. Adve, Mark D. Hill. «Weak Ordering -A new definition». CiteSeerX (en inglés). Consultado el 11 de mayo de 2023.
- ↑ Renesse, Robbert; Tanenbaum, Andrew S.; Mullender, Sape J. (1990). The evolution of a distributed operating system. Springer Berlin Heidelberg. pp. 1-12. ISBN 978-3-540-52609-4. Consultado el 11 de mayo de 2023.
- ↑ Keleher, Pete; Cox, Alan L.; Zwaenepoel, Willy (1 de abril de 1992). «Lazy release consistency for software distributed shared memory». Proceedings of the 19th annual international symposium on Computer architecture. ISCA '92 (Association for Computing Machinery): 13-21. ISBN 978-0-89791-509-0. doi:10.1145/139669.139676. Consultado el 8 de mayo de 2023.
- ↑ Vogels, Werner (1 de octubre de 2008). «Eventually Consistent: Building reliable distributed systems at a worldwide scale demands trade-offs?between consistency and availability.». Queue 6 (6): 14-19. ISSN 1542-7730. doi:10.1145/1466443.1466448. Consultado el 5 de mayo de 2023.
- ↑ Burckhardt, Sebastian (9 de octubre de 2014). «Principles of Eventual Consistency». Foundations and Trends in Programming Languages 1 (1-2): 1-150. ISSN 2325-1107. doi:10.1561/2500000011. Consultado el 5 de mayo de 2023.
- ↑ Bailis, Peter; Ghodsi, Ali (1 de marzo de 2013). «Eventual Consistency Today: Limitations, Extensions, and Beyond: How can applications be built on eventually consistent infrastructure given no guarantee of safety?». Queue 11 (3): 20-32. ISSN 1542-7730. doi:10.1145/2460276.2462076. Consultado el 6 de mayo de 2023.
- ↑ Almeida, Paulo Sérgio; Shoker, Ali; Baquero, Carlos (1 de enero de 2018). «Delta state replicated data types». Journal of Parallel and Distributed Computing (en inglés) 111: 162-173. ISSN 0743-7315. doi:10.1016/j.jpdc.2017.08.003. Consultado el 7 de mayo de 2023.
- ↑ «PRAM: A Scalable Shared Memory | Computer Science Department at Princeton University». www.cs.princeton.edu. Consultado el 11 de mayo de 2023.
- ↑ Lê, Nhat Minh; Guatto, Adrien; Cohen, Albert; Pop, Antoniu (2013-10). «Correct and Efficient Bounded FIFO Queues». 2013 25th International Symposium on Computer Architecture and High Performance Computing: 144-151. doi:10.1109/SBAC-PAD.2013.8. Consultado el 11 de mayo de 2023.
- ↑ Santos, Nuno; Veiga, Luís; Ferreira, Paulo (2007). Vector-Field Consistency for Ad-Hoc Gaming. Springer Berlin Heidelberg. pp. 80-100. ISBN 978-3-540-76777-0. Consultado el 11 de mayo de 2023.