Preguntas sobre la implementación de Paxos

Question

Estoy implementando paxos en una aplicación de simulador de clúster, utilizando la documentación disponible en Wikipedia. Desafortunadamente, deja varias puertas abiertas a la interpretación y no proporciona mucha información sobre problemas clave de implementación. No está claro e incompleto.

• Suponiendo un clúster dividido en 3 regiones, cada uno con 3 nodos (total = 9 nodos). ¿Qué sucede si la comunicación se rompe entre las regiones? No hay forma de que un líder pueda alcanzar el quórum (que es 5).

¿No va a ingresar Paxos en un bucle infinito? Supongo que uno no debe iniciar paxos si no se puede comunicar con al menos un quórum de nodos.

• En la fase 1b: 'Si el número de propuesta N es mayor que cualquier propuesta anterior, entonces cada aceptador promete no aceptar propuestas inferiores a N, y envía el valor que se aceptó por última vez por esta instancia al proponente'.

¿Cuál es 'el último valor que aceptó'? ¿Es algún número de propuesta anterior del propuesta? ¿A qué se refiere 'instancia' exactamente en este caso?

• En la Fase 1A: ¿uno incluye el valor para acordar con el mensaje de preparación o es esto diferido para aceptar! ¿mensaje? ¿O importa?

• En la fase 2a: 'Si alguno de los aceptores ya ha aceptado un valor, el líder debe Elija un valor con el número máximo de propuesta n'.

¿Qué es el valor aquí? ¿Es el número de propuesta? Creo que no, pero esta frase no está clara.

• En la fase 2A: "De lo contrario, el proponente es libre de elegir cualquier valor". ¿Qué significa esto? ¿Un valor para qué? Para el número de propuesta?

• ¿Paxos parece confiar en un valor creciente de n (número de propuesta) para que funcione? ¿Es esto correcto?

• La entrada de Wikipedia no discute los valores iniciales que un nodo debe establecer antes de comenzar a participar en Paxos. ¿Que son estos?

PD: No tengo suficiente reputación para crear una etiqueta de 'Paxos' (¿algún voluntario?)

Answer 1

¿Qué es una instancia?

La nomenclatura en Paxos es un poco poco intuitiva.

• Un instancia es el algoritmo para elegir una valor.
• A redondo se refiere al intento único de un propuesta de fase 1 + fase 2. Un nodo puede tener múltiples rondas en un instancia de Paxos. Una identificación redonda es única por instancia en todos los nodos. Esto a veces se llama número de propuesta.
• Un nodo puede asumir varios roles; Lo más notablemente proponente y aceptador. En mis respuestas, asumiré que cada nodo adquiere ambos roles.
• La fase 1 también se conoce como la fase de preparación.
  • En la fase 1A, un propomedor envía un mensaje preparado! (Roundid) a los aceptores
  • ¡En la fase 1b, los aceptores responden con promesa! (Roundid, valor) o prepararenack! ()
• La fase 2 también se conoce como la fase de aceptación.
  • En la fase 2A, un propositor envía un mensaje de aceptación! (RoundId, valor) a los aceptores
  • ¡En la fase 2b, los aceptores responden con aceptado! (...) o aceptación! ()

Suponiendo un clúster dividido en 3 regiones, cada uno con 3 nodos (total = 9 nodos). ¿Qué sucede si la comunicación se rompe entre las regiones? No hay forma de que un líder pueda alcanzar el quórum (que es 5).

Paxos requiere que pueda obtener al menos un quórum (5 nodos en su caso). Vaya con su solución de tres regiones; Tener dos particiones de red entre las tres regiones es muy mala noticia. También uso una versión de Paxos que puede cambiar la membresía del nodo de una instancia a la siguiente. Esto es útil para particiones y falla del nodo.

¿No va a ingresar Paxos en un bucle infinito?

No se garantiza que una implementación ingenua de Paxos rescindga porque múltiples nodos pueden preparar las fases de preparación. Hay dos formas de evitar esto. Una es tener un retroceso aleatorio antes de comenzar nuevas fases de preparación. El segundo es enrutar todas las solicitudes a un líder designado, que actúa como proponente (el líder es elegido por una instancia de Paxos. Ver también Multi-Paxos)

En la fase 1b: 'Si el número de propuesta N es mayor que cualquier propuesta anterior, entonces cada >> Aceptor promete no aceptar propuestas inferiores a N, y envía el valor que se aceptó por última vez para >> esta instancia al propuesta'.

¿Cuál es 'el último valor que aceptó'? ¿Es algún número de propuesta anterior del propuesta?

Cuando un nodo recibe un mensaje de aceptación! (RoundId, valor) de un proponente y No ha prometido no aceptar el valor (¡debido a un mensaje de preparación! (HighRoundid)), almacena el valor y el Roundid (los llamaré acceptedValue y acceptedRoundId). ¡Puede escribir sobre estos debido a los mensajes de aceptación posteriores! (...).

Cuando un nodo recibe un mensaje de preparación! (Roundid) de un proponente, almacena Roundid como promiseRoundId = max(roundId, promiseRoundId). Luego envía un Promise!(acceptedRoundId, acceptedValue) Volver al propuesta. NB: ¡Si un nodo no ha recibido un mensaje de aceptación! (...), responde con Promise!(null, null).

En la Fase 1A: ¿uno incluye el valor para acordar con el mensaje de preparación o es esto diferido para aceptar! ¿mensaje? ¿O importa?

