Algorítmos de Consenso Raft y Paxos

RAFT

Es un algoritmo de consenso, con el que se busca lograr consistencia en un grupo de nodos los cuales comparten información. Trabaja seleccionando un nodo líder sobre el que se realizan las solicitudes y coordinación del resto de los nodos para implementarlas. El clúster de nodos de raft, trabaja mientras que exista una mayoría (51%) de nodos en línea.

Los nodos participantes pueden estar en tres estados:

• Líder: todos los cambios que se realicen en el cluster pasan por él primero.
• Seguidor: Nodo pasivo cuya responsabilidad es responder a las peticiones del nodo líder
• Candidato: nodo que no ha encontrado líder y solicita su elección.

Cada nodo tiene un tiempo de espera aleatorio después del cual, si un líder no se comunica con él, pasa a estado candidato y pide ser elegido como líder.

El ejemplo por excelencia en donde se utiliza este algoritmo es en la escritura de un registro de log replicado.

Se puede ver una excelente visualización on-line del algoritmo, en el siguiente link: https://raft.github.io/

Ejemplo de situación de Raft con partición de Red

En el siguiente ejemplo, se muestra gráficamente, una situación en la que Raft podría recuperarse de una partición de la red. Es decir, cuando una minoría de nodos queda durante un tiempo desconectado de la mayoría, y posteriormente se reconecta. Se plantea el caso de una red con 5 nodos, en donde ocurre una partición, quedando la red dividida en:

• El líder + 1 nodo
• 3 nodos

Se grafica a partir del punto en que la red está particionada y hasta que vuelve a conectarse, en donde el resto de los nodos se re-sincroniza.

PAXOS

Es un algoritmo de consenso que cuenta con cierto grado de tolerancia a fallos. Funciona con el modelo de paso de mensajes asincrónicos y con menos de n/2 fallos (pero no con fallos bizantinos), garantizando que se llegará a un acuerdo y a la finalización, si hay un tiempo suficientemente largo sin que ningún proceso reinicie el protocolo.

Ejemplo de situación de PAXOS

Supongamos que tenemos una red que está ejecutando el algoritmo Paxos para actualizar un valor y tenemos esta situación como se refleja en el diagrama siguiente:

¿Por qué se podría haber llegado a esa situación?

Por lo que puedo interpretar del diagrama, es la primera fase del algoritmo, en donde se envían las solicitudes de preparación (prepare request). Hay dos proponentes (Proposer A y Proposer B) que envían una solicitud de preparación a tres aceptadores (Acceptor X, Acceptor Y y Acceptor Z).

La solicitud del proponente A, llega a los aceptadores X e Y antes de la solicitud del proponente B y la aceptan porque todavía no han prometido tener en cuenta otra solicitud con valor mayor que n. En el caso de la solicitud del proponente B, ésta llega primero al aceptador Z y es la que acepta, dado que el valor de n es mayor que la solicitud del proponente A.

¿Cómo podríamos resolver la situación anterior?

Respondo separando en tiempos en que suceden las propuestas y respuestas de aceptación.

Tiempo T1:

• Aceptador X: Recibe la propuesta del proponente A y la acepta, dado que no tiene una solicitud de propuesta anterior con un n mayor a 2. La manera en que “acepta” la propuesta de A, es responder al proponente A con una respuesta de preparación (prepare response) en donde se compromete a no aceptar otras propuestas con un número menor de rondas (n menor a 2).
• Aceptador Y: Caso igual al del aceptador X.
• Aceptador Z: Recibe la propuesta del proponente B y la acepta, por lo mismo explicado en el punto del Aceptador X.

El gráfico del tiempo T1 sería el siguiente:

Tiempo T2:

• Aceptador X: Recibe la solicitud del proponente B, en donde n es mayor al anterior (proponente A), así que ignora la solicitud anterior aceptando la nueva, por lo que envía una respuesta de preparación (prepare response) al proponente B con los valores previos recibidos (n=2 y v=8).
• Aceptador Y: Mismo caso que el aceptador X.
• Aceptador Z: Recibe la solicitud del proponente A, pero n es menor que el anterior, por lo tanto, ignora la solicitud.

El gráfico del tiempo T2 sería el siguiente:

Tiempo T3:

Una vez que el proponente ha recibido las respuestas de preparación de la mayoría de los aceptadores, puede emitir una solicitud de aceptación (accept request). Eso es lo que hace el proponente A, pero en éste tiempo, los 3 aceptadores, ya tienen solicitudes con un n mayor al de A y se han comprometido con B para no aceptar solicitudes con un n menor a 4, por lo que rechazan ésta solicitud de aceptación. El proponente B, hace lo mismo, enviando las solicitudes de aceptación a cada aceptador. Los tres aceptadores, tienen un número de ronda (n=4), que corresponde a B, por lo que aceptan y envían una notificación (accepted) a cada nodo de aprendizaje (Learner).

