Paxos es una familia de protocolos para resolver consensos en una red de procesadores falibles o poco confiables. El consenso es el proceso de acordar un resultado entre un grupo de participantes. Este problema se vuelve difícil cuando los participantes o sus comunicaciones pueden experimentar fallas. [1]
Los protocolos de consenso son la base del enfoque de replicación de máquinas de estados para la computación distribuida , como lo sugiere Leslie Lamport [2] y lo analizó Fred Schneider . [3] La replicación de la máquina de estados es una técnica para convertir un algoritmo en una implementación distribuida tolerante a fallas. Las técnicas ad hoc pueden dejar sin resolver casos importantes de fallas. El enfoque de principios propuesto por Lamport et al. garantiza que todos los casos se manejen de forma segura.
El protocolo Paxos se presentó por primera vez en 1989 y recibió el nombre de un sistema de consenso legislativo ficticio utilizado en la isla de Paxos en Grecia, donde Lamport escribió que el parlamento tenía que funcionar "a pesar de que los legisladores entraban y salían continuamente de la Cámara parlamentaria". [4] Posteriormente se publicó como artículo de revista en 1998. [5]
La familia de protocolos Paxos incluye un espectro de compensaciones entre la cantidad de procesadores, la cantidad de retrasos en los mensajes antes de conocer el valor acordado, el nivel de actividad de los participantes individuales, la cantidad de mensajes enviados y los tipos de fallas. Aunque ningún protocolo de consenso determinista tolerante a fallos puede garantizar el progreso en una red asíncrona (un resultado demostrado en un artículo de Fischer , Lynch y Paterson [6] ), Paxos garantiza la seguridad (consistencia) y las condiciones que podrían impedirle avanzar. Son difíciles de provocar.
Paxos se utiliza normalmente cuando se requiere durabilidad (por ejemplo, para replicar un archivo o una base de datos ), en los que la cantidad de estado duradero podría ser grande. El protocolo intenta avanzar incluso durante los períodos en los que un número limitado de réplicas no responden. También existe un mecanismo para descartar una réplica con error permanente o agregar una nueva réplica.
El tema es anterior al protocolo. En 1988, Lynch , Dwork y Stockmeyer habían demostrado [7] la solucion del consenso en una amplia familia de sistemas "parcialmente sincrónicos". Paxos tiene fuertes similitudes con un protocolo utilizado para acuerdos en "replicación con sello de vista", publicado por primera vez por Oki y Liskov en 1988, en el contexto de transacciones distribuidas. [8] A pesar de este trabajo previo, Paxos ofreció un formalismo particularmente elegante e incluyó una de las primeras pruebas de seguridad para un protocolo de consenso distribuido tolerante a fallas.
Las máquinas de estados reconfigurables tienen fuertes vínculos con trabajos anteriores sobre protocolos de multidifusión grupal confiables que soportan la membresía dinámica en grupos, por ejemplo el trabajo de Birman en 1985 y 1987 sobre el protocolo gbcast [9] virtualmente sincrónico . Sin embargo, gbcast es inusual en cuanto a soporte de durabilidad y solución de fallas de partición. La mayoría de los protocolos de multidifusión confiables carecen de estas propiedades, que son necesarias para las implementaciones del modelo de replicación de la máquina de estados. Este punto se desarrolla en un artículo de Lamport , Malkhi y Zhou. [10]
Los protocolos de Paxos son miembros de una clase teórica de soluciones a un problema formalizado como un acuerdo uniforme con fallas de choque. Keidar y Shraer han demostrado los límites inferiores de este problema . [11] Derecho, [12] una biblioteca de software C++ para replicación de máquinas de estado a escala de nube, ofrece un protocolo Paxos que se ha integrado con una membresía virtualmente síncrona autoadministrada. Este protocolo coincide con los límites de optimización de Keidar y Shraer y se asigna de manera eficiente al hardware moderno del centro de datos remoto DMA (RDMA) (pero usa TCP si RDMA no está disponible).
Para simplificar la presentación de Paxos, se hacen explícitos los siguientes supuestos y definiciones. Las técnicas para ampliar la aplicabilidad se conocen en la literatura y no se tratan en este artículo.
En general, un algoritmo de consenso puede progresar utilizando procesadores, a pesar del fallo simultáneo de cualquier procesador: [13] en otras palabras, el número de procesos no defectuosos debe ser estrictamente mayor que el número de procesos defectuosos. Sin embargo, al utilizar la reconfiguración, se puede emplear un protocolo que sobreviva cualquier número de fallos totales, siempre que no fallen más de F simultáneamente. Para los protocolos Paxos, estas reconfiguraciones se pueden manejar como configuraciones separadas . [14]
Para garantizar la seguridad (también llamada "consistencia"), Paxos define tres propiedades y garantiza que las dos primeras se mantengan siempre, independientemente del patrón de fallas:
Tenga en cuenta que no se garantiza que Paxos finalice y, por lo tanto, no tiene la propiedad de vida. Esto está respaldado por el resultado de imposibilidad (FLP) de Fischer Lynch Paterson [6] que establece que un protocolo de coherencia solo puede tener dos: seguridad , vivacidad y tolerancia a fallas . Como el objetivo de Paxos es garantizar la tolerancia a fallas y garantizar la seguridad, no puede garantizar también la vida.
En la mayoría de las implementaciones de Paxos, cada proceso participante actúa en tres roles; Proponente, Aceptante y Alumno. [17] Esto reduce significativamente la complejidad del mensaje, sin sacrificar la corrección:
En Paxos, los clientes envían comandos a un líder. Durante la operación normal, el líder recibe el comando de un cliente, le asigna un nuevo número de comando y luego comienza la enésima instancia del algoritmo de consenso enviando mensajes a un conjunto de procesos aceptadores. [dieciséis]
Al fusionar roles, el protocolo "colapsa" en una implementación eficiente de estilo cliente-maestro-réplica, típica de la comunidad de bases de datos. [18] El beneficio de los protocolos Paxos (incluidas las implementaciones con roles fusionados) es la garantía de sus propiedades de seguridad.
El flujo de mensajes de una implementación típica se trata en la sección Multi-Paxos.
Este protocolo es el más básico de la familia Paxos. Cada "instancia" (o "ejecución") del protocolo básico de Paxos decide sobre un único valor de salida. El protocolo se desarrolla en varias rondas. Una ronda exitosa tiene 2 fases: la fase 1 (que se divide en las partes a y b ) y la fase 2 (que se divide en las partes a y b ). Vea a continuación la descripción de las fases. Recuerde que asumimos un modelo asíncrono, por lo que, por ejemplo, un procesador puede estar en una fase mientras que otro procesador puede estar en otra.
Este mensaje de Aceptar debe interpretarse como una "solicitud", como en "¡Acepte esta propuesta, por favor!".
Tenga en cuenta que el consenso se logra cuando la mayoría de los Aceptadores aceptan el mismo número de identificador (en lugar del mismo valor ). Debido a que cada identificador es exclusivo de un Proponente y solo se puede proponer un valor por identificador, todos los Aceptadores que aceptan el mismo identificador aceptan el mismo valor. Estos hechos dan como resultado algunos escenarios contrarios a la intuición que no afectan la corrección: los Aceptadores pueden aceptar múltiples valores, un valor puede lograr una mayoría entre los Aceptadores (con diferentes identificadores) solo para cambiarse más tarde, y los Aceptadores pueden continuar aceptando propuestas después de una identificador ha alcanzado la mayoría. Sin embargo, el protocolo Paxos garantiza que el consenso es permanente y el valor elegido es inmutable.
Observe que un Proponente en Paxos podría proponer "Yo soy el líder" (o, por ejemplo, "El Proponente X es el líder"). [20] Debido al acuerdo y las garantías de validez de Paxos, si es aceptado por un Quórum, ahora se sabe que el Proponente es el líder de todos los demás nodos. Esto satisface las necesidades de la elección del líder [21] porque hay un solo nodo que cree que es el líder y un solo nodo que se sabe que es el líder en todo momento.
Los siguientes diagramas representan varios casos/situaciones de aplicación del protocolo Paxos Básico. Algunos casos muestran cómo el protocolo Basic Paxos hace frente a la falla de ciertos componentes (redundantes) del sistema distribuido.
Tenga en cuenta que los valores devueltos en el mensaje de Promesa son "nulos" la primera vez que se realiza una propuesta (ya que ningún Aceptador ha aceptado un valor antes en esta ronda).
En el siguiente diagrama, hay 1 cliente, 1 proponente, 3 aceptantes (es decir, el tamaño del quórum es 3) y 2 estudiantes (representados por las 2 líneas verticales). Este diagrama representa el caso de una primera ronda que tiene éxito (es decir, ningún proceso en la red falla).
Aquí, V es el último de (Va, Vb, Vc).
Los casos de error más simples son el fallo de un Aceptador (cuando un Quórum de Aceptadores permanece vivo) y el fallo de un Aprendiz redundante. En estos casos, el protocolo no requiere "recuperación" (es decir, aún tiene éxito): no se requieren rondas ni mensajes adicionales, como se muestra a continuación (en los dos diagramas/casos siguientes).
En el siguiente diagrama, uno de los Aceptadores del Quórum falla, por lo que el tamaño del Quórum pasa a ser 2. En este caso, el protocolo Paxos Básico aún tiene éxito.
Cliente Proponente Aceptador Aprendiz | | | | | | | X-------->| | | | | | Pedido | X--------->|->|->| | | Preparar(1) | | | | ! | | !! FALLAR !! | |<---------X--X | | Promesa(1,{Va, Vb, nulo}) | X--------->|->| | | ¡Aceptar!(1,V) | |<---------X--X--------->|->| Aceptado(1,V) |<---------------------------------X--X Respuesta | | | | | |
En el siguiente caso, uno de los alumnos (redundantes) falla, pero el protocolo Paxos básico aún tiene éxito.
Cliente Proponente Aceptador Aprendiz | | | | | | | X-------->| | | | | | Pedido | X--------->|->|->| | | Preparar(1) | |<---------X--X--X | | Promesa(1,{Va,Vb,Vc}) | X--------->|->|->| | | ¡Aceptar!(1,V) | |<---------X--X--X------>|->| Aceptado(1,V) | | | | | | ! !! FALLAR !! |<---------------------------------X Respuesta | | | | | |
En este caso, un Proponente fracasa después de proponer un valor, pero antes de que se llegue a un acuerdo. Específicamente, falla en medio del mensaje de aceptación, por lo que solo un Aceptador del Quórum recibe el valor. Mientras tanto, se elige un nuevo Líder (un Proponente) (pero esto no se muestra en detalle). Tenga en cuenta que en este caso hay 2 rondas (las rondas se realizan verticalmente, de arriba a abajo).
Cliente Proponente Aceptador Aprendiz | | | | | | | X----->| | | | | | Pedido | X------------>|->|->| | | Preparar(1) | |<------------X--X--X | | Promesa(1,{Va, Vb, Vc}) | | | | | | | | | | | | | | !! ¡¡Líder falla durante la transmisión!! | X------------>| | | | | ¡Aceptar!(1,V) | ! | | | | | | | | | | | | !! ¡¡NUEVO LÍDER!! | X--------->|->|->| | | Preparar(2) | |<---------X--X--X | | Promesa(2,{V, nulo, nulo}) | X--------->|->|->| | | ¡Acepta!(2,V) | |<---------X--X--X------>|->| Aceptado(2,V) |<---------------------------------X--X Respuesta | | | | | | |
El caso más complejo es cuando varios Proponentes se creen Líderes. Por ejemplo, el líder actual puede fracasar y luego recuperarse, pero los otros Proponentes ya han vuelto a seleccionar un nuevo líder. El líder recuperado aún no se ha enterado de esto e intenta comenzar una ronda en conflicto con el líder actual. En el siguiente diagrama se muestran 4 rondas fallidas, pero podría haber más (como se sugiere en la parte inferior del diagrama).
Cliente Proponente Aceptador Aprendiz | | | | | | | X----->| | | | | | Pedido | X------------>|->|->| | | Preparar(1) | |<------------X--X--X | | Promesa(1,{nulo,nulo,nulo}) | ! | | | | | !! EL LÍDER FALLA | | | | | | | !! NUEVO LÍDER (sabe que el último número fue 1) | X--------->|->|->| | | Preparar(2) | |<---------X--X--X | | Promesa(2,{nulo,nulo,nulo}) | | | | | | | | !! VIEJO LÍDER se recupera | | | | | | | | !! VIEJO LÍDER intenta 2, negado | X------------>|->|->| | | Preparar(2) | |<------------X--X--X | | desnudo(2) | | | | | | | | !! VIEJO LÍDER intenta 3 | X------------>|->|->| | | Preparar(3) | |<------------X--X--X | | Promesa(3,{nulo,nulo,nulo}) | | | | | | | | !! NUEVO LÍDER propone, desestimado | | X--------->|->|->| | | ¡Acepta!(2,Va) | | |<---------X--X--X | | Nack(3) | | | | | | | | !! NUEVO LÍDER intenta 4 | | X--------->|->|->| | | Preparar(4) | | |<---------X--X--X | | Promesa(4,{nulo,nulo,nulo}) | | | | | | | | !! VIEJO LÍDER propone, negado | X------------>|->|->| | | ¡Aceptar!(3,Vb) | |<------------X--X--X | | desnudo(4) | | | | | | | | ... etcétera ...
En el siguiente caso, un Proponente logra la aceptación del valor V1 por parte de un Aceptante antes de fallar. Un nuevo Proponente prepara a los Aceptadores que nunca aceptaron V1, permitiéndole proponer V2. Luego, V2 es aceptado por todos los Aceptadores, incluido el que inicialmente aceptó V1.
Proponente Aceptador Aprendiz | | | | | | | X--------->|->|->| | | Preparar(1) |<---------X--X--X | | Promesa(1,{nulo,nulo,nulo}) x--------->| | | | | ¡Aceptar!(1,V1) | | X------------>|->| Aceptado(1,V1) ! | | | | | | !! FALLAR !! | | | | | | X--------->|->| | | Preparar(2) |<---------X--X | | Promesa(2,{nulo,nulo}) X------>|->|->| | | ¡Acepta! (2,V2) |<------X--X--X------>|->| Aceptado(2,V2) | | | | | |
En el siguiente caso, un Proponente logra la aceptación del valor V1 de un Aceptante antes de fallar. Un nuevo Proponente prepara a los Aceptadores que nunca aceptaron V1, permitiéndole proponer V2. Este Proponente puede conseguir que un Aceptador acepte V2 antes de fallar. Un nuevo Proponente encuentra una mayoría que incluye al Aceptante que ha aceptado V1 y debe proponerlo. El Proponente logra que dos Aceptadores lo acepten antes de fallar. En este punto, tres Aceptadores han aceptado V1, pero no para el mismo identificador. Finalmente, un nuevo Proponente prepara a la mayoría que no ha visto el mayor identificador aceptado. El valor asociado al mayor identificador de esa mayoría es V2, por lo que deberá proponerlo. Luego, este Proponente consigue que todos los Aceptadores acepten la V2, logrando un consenso.
Proponente Aceptador Aprendiz | | | | | | | | | | | X--------------->|->|->|->|->| | | Preparar(1) |<---------------X--X--X--X--X | | Promesa(1,{nulo,nulo,nulo,nulo,nulo}) x--------------->| | | | | | | ¡Aceptar!(1,V1) | | | | X------------------>|->| Aceptado(1,V1) ! | | | | | | | | | | !! FALLAR !! | | | | | | | | | | X--------------->|->|->|->| | | Preparar(2) |<---------------X--X--X--X | | Promesa(2,{nulo,nulo,nulo,nulo}) X--------------->| | | | | | ¡Acepta! (2,V2) | | | | X--------------->|->| Aceptado(2,V2) ! | | | | | | | | | !! FALLAR !! | | | | | | | | | X--------->|---->|->|->| | | Preparar(3) |<---------X-----X--X--X | | Promesa(3,{V1,nulo,nulo,nulo}) X--------------->|->| | | | ¡Acepta! (3,V1) | | | | X--X--------->|->| Aceptado(3,V1) ! | | | | | | | | !! FALLAR !! | | | | | | | | X------>|->|------->| | | Preparar(4) |<------X--X--|--|--X | | Promesa(4,{V1(1),V2(2),nulo}) X------>|->|->|->|->| | | ¡Acepta! (4,V2) | X--X--X--X--X------>|->| Aceptado(4,V2)
En el siguiente caso, un Proponente logra la aceptación del valor V1 de dos Aceptadores antes de fallar. Un nuevo Proponente puede comenzar otra ronda, pero ahora le resulta imposible preparar una mayoría que no incluya al menos un Aceptante que haya aceptado V1. Como tal, aunque el Proponente no ve el consenso existente, su única opción es proponer el valor ya acordado. Los nuevos proponentes pueden aumentar continuamente el identificador para reiniciar el proceso, pero el consenso nunca se puede cambiar.
Proponente Aceptador Aprendiz | | | | | | | X--------->|->|->| | | Preparar(1) |<---------X--X--X | | Promesa(1,{nulo,nulo,nulo}) x--------->|->| | | | ¡Aceptar!(1,V1) | | X--X--------->|->| Aceptado(1,V1) ! | | | | | | !! FALLAR !! | | | | | | X--------->|->| | | Preparar(2) |<---------X--X | | Promesa(2,{V1,nulo}) X------>|->|->| | | ¡Acepta! (2,V1) |<------X--X--X------>|->| Aceptado(2,V1) | | | | | |
Una implementación típica de Paxos requiere un flujo continuo de valores acordados que actúan como comandos para una máquina de estado distribuida. Si cada comando es el resultado de una única instancia del protocolo Basic Paxos, se produciría una cantidad significativa de gastos generales.
Si el líder es relativamente estable, la fase 1 se vuelve innecesaria. Por tanto, es posible saltarse la fase 1 para futuras instancias del protocolo con el mismo líder.
Para lograr esto, el número de ronda I se incluye junto con cada valor que se incrementa en cada ronda por el mismo Líder. Multi-Paxos reduce el retraso de los mensajes sin fallos (propuesta de aprendizaje) de 4 retrasos a 2 retrasos.
En el siguiente diagrama, solo se muestra una instancia (o "ejecución") del protocolo básico de Paxos, con un líder inicial (un proponente). Tenga en cuenta que un Multi-Paxos consta de varias instancias del protocolo Paxos básico.
Cliente Proponente Aceptador Aprendiz | | | | | | | --- Primera Solicitud --- X-------->| | | | | | Pedido | X--------->|->|->| | | Preparar(N) | |<---------X--X--X | | Promesa(N,I,{Va,Vb,Vc}) | X--------->|->|->| | | ¡Aceptar!(N,I,V) | |<---------X--X--X------>|->| Aceptado(N,I,V) |<---------------------------------X--X Respuesta | | | | | | |
donde V = último de (Va, Vb, Vc).
En este caso, las instancias posteriores del protocolo Paxos básico (representado por I+1 ) usan el mismo líder, por lo que la fase 1 (de estas instancias posteriores del protocolo Paxos básico), que consiste en las subfases Preparar y Promesa, se omite. Tenga en cuenta que el líder debe ser estable, es decir, no debe fallar ni cambiar.
Cliente Proponente Aceptador Aprendiz | | | | | | | --- Siguiendo solicitudes --- X-------->| | | | | | Pedido | X--------->|->|->| | | ¡Aceptar!(N,I+1,W) | |<---------X--X--X------>|->| Aceptado(N,I+1,W) |<---------------------------------X--X Respuesta | | | | | | |
Un despliegue común de los Multi-Paxos consiste en reducir el papel de los Proponentes, Aceptadores y Alumnos a "Servidores". Entonces, al final, solo existen "Clientes" y "Servidores".
El siguiente diagrama representa la primera "instancia" de un protocolo básico de Paxos, cuando los roles de Proponente, Aceptador y Aprendiz se reducen a un solo rol, llamado "Servidor".
Servidores de clientes | | | | --- Primera Solicitud --- X-------->| | | Pedido | X->|->| Preparar(N) | |<-X--X Promesa(N, I, {Va, Vb}) | X->|->| ¡Aceptar!(N,I,Vn) | X<>X<>X Aceptado(N,I) |<--------X | | Respuesta | | | |
En las instancias posteriores del protocolo Paxos básico, con el mismo líder que en las instancias anteriores del protocolo Paxos básico, se puede omitir la fase 1.
Servidores de clientes X-------->| | | Pedido | X->|->| ¡Aceptar!(N,I+1,W) | X<>X<>X Aceptado(N,I+1) |<--------X | | Respuesta | | | |
Se pueden realizar varias optimizaciones para reducir la cantidad de mensajes intercambiados, mejorar el rendimiento del protocolo, etc. Algunas de estas optimizaciones se informan a continuación.
Cheap Paxos extiende Basic Paxos para tolerar fallas F con procesadores principales F+1 y procesadores auxiliares F mediante la reconfiguración dinámica después de cada falla.
Esta reducción en los requisitos del procesador se produce a expensas de la vida; Si fallan demasiados procesadores principales en poco tiempo, el sistema debe detenerse hasta que los procesadores auxiliares puedan reconfigurar el sistema. Durante los períodos estables, los procesadores auxiliares no participan en el protocolo.
"Con sólo dos procesadores p y q, un procesador no puede distinguir el fallo del otro procesador del fallo del medio de comunicación. Se necesita un tercer procesador. Sin embargo, ese tercer procesador no tiene que participar en la elección de la secuencia de comandos. Debe tome medidas sólo en caso de que p o q fallen, después de lo cual no hace nada mientras p o q continúan operando el sistema por sí solos. Por lo tanto, el tercer procesador puede ser pequeño/lento/barato, o un procesador dedicado principalmente a otras tareas. ". [22]
Un ejemplo que involucra tres aceptadores principales, un aceptador auxiliar y un tamaño de quórum de tres, que muestra la falla de un procesador principal y su posterior reconfiguración:
{ Aceptadores }Estudiante auxiliar principal del proponente| | | | | | -- Fase 2 --X----------->|->|->| | | ¡Aceptar!(N,I,V)| | | ! | | --- ¡FALLAR! ---|<-----------X--X--------------->| Aceptado(N,I,V)| | | | | -- Fallo detectado (solo se aceptan 2) --X----------->|->|------->| | ¡Aceptar!(N,I,V) (retransmitir, incluir Aux)|<-----------X--X--------X------>| Aceptado(N,I,V)| | | | | -- Reconfigurar: Quórum = 2 --X----------->|->| | | ¡Aceptar!(N,I+1,W) (Aux no participa)|<-----------X--X--------------->| Aceptado(N,I+1,W)| | | | |
Fast Paxos generaliza Basic Paxos para reducir los retrasos en los mensajes de un extremo a otro. En Basic Paxos, el retraso del mensaje desde la solicitud del cliente hasta el aprendizaje es de 3 retrasos de mensaje. Fast Paxos permite 2 retrasos de mensajes, pero requiere que (1) el sistema esté compuesto por 3f+ 1 aceptadores para tolerar hasta f fallas (en lugar de los clásicos 2f+1), y (2) que el Cliente envíe su solicitud a múltiples destinos .
Intuitivamente, si el líder no tiene ningún valor que proponer, entonces un cliente podría enviar un ¡ Aceptar! mensaje a los Aceptadores directamente. Los Aceptadores responderían como en Paxos Básico, enviando mensajes Aceptados al líder y cada Estudiante logrando dos retrasos en los mensajes de Cliente a Estudiante.
Si el líder detecta una colisión, la resuelve enviando ¡Aceptar! mensajes para una nueva ronda que se aceptan como de costumbre. Esta técnica de recuperación coordinada requiere cuatro retrasos en los mensajes del cliente al alumno.
La optimización final ocurre cuando el líder especifica una técnica de recuperación de antemano, lo que permite a los Aceptadores realizar ellos mismos la recuperación de la colisión. Por lo tanto, la recuperación de colisiones no coordinada puede ocurrir en tres retrasos de mensajes (y sólo dos retrasos de mensajes si todos los Estudiantes también son Aceptadores).
Cliente Líder Aceptador Aprendiz | | | | | | | | | X--------->|->|->|->| | | Cualquiera(N,I,Recuperación) | | | | | | | | X------------------->|->|->|->| | | ¡Aceptar!(N,I,W) | |<---------X--X--X--X------>|->| Aceptado(N,I,W) |<------------------------------------X--X Respuesta(W) | | | | | | | |
Propuestas contradictorias con recuperación coordinada. Nota: el protocolo no especifica cómo manejar la solicitud del cliente descartado.
Cliente Líder Aceptador Aprendiz | | | | | | | | | | | | | | | | | | | | | | | | | | | !! Propuestas contradictorias concurrentes | | | | | | | | | !! recibido en diferente orden | | | | | | | | | !! por los aceptantes | X--------------?|-?|-?|-?| | | ¡Aceptar!(N,I,V) X-----------------?|-?|-?|-?| | | ¡Aceptar!(N,I,W) | | | | | | | | | | | | | | | | | | !! Los aceptantes no están de acuerdo con el valor | | |<-------X--X->|->|----->|->| Aceptado(N,I,V) | | |<-------|<-|<-X--X----->|->| Aceptado(N,I,W) | | | | | | | | | | | | | | | | | | !! Detectar colisión y recuperarse | | X------->|->|->|->| | | ¡Aceptar!(N+1,I,W) | | |<-------X--X--X--X----->|->| Aceptado(N+1,I,W) |<---------------------------------X--X Respuesta(W) | | | | | | | | |
Propuestas contradictorias con recuperación descoordinada.
Cliente Líder Aceptador Aprendiz | | | | | | | | | | | X------->|->|->|->| | | Cualquiera(N,I,Recuperación) | | | | | | | | | | | | | | | | | | !! Propuestas contradictorias concurrentes | | | | | | | | | !! recibido en diferente orden | | | | | | | | | !! por los aceptantes | X--------------?|-?|-?|-?| | | ¡Aceptar!(N,I,V) X-----------------?|-?|-?|-?| | | ¡Aceptar!(N,I,W) | | | | | | | | | | | | | | | | | | !! Los aceptantes no están de acuerdo con el valor | | |<-------X--X->|->|----->|->| Aceptado(N,I,V) | | |<-------|<-|<-X--X----->|->| Aceptado(N,I,W) | | | | | | | | | | | | | | | | | | !! Detectar colisión y recuperarse | | |<-------X--X--X--X----->|->| Aceptado(N+1,I,W) |<---------------------------------X--X Respuesta(W) | | | | | | | | |
(roles fusionados de Aceptador/Aprendiz)
Servidores de clientes | | | | | | | | X->|->|->| Cualquiera(N,I,Recuperación) | | | | | | | | | | | | !! Propuestas contradictorias concurrentes | | | | | | !! recibido en diferente orden | | | | | | !! por los servidores | X--------?|-?|-?|-?| ¡Aceptar!(N,I,V) X-----------?|-?|-?|-?| ¡Aceptar!(N,I,W) | | | | | | | | | | | | !! Los servidores no están de acuerdo con el valor | | X<>X->|->| Aceptado(N,I,V) | | |<-|<-X<>X Aceptado(N,I,W) | | | | | | | | | | | | !! Detectar colisión y recuperarse | | X<>X<>X<>X Aceptado(N+1,I,W) |<-----------X--X--X--X Respuesta(W) | | | | | |
El consenso generalizado explora la relación entre las operaciones de la máquina de estados replicada y el protocolo de consenso que la implementa. [16] El descubrimiento principal implica optimizaciones de Paxos cuando se pueden aplicar propuestas contradictorias en cualquier orden. es decir, cuando las operaciones propuestas son operaciones conmutativas para la máquina de estados. En tales casos, se pueden aceptar ambas operaciones en conflicto, evitando los retrasos necesarios para resolver los conflictos y volver a proponer las operaciones rechazadas.
Este concepto se generaliza aún más en secuencias cada vez mayores de operaciones conmutativas, algunas de las cuales se sabe que son estables (y, por lo tanto, pueden ejecutarse). El protocolo rastrea estas secuencias asegurando que todas las operaciones propuestas de una secuencia se estabilicen antes de permitir que cualquier operación que no conmute con ellas se estabilice.
Para ilustrar Paxos generalizado, el siguiente ejemplo muestra un flujo de mensajes entre dos clientes que se ejecutan simultáneamente y una máquina de estado replicada que implementa operaciones de lectura/escritura en dos registros distintos A y B.
Tenga en cuenta queEn esta tabla se indican operaciones que no son conmutativas.
Una posible secuencia de operaciones:
<1:Leer(A), 2:Leer(B), 3:Escribir(B), 4:Leer(B), 5:Leer(A), 6:Escribir(A)>
Dado que 5:Read(A)
conmuta con ambos 3:Write(B)
y 4:Read(B)
, una posible permutación equivalente al orden anterior es la siguiente:
<1:Leer(A), 2:Leer(B), 5:Leer(A), 3:Escribir(B), 4:Leer(B), 6:Escribir(A)>
En la práctica, un viaje se produce sólo cuando las operaciones se proponen al mismo tiempo.
No se muestran las respuestas. Nota: las abreviaturas de los mensajes difieren de los flujos de mensajes anteriores debido a las características específicas del protocolo; consulte [23] para obtener una discusión completa.
Cliente Líder Aceptador Aprendiz | | | | | | | | !! Nuevo líder comienza la ronda | | X----->|->|->| | | Preparar(N) | | |<-----X- X- X | | Promesa(N,nula) | | X----->|->|->| | | Fase2Inicio(N,nulo) | | | | | | | | | | | | | | | | !! Propuestas de desplazamientos simultáneos | X------- ?|-----?|-?|-?| | | Proponer (Leer A) X-----------?|-----?|-?|-?| | | Proponer (Leer B) | | X------X-------------->|->| Aceptado(N,<LeerA,LeerB>) | | |<--------X--X-------->|->| Aceptado(N,<LeerB,LeerA>) | | | | | | | | | | | | | | | | !! Sin conflicto, ambos aceptados. | | | | | | | | Estable = <LeerA, LeerB> | | | | | | | | | | | | | | | | !! Propuestas contradictorias concurrentes X-----------?|-----?|-?|-?| | | Proponer(<EscribirB,LeerA>) | X--------?|-----?|-?|-?| | | Proponer (Leer B) | | | | | | | | | | X------X-------------->|->| Aceptado(N,<EscribirB,LeerA> . <LeerB>) | | |<--------X--X-------->|->| Aceptado(N,<LeerB>. <EscribirB,LeerA>) | | | | | | | | | | | | | | | | !! Conflicto detectado, líder elige | | | | | | | | orden conmutativo: | | | | | | | | V = <LeerA, EscribirB, LeerB> | | | | | | | | | | X----->|->|->| | | Fase2Inicio(N+1,V) | | |<-----X- X- X-------->|->| Aceptado(N+1,V) | | | | | | | | Estable = <LeerA, LeerB>. | | | | | | | | <LeerA, EscribirB, LeerB> | | | | | | | | | | | | | | | | !! Propuestas más conflictivas X-----------?|-----?|-?|-?| | | Proponer(EscribirA) | X--------?|-----?|-?|-?| | | Proponer (Leer A) | | | | | | | | | | X------X-------------->|->| Aceptado(N+1,<EscribirA> . <LeerA>) | | |<--------X- X-------->|->| Aceptado(N+1,<LeerA>. <EscribirA>) | | | | | | | | | | | | | | | | !! El líder elige el orden: | | | | | | | | W = <EscribirA, LeerA> | | | | | | | | | | X----->|->|->| | | Fase2Inicio(N+2,W) | | |<-----X- X- X-------->|->| Aceptado(N+2,W) | | | | | | | | Estable = <LeerA, LeerB>. | | | | | | | | <LeerA, EscribirB, LeerB> . | | | | | | | | <EscribirA, LeerA> | | | | | | | |
El flujo de mensajes anterior nos muestra que Generalized Paxos puede aprovechar la semántica de operación para evitar colisiones cuando falla el ordenamiento espontáneo de la red. Esto permite que el protocolo sea en la práctica más rápido que Fast Paxos. Sin embargo, cuando ocurre una colisión, Generalized Paxos necesita dos viajes de ida y vuelta adicionales para recuperarse. Esta situación se ilustra con las operaciones WriteB y ReadB en el esquema anterior.
En el caso general, estos viajes de ida y vuelta son inevitables y se deben al hecho de que se pueden aceptar múltiples comandos durante un recorrido. Esto hace que el protocolo sea más caro que Paxos cuando los conflictos son frecuentes. Esperemos que sean posibles dos posibles mejoras de Generalized Paxos para mejorar el tiempo de recuperación. [24]
Paxos también puede extenderse para soportar fallas arbitrarias de los participantes, incluyendo mentiras, fabricación de mensajes, colusión con otros participantes, no participación selectiva, etc. Este tipo de fallas se denominan fallas bizantinas , en honor a la solución popularizada por Lamport. [26]
Byzantine Paxos [27] introducido por Castro y Liskov agrega un mensaje adicional (Verificar) que actúa para distribuir conocimiento y verificar las acciones de los otros procesadores:
Cliente Proponente Aceptador Aprendiz | | | | | | | X-------->| | | | | | Pedido | X--------->|->|->| | | ¡Aceptar!(N,I,V) | | X<>X<>X | | Verificar(N,I,V) - TRANSMISIÓN | |<---------X--X--X------>|->| Aceptado(N,V) |<---------------------------------X--X Respuesta(V) | | | | | | |
Fast Byzantine Paxos [28] introducido por Martin y Alvisi elimina este retraso adicional, ya que el cliente envía comandos directamente a los Aceptadores.
Tenga en cuenta que el mensaje Aceptado en Fast Byzantine Paxos se envía a todos los Aceptadores y a todos los Estudiantes, mientras que Fast Paxos envía mensajes Aceptados solo a los Estudiantes):
Aprendiz aceptador de clientes | | | | | | X----->|->|->| | | ¡Aceptar!(N,I,V) | X<>X<>X------>|->| Aceptado(N,I,V) - TRANSMISIÓN |<-------------------X--X Respuesta(V) | | | | | |
El escenario de falla es el mismo para ambos protocolos; Cada alumno espera recibir mensajes idénticos F+1 de diferentes aceptantes. Si esto no ocurre, los propios Aceptadores también lo sabrán (ya que intercambiaron mensajes entre sí en la ronda de transmisión), y los Aceptadores correctos retransmitirán el valor acordado:
Aprendiz aceptador de clientes | | | ! | | !! Un aceptador está defectuoso X----->|->|->! | | ¡Aceptar!(N,I,V) | X<>X<>X------>|->| Aceptado(N,I,{V,W}) - TRANSMISIÓN | | | ! | | !! Los alumnos reciben 2 comandos diferentes. | | | ! | | !! Corregir Los aceptantes notan el error y eligen | X<>X<>X------>|->| Aceptado(N,I,V) - TRANSMISIÓN |<-------------------X--X Respuesta(V) | | | ! | |
Con el surgimiento de redes de centros de datos confiables de muy alta velocidad que admiten DMA remoto ( RDMA ), ha habido un interés sustancial en optimizar Paxos para aprovechar la descarga de hardware, en la que la tarjeta de interfaz de red y los enrutadores de red brindan confiabilidad y control de congestión en la capa de red, liberando la CPU host para otras tareas. La biblioteca Derecho C++ Paxos es una implementación de Paxos de código abierto que explora esta opción. [12]
Derecho ofrece tanto un Paxos clásico, con durabilidad de datos en secuencias completas de apagado/reinicio, como un Paxos vertical (multidifusión atómica), para replicación en memoria y sincronización de máquina de estado. Los protocolos de Paxos empleados por Derecho debían adaptarse para maximizar la transmisión de datos asincrónica y eliminar otras fuentes de retraso en la ruta crítica del líder. Esto permite a Derecho mantener la velocidad de datos RDMA bidireccional completa. Por el contrario, aunque los protocolos tradicionales de Paxos se pueden migrar a una red RDMA simplemente asignando las operaciones de envío de mensajes a operaciones RDMA nativas, hacerlo deja retrasos de ida y vuelta en la ruta crítica. En las redes RDMA de alta velocidad, incluso los retrasos pequeños pueden ser lo suficientemente grandes como para impedir la utilización de todo el ancho de banda potencial.
{{cite journal}}
: Citar diario requiere |journal=
( ayuda ){{cite book}}
: Mantenimiento CS1: fecha y año ( enlace )