Algoritmo de Paxos

El algoritmo de Paxos es un algoritmo para llegar a consensos en sistemas distribuidos con cierto grado de tolerancia a fallos. Entendemos consenso como el proceso de ponerse de acuerdo sobre uno de los resultados entre un grupo de participantes. Este problema se hace difícil cuando los participantes o su medio de comunicación puede experimentar fallos.

El protocolo Paxos primero fue publicado en 1989 por Leslie Lamport aunque pasó desapercibido hasta 1998 cuando lo publicó en una revista especializada. Desde entonces se han publicado varias mejoras y adaptaciones.[1]

El algoritmo incluye una gama de soluciones de compensación entre el número de procesos, el número de mensajes con retraso antes de aprender el valor acordado, el nivel de actividad de los participantes, el número de mensajes enviados, y los tipos de fallos. Aunque un protocolo de consenso con tolerancia a fallos determinista no puede garantizar el progreso en una red asíncrona, Paxos garantiza la seguridad (libre de inconsistencia), y las condiciones que podrían hacer que no progrese son difíciles de ocurrir.

Funciona en el modelo de paso de mensajes con asincronía y con menos n/2 fallos (pero no con fallos bizantinos). El algoritmo de Paxos garantiza que se llegará a un acuerdo y garantiza la finalización si hay un tiempo suficientemente largo sin que ningún proceso reinicie el protocolo.

Descripción general

Básicamente Paxos es un algoritmo para decidir un solo valor en un clúster de nodos. Decidir múltiples valores es una extensión a este algoritmo. Hay una serie de roles que pueden tener los nodos (procesos). En las implementaciones típicas, un mismo proceso puede tener diferentes roles al mismo tiempo. Estos roles son:

  • Proponentes: Proponen valores que deberían ser escogidos por consenso. Actúan como un coordinador para seguir adelante con el protocolo cuando se producen conflictos. Normalmente Paxos requiere un proponente completo (llamado el Líder) para garantizar que el sistema va pasando por las diferentes fases y concluye finalmente. Muchos procesos pueden creer que son líder, pero el protocolo sólo garantiza el progreso, si uno de ellos es finalmente elegido. Si dos procesos creen que son los líder, pueden paralizar el protocolo de forma continua proponiendo cambios conflictivos.
  • Aceptadores: Forma el consenso y aceptan valores. Actúan como la "memoria" con tolerancia a fallos del protocolo. Las decisiones de los aceptadores son locales y ningún único aceptador conoce la decisión de la mayoría.
  • Aprendices: Son los que aprenden qué valor ha sido escogido por los aceptadores. Obtienen la información de los aceptadores. Actúan como el factor de replicación para el protocolo. Una vez que la petición del cliente ha sido acordada por los Aceptadores, el aprendiz puede actuar (es decir, ejecutar la petición y enviar una respuesta al cliente).

Un nodo puede tener varios roles. Por ejemplo un cliente de base de datos puede ser un proponente y también un aprendiz.

Normalmente se considera un cuarto rol llamado Cliente y que es el rol de un nodo (que puede ser externo) que es el que hace la petición de cambio de estado al sistema distribuido (a un proponente) y espera una respuesta

Para que un valor se considere aceptado, tiene que haber cierto quorum de aceptadores. Típicamente, un cuórum es cualquier mayoría de aceptadores participantes. Por ejemplo, dado el conjunto de aceptadores {A, B, C, D}, un cuórum válido sería cualquiera de los tres grupos de aceptadores: {A, B, C}, {A, C, D}, {A, B, D} , {B, C, D}.

Seguridad

La familia Paxos define tres propiedades de seguridad que siempre han de llevarse a cabo para poder garantizar la seguridad, independientemente del patrón de fallos:

  • No trivialidad: Solo valores propuestos se pueden aprender.[2]
  • Consistencia: El valor aprendido tiene que ser único (es decir, dos aprendices distintos no pueden aprender valores diferentes).
  • Vitalidad: Si un líder vive lo suficiente, entonces es capaz de sacar adelante la solución de consenso.

Paxos solo funciona si la mayoría de los aceptadores están activos. Si fallan más de (n/2)-1 aceptadores entonces ningún proponente puede obtener suficientes respuestas a sus mensajes 'preparar' y ningún valor será aceptado. Otro punto débil está relacionado con el momento donde los proponentes envían los mensajes. En caso de que tengamos un solo proponente siempre se aceptará el valor mayor. Cuando hay varios proponentes éstos pueden interferir entre ellos. Por ejemplo ya se podría haber escogido una elección mejor que otra que ya ha sido aceptada. A esto se le llama duelo de proponentes. En la práctica este problema normalmente se resuelve eligiendo un coordinador que implemente algún algoritmo de detección de fallos o simplemente usando un backoff exponencial (como usa ethernet )

Funcionamiento