El valor de V final que queda es 8, que difiere del que tenía originalmente B (5), porque es el valor más alto de los mensajes de respuesta de preparación (prepare response) que recibió B.

El gráfico del tiempo T3 sería el siguiente:

Comparación de Raft con Paxos

Similitudes con Paxos:

• Tanto Paxos como Raft suponen que eventualmente existirá un líder en el que todos los nodos estables confíen.
• En ambos, todos los miembros del clúster son de confianza.
• Ambos son tolerantes a fallos.
• El número de nodos está predeterminado. Esto hace que en ambos algoritmos, sea difícil escalar. Además, con un número fijo de nodos, uno probablemente deba renunciar a la seguridad (al permitir que cualquier nodo se una) o al anonimato del nodo (para autenticarse).
• Ambos tienen reglas para considerar las transacciones nuevas.
• Tanto en Raft como en Paxos, el líder podría convertirse en un cuello de botella ya que todo el tráfico pasa por él.

Diferencias con Paxos:

• Paxos tiene varios roles y reglas para las interacciones entre ellos. Raft no tiene nada de eso: solo son servidores, con uno de los servidores designado como líder.
• En Paxos, solo se está administrando un solo valor de consenso; en Raft, se tiene una secuencia de entradas de registro.
• Paxos se define en términos de mensajes. Raft está diseñado en términos de llamadas a procedimientos remotos (RPC).
• En Raft, solo el servidor más actualizado puede convertirse en un líder, mientras que Paxos permite que cualquier servidor se convierta en un líder. Esta flexibilidad, sin embargo, viene con una complejidad adicional.
• Paxos incluye un protocolo de dos fases para el consenso básico y un mecanismo separado para la elección del líder. A diferencia, Raft incorpora la elección del líder directamente en el algoritmo de consenso y lo usa como la primera de las dos fases de consenso.
• En Raft, un servidor envía una “solicitud de líder” a otros servidores y espera una respuesta de la mayoría de ellos antes de considerarse un líder. Si no obtiene una respuesta de la mayoría de los servidores o un mensaje que indique que otro servidor se ha convertido en el líder, se agotará el tiempo de espera y se iniciará un nuevo proceso de elección. Los servidores solo pueden votar por una solicitud de líder por vez. Sin embargo, Paxos realmente no define cómo un servidor se convierte en un líder. Para simplificar, los investigadores explotan el rango a priori entre procesos tales como la identificación del servidor (por ejemplo, un número entero). Entonces, el servidor con el rango más alto o más bajo que no se sospecha se convierte en el nuevo líder.
• Raft impone una restricción al proceso de elección del líder: sólo el servidor más actualizado puede convertirse en un líder. Básicamente, garantiza que un líder ha cometido entradas de términos anteriores y no necesita aprender acerca de entradas antiguas en el registro replicado de las que no tiene conocimiento. Entonces, después de convertirse en un líder, un servidor simplemente puede comenzar a “imponer” sus “deseos” en otros servidores. Paxos, sin embargo, permite que cualquier servidor se convierta en un líder. Por lo tanto, un servidor debe aprender sobre el pasado antes de comenzar a “imponer” sus “deseos” en otros servidores y, como siempre, la flexibilidad conlleva una complejidad adicional.
• Ambos algoritmos deben evitar cuidadosamente sobrescribir una decisión tomada por un antiguo líder y, por lo tanto, violar la seguridad, pero lo hacen de enfoques diferentes:
• En Raft, se determina cuál de los dos registros está más actualizado al comparar el índice y el término de las últimas entradas en los registros. Si los registros tienen las últimas entradas con términos diferentes, entonces el registro con el último término está más actualizado. Si los registros finalizan con el mismo término, el registro que sea más largo estará más actualizado. Entonces, el líder solo necesita asegurarse de que el registro duplicado en los servidores finalmente converja.
• En Paxos, cualquier servidor puede convertirse en un líder, de modo que la tarea de evitar que una decisión no se sobreescriba se vuelve un poco más compleja ya que el nuevo líder tiene que descubrir qué han procesado otros servidores hasta ahora antes de comenzar a “imponer” su deseos “en otros.
• Si hay un problema en la red en Paxos, se puede generar un fork. En el caso de Raft, deja de funcionar con menos de la mayoría de los nodos en línea.