No hay necesidad de enviarlo. Yo no.

En la fase 2A: 'Si alguno de los aceptores ya ha aceptado un valor, el líder debe elegir un valor con el número máximo de propuesta n'.

¿Qué es el valor aquí? ¿Es el número de propuesta? Creo que no, pero esta frase no está clara.

El valor son los datos reales en los que el algoritmo está llegando a consenso. Voy a reformular esto a

Para comenzar la fase de aceptación, el propositor debe elegir un valor que se acepte dependiendo de los resultados de la fase de preparación. Si algún aceptador respondió con Promise (RoundId, Value), el proponente debe usar el valor asociado con el Roundid más alto. De lo contrario, el proponente recibió solo promesa (NULL, NULL), y puede elegir cualquier valor para enviar a los aceptores.

NB: El número de propuesta aquí es lo mismo que Roundid.

En la fase 2A: "De lo contrario, el proponente es libre de elegir cualquier valor". ¿Qué significa esto? ¿Un valor para qué? Para el número de propuesta?

Este es el valor en el que desea tener consenso. Este es típicamente un cambio de estado en todo el sistema distribuido, tal vez activado por una solicitud de cliente.

¿Paxos parece confiar en un valor creciente de n (número de propuesta) para que funcione? ¿Es esto correcto?

La entrada de Wikipedia no discute los valores iniciales que un nodo debe establecer antes de comenzar a participar en Paxos. ¿Que son estos?

IDS redondos (también conocidos como números de propuestas) debería estar aumentando y deber Sea único por instancia en todos los nodos. El artículo de Paxos supone que puede hacer esto porque es trivial de lograr. Aquí hay un esquema que produce los mismos resultados en todos los nodos:

1. Digamos que hay M nodos que participan en una instancia de Paxos.
2. Ordena todos los nodos lexicográficamente. El índice [nodo] es el índice de un nodo en esta lista ordenada.
3. roundId = i*M + index[node] Donde yo es el ésimo alrededor de este nodo está comenzando (es decir, es único por nodo por instancia de Paxos, y está aumentando monotónicamente).

O en el código de pseudo (que claramente carece de algunas optimizaciones importantes):

define runPaxos( allNodesThisPaxosInstance, myValue ) {
    allNodesThisPaxosInstance.sort()
    offset = allNodesThisPaxosInstance.indexOf( thisNode )
    for (i = 0; true; i++) {
        roundId = offset + i * allNodesThisPaxosInstance.size()
        prepareResult = doPreparePhase( roundId )

        if (!prepareResult.shouldContinue?)
            return

        if (prepareResult.hasAnyValue?)
           chosenValue = prepareResult.valueWithHighestRoundId
        else
            chosenValue = myValue

        acceptResult = doAcceptPhase( roundId, chosenValue )

        if (!acceptResult.shouldContinue?)
            return
    }
}

Answer 2

He encontrado lo siguiente documento Explicando paxos en más detalles. He actualizado la entrada de Wikipedia en consecuencia.

Las respuestas a mi pregunta que pude encontrar son:

¿No va a ingresar Paxos en un bucle infinito?

Paxos solo funciona si al menos un quórum de nodos puede comunicarse entre sí (en nuestro caso 5). Por lo tanto, si un nodo no puede comunicarse con al menos un quórum de nodos, no debe probar paxos.

¿Cuál es 'el último valor que aceptó'?

Es el último número de propuesta aceptado y el valor correspondiente.

¿A qué se refiere 'instancia' exactamente en este caso?

Se refiere al aceptador.

¿Uno incluye el valor para acordar con el mensaje de preparación o es esto diferido para aceptar! ¿mensaje? ¿O importa?

El valor no está incluido en el mensaje de preparación, se deja al mensaje de solicitud de aceptación.

¿Qué es el valor aquí? ¿Es el número de propuesta? Creo que no, pero esta frase no está clara.

"De lo contrario, el proponente es libre de elegir cualquier valor". ¿Qué significa esto? ¿Un valor para qué? Para el número de propuesta?

Si los aceptores ya han aceptado una propuesta del propuesta, pueden devolver el número y el valor de la propuesta correspondiente, de lo contrario nada.

La segunda pregunta cae, ya que la entrada de Wikipedia fue engañosa. Se puede elegir un valor arbitrario para una propuesta dada o derivarla de los valores correspondientes a las propuestas aceptadas anteriormente.

¿Paxos parece confiar en un valor creciente de n (número de propuesta) para que funcione? ¿Es esto correcto?

Sí. Un proponente P necesita numerar sus propuestas cada vez más.

La entrada de Wikipedia no discute los valores iniciales que un nodo debe establecer antes de comenzar a participar en Paxos. ¿Que son estos?

Los nodos deben mantener su último número de propuesta aceptado y, finalmente, el valor correspondiente también. Deberían persistirlo. Al conectarse por primera vez, el número de propuesta inicial para un propositor dado debe ser nulo (o cualquier equivalente).

Answer 3

Paxos seems to rely on an increasing value of N (proposal number) to work? Is this correct?

Cada propositor tiene almacenamiento estable. Cada propuesta recuerda (en almacenamiento estable) la propuesta de mayor número que ha tratado de emitir, y comienza la Fase 1 con un número de propuesta más alto que cualquiera que ya haya utilizado.