Paxos en su corazón es muy simple

El algoritmo Paxos, cuando se presenta en inglés sencillo, es muy simple. — Leslie Lamport 2001

Voy a tratar de explicar el decreto único Paxos de una manera, con suerte, que sea fácil de entender.

Hasta el día de hoy, IMO, la conferencia de John Ousterhout sobre Paxos sigue siendo LA MEJOR que hay. El material de este post se basa en gran medida en la conferencia del profesor Ousterhout. Con el acuerdo de John Ousterhout, utilicé algunas de sus diapositivas para ayudar a explicar Paxos.

Consenso

Paxos como protocolo, está tratando de resolver el problema del consenso. Dicho en inglés sencillo, está tratando de resolver un problema de que un sistema solo elija un valor cuando uno o más servidores pueden proponer diferentes valores.

El ejemplo del mundo real sería algo así como una elección. La gente puede votar por un presidente diferente. Pero solo se puede elegir un presidente.

Paxos está diseñado para hacer frente a parada/bloqueo por error (no bizantino) y demora/pérdida de mensajes. También hay un requisito de vida de que se elija algún valor propuesto, siempre y cuando la mayoría de los servidores se ejecuten. Esto es para evitar soluciones poco interesantes como nunca aceptar ningún valor. Si no haces nada, no harás nada malo. Del mismo modo, no se quiere que se elija a más de un presidente y se quiere tener un presidente con el tiempo, siempre y cuando la gente vote.

En una nota al margen, para ser honesto, creo que tratar de usar la votación como ejemplo para explicar Paxos, en el documento original del Parlamento a tiempo Parcial, es muy natural. Pero de alguna manera no funcionó muy bien. Lamport también dijo en una entrevista que es un fracaso total, lo cual es desafortunado.

Aceptador único

Screen-Shot-2018-11-13-at-11.17.43-PM
Con un clúster de servidores 2F+1, qué sucede si siempre hacemos una caja determinada para aceptar propuestas. Y se elige cualquier propuesta que acepte esa caja.

El problema de este enfoque es que una sola caja descendente puede hacer que el servicio no esté disponible. Pero el requisito dice que el servicio debe estar en funcionamiento mientras la mayoría de los servidores se estén ejecutando (F+1 en este caso).

Observe que este es efectivamente un modelo de replicación maestro único. Y esta es exactamente la razón por la que el tiempo de inactividad es inevitable con la replicación maestro-esclavo.

Quorum

Así que si tener un solo aceptador no funciona, tal vez deberíamos esperar hasta que varios servidores hayan aceptado una propuesta antes de reclamar un valor que se está eligiendo.

¿cuántos?

Si los aceptadores son fijos y es <=F, de nuevo, no toleramos servidores bloqueados F. Si los aceptadores pueden ser cualquier servidor y es <=F, en un clúster de 2F+1 servidores, podríamos tener dos propuestas diferentes que van a dos conjuntos disjuntos de aceptadores causando que se elijan dos valores.

Así que el número de aceptadores tiene que ser >=F+1. Dado que menos aceptadores, mejor, vamos con F+1. Y puede ser cualquier servidor F+1 en el clúster.

ya Hemos hecho algunos progresos! Si los servidores F+1 aceptan alguna propuesta, se elige.

Aceptar propuestas

Ahora veamos cómo los aceptantes deben decidir si aceptan una propuesta o no.

¿Aceptar solo la primera propuesta?
Screen-Shot-2018-11-13-at-11.17.27-PM

no funcionaría, porque podemos terminar nunca tienen ningún valor elegido como el caso anterior. Esto viola el requisito de vida.

No tiene sentido decir aceptar una segunda propuesta o algo así porque nunca se sabe si alguna vez habrá una segunda propuesta.

Así que tenemos que aceptar la primera propuesta, pero tal vez no solo la primera propuesta.

¿Acepta todas las propuestas?
Screen-Shot-2018-11-13-at-11.31.11-PM
Esto violaría el requisito de seguridad, ya que podemos terminar eligiendo más de un valor.

Core

Aquí viene el truco, que creo que es LA parte MÁS interesante de Paxos.

Una vez elegido un valor, las propuestas futuras deben proponer el mismo valor.

Esto significa que se necesitaría un protocolo de dos fases. En la primera fase, los proponentes deben averiguar si ya se ha elegido algún valor. Y proponer en la segunda fase.