Supongamos que la decisión consiste en tomar el número mayor. Por tanto una propuesta en una ronda i es considerada como válida si es mayor que el resto de propuestas en esa ronda. Todas aquellas propuestas para esa ronda con números más pequeños son consideradas no válidas.

El sistema funciona con dos fases: Fase de preparación y fase de aceptación. Un proponente no debe iniciar el protocolo si no se puede comunicar con al menos un quorum de aceptadores.[3]

Fase de preparación
Preparar
Un proponente empieza el protocolo recopilando información de los aceptadores. Para ello envía un mensaje 'prepara' identificada con un número de ronda N. Este debe ser mayor que cualquier número de propuesta del que tenga conocimiento. Después, envía el mensaje PREPARA a todos los participantes, conteniendo el número de ronda. Al mensaje enviado por el proponente se le suele llamar prepara(N) El propósito de que cada mensaje cuente con un identificados es que sea una propuesta única y que permite al nodo receptor saber cual es la última propuesta que recibió
Prometer
Cuando un aceptador recibe un mensaje 'prepara(N)' entonces:
  • Si el número de la propuesta N es mayor que cualquier número recibido previamente, entonces el aceptante envía un mensaje PROMESA al proponente y con ello se compromete a ignorar todas las propuestas que tienen un número menor que N.
  • Si no, si el aceptante recibió una propuesta en algún momento en el pasado, debe incluir en el mensaje PROMESA que recibe el número de la propuesta anterior y el valor anterior en su respuesta al proponente.
  • Si no, si el número de propuesta N es menor que otro con el que ya se comprometió, el aceptante puede ignorar la propuesta recibida. No tiene que responder en este caso para que funcione Paxos. Sin embargo, en bien de la economía de mensajes, el envío de una respuesta negativa (Nack) le diría al proponente que puede poner fin a su intento de crear un consenso con la propuesta N.
Los mensajes de respuesta de los aceptadores tienen los siguientes campos:
  • Propuesta rechazada/aceptada
  • El mayor número que el aceptador ha visto.
  • Si el aceptador ya había aceptado otro valor, entonces se incluye el valor antes aceptado.

Fase de aceptación
Si el Proponente recibe suficientes promesas (quorum) de los Aceptadores a su petición, entonces tendrá que establecer un valor con su propuesta.
Aceptar petición
  • Si alguno de los aceptantes había aceptado previamente cualquier propuesta, entonces ellos han enviado sus valores al líder, que ahora debe igualar el valor de su propuesta con el valor más reciente reportado por algún aceptante. Es decir, el valor asociado con el mayor número de propuesta reportado en un mensaje PROMESA, recién recibido.
  • En cambio, si ninguno de los aceptantes había aceptado una propuesta hasta este punto, entonces el proponente puede elegir cualquier valor para su propuesta. .
El proponente envía un mensaje ACEPTAR a un cuórum de aceptantes con el valor elegido para su propuesta.
Aceptado
Si un Aceptador recibe un mensaje de petición de aceptación para la propuesta N, este debe aceptarlo si y solamente si todavía no ha prometido tener en cuenta las propuestas que tengan un identificador mayor que N, es decir, si todavía no ha respondido a ninguna petición de aceptación prepara de un valor mayor que N. En este caso, se debe registrar el valor correspondiente V y enviar un mensaje de aceptado al Proponente y cada aprendiz. Si no, se puede ignorar la petición Aceptar.
Las fases fallan cuando varios Proponentes envían mensajes conflictivos de aceptación, o cuando el Proponente no recibe la respuesta del quorum (promesa o aceptado). En estos casos, una nueva iteración del protocolo debe iniciarse con un número de propuesta superior.
Hay que tener en cuenta que cuando un Aceptador acepta una solicitud, está reconociendo el liderazgo del Proponente. Por lo tanto, Paxos se puede utilizar para seleccionar un líder en un grupo de nodos.

Flujo de mensajes

Representaciones gráficas del protocolo.

Iteración inicial sin fallos

 
 Cliente   Proponente   Aceptadores    Aprendices
   |           |          |  |  |        |  |
   X---------->|          |  |  |        |  |    Petición
   |           X--------->|->|->|        |  |    Prepara(1)
   |           |<---------X--X--X        |  |    Promesa(1,{Va,Vb,Vc})
   |           X--------->|->|->|        |  |    Aceptar!(1,Vn)
   |           |<---------X--X--X------->|->|    Aceptado(1,Vn)
   |<------------------------------------X--X    Respuesta
   |           |          |  |  |        |  |

Vn = mayor(Va, Vb, Vc)

