La replicación optimista , también conocida como replicación perezosa , [1] [2] es una estrategia de replicación , en la que las réplicas pueden divergir. [3]
Los sistemas de replicación pesimistas tradicionales intentan garantizar desde el principio que todas las réplicas sean idénticas entre sí, como si solo hubiera una única copia de los datos desde el principio. La replicación optimista elimina esto a favor de la consistencia eventual , lo que significa que se garantiza que las réplicas converjan solo cuando el sistema ha estado inactivo durante un período de tiempo. Como resultado, ya no es necesario esperar a que todas las copias se sincronicen al actualizar los datos, lo que ayuda a la simultaneidad y el paralelismo . La compensación es que diferentes réplicas pueden requerir una reconciliación explícita más adelante, lo que podría resultar difícil o incluso insoluble.
Algoritmos
Un algoritmo de replicación optimista consta de cinco elementos:
- Envío de operaciones : los usuarios envían operaciones en sitios independientes.
- Propagación : cada sitio comparte las operaciones que conoce con el resto del sistema.
- Programación : cada sitio decide un pedido para las operaciones que conoce.
- Resolución de conflictos : si hay algún conflicto entre las operaciones que un sitio ha programado, debe modificarlo de alguna manera.
- Compromiso : Los sitios acuerdan un cronograma final y el resultado de la resolución de conflictos, y las operaciones se vuelven permanentes.
Hay dos estrategias de propagación: transferencia de estado, donde los sitios propagan una representación del estado actual, y transferencia de operaciones, donde los sitios propagan las operaciones que se realizaron (esencialmente, una lista de instrucciones sobre cómo alcanzar el nuevo estado).
La programación y la resolución de conflictos pueden ser sintácticas o semánticas. Los sistemas sintácticos se basan en información general, como cuándo o dónde se envió una operación. Los sistemas semánticos pueden hacer uso de información específica de la aplicación para tomar decisiones más inteligentes. Tenga en cuenta que los sistemas de transferencia de estado generalmente no tienen información sobre la semántica de los datos que se transfieren, por lo que deben utilizar la programación sintáctica y la resolución de conflictos.
Ejemplos de
Un ejemplo bien conocido de un sistema basado en la replicación optimista es el sistema de control de versiones CVS , o cualquier otro sistema de control de versiones que utilice el paradigma copiar-modificar-fusionar . CVS cubre cada uno de los cinco elementos:
- Envío de operaciones: los usuarios editan las versiones locales de los archivos.
- Propagación: los usuarios extraen manualmente las actualizaciones de un servidor central o envían los cambios una vez que el usuario siente que está listo.
- Programación: las operaciones se programan en el orden en que las recibe el servidor central.
- Resolución de conflictos: cuando un usuario empuja o saca del repositorio central, cualquier conflicto se marcará para que ese usuario lo solucione manualmente.
- Compromiso: Una vez que el servidor central acepta los cambios que impulsa un usuario, se comprometen permanentemente.
Un caso especial de replicación es la sincronización , donde solo hay dos réplicas. Por ejemplo, los asistentes digitales personales (PDA) permiten a los usuarios editar datos en la PDA o en una computadora, y luego fusionar estos dos conjuntos de datos. Sin embargo, tenga en cuenta que la replicación es un problema más amplio que la sincronización, ya que puede haber más de dos réplicas.
Otros ejemplos incluyen:
- Usenet y otros sistemas que utilizan la regla de escritura de Thomas (ver Rfc677 )
- Replicación de base de datos multimaestro [4]
- El sistema de archivos distribuido Coda
- Transformación operativa , un marco teórico para la edición grupal
- Wikis de igual a igual
- Tipos de datos replicados sin conflictos
- La base de datos distribuida Bayou [5]
- IceCube [6]
Trascendencia
Las aplicaciones creadas sobre bases de datos replicadas optimistas deben tener cuidado para asegurarse de que las actualizaciones retrasadas observadas no perjudiquen la corrección de la aplicación.
Como ejemplo simple, si una aplicación contiene una forma de ver alguna parte del estado de la base de datos y una forma de editarlo, los usuarios pueden editar ese estado pero no verlo cambiar en el visor. Alarmados de que su edición "no funcionó", es posible que vuelvan a intentarlo, posiblemente más de una vez. Si las actualizaciones no son idempotentes (por ejemplo, incrementan un valor), esto puede conducir al desastre. Incluso si son idempotentes, las actualizaciones falsas de la base de datos pueden provocar cuellos de botella en el rendimiento, especialmente cuando los sistemas de base de datos están procesando cargas pesadas; esto puede convertirse en un círculo vicioso.
La prueba de aplicaciones se realiza a menudo en un entorno de prueba, de menor tamaño (quizás sólo un servidor) y menos cargado que el entorno "en vivo". El comportamiento de replicación de una instalación de este tipo puede diferir de un entorno en vivo en formas que significan que es poco probable que se observe un retraso de replicación en las pruebas, enmascarando errores sensibles a la replicación. Los desarrolladores de aplicaciones deben tener mucho cuidado con las suposiciones que hacen sobre el efecto de una actualización de la base de datos y deben asegurarse de simular retrasos en sus entornos de prueba.
Las bases de datos replicadas de manera optimista deben tener mucho cuidado al ofrecer características tales como restricciones de validez en los datos. Si una actualización determinada puede o no ser aceptada en función del estado actual del registro, entonces dos actualizaciones (A y B) pueden ser legales individualmente contra el estado inicial del sistema, pero una o más de las actualizaciones pueden no ser legales. contra el estado del sistema después de la otra actualización (por ejemplo, A y B son legales, pero AB o BA son ilegales). Si A y B se inician aproximadamente al mismo tiempo dentro de la base de datos, entonces A se puede aplicar con éxito en algunos nodos y B en otros, pero tan pronto como A y B "se encuentran" y se intenta uno en un nodo que ya ha aplicado el otro, se encontrará un conflicto. En este caso, el sistema debe decidir qué actualización "gana" finalmente y hacer los arreglos necesarios para que los nodos que ya hayan aplicado la actualización perdida la reviertan. Sin embargo, algunos nodos pueden exponer temporalmente el estado con la actualización revertida, y es posible que no haya forma de informar al usuario que inició la actualización de su falla, sin requerir que espere (potencialmente para siempre) la confirmación de aceptación en cada nodo.
Referencias
- ^ Ladino, R .; Liskov, B .; Shrira, L .; Ghemawat, S. (1992). "Proporcionar alta disponibilidad mediante la replicación diferida". Transacciones ACM en sistemas informáticos . 10 (4): 360–391. CiteSeerX 10.1.1.586.7749 . doi : 10.1145 / 138873.138877 . S2CID 2219840 .
- ^ Ladin, R .; Liskov, B .; Shrira, L. (1990). Replicación perezosa: explotando la semántica de los servicios distribuidos . Actas del Noveno Simposio Anual de ACM sobre Principios de Computación Distribuida . págs. 43–57. doi : 10.1145 / 93385.93399 .
- ^ Saito, Yasushi; Shapiro, Marc (2005). "Replicación optimista". Encuestas de computación ACM . 37 (1): 42–81. CiteSeerX 10.1.1.324.3599 . doi : 10.1145 / 1057977.1057980 . S2CID 1503367 .
- ^ Gray, J .; Helland, P .; O'Neil, P .; Shasha, D. (1996). Los peligros de la replicación y una solución (PDF) . Actas de la Conferencia Internacional ACM SIGMOD de 1996 sobre Gestión de Datos . págs. 173-182. doi : 10.1145 / 233269.233330 .[ enlace muerto permanente ]
- ^ Terry, DB; Theimer, MM; Petersen, K .; Demers, AJ; Spreitzer, MJ; Hauser, CH (1995). Gestión de conflictos de actualización en Bayou, un sistema de almacenamiento replicado débilmente conectado . Actas del Decimoquinto Simposio de ACM sobre principios de sistemas operativos. págs. 172-182. doi : 10.1145 / 224056.224070 .
- ^ Kermarrec, AM; Rowstron, A .; Shapiro, M .; Druschel, P. (2001). El enfoque de IceCube para la reconciliación de réplicas divergentes . Actas del Vigésimo Simposio Anual de ACM sobre Principios de Computación Distribuida . págs. 210–218. doi : 10.1145 / 383962.384020 .
enlaces externos
- Saito, Yasushi; Shapiro, Marc (septiembre de 2003). "Replicación optimista" (PDF) . Microsoft. Cite journal requiere
|journal=
( ayuda )