Algoritmo de balsa
Raft descompone el algoritmo de consenso en varios módulos clave, como elección de líder, replicación de registros y seguridad. Este artículo analizará brevemente el algoritmo Raft basado en el papel balsa.
Raft es un modelo de líder fuerte, y todo está dirigido por el líder. Por ejemplo, los registros solo se pueden replicar desde el líder a otros servidores. Entonces la elección de líderes es una parte muy importante.
En primer lugar, se introducen los tres estados de servicio del algoritmo raft:
Solo puede haber un líder en un clúster a la vez.
Raft utiliza el mecanismo de latido para implementar la elección de líder. Cuando se inicia el servicio, está en el rol de seguidor. Tenga en cuenta que el tiempo de espera para cada latido entregado al líder es aleatorio (150-300 ms).
Como se muestra en la figura anterior, hay tres puntos A, B y C en el clúster, y los tiempos de espera son 150 ms, 200 ms y 300 ms respectivamente. Los números de los términos iniciales son todos 0 y todos son roles de seguidor. Los tiempos de espera de latidos del nodo A y del líder son los más cortos, por lo que primero cambian del estado de seguidor al estado de candidato y aumentan el número de términos. Primero, votan por sí mismos y envían información de votación a otros nodos del clúster. Cuando los nodos B y C reciben la solicitud de votación de A, aceptan la solicitud de votación de A sin votar por otros nodos en esta etapa, con un período de 1. En este momento, el nodo A aceptó los votos de más de la mitad de los nodos del grupo y se convirtió en líder con un mandato de 1.
La apelación es el proceso electoral más sencillo. Hay muchos conceptos que es necesario explicar, como por ejemplo, ¿por qué las horas extras son diferentes? ¿Qué es un número de semestre? ¿Cuáles son las reglas para la comparación de votos?
1. Número de mandato
Cada líder tiene su propio número de mandato durante las elecciones, que es un número que aumenta monótonamente en todo el mundo. Cada nodo almacena el número de término del líder actual. Cuando se encuentre en la etapa de candidato, el número de término actual se incrementará en 1 cuando se inicie la votación.
Además, cuando un nodo recibe una solicitud para un término superior al suyo, actualizará su número de término a un número de término superior. Si el personaje actual es un líder, cambiará del rol de líder al rol de seguidor. Al recibir una solicitud con una cantidad menor de elementos que él mismo, el nodo simplemente rechazará la solicitud.
2. Reglas de comparación de votación
A. Por orden de llegada: un nodo solo puede votar una vez durante un período. Si los nodos A y B solicitan al nodo C que vote, si el nodo C vota por A primero, rechazará la solicitud de voto del nodo B.
b. Integridad del registro: si un nodo acepta un registro de información de votación más pequeño que el suyo, rechazará la solicitud de votación.
C. Media estrategia: cuando un nodo recibe votos de más de la mitad de los nodos del clúster, se convierte en el líder durante el período y envía latidos de líder a otros nodos.
D. Mientras espera una votación, un candidato puede recibir RPC AppendEntries de otro nodo del servidor que afirma ser el líder. Si el número de mandato del líder (incluido en el RPC) no es menor que el número de mandato actual del candidato, el candidato reconocerá el estatus legal del líder y volverá al estatus de seguidor.
3. Tiempo de espera aleatorio
Como se mencionó anteriormente, cada punto tiene un tiempo de espera de latido diferente al del líder. La ventaja de esto es evitar la división de votos y realizar elecciones de líderes rápidamente. Si el tiempo de espera es el mismo para todos los nodos, será fácil dividir los votos. Si cada nodo no obtiene más de la mitad de los votos, se celebrará la siguiente ronda de elecciones y el tiempo electoral será muy largo. Utilizando un mecanismo de tiempo de espera aleatorio, en circunstancias normales, solo un nodo inicia una solicitud de votación dentro de un período de tiempo.
La siguiente figura es un diagrama de flujo de los cambios de roles de servicio en todo el clúster.
Después de elegir al líder, atiende al cliente, agrega las instrucciones recibidas al registro como nuevas entradas de registro y luego inicia AppendEntries RPC en paralelo con otros servidores para que puedan copiar las entradas del registro. Cuando la entrada del registro se ha replicado de forma segura (se han replicado más de la mitad de los nodos), el líder aplica la entrada del registro a su máquina de estado (la máquina de estado ejecuta las instrucciones) y devuelve los resultados de la ejecución al cliente. Si un seguidor falla o es lento, o la red pierde paquetes, el líder seguirá intentando AppendEntries RPC (incluso si ha respondido al cliente) hasta que todos los seguidores finalmente hayan almacenado todos los registros.
La figura anterior muestra el formato del registro. Una entrada de registro contiene tres partes.
El líder copia registros a otros nodos a través de AppendEntries RPC.
AppendEntries RPC:
Implementación del receptor:
La apelación es el proceso de aceptación de los parámetros AppendeEntries RPC. Introducir $term y leaderId es muy simple, pero la función de prevLogIndex y prevLogTerm es verificar la coherencia del registro. Si un seguidor no encuentra una entrada con la misma posición de índice y número de término en su registro, rechazará la nueva entrada del registro. La verificación de coherencia es como un paso inductivo: primero, el estado del registro vacío debe satisfacer las propiedades de coincidencia del registro, y luego la verificación de coherencia garantiza las propiedades de coincidencia del registro cuando se expande el registro. Por lo tanto, cada vez que AppendEntries RPC regresa exitosamente, el líder sabe que el registro del seguidor debe ser idéntico al suyo (desde la primera entrada del registro hasta la última).
Durante el funcionamiento normal, los registros de líder y seguidor son coherentes, por lo que la comprobación de coherencia de AppendEntries RPC nunca falla. Sin embargo, la falla de un líder puede dejar el registro en un estado inconsistente (es posible que el líder anterior no haya replicado completamente todas las entradas en su registro). Las siguientes situaciones:
En el algoritmo Raft, el líder resuelve el problema de inconsistencia obligando a los seguidores a copiar sus registros. Esto significa que las entradas de registro de seguidores que entren en conflicto con el líder serán sobrescritas por las entradas de registro del líder.
El líder mantiene un nextIndex para cada seguidor, que indica el índice de la siguiente entrada de registro que el líder enviará al seguidor. Cuando se selecciona un nuevo líder, el líder inicializa todos los valores de nextIndex en el índice de su última entrada de registro más 1. Si el registro del seguidor es inconsistente con el registro del líder, la verificación de coherencia en AppendEntries RPC fallará la próxima vez. Después de ser rechazado por un seguidor, el líder disminuirá el valor de nextIndex y volverá a intentar el RPC AppendEntries. Con el tiempo, nextIndex hará que los registros del líder y del seguidor coincidan en algún momento. En este punto, AppendEntries RPC tendrá éxito, eliminará todas las entradas de registro en el seguidor que entren en conflicto con el líder y luego agregará las entradas de registro en el líder (si las hay). Una vez que AppendEntries RPC tenga éxito, el registro del seguidor será coherente con el registro del líder y permanecerá coherente durante el resto del semestre.
Esta máquina presenta brevemente la elección del líder de la balsa y la replicación de registros. Por supuesto, la balsa tiene otras características que no se tratan en este artículo. Se recomienda leer el artículo de raft para tener una comprensión completa de raft.
Mi artículo anterior sobre el protocolo zab analizó el protocolo ZAB del cuidador del zoológico. Aquí compararé las similitudes y diferencias entre los dos.
Último/blob/master/raft-zh_cn.md.