Iteración inicial con fallo de aceptador

 
 Cliente   Proponente   Aceptadores    Aprendices
   |           |          |  |  |         |  |
   X---------->|          |  |  |         |  |    Petición
   |           X--------->|->|->|         |  |    Prepara(1)
   |           |          |  |  !         |  |    !! FALLO !!
   |           |<---------X--X            |  |    Promesa(1,{null,null, null})
   |           X--------->|->|            |  |    Aceptar(1,V)
   |           |<---------X--X----------->|->|    Aceptado(1,V)
   |<-------------------------------------X--X    Respuesta
   |           |          |  |            |  |

Iteración inicial con fallo de aprendiz redundante

 
 Cliente   Proponente   Aceptadores    Aprendices
   |           |          |  |  |         |  |
   X---------->|          |  |  |         |  |    Petición
   |           X--------->|->|->|         |  |    Prepara(1)
   |           |<---------X--X--X         |  |    Promesa(1,{null,null,null})
   |           X--------->|->|->|         |  |    Aceptar(1,V)
   |           |<---------X--X--X-------->|->|    Aceptado(1,V)
   |           |          |  |  |         |  !    !! FALLO !!
   |<-------------------------------------X       Respuesta
   |           |          |  |  |         |

Iteración inicial con fallo del proponente

(Reelección no mostrada, una instancia, dos rondas)

Cliente   Proponente   Aceptadores    Aprendices
   |         |           |  |  |         |  |
   X-------->|           |  |  |         |  |  Petición
   |         X---------->|->|->|         |  |  Prepara(1)
   |         |<----------X--X--X         |  |  Promesa(1,{null, null, null})
   |         |           |  |  |         |  |
   |         X---------->|  |  |         |  |  Aceptar(1,Va) !! FALLO DEL LÍDER DURANTE LA DIFUSIÓN !!
   |         !           |  |  |         |  |
   |         |           |  |  |         |  |  !! NUEVO LÍDER !!
   |         X---------->|->|->|         |  |  Prepara(2)
   |         |<----------X--X--X         |  |  Promesa(2,{null, null, null})
   |         X---------->|->|->|         |  |  Aceptar(2,V)
   |         |<----------X--X--X-------->|->|  Aceptado(2,V)
   |<------------------------------------X--X  Respuesta
   |         |           |  |  |         |  |

Ejemplo de falta teórica de consenso

Aquí podemos ver un ejemplo del algoritmo en esas situaciones en las que pudiera darse una situación de interbloqueo que al final va a resolverse entre dos postulantes que están compitiendo y se caen o tienen retardos importantes, y que por tanto no se podría llegar a tener consenso. Esto en la práctica es imposible que se de ya que en un número de rondas (reintentos) acaba dándole tiempo a uno u a otro de hacer las dos fases seguidas sin que se le meta otro postulante entremedias.

Multi-Paxos

Normalmente lo que se requiere es un flujo continuo de los valores acordados que actúan como comandos para una máquina de estado distribuido. Si cada comando es el resultado de una única instancia del protocolo básico de Paxos, obtendríamos una gran cantidad de gasto.

Si el proceso que actúa como líder es relativamente estable, la fase 1 sería innecesaria. Por lo tanto, es posible omitir la fase 1 para futuras instancias del protocolo con el mismo líder.

Para lograr esto, el número de instancia I es incluido junto con cada valor. Multi-Paxos reduce el retraso de los mensajes libres de fallos (del proponente al aprendiz) a la mitad (de 4 a 2 delays).

Inicio de líder

(Primera estancia con un nuevo líder)

 Cliente   Proponente   Aceptadores    Aprendices
   |           |          |  |  |         |  |   --- Primera petición ---
   X---------->|          |  |  |         |  |    Petición
   |           X--------->|->|->|         |  |    Prepara(N)
   |           |<---------X--X--X         |  |    Promesa(N,I,{Va,Vb,Vc})
   |           X--------->|->|->|         |  |    Aceptar(N,I,Vm)
   |           |<---------X--X--X-------->|->|    Aceptado(N,I,Vm)
   |<-------------------------------------X--X    Respuesta
   |           |          |  |  |         |  |

Vm = last of (Va, Vb, Vc)

Estado estacionario con el mismo líder

(Instancias posteriores con el mismo líder

 Cliente   Proponente   Aceptadores    Aprendices
   |           |          |  |  |         |  |    --- Primera petición ---
   X---------->|          |  |  |         |  |    Petición
   |           X--------->|->|->|         |  |    Aceptar(N,I+1,W)
   |           |<---------X--X--X-------->|->|    Aceptado (N,I+1,W)
   |<-------------------------------------X--X    Respuesta
   |           |          |  |  |         |  |

Véase también

Referencias
  1. Consensus on a multicore machine. Roni Häcki. 2015. Systems Group, Department of Computer Science, ETH Zurich
  2. Lamport, Leslie (2005). «Fast Paxos».
  3. Lamport, Leslie (2001). Paxos Made Simple ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) 51-58.

Bibliografía extra
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.