Algoritmo de Paxos
El algoritmo Paxos juega un papel muy importante en el campo distribuido. Pero el algoritmo de Paxos tiene dos deficiencias obvias: 1. Es difícil de entender. 2. Es más difícil de lograr en ingeniería.
Hay muchos artículos que explican el algoritmo de Paxos en Internet, pero la calidad varía. Después de leer mucha información sobre Paxos, descubrí que la mejor información para aprender Paxos es el artículo sobre cómo simplificar Paxos, seguido de la introducción a Paxos en Wikipedia en chino e inglés. Este artículo intenta guiarte paso a paso para descubrir el misterio de Paxos.
¿Qué es Paxos?
El algoritmo Paxos es un algoritmo de consenso basado en el paso de mensajes y es altamente tolerante a fallos. Actualmente se reconoce que resuelve el problema de coherencia distribuida. Uno de los algoritmos más eficientes.
Mike Burrows, autor de Google Chubby, dijo que sólo existe un algoritmo de consenso en el mundo, es Paxos, y que todos los demás algoritmos son defectuosos.
Aunque Mike Burrows es un poco exagerado, al menos ilustra el estado del algoritmo de Paxos. Sin embargo, el algoritmo de Paxos también es conocido por su oscuridad. El propósito de este artículo es llevar a todos a comprender el algoritmo de Paxos de una manera simple y fácil de entender, no solo para comprender su proceso de ejecución, sino también para comprender el proceso de derivación del algoritmo y cómo se le ocurrió al autor. con la solución final paso a paso. Sólo comprendiendo el proceso de derivación podremos comprender profundamente la esencia del algoritmo. Además, comprender el proceso de derivación también es muy útil para nuestro pensamiento, puede brindarnos algunas ideas para resolver problemas e inspirarnos.
Antecedentes del problema.
En los sistemas distribuidos comunes, siempre ocurrirán cosas como tiempo de inactividad de la máquina o anomalías de la red (incluidos retrasos en los mensajes, pérdidas, duplicaciones, desorden y segmentación de la red). El problema que el algoritmo Paxos debe resolver es cómo verificar rápida y correctamente los lugares donde pueden ocurrir las excepciones anteriores dentro del clúster en un sistema distribuido. El valor de determinados datos es coherente, lo que garantiza que, independientemente de que se produzca alguna de las excepciones anteriores, no se destruirá la coherencia de todo el sistema.
Nota: El valor de un determinado dato aquí no es solo un número en sentido estricto, puede ser un registro o un comando. . . Según los diferentes escenarios de aplicación, el valor de un determinado dato tiene diferentes significados.
Conceptos relacionados
En el algoritmo de Paxos, existen tres roles:
Solicitante
Aceptor
Aprendiz
En una implementación específica, un proceso puede desempeñar múltiples roles al mismo tiempo. Por ejemplo, un proceso puede ser a la vez proponente, destinatario y alumno.
También existe un concepto muy importante llamado propuesta. El valor final a acordar está en la propuesta.
Nota:- Asumimos que "Propuesta = Valor" significa que la propuesta solo contiene valor. En nuestra próxima derivación, encontraremos que habrá problemas si la propuesta solo contiene valor, así que analicemos la propuesta nuevamente. Rediseño. ——Por el momento, “el proponente podrá presentar directamente la propuesta”. En nuestra derivación posterior, encontraremos que habrá problemas si el proponente hace una propuesta directamente y es necesario agregar un proceso de aprendizaje de la propuesta.
El proponente puede hacer una propuesta; el aceptador puede aceptar la propuesta; si se selecciona la propuesta, se selecciona el valor de la propuesta.
Volviendo a lo que acabo de decir sobre "llegar a un acuerdo sobre el valor de un determinado dato", significa que el proponente, el destinatario y el alumno piensan que se ha elegido el mismo valor. Entonces, ¿bajo qué circunstancias el proponente, el receptor y el alumno pueden considerar elegido un determinado valor?
Proponente: Siempre que la propuesta emitida por el proponente sea aceptada por el aceptante (inicialmente se piensa que solo se necesita un aceptador, durante el proceso de derivación se encontrará que más de la mitad de los destinatarios de acuerdo), el proponente cree que se ha seleccionado el valor de la propuesta.
Aceptador: Siempre que el Aceptador acepte la sugerencia, el Aceptador seleccionará el valor en la sugerencia.
Alumno: el receptor le dice al alumno qué valor se seleccionó y el alumno cree que se seleccionó ese valor.
Descripción del problema
Supongamos que hay un conjunto de procesos que pueden proponer)valor(valor(valor(valor(valor) está en la propuesta)). El algoritmo de consenso debe garantizar que entre tantos valores propuestos, solo se seleccione un valor. Si no se propone ningún valor, no se debe seleccionar ningún valor.
Si se elige un valor, ¿todos los procesos deberían poder hacerlo? Conozca este valor seleccionado. Para el algoritmo de consenso, los requisitos de seguridad son los siguientes:
Solo se pueden seleccionar los valores recomendados.
Solo se selecciona un valor, y
Si un proceso cree que se selecciona un valor, entonces este valor debe ser el valor que realmente está seleccionado.
No hemos definido con precisión sus requisitos de vida. Nuestro objetivo es garantizar que finalmente se elija un valor recomendado. Cuando se elige un valor, el proceso eventualmente puede aprender ese valor.
El objetivo de Paxos: garantizar que finalmente se seleccione un valor y que cuando se seleccione el valor, el proceso pueda eventualmente obtener el valor seleccionado.
Suponiendo que diferentes actores pueden comunicarse enviando mensajes, entonces:
Cada actor se ejecuta a una velocidad arbitraria y puede detenerse o reiniciarse debido a errores. Después de seleccionar un valor, todos los roles pueden fallar y luego reiniciarse. A menos que los personajes que se reinician después de un error puedan registrar alguna información, el valor de la selección no se puede determinar después de un reinicio.
Los mensajes pueden retrasarse durante cualquier período de tiempo en tránsito y pueden duplicarse o perderse. Pero el mensaje no será destruido, es decir, el contenido del mensaje no será alterado (problema general bizantino)
Proceso de deducción
La solución más simple: un solo receptor
p>Suponiendo que solo hay un aceptador (puede haber varios proponentes), siempre que el aceptador acepte la primera propuesta que recibe, la propuesta se selecciona y el valor en la propuesta es el valor seleccionado. Esto garantiza que solo se seleccione un valor.
Sin embargo, si el único destinatario cae, ¡todo el sistema fallará!
¡Por lo tanto, debe haber varios destinatarios!
Múltiples receptores
La situación con múltiples destinatarios se muestra a continuación. Entonces, ¿cómo se garantiza que se elegirá un valor en el caso de múltiples proponentes y múltiples aceptantes?
Empecemos a buscar soluciones.
Si queremos que incluso un proponente proponga un valor, este valor eventualmente será seleccionado.
Luego se obtienen las siguientes restricciones:
P1: El aceptador debe aceptar la primera sugerencia que recibe.
Sin embargo, esto lleva a otro problema: si cada proponente propone un valor diferente y lo envía a un destinatario diferente. Según P1, el Aceptador acepta los valores que recibe por separado, lo que da como resultado que se seleccionen diferentes valores. Hay inconsistencias. Como se muestra en la siguiente figura:
El problema de inconsistencia anterior ocurre solo porque "siempre que el destinatario acepte una sugerencia, se selecciona el valor de la sugerencia". Por lo tanto, necesitamos agregar una estipulación:
Estipulación: Una propuesta seleccionada debe ser aceptada por más de la mitad de los destinatarios.
Esta disposición también significa: "¡El aceptador debe poder aceptar más de una propuesta! De lo contrario, no se podrá seleccionar ningún valor al final. Por ejemplo, en la imagen de arriba. V1, v2 y v3 son no seleccionados porque solo son aceptados por un destinatario.
La propuesta = valor original ya no puede satisfacer las necesidades, por lo que rediseñamos la propuesta y agregamos un número de propuesta a cada propuesta para indicar el orden en el que se enviaron. se envió la propuesta. Orden "Propuesta = Número de propuesta + Valor".
Aunque se permite seleccionar varias propuestas, se debe garantizar que todas las propuestas seleccionadas tengan el mismo valor. Entonces existen las siguientes restricciones:
P2: Si se selecciona una sugerencia con un valor de V, cada sugerencia seleccionada con un número mayor también debe tener un valor de V..
Una sugerencia solo se puede seleccionar si es aceptada por el aceptador, por lo que podemos reescribir la restricción P2 de la sugerencia aceptada por el aceptador como una restricción P2a
P2a: Si se selecciona la sugerencia con valor V. , entonces el valor de cada sugerencia con un número mayor aceptada por el Aceptador también debe ser V.
Mientras se cumpla P2a, se puede satisfacer P2
Sin embargo, considere el. siguiente situación: Supongamos que hay 5 aceptantes en total. El proponente 2 propuso la propuesta [M1, V1] y los aceptantes 2 ~ 5 (más de la mitad) aceptaron la propuesta, por lo que tanto para los aceptantes 2 ~ 5 como para el proponente 2, V1 fue. seleccionado.
El Aceptador1 acaba de recuperarse del cierre (el Aceptador1 no ha recibido ninguna propuesta antes. En este momento, el proponente 1 envía la propuesta de [M2, V2] al Aceptador1 (V2≠V1 y m2>: M1, esto). fue la primera propuesta que recibió. Según P1 (el aceptador debe aceptar la primera propuesta que recibe), ¡el aceptador1 debe aceptar la propuesta! Al mismo tiempo, Acceptor1 cree que se ha seleccionado V2. Esto plantea dos preguntas:
El aceptador 1 piensa que V2 está seleccionado, mientras que los aceptadores 2~5 y el proponente 2 piensan que V1 está seleccionado. Hay inconsistencias. ?
Se selecciona V1, pero el valor de la propuesta de mayor valor del Aceptador1 [M2, V2] es V2, V2≠V1. Esto contradice P2a (si se selecciona una propuesta con un valor de V, entonces cada propuesta con un número mayor aceptada por el Aceptador también debe tener un valor de V).
¡Así que necesitamos fortalecer las limitaciones de P2a!
P2a es una restricción a la propuesta aceptada por el aceptante, pero en realidad la propuesta es propuesta por el proponente, por lo que podemos restringir la propuesta propuesta por el proponente. Obtener P2b:
P2b: si se selecciona una propuesta con un valor de V, cualquier propuesta con un número mayor del proponente también debe tener un valor de V.
Se puede obtener de P2b Deduzca P2a y luego podrá deducir P2.
Entonces, ¿cómo garantizar que después de seleccionar una propuesta con un valor de V, todas las propuestas con números más altos presentadas por el proponente tengan el valor de V?
Siempre que se cumpla P2c:
P2c: Para cualquier N y V, si se hace una propuesta [N, V], entonces hay un conjunto S que consta de más de la mitad de los aceptantes, Satisface cualquiera de las dos condiciones siguientes: Cada aceptador en -S nunca ha aceptado una propuesta con un número menor que N. El valor de la propuesta con el mayor número aceptado por el aceptador en -S es v.
Los proponentes generan propuestas.
Para satisfacer P2b, hay una idea importante aquí: antes de generar una propuesta, el proponente primero debe "aprender" el valor que ha sido seleccionado o puede ser seleccionado, y luego usar este valor como valor valor de su propia propuesta. Si no se selecciona ningún valor, el proponente puede decidir él mismo el valor del valor. Sólo entonces podremos llegar a un acuerdo. Esta fase de aprendizaje se logra a través de "Preparar Solicitudes".
Así, obtenemos el siguiente algoritmo de generación de propuestas:
El proponente elige una nueva propuesta número n y luego envía una solicitud a un conjunto de aceptantes (más de la mitad) solicitando Cada de los destinatarios responde lo siguiente. (a) ¿Asumir un compromiso con el proponente? Ya no se aceptarán propuestas con un número menor que n. (b) Si el aceptante acepta la propuesta, responderá a la propuesta aceptada del proponente con un número máximo menor que n.
A esta solicitud la llamamos solicitud de preparación numerada n.
Si el proponente recibe respuestas de más de la mitad de los destinatarios, puede generar un número N propuestas con un valor v [N, V]. v aquí está una de todas las respuestas. El valor de la sugerencia con el número más alto. Si no hay propuestas entre todas las respuestas, el proponente puede elegir V. Una vez generada la propuesta, ¿el proponente la envía a? Una colección de más de la mitad de los destinatarios que se espera que acepten la propuesta. A esta solicitud la llamamos solicitud de aceptación. (Nota: el conjunto de aceptadores que acepta la solicitud de aceptación en este momento no es necesariamente el conjunto de aceptadores que respondió previamente a la solicitud de preparación).
Los aceptadores aceptan sugerencias
El aceptador puede ignorar cualquier solicitud (incluida la preparación y aceptación de solicitudes) sin preocuparse por romper la seguridad del algoritmo. Por lo tanto, lo que vamos a discutir aquí es cuándo el Aceptador puede responder a una solicitud.
Tenemos las siguientes restricciones para que los aceptantes acepten propuestas:
P1a: Siempre que el aceptador no responda a ninguna solicitud de preparación con un número mayor que N, ¿entonces puede? Aceptar la propuesta numerada n.
Si el Aceptador recibe una solicitud de preparación con el número n, entonces ha respondido previamente a una solicitud de preparación con el número mayor que n. Según P1a, es imposible que el aceptador acepte la propuesta número n, por lo que el aceptador puede ignorar la solicitud de preparación número n. Por supuesto, también puede responder con un error para informarle al proponente lo antes posible que su propuesta. no será aceptado.
Así que un aceptador sólo necesita recordar: 1. Se aceptó la propuesta con mayor número de personas. El número máximo de solicitudes a las que responder.
El algoritmo de Paxos se divide en dos etapas. Los detalles son los siguientes:
(a) El proponente selecciona una propuesta número n y luego envía una solicitud de preparación numerada n a más de la mitad de los destinatarios.
(b) Si el aceptador recibe una cantidad de solicitudes de preparación n, y n es mayor que la cantidad de todas las solicitudes de preparación a las que el aceptador ha respondido, ¿las enviará? La propuesta aceptada con el número más alto (si la hay) se devuelve al proponente. En respuesta, el aceptador promete no aceptar ninguna propuesta con un número inferior a n.
(a) Si el proponente recibe respuestas de más de la mitad de los destinatarios a su solicitud de preparación de número N, ¿el proponente enviará una propuesta para [N, V]? Aceptar solicitudes de más de la mitad de los destinatarios. Nota: V es el valor de la sugerencia numerada más alta entre las respuestas recibidas. ¿Si la respuesta está en progreso? no contiene ninguna propuesta, entonces v lo decide el proponente.
(b) ¿Si el destinatario recibe una solicitud de aceptación para la propuesta número n, siempre y cuando el destinatario no realice una solicitud de preparación para el número n o más? En respuesta, aceptó la oferta.
El alumno aprende el valor seleccionado.
Hay tres opciones para que los alumnos aprendan (obtengan) el valor seleccionado:
Cómo garantizar la actividad del algoritmo de Paxos
Seleccionando el proponente principal , puede garantizar la actividad del algoritmo de Paxos. En este punto, hemos obtenido un algoritmo de consenso distribuido que puede garantizar tanto la seguridad como la vida. Algoritmo de Paxos.
Datos de referencia
Paxos simplificado
Documento "Parlamento a tiempo parcial"
Paxos en Wikipedia en inglés
Wikipedia china
Libros desde parques hasta cuidadores de zoológicos