Si es un veterano del sistema distribuido, ya debe haber notado una palabra clave en la declaración anterior. Y es “futuro”. Revisé el Tiempo y el orden antes. El sistema distribuido se trata de ordenar. “futuro” aquí implica ordenar (suceder – antes de la relación). Así que tenemos que ordenar todas las propuestas. Luego, en el siguiente ejemplo, podemos rechazar red porque sabemos que blue es elegido y red es una propuesta antigua.

Screen-Shot-2018-11-13-at-11.39.37-PM

Boleta Número

Una manera fácil de propuestas de pedido es tener un único número de boleta para cada propuesta en la forma de <seq_id, server_id>. Para garantizar el pedido, seq_id debe persistir en el bloqueo cruzado/reinicio. Por lo tanto, debe almacenarse localmente de forma duradera.

Paxos

Ahora estamos listos para describir el protocolo Paxos de dos fases real. Llamaremos a la primera fase la fase prepare y a la segunda fase la fase accept. prepare la fase sirve para dos propósitos en un viaje de ida y vuelta.

  1. conozca cualquier valor que ya haya elegido
  2. evite que los aceptantes acepten propuestas anteriores (muy parecido al paso de RESERVA en la confirmación de dos fases)

Screen-Shot-2018-11-13-at-11.53.52-PM
El aceptador tiene que almacenar de forma duradera algunas cosas

  • minProposal
  • acceptedProposal
  • acceptedValue
    Observe que en lugar de “transmitir a todos los servidores”, debe ser “transmitir a al menos servidores F+1”. Y el proponente debe enviar el mensaje de aceptación al mismo conjunto de servidores F+1 que en la fase de preparación.

Echemos un vistazo de cerca a cada paso.

Prepare phase

En esta fase, el proponente intenta obtener una promesa del aceptante de no aceptar ninguna propuesta anterior a la suya. Al mismo tiempo, los aceptantes informarán a los proponentes de los valores ya aceptados hasta el momento.

En los pasos 3 y 4, un proponente cambiará su propuesta a la última propuesta aceptada de los aceptantes con los que habló. Parece ser muy conservador porque es posible que obtengas una propuesta aceptada que no sea elegida y el proponente termine renunciando a su propuesta. Pero eso está bien, ya que solo nos importa el consenso. En la primera fase, es difícil para el proponente saber si se elige un valor o no. Es posible que no se elija un valor aceptado. ¡Pero un valor elegido debe ser aceptado por la mayoría de los servidores! Y los aceptantes rechazan propuestas más antiguas (paso 6). Con dos invariantes, sabemos que la última propuesta aceptada devuelta a la propuesta en la fase uno ya ha sido elegida, o no se ha elegido ningún valor en este momento. De cualquier manera, es seguro proponer ese valor.

¿Por qué hacer un seguimiento de minProposal?
Puede haber dos propuestas de carreras en fase de preparación mientras no se haya aceptado nada todavía. Esto significa que ambos pasarán a aceptar la fase. Gracias al pedido total que tenemos para todas las propuestas y al requisito F+1, al menos un aceptante verá la propuesta más reciente y rechazará el mensaje accept de la propuesta perdedora/anterior. El invariante aquí es minProposal >= acceptedProposal.

Screen-Shot-2018-11-14-at-12.28.11-AM

Este es probablemente el caso más interesante, ya que el segundo proponente no vio el valor aceptado anteriormente y no se eligió un valor en el momento de la fase de preparación. En este caso, seguirá adelante y enviará accept(Y) a otros servidores. Dado que S3 ha prometido que solo aceptará propuestas posteriores a 4.5, rechaza X. Si no hacemos un seguimiento de minProposal, X será aceptado por S3. Entonces, tanto X como Y habrían sido aceptados por tres servidores y considerados elegidos, lo que viola el requisito de seguridad.

Ahí lo tienes. Este es el decreto único Paxos. Dicho esto, la implementación de Paxos ha demostrado ser muy, muy difícil.

  1. Paxos hecho simple https://lamport.azurewebsites.net/pubs/paxos-simple.pdf ↩︎

  2. El Parlamento https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf ↩︎

  3. Paxos hecho vivir https://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf ↩︎

Deja una respuesta

Tu dirección de correo electrónico no será publicada.