sistemas distribuidos consenso coin algoritmos algoritmo algorithm distributed consensus paxos

algorithm - coin - ¿Cuáles son los algoritmos más rápidos relacionados con Paxos para el consenso en sistemas distribuidos?



paxos algorithm (8)

Con Multi-Paxos cuando el líder está galopando, puede responder a la escritura del cliente cuando ha escuchado que la mayoría de los nodos han escrito el valor en el disco. Esto es lo más bueno y eficiente posible para mantener las garantías de consistencia que Paxos ofrece.

Por lo general, aunque las personas usan algo como paxos, como zookeeper, como un servicio externo (clúster dedicado) para mantener la información crítica coherente (quién ha bloqueado qué, quién es el líder, quién está en un clúster, cuál es la configuración del clúster) y luego ejecuta una algoritmo menos estricto con menos garantías de consistencia que se basa en aspectos específicos de la aplicación (por ejemplo, relojes vectoriales y hermanos combinados). El ebook corto distribuyó los sistemas para diversión y beneficio como una buena visión general de las alternativas.

Tenga en cuenta que muchas bases de datos compiten en la velocidad mediante el uso de valores predeterminados riesgosos que pueden comprometer la coherencia y pueden perder datos en las particiones de la red. La serie de blogs de Aphry sobre Jepson muestra si los sistemas openso de datos bien conocidos pierden datos. Uno no puede engañar al teorema de la PAC; Si configura los sistemas por seguridad, terminarán haciendo más o menos la misma mensajería y las mismas escrituras de disco que paxos. Entonces, realmente no puede decir que Paxos es lento, tiene que decir "una parte de un sistema que necesita consistencia en las particiones de red requiere un número mínimo de mensajes y descargas de disco por operación y eso es lento".

He leído el paper de Lamport sobre Paxos. También he oído que no se usa mucho en la práctica, por razones de rendimiento. ¿Qué algoritmos se usan comúnmente para el consenso en sistemas distribuidos?

Debes revisar el proyecto Apache Zookeeper. Se usa en producción por Yahoo! y Facebook entre otros.

http://hadoop.apache.org/zookeeper/

Si busca artículos académicos que lo describan, se describe en un documento en usenix ATC''10. El protocolo de consenso (una variante de Paxos) se describe en un artículo en DSN''11.

El sistema Paxos que ejecuto (que es compatible con sitios web realmente grandes) está a medio camino entre Paxos Multi-Paxos básicos. Planeo moverlo a una implementación completa de Multi-Paxos.

Paxos no es tan bueno como un sistema de almacenamiento de datos de alto rendimiento, pero es excelente en el soporte de esos sistemas al proporcionar una elección líder. Por ejemplo, supongamos que tiene un almacén de datos replicado en el que desea un solo maestro por razones de rendimiento. Los nodos de su almacén de datos utilizarán el sistema Paxos para elegir el maestro.

Al igual que Google Chubby, mi sistema se ejecuta como un servicio y también puede almacenar datos como contenedor de configuración. (Uso la configuración a la ligera; escucho que Google usa Chubby para DNS). Estos datos no cambian tan a menudo como lo hacen los usuarios, por lo que no necesitan SLA de escritura de alto rendimiento. La lectura, por otro lado, es extremadamente rápida porque está completamente replicada y se puede leer desde cualquier nodo.

Actualizar

Desde que escribí esto, actualicé mi sistema Paxos. Ahora estoy usando un protocolo de consenso en cadena como el sistema de consenso primario. El sistema de cadena todavía utiliza Paxos básicos para la reconfiguración, incluida la notificación de los nodos de la cadena cuando cambia la membresía de la cadena.

Google documentó cómo hicieron paxos rápidos para su megastore en el siguiente documento: Link .

No estoy seguro de si esto es útil (ya que no se trata de información de producción real), pero en nuestro curso de "sistemas distribuidos" hemos estudiado, junto con Paxos, los algoritmos de Chandra-Toueg y Mostefaoui-Raynal (de este último nuestro profesor era especialmente aficionado).

Paxos es óptimo en términos de rendimiento de los protocolos de consenso, al menos en términos del número de retrasos en la red (que a menudo es el factor dominante). Es evidente que no es posible lograr un consenso confiable mientras se toleran hasta f fallas sin una sola comunicación de ida y vuelta a al menos (f-1) otros nodos entre una solicitud del cliente y la confirmación correspondiente, y Paxos logra este límite inferior. Esto proporciona un límite estricto en la latencia de cada solicitud a un protocolo basado en consenso, independientemente de la implementación. En particular, Raft, Zab, Viewstamped Replication y todas las demás variantes en los protocolos de consenso tienen la misma restricción de rendimiento.

Una cosa que se puede mejorar con los Paxos estándar (también Raft, Zab, ...) es que hay un líder distinguido que termina haciendo más que su parte justa del trabajo y, por lo tanto, puede terminar siendo un cuello de botella. Existe un protocolo conocido como Paxos igualitarios que distribuye la carga a través de múltiples líderes, aunque su IMO es extremadamente complicada, solo es aplicable a ciertos dominios y aún debe obedecer el límite inferior del número de viajes de ida y vuelta dentro de cada solicitud. Consulte el documento "Hay más consenso en los parlamentos igualitarios" de Moraru y otros para obtener más detalles.

Cuando escuchas que Paxos se usa raramente debido a su bajo rendimiento, con frecuencia significa que el consenso en sí mismo rara vez se usa debido a un bajo rendimiento, y esto es una crítica justa: es posible lograr un rendimiento mucho mayor si puedes evitar la necesidad para la coordinación basada en el consenso entre nodos tanto como sea posible, porque esto permite la escalabilidad horizontal.

Snarkily, también es posible lograr un mejor rendimiento al afirmar que se está utilizando un protocolo de consenso adecuado, pero en realidad se está haciendo algo que falla en algunos casos. El blog de Aphyr está lleno de ejemplos de estos fallos que no son tan raros como le gustaría, donde las implementaciones de la base de datos han introducido errores en los protocolos de buen consenso a modo de "optimización", o bien se han desarrollado protocolos personalizados de consenso que no se pueden hacer. totalmente correcto de alguna manera sutil. Esto es difícil.