Paxos y Balsa son dos protocolos de consenso bien conocidos que han existido durante mucho tiempo y siguen siendo vitales para comprender la replicación de máquinas de estado en sistemas informáticos distribuidos. Paxos es en realidad una familia de protocolos que se basan en un grupo de supuestos diferentes según el sistema, mientras que Raft es un consenso alternativo a Paxos diseñado para ser más comprensible..
Comprender tanto Paxos como Raft es muy útil para ampliar el conocimiento de cómo funcionan los protocolos de consenso distribuidos en las criptomonedas, como la prueba de trabajo y la práctica tolerancia a fallas bizantinas..
Antecedentes de Paxos y Balsa
Paxos se propuso inicialmente en 1989 y se distinguió como un método particularmente elegante de probar la seguridad para el consenso distribuido tolerante a fallas. A pesar de su novedad inicial, Paxos a menudo se considera difícil de entender debido a sus suposiciones generales y su comportamiento complejo..
Raft se desarrolló como una alternativa más comprensible a Paxos que esencialmente es equivalente a Paxos en rendimiento y garantías de tolerancia a fallas. Hay amplios recursos disponibles tanto en Paxos como en Raft, y se estudian y utilizan ampliamente en una variedad de aplicaciones y sistemas en la actualidad..
Algunos de los usos prácticos más conocidos de Paxos se encuentran en la base de datos NewSQL de Google. Llave y el Controlador de volumen IBM SAN para servicios de visualización de almacenamiento.
Raft tiene varios códigos abiertos implementaciones de referencia en varios idiomas, incluidos Go, Java, C ++ y Rust.
Que es Paxos?
El consenso en un sistema distribuido tolerante a fallas es acordar un resultado entre un grupo de participantes poco confiables. Paxos es una familia de algoritmos de consenso que realizan diversas compensaciones entre las suposiciones sobre los procesadores, los participantes y los mensajes de un sistema determinado. El protocolo garantiza la seguridad y a menudo se emplea cuando se requiere la durabilidad de grandes conjuntos de datos..
Los protocolos de consenso asincrónicos no pueden garantizar tanto la seguridad como la vitalidad, por lo que todos vienen con sus propias compensaciones inherentes. Paxos fue uno de los primeros protocolos de consenso distribuidos tolerantes a fallas para garantizar la seguridad y los intentos de producir vida al garantizar que un valor propuesto sea finalmente seleccionado por el grupo de participantes en una ronda de consenso..
Hay tres roles en el consenso de Paxos, conocidos como agentes:
- Proponentes
- Aceptadores
- Aprendices
El objetivo del consenso es que un grupo de participantes llegue a un acuerdo sobre un valor único para cada ronda. Una ronda de consenso comienza cuando un proponente envía un valor propuesto a un grupo de aceptantes. Los aceptadores pueden aceptar el valor propuesto por un proponente determinado, y una vez que se alcanza un cierto umbral, la red aprueba ese valor..
Sin embargo, para que el consenso funcione correctamente, la primera condición de Paxos es:
“Los aceptadores deben aceptar el primer valor propuesto que reciben”.
Esto lleva al problema de que varios proponentes envían valores propuestos que son aceptados por los aceptadores, pero todos no aceptan ningún valor mayoritario ya que están aceptando el primer valor propuesto. Paxos resuelve esto indexando de forma única cada valor propuesto que recibe un aceptador, lo que le permite aceptar más de una propuesta..
Un número único define cada propuesta, y la red selecciona un valor una vez que la mayoría de los aceptadores aceptan un valor propuesto específico, conocido como elegido valor. Se pueden elegir múltiples propuestas, pero es necesario validar la propiedad de seguridad garantizando que todas estas propuestas tengan el mismo valor. Según la definición de Leslie Lamport de la segunda condición requerida de Paxos que garantiza la seguridad:
“Si se elige una propuesta con valor v, entonces cada propuesta con un número más alto que se elija tiene valor v”.
La comunicación en la red es asíncrona, por lo que es posible que ciertos aceptadores no hayan recibido el valor elegido, lo cual está bien siempre y cuando no se violen las condiciones 1 y 2.
Los proponentes emplean ciertas restricciones como mensajes a conjuntos de aceptantes junto con los valores. Estos se llaman preparar solicitudes y contienen 2 solicitudes principales:
- Prometa no aceptar nunca una propuesta menos de norte (n es el nuevo número de propuesta)
- Responda con la propuesta con el número más alto menor que norte que el aceptador ha aceptado.
Según Lamport:
“Si el proponente recibe las respuestas solicitadas de la mayoría de los aceptantes, entonces puede emitir una propuesta con el número n y el valor v, donde v es el valor de la propuesta con el número más alto entre las respuestas o cualquier valor seleccionado por el proponente si los que respondieron no informaron propuestas “.
Posteriormente, los proponentes envían una solicitud de aceptación que es reconocida por los aceptantes. Luego, el proponente envía un mensaje de compromiso a los aceptantes que pueden ignorar (sin comprometer la seguridad) o indicar el éxito del compromiso de valor. Una vez que un cierto umbral de aceptadores ha comprometido el valor, entonces el protocolo para esa ronda de consenso termina y externaliza el valor..
El intrincado diseño de Paxos es que puede aceptar valores cuando la mayoría de los nodos están de acuerdo a pesar de que otros nodos ignoran o niegan un valor propuesto. Esto difiere de las iteraciones anteriores de consenso que requerían que todos los nodos estuvieran de acuerdo y estaban sujetos al bloqueo del protocolo debido a la falla de un solo nodo..
Siempre que los números de propuesta sean únicos, Paxos puede seleccionar un valor que garantice la seguridad. Es importante tener en cuenta que un aceptante solo necesita recordar la propuesta con el número más alto que ha aceptado. Por el contrario, un proponente siempre puede abandonar una propuesta siempre que no vuelva a emitir una propuesta con el mismo número único..
El desglose de los roles del proponente y el aceptante en el protocolo es el siguiente:
Proponente
- Presentar propuesta norte a los aceptantes junto con la solicitud de preparación, espere a que la mayoría responda.
- Si la mayoría de los aceptadores responden que están de acuerdo, responderán con el valor acordado. Si la mayoría lo rechaza, abandone y reinicie el proceso..
- El proponente envía posteriormente un mensaje de confirmación con norte y valora si la mayoría acepta.
- Si la mayoría de los aceptadores aceptan el mensaje de confirmación, la ronda de protocolo se completa.
Aceptador
- Reciba la propuesta y compárela con la propuesta con el número más alto ya acordado.
- Si norte es mayor entonces acepta la propuesta, si n es menor entonces rechaza la propuesta.
- Aceptar el mensaje de confirmación posterior si su valor es el mismo que el de una propuesta aceptada previamente y su número de secuencia es el número más alto acordado.
Las propuestas pueden realizar varias propuestas, pero deben seguir el algoritmo de cada propuesta de forma individual.
Finalmente, el papel del aprendices es descubrir que la mayoría de los aceptantes han aceptado una propuesta de los proponentes. Se selecciona un alumno distinguido que propaga el valor elegido a los demás alumnos de la red. Se pueden usar variaciones de este proceso donde todos los aceptadores informan a los alumnos correspondientes de sus decisiones o los aceptadores responden a un conjunto distinto de alumnos que luego propagan el mensaje al resto de los alumnos..
Formalmente, el algoritmo de Paxos distingue a un líder (proponente) para cada ronda que se requiere para avanzar. Los aceptadores pueden reconocer el liderazgo de un proponente, lo que permite que Paxos se utilice para seleccionar un líder dentro de un grupo de nodos. Sin embargo, Paxos puede detenerse si dos proponentes compiten por la posición de líder sin un acuerdo sobre cuál es el líder. Aunque es poco probable que este estado de no terminación persista.
Que es balsa?
Raft se creó como una versión más comprensible de Paxos con la misma tolerancia a fallas y garantías de rendimiento. Raft también mejora la construcción de implementaciones prácticas de protocolos sobre él. Debido a la complejidad de Paxos, no es útil para proporcionar una base sólida sobre la que desarrollarse. Raft es similar a Paxos, por lo que comparar los dos requiere un breve desglose de cómo Raft simplifica el proceso de Paxos.
Raft emplea un modelo de líder y seguidor basado en la suposición de que un grupo de nodos solo tiene un líder elegido. El líder gestiona la replicación de registros en los nodos participantes y se reemplaza una vez que falla o se desconecta.
También se elige un líder cuando comienza el algoritmo. Para darle a la selección de líderes algo de contexto, juega un papel vital en el consenso y se distingue en algoritmos específicos. Por ejemplo, en Nakamoto Proof of Work, la selección del líder se logra a través del proceso de minería similar a una lotería para cada ronda, que es aproximadamente cada 10 minutos. En Practical Byzantine Fault Tolerance (pBFT), la selección de líder se realiza a través de un formato de estilo round-robin.
Leer: ¿Qué es el Consenso de Nakamoto??
Raft selecciona al líder a través de un proceso iniciado por un nodo candidato. Si los candidatos no reciben comunicación durante una fase conocida como tiempo de espera de las elecciones, luego votan por sí mismos después de aumentar su contador de término y transmitirlo a los otros nodos. Los candidatos se convierten en seguidores de otros candidatos que tienen un número de mandatos al menos tan grande como el suyo, y este efecto dominó continúa entre los nodos hasta que un candidato recibe la mayoría de seguidores..
El líder controla la replicación de registros entre los nodos donde envía los comandos de solicitud del cliente a sus seguidores. Si la mayoría de los seguidores confirman la replicación, la solicitud se confirma. Los seguidores también aplican las confirmaciones a sus máquinas estatales locales..
Raft conserva la tolerancia a fallas de los nodos sujetos a fallas o una falla de líder al hacer que un nuevo líder obligue a sus seguidores a duplicar sus propios registros. Todas las entradas que no coinciden entre sí se eliminan, manteniendo la coherencia de la replicación del registro..
Los candidatos a líder deben tener un registro más actualizado que los registros de seguidores. Si el registro de un candidato está menos actualizado que el de un posible seguidor (un votante en este contexto), el candidato es rechazado..
En general, Raft deconstruye el consenso en 3 subproblemas individuales:
- Elección de líder
- Replicación de registros
- La seguridad
El protocolo de consenso utiliza un líder fuerte, lo que significa que el nodo líder en Raft ejerce una influencia sustancial en el proceso mientras permanece restringido por los límites del protocolo. Como resultado, Raft tiene un diseño más sencillo que Paxos.
Conclusión
Paxos y Raft son protocolos de consenso importantes que son componentes centrales del ecosistema distribuido de tolerancia a fallas más grande. Si bien no se emplean directamente en las criptomonedas, los protocolos de consenso utilizados en las redes de criptomonedas derivan muchas de sus suposiciones características del diseño de Paxos y Raft..
