algorithm - problema - algoritmo de consenso sistemas distribuidos
¿Cuándo usar Paxos(casos reales de uso práctico)? (5)
¿Podría alguien darme una lista de casos reales de uso de Paxos? Estos son problemas reales que requieren consenso como parte de un problema mayor.
¿Es el siguiente un caso de uso de Paxos?
Supongamos que hay dos clientes que juegan póquer entre sí en un servidor de póquer. El servidor de póquer está replicado. Mi entendimiento de Paxos es que podría usarse para mantener la coherencia de las estructuras de datos en memoria que representan la mano actual del póker. Es decir, asegúrese de que todas las réplicas tengan exactamente el mismo estado de memoria de la mano.
¿Pero por qué es necesario Paxos? Supongamos que una nueva tarjeta necesita ser repartida. Cada réplica que ejecuta el mismo código generará la misma tarjeta si todo fue correcto. ¿Por qué los clientes no pueden simplemente solicitar el estado más reciente de todos los servidores replicados y elegir la tarjeta que aparece más? Por lo tanto, si un servidor tuvo un error, el cliente seguirá obteniendo el estado correcto de solo elegir la mayoría.
Casos de uso en la vida real:
En el caso que describas, tienes razón, Paxos no es realmente necesario: una única autoridad central puede generar una permutación para el mazo y distribuirla a todos al principio de la mano. De hecho, para un juego de póker en general, donde hay un orden de turno estricto y un solo jugador activo como en el póquer, no puedo ver una situación sensata en la que deba usar Paxos, excepto quizás para elegir la autoridad central que baraja barajas
Un mejor ejemplo podría ser un juego con movimientos simultáneos, como Jeopardy. Los Paxos en esta situación permitirían a todos los servidores decidir juntos en qué secuencia ocurrieron una serie de eventos cronometrados (como las pulsaciones del timbre), de modo que todos los servidores lleguen a la misma conclusión.
Paxos se utiliza para la replicación basada en WAN de los repositorios de Subversion y la alta disponibilidad de Hadoop NameNode por parte de la compañía para la que trabajo (WANdisco plc.)
Usted asume que todos los servidores están sincronizados entre sí (es decir, tienen el mismo estado), por lo que cuando un servidor necesita seleccionar la siguiente tarjeta, cada uno de los servidores seleccionará exactamente la misma tarjeta (asumiendo que su código es determinista).
Sin embargo, el estado de sus servidores también depende de las acciones del usuario. Por ejemplo, si un usuario decide aumentar los $ 50, su servidor necesita almacenar esa información en algún lugar. Ahora, supongamos que su servidor respondió "ok" al cliente web (supongo que es un juego de póquer basado en la web) y luego el servidor se bloqueó. Es posible que sus otros servidores no tengan la información sobre el aumento de 50 $, y su sistema será inconsistente (en el sentido de que el cliente cree que se realizó el aumento de 50 $, mientras que los servidores sobrevivientes no lo tienen en cuenta).
Tenga en cuenta que la mayoría no ayudará aquí, ya que los datos se pierden. Además, suponga que, en lugar de que el servidor principal se bloquee, el servidor principal y otro más obtuvieron los 50 $ de aumento de datos. En este caso, el uso de la mayoría podría ser incluso peor: si obtiene una respuesta de los dos servidores con los datos, pensará que se realizó el aumento de 50 $. Pero si uno de ellos falla, entonces no tendrá mayoría, y pensará que la subida no se realizó.
En general, Paxos se puede utilizar para replicar una máquina de estados, de forma tolerante a fallos. Donde "máquina de estado" se puede considerar como un algoritmo que tiene un estado inicial, y avanza el estado de manera determinista según los mensajes recibidos desde el exterior (es decir, el cliente web).
Más apropiadamente, Paxos debe considerarse como un registro distribuido, puede leer más sobre esto aquí: Descripción de Paxos - Parte 1
Actualización 2018: Mysql High Availability utiliza paxos: https://mysqlhighavailability.com/the-king-is-dead-long-live-the-king-our-homegrown-paxos-based-consensus/
Ejemplo del mundo real:
Cassandra usa Paxos para garantizar que los clientes conectados a diferentes nodos de clúster puedan realizar operaciones de escritura de manera segura agregando "SI NO EXISTE" a las operaciones de escritura. Cassandra no tiene nodo maestro, por lo que se pueden emitir dos operaciones en conflicto simultáneamente en varios nodos. Cuando se utiliza la sintaxis if-not-existe, el algoritmo paxos se utiliza para realizar operaciones entre máquinas para garantizar que solo una tenga éxito. Esto puede ser utilizado por los clientes para almacenar datos autorizados con un contrato de vencimiento . Mientras la mayoría de los nodos de Cassandra estén funcionando, funcionará. Entonces, si define el factor de replicación de su espacio de claves como 3, entonces 1 nodo puede fallar, de 5 entonces 2 puede fallar, etc.
Para escrituras normales, Caassandra permite que múltiples escrituras en conflicto sean aceptadas por diferentes nodos que pueden ser temporales y no pueden comunicarse. En ese caso, no utiliza Paxos, por lo que puede perder datos cuando se producen dos Escrituras al mismo tiempo para la misma clave. Hay estructuras de datos especiales integradas en Cassandra que no pierden datos que son solo de inserción.
Poker y Paxos:
Como otras respuestas, note que el poker está basado en turnos y tiene reglas. Si permite un maestro y muchas réplicas, el maestro arbitra la siguiente acción. Digamos que un usuario primero hace clic en el botón "verificar" y luego cambia de opinión y hace clic en "plegar". Esos son comandos conflictivos, solo el primero debe ser aceptado. El navegador no debe permitir que presionen el segundo botón, lo desactivará cuando presionen el primer botón. Dado que el dinero está involucrado, el servidor maestro también debe hacer cumplir las reglas y permitir solo una acción por jugador por turno. El problema viene cuando el maestro se estrella durante el juego. ¿Qué réplica puede convertirse en maestra y cómo se hace cumplir que solo una réplica se convierte en maestra?
Una forma de manejar la elección de un nuevo maestro es usar un servicio externo sólido y consistente. Podemos usar Cassandra para crear un contrato de arrendamiento para el nodo maestro. Las réplicas pueden agotar el tiempo de espera en el maestro e intentar tomar el contrato de arrendamiento. Como Cassandra está utilizando Paxos, es tolerante a las fallas; Aún puede leer o actualizar el contrato de arrendamiento incluso si se bloquean los nodos de Cassandra.
En el ejemplo anterior, el maestro de póker y las réplicas son finalmente consistentes. El maestro puede enviar latidos para que las réplicas sepan que todavía están conectados al maestro. Eso es rápido ya que los mensajes fluyen en una dirección. Cuando el maestro se bloquea, puede haber condiciones de carrera en las réplicas que intentan ser el maestro. El uso de Paxos en ese punto le da una gran consistencia en el resultado de qué nodo es ahora el maestro. Esto requiere mensajes adicionales entre nodos para garantizar un resultado de consenso de un solo maestro.