algorithm - ¿Cuál es la diferencia entre Paxos y W+R>=N en Cassandra?
synchronization apache-zookeeper (4)
No hay diferencia. La definición de quórum dice que la intersección de dos quórumes no está vacía. El quórum de mayoría simple es un ejemplo, NO una definición. Eche un vistazo al último documento del Dr. Lamport, "Paxos verticales", donde dio algunas otras configuraciones posibles de quórumes.
Protocolo de paxos de varios decretos (AKA Multi-Paxos), en estado estable es solo una confirmación de dos fases. Los cambios en el número de boletas solo son necesarios cuando el líder falla.
El protocolo de replicación de Zookeeper (ZAB) y RAFT se basan en Paxos. Las diferencias están en la detección de fallas y la transición después de que un líder falla.
Las bases de datos tipo dinamo (por ejemplo, Cassandra) pueden imponer la consistencia por medio del quórum, es decir, un número de réplicas escritas sincrónicamente (W) y un número de réplicas para leer (R) deben elegirse de tal manera que W + R> N donde N es un factor de replicación. Por otro lado, los sistemas basados en PAXOS como Zookeeper también se utilizan como un almacenamiento consistente tolerante a fallos.
¿Cuál es la diferencia entre estos dos enfoques? ¿PAXOS proporciona garantías que no son proporcionadas por el esquema W + R> N?
Paxos no es trivial de implementar, y es lo suficientemente caro como para que muchos sistemas que lo usan también usen pistas, o solo para la elección del líder, o algo así. Sin embargo, proporciona una consistencia garantizada en presencia de fallas, sujeto por supuesto a los límites de su modelo particular de falla.
Los primeros sistemas basados en el quórum que vi asumieron algún tipo de infraestructura líder o de transacción que garantizaría la suficiente coherencia en la que podría confiar que el mecanismo del quórum funcionó. Esta infraestructura bien podría estar basada en Paxos.
Al ver descripciones como https://cloudant.com/blog/dynamo-and-couchdb-clusters/ , parece que Dynamo no se basa en una infraestructura que garantice la coherencia de su sistema de quórum, por lo que es muy inteligente o ¿esquinas de corte? Según http://muratbuffalo.blogspot.co.uk/2010/11/dynamo-amazons-highly-available-key.html , "El sistema Dynamo enfatiza la disponibilidad hasta el punto de sacrificar la consistencia. El resumen dice" El dinamo sacrifica la consistencia bajo ciertos escenarios de falla ". En realidad, más tarde, queda claro que Dynamo sacrifica la consistencia incluso en ausencia de fallas: Dynamo puede volverse inconsistente en la presencia de múltiples solicitudes de escritura concurrentes, ya que las réplicas pueden divergir debido a múltiples coordinadores". (cita final)
Por lo tanto, parece que en el caso de los quórumes implementados en Dynamo, Paxos ofrece garantías de confiabilidad más sólidas.
Paxos y el quórum W + R> N intentan resolver problemas ligeramente diferentes. Paxos generalmente se describe como una forma de replicar una máquina de estado, pero de hecho es más como un registro distribuido: cada elemento escrito en el registro obtiene un índice, y los diferentes servidores finalmente mantienen los mismos elementos de registro + su índice. (La máquina de estado replicada se puede lograr al escribir en el registro las entradas a la máquina de estado y cada servidor reproduce la máquina de estado en las entradas acordadas de acuerdo con su índice). Puedes leer más sobre Paxos en una publicación de blog que escribí here .
El quórum W + R> N resuelve el problema de compartir un valor único entre varios servidores. En la academia se llama "registro compartido". Un registro compartido tiene dos operaciones: lectura y escritura, donde esperamos que la lectura devuelva el valor de la escritura anterior.
Entonces, Paxos y el quórum W + R> N viven en diferentes dominios y tienen diferentes propiedades (por ejemplo, Paxos guarda una lista ordenada de elementos). Sin embargo, Paxos se puede usar para implementar un registro compartido, y un quórum W + R> N se puede usar para implementar un registro distribuido (aunque muy ineficientemente).
Dicho todo lo anterior, a veces los quórumes W + R> N no se implementan de forma totalmente robusta, ya que requerirá más de una ronda de comunicación. Por lo tanto, en los sistemas que desean una latencia baja, es posible que su implementación de quórumes W + R> N proporcione propiedades más débiles (por ejemplo, pueden existir valores en conflicto).
En resumen, en teoría, Paxos y W + R> N pueden lograr los mismos objetivos. En la práctica, sería muy ineficiente, y cada uno es mejor para algo ligeramente diferente. Aún más práctico, W + R> N no siempre se implementa completamente, lo que asusta algunas propiedades de consistencia para la velocidad.
Actualización : Paxos admite un modelo de falla muy general: los mensajes pueden eliminarse, los nodos pueden bloquearse y reiniciarse. El esquema de quórum W + R> N tiene diferentes implementaciones, muchas de las cuales asumen fallas menos generales. Por lo tanto, la diferencia entre los dos también depende de la suposición de las posibles fallas que son compatibles.
Sí, Paxos proporciona garantías que no son proporcionadas por los sistemas tipo Dynamo y sus quórumes de lectura-escritura. La diferencia es cómo se manejan las fallas y qué sucede durante una escritura. Después de una escritura exitosa, ambos tipos de sistemas se comportan de manera similar. Los datos se guardarán y estarán disponibles para su lectura posterior (hasta que se sobrescriban o eliminen), etc.
La diferencia aparece durante una escritura y después de fallos. Hasta que no obtenga una respuesta exitosa de los nodos W al escribir algo en los sistemas eventualmente coherentes, es posible que los datos se hayan escrito en algunos nodos y no en otros, y no hay garantía de que todo el sistema esté de acuerdo con el valor actual. Si intenta leer los datos nuevamente en este punto, algunos clientes pueden recuperar los datos nuevos y otros los datos antiguos. En otras palabras, el sistema no es inmediatamente consistente. Esto se debe a que las escrituras no son atómicas en los nodos de estos sistemas. Por lo general, existen mecanismos para "curar" una inconsistencia como esta y "eventualmente" el sistema volverá a ser consistente (es decir, las lecturas volverán a tener el mismo valor, hasta que se escriba algo nuevo). Esta es la razón por la que a menudo se los llama "eventualmente consistentes". Las inconsistencias pueden aparecer (y lo harán), pero siempre serán tratadas y reconciliadas eventualmente.
Con Paxos, las escrituras pueden hacerse atómicas a través de nodos y, por lo tanto, es posible evitar las inconsistencias entre nodos. El algoritmo de Paxos permite garantizar que los nodos no defectuosos nunca estén en desacuerdo con el resultado de una escritura, en cualquier momento. O bien la escritura tuvo éxito en todas partes o en ninguna parte. Nunca habrá lecturas inconsistentes en ningún punto (si se implementa correctamente y si todas las suposiciones se mantienen, por supuesto). Sin embargo, esto tiene un costo. Principalmente, es posible que el sistema deba retrasar algunas solicitudes y no estar disponible cuando, por ejemplo, demasiados nodos (o la comunicación entre ellos) no estén funcionando. Esto es necesario para asegurar que no se den respuestas inconsistentes.
Para resumir: la principal diferencia es que los sistemas de tipo Dynamo pueden devolver resultados inconsistentes durante las escrituras o después de fallas por algún tiempo (pero eventualmente se recuperarán), mientras que los sistemas basados en Paxos pueden garantizar que nunca haya tales inconsistencias al ser a veces no disponible y retrasando las solicitudes en su lugar.