Algoritmo de consenso: balsa
De modo que el problema de los generales bizantinos se simplifica en términos de problemas de trabajo comunes: suponiendo que no hay rebeldes entre los generales y que la información del mensajero es confiable pero puede ser asesinado, ¿cómo llegan los generales a un acuerdo? decisión unánime?
Este problema simplificado tiene muchas soluciones. El primer algoritmo de consenso probado fue Paxos, propuesto en 1990 por Leslie Lamport, autora del Problema general bizantino. Inicialmente, era conocido por sus trabajos difíciles. Más tarde, este tipo reeditó un documento sencillo que Paxos hizo en 2001, que todavía era bastante difícil de entender.
Debido a que Paxos es difícil de entender e implementar, un profesor de la Universidad de Stanford publicó un nuevo protocolo distribuido Raft en 2014. En comparación con Paxos, la eficiencia operativa de Raft es básicamente la misma, pero es más fácil de entender y usar para el desarrollo de sistemas.
Usemos el ejemplo de un general bizantino para ayudar a comprender a Raft.
La solución de Raft puede entenderse a grandes rasgos como seleccionar primero a un general entre todos los generales, y todas las decisiones serán tomadas por el general. Elección: por ejemplo, hay tres generales A, B y C. Cada general tiene un dispositivo de cuenta atrás de tiempo aleatorio. Tan pronto como termine la cuenta regresiva, el general se considerará candidato general y luego enviará un mensajero para preguntar a otros generales si pueden elegirme como general. Supongamos ahora que la cuenta regresiva del General A ha terminado, envía un mensajero para transmitir la información de la votación al General B y al General C. Si el General B y el General C no se han considerado candidatos (la cuenta regresiva aún no ha terminado), aún no han votado. para Otros, luego votan por el General A. Cuando el mensajero regresa al General A, el General A sabe que ha recibido suficientes votos para convertirse en general. Después de eso, el general decide si atacar y luego envía un mensajero para informar a los otros dos generales. Si no se recibe respuesta después de un período de tiempo (es posible que el mensajero haya sido asesinado), envíe otro mensajero hasta que se reciba una respuesta.
La historia termina aquí. Espero que los amigos no técnicos puedan entender el principio de la balsa. Hablemos de los principios de Raft desde una perspectiva técnica comparada.
Desde la historia de los generales bizantinos hasta los sistemas distribuidos, cada general es equivalente a un nodo de red distribuida. Cada nodo tiene tres estados: seguidor, candidato, líder y los estados se transforman entre sí. Consulte la imagen a continuación para obtener más detalles.
Cada nodo tiene un tiempo de espera de elección, que varía aleatoriamente entre 150 ms y 300 ms. Hay varias situaciones que restablecen el tiempo de espera:
Durante la operación de la balsa salvavidas, hay dos actividades principales:
Supongamos que hay cinco nodos, como se muestra en la Figura 5, los cinco La inicial El estado de los nodos es Seguidor.
Después de que finaliza la cuenta regresiva de un nodo (tiempo de espera), el estado del nodo cambia a Candidato para comenzar la elección y envía la solicitud de elección Voto a varios otros nodos.
Los otros cuatro nodos regresan con éxito y el estado de este nodo cambia de candidato a líder. Después de un corto período de tiempo, se envía un latido a todos los nodos esclavos para mantener el estado de todos los nodos, y el nodo esclavo restablece el tiempo de espera después de recibir el latido del nodo maestro.
Este es el caso más sencillo para seleccionar un líder. Siempre que más de la mitad de los nodos voten a favor, el candidato será elegido líder. En el caso de cinco nodos, tres nodos (incluido el propio nodo candidato) serán suficientes.
Ya hay un líder al principio y todos los nodos se están ejecutando normalmente.
Si el líder falla y cuelga, los otros cuatro seguidores reelegirán al líder.
El proceso de selección de cuatro nodos es similar al proceso de selección de cinco nodos. Cuando se selecciona un nuevo líder, el líder original se restaura y se vuelve a conectar. ¿Qué debo hacer en este momento? En Raft se registra la primera vuelta de las elecciones. El líder que se reincorporó fue elegido en la primera ronda de elecciones ($Término 1), pero ahora es el $Término 2 y todos los líderes originales son degradados conscientemente a seguidores.
Supongamos que hay cuatro nodos al principio, todos los cuales son seguidores.
Dos seguidores expiraron al mismo tiempo, ambos se convirtieron en candidatos y comenzaron la elección, y cada uno envió una solicitud de votación a un seguidor.
Los dos seguidores regresaron sanos y salvos. En este punto, ambos candidatos sólo tienen 2 votos y necesitan 3 votos para ser elegido líder.
Ambos candidatos enviarán solicitudes de voto a los seguidores del otro que no votaron por sí mismos.
Sin embargo, como los seguidores ya habían votado en esta ronda electoral, todos rechazaron su solicitud. Por lo tanto, no se selecciona ningún líder en el $Término 2.
En este momento, el estado de dos nodos es candidato y dos de seguidor, pero sus temporizadores de cuenta regresiva aún están en marcha y el nodo que agote el tiempo primero votará para iniciar una nueva ronda de $Term 3.
Dos seguidores aún no han votado en $Term 3, por lo que vuelven a OK. En este punto, el candidato tiene tres votos y es elegido líder.
Si el latido del corazón del líder es posterior al tiempo de espera del otro candidato, el otro candidato igualmente enviará una solicitud de elección.
Dos seguidores ya votaron y rechazaron la solicitud de voto del candidato.
El líder envía un latido. Una vez que el candidato lo recibe, el estado cambia automáticamente a seguidor, completando la selección del líder.
Lo anterior es una introducción a una de las actividades más importantes en una balsa, y cómo elegir la actividad principal en diferentes situaciones.
La coherencia de Raft en escenarios de aplicación reales se refleja más en la coherencia de los datos entre diferentes nodos. Cuando un cliente envía una solicitud a cualquier nodo, puede recibir una respuesta consistente. Cuando un nodo falla, otros nodos aún pueden funcionar normalmente utilizando los datos existentes. Replicar los registros después de seleccionar el servidor maestro es lograr este objetivo.
Inicialmente ni el líder ni los dos seguidores tienen ningún dato.
El cliente envía una solicitud al líder para almacenar datos "sally", y el líder primero escribe los datos en el registro local. En este momento, los datos aún no han sido enviados (aún no confirmados, se muestran en rojo).
El líder envía solicitudes AppendEntries a ambos seguidores. Si no hay conflicto entre los datos del seguidor, los datos se escribirán temporalmente en el registro local y los datos del seguidor permanecerán sin confirmar.
El seguidor escribe datos localmente y devuelve OK. El líder regresa con éxito después de recibirlo. Tan pronto como se recibe más de la mitad del número de devoluciones exitosas (incluido el líder), el líder cambia el estado de la "salida" de datos a Comprometido. (En este momento, el líder puede regresar con el cliente).
El líder envía una solicitud AppendEntries a los seguidores nuevamente. Después de recibir la solicitud, el seguidor cambia los datos no confirmados en el registro local a confirmados. De esta forma se completa todo el proceso de copia del registro y los datos de los tres nodos son consistentes.
En el caso de la partición de la red, algunos nodos no pueden comunicarse entre sí. Raft también puede garantizar la coherencia de los datos.
Inicialmente, los cinco nodos se encuentran en el mismo estado de red.
La partición de red divide los nodos en dos lados, dos nodos en un lado y tres nodos en el otro lado.
Estos dos nodos ya tienen un Líder aquí, y los datos "bob" del cliente se sincronizan con los seguidores a través del Líder.
Debido a que solo hay dos nodos, menos de tres nodos, el estado de "bob" aún no está confirmado. Entonces aquí, el servidor devolverá un error al cliente.
La otra partición tiene tres nodos, así que vuelva a seleccionar la partición primaria. Los datos del cliente "tom" se envían al nuevo líder y se sincronizan con los otros dos seguidores mediante un proceso similar al del estado de red anterior.
Debido a que esta partición tiene tres nodos, más de la mitad, se han enviado los datos "tom".
El estado de la red se restablece y los cinco nodos vuelven a estar en el mismo estado de red. Pero "Bob" y "Tom" tienen conflictos de datos.
Los líderes de los tres nodos transmiten AppendEntries.
El líder de la partición de los dos nodos se degrada automáticamente a seguidor. Debido a que los datos "bob" de esta partición no se envían, se devuelve un error al cliente. El cliente sabe que la solicitud no tuvo éxito, por lo que el seguidor puede eliminar "bob" cuando recibe la solicitud AppendEntries.
Luego sincronice "tom". A través de este proceso, se completa el registro de replicación en el caso de la partición de red, lo que garantiza la coherencia de los datos.
Raft es un algoritmo que puede lograr una gran coherencia en sistemas distribuidos. Cada nodo del sistema tiene tres estados: seguidor, candidato y líder. Las dos cosas más importantes para implementar el algoritmo Raft son: selección de líder y replicación de registros.
Enlace de referencia:
Sitio web oficial de Raft:/raft/
Originalmente no quería publicar las imágenes una por una, pero no pude. Acceda a este enlace en casa, así que lo acabo de publicar. Se repitió todo el proceso. )