Raft es un algoritmo de consenso diseñado como una alternativa a la familia de algoritmos Paxos . Se suponía que era más comprensible que Paxos mediante la separación de la lógica, pero también se ha demostrado formalmente que es seguro y ofrece algunas características adicionales. [1] Raft ofrece una forma genérica de distribuir una máquina de estados en un clúster de sistemas informáticos, lo que garantiza que cada nodo del clúster esté de acuerdo con la misma serie de transiciones de estados. Tiene varias implementaciones de referencia de código abierto, con implementaciones de especificación completa en Go , C++ , Java y Scala . [2] Su nombre se debe a las palabras Reliable, Replicated, Redundant, And Fault-Tolerant (fiable, replicado, redundante y tolerante a fallos). [3]
Raft no es un algoritmo tolerante a fallas bizantinas (BFT); los nodos confían en el líder elegido. [1]
Raft logra el consenso a través de un líder elegido. Un servidor en un clúster de raft es un líder o un seguidor , y puede ser un candidato en el caso preciso de una elección (líder no disponible). El líder es responsable de la replicación de registros a los seguidores. Informa regularmente a los seguidores de su existencia enviando un mensaje de latido. Cada seguidor tiene un tiempo de espera (normalmente entre 150 y 300 ms) en el que espera el latido del líder. El tiempo de espera se restablece al recibir el latido. Si no se recibe ningún latido, el seguidor cambia su estado a candidato y comienza una elección de líder. [1] [4]
Raft implementa el consenso mediante un enfoque de líder. El clúster tiene un único líder elegido que es totalmente responsable de administrar la replicación de registros en los demás servidores del clúster. Esto significa que el líder puede decidir sobre la ubicación de las nuevas entradas y el establecimiento del flujo de datos entre él y los demás servidores sin consultar a otros servidores. Un líder lidera hasta que falla o se desconecta, en cuyo caso los servidores supervivientes eligen un nuevo líder.
El problema del consenso se descompone en Raft en dos subproblemas relativamente independientes que se enumeran a continuación.
Cuando el líder existente falla o cuando el algoritmo se inicializa, es necesario elegir un nuevo líder.
En este caso, comienza un nuevo mandato en el clúster. Un mandato es un período de tiempo arbitrario en el servidor para el cual se debe elegir un nuevo líder. Cada mandato comienza con una elección de líder. Si la elección se completa con éxito (es decir, se elige un solo líder), el mandato continúa con las operaciones normales orquestadas por el nuevo líder. Si la elección falla, comienza un nuevo mandato, con una nueva elección.
La elección de un líder la inicia un servidor candidato . Un servidor se convierte en candidato si no recibe ninguna comunicación del líder durante un período llamado tiempo de espera de la elección , por lo que asume que ya no hay un líder en funciones. Comienza la elección aumentando el contador de mandatos, votando por sí mismo como nuevo líder y enviando un mensaje a todos los demás servidores solicitando su voto. Un servidor votará solo una vez por mandato, por orden de llegada. Si un candidato recibe un mensaje de otro servidor con un número de mandato mayor que el mandato actual del candidato, la elección del candidato es derrotada y el candidato se convierte en seguidor y reconoce al líder como legítimo. Si un candidato recibe una mayoría de votos, se convierte en el nuevo líder. Si no ocurre nada de esto, por ejemplo, debido a una votación dividida, comienza un nuevo mandato y una nueva elección. [1]
Raft utiliza un tiempo de espera aleatorio para las elecciones para garantizar que los problemas de votación dividida se resuelvan rápidamente. Esto debería reducir la posibilidad de una votación dividida porque los servidores no se convertirán en candidatos al mismo tiempo: un solo servidor se quedará sin tiempo, ganará la elección, luego se convertirá en líder y enviará mensajes de latido a otros servidores antes de que cualquiera de los seguidores pueda convertirse en candidato. [1]
El líder es responsable de la replicación del registro. Acepta las solicitudes de los clientes. Cada solicitud de cliente consta de un comando que deben ejecutar las máquinas de estado replicadas en el clúster. Después de agregarse al registro del líder como una nueva entrada, cada una de las solicitudes se reenvía a los seguidores como mensajes AppendEntries. En caso de no disponibilidad de los seguidores, el líder vuelve a intentar enviar mensajes AppendEntries indefinidamente, hasta que la entrada del registro se almacena finalmente en todos los seguidores.
Una vez que el líder recibe confirmación de más de la mitad de sus seguidores de que la entrada ha sido replicada, el líder aplica la entrada a su máquina de estado local y la solicitud se considera confirmada . [1] [4] Este evento también confirma todas las entradas anteriores en el registro del líder. Una vez que un seguidor se entera de que una entrada de registro está confirmada, aplica la entrada a su máquina de estado local. Esto garantiza la coherencia de los registros entre todos los servidores a través del clúster, lo que garantiza que se respete la regla de seguridad de Log Matching.
En caso de una falla del líder, los registros pueden quedar inconsistentes, y algunos registros del líder anterior no se replicarán completamente en todo el clúster. El nuevo líder manejará la inconsistencia al obligar a los seguidores a duplicar su propio registro. Para ello, para cada uno de sus seguidores, el líder comparará su registro con el registro del seguidor, buscará la última entrada en la que coincidan y luego eliminará todas las entradas posteriores a esta entrada crítica en el registro del seguidor y la reemplazará con sus propias entradas de registro. Este mecanismo restaurará la consistencia del registro en un clúster sujeto a fallas.
Raft garantiza cada una de estas propiedades de seguridad:
Las primeras cuatro reglas están garantizadas por los detalles del algoritmo descrito en la sección anterior. La seguridad de la máquina de estados está garantizada por una restricción en el proceso de elección.
Esta regla se garantiza mediante una restricción simple: un candidato no puede ganar una elección a menos que su registro contenga todas las entradas confirmadas. Para ser elegido, un candidato debe contactar a la mayoría del clúster y, dadas las reglas para que se confirmen los registros, esto significa que cada entrada confirmada estará presente en al menos uno de los servidores con los que se contacta el candidato.
Raft determina cuál de los dos registros (que se encuentran en dos servidores distintos) está más actualizado comparando el término de índice de las últimas entradas de los registros. Si los registros tienen una última entrada con términos diferentes, entonces el registro con el término posterior está más actualizado. Si los registros terminan con el mismo término, entonces el registro más extenso está más actualizado.
En Raft, la solicitud de un candidato a un votante incluye información sobre el registro del candidato. Si su propio registro está más actualizado que el del candidato, el votante niega su voto al candidato. Esta implementación garantiza la regla de seguridad de la máquina de estados.
Si un seguidor falla, las AppendEntries y las solicitudes de voto enviadas por otros servidores fallarán. Estos fallos son manejados por los servidores que intentan indefinidamente comunicarse con el seguidor caído. Si el seguidor se reinicia, las solicitudes pendientes se completarán. Si la solicitud ya se había tenido en cuenta antes del fallo, el seguidor reiniciado simplemente la ignorará.
El timing es fundamental en Raft para elegir y mantener un líder estable a lo largo del tiempo, con el fin de tener una disponibilidad perfecta del cluster. La estabilidad se garantiza respetando el requisito de timing del algoritmo:
tiempoDeTransmisión<< TiempoDeEsperaDeElección<< MTBF
Los valores típicos para estos valores pueden ser de 0,5 ms a 20 ms para broadcastTime , lo que implica que el programador establece electionTimeout en algún lugar entre 10 ms y 500 ms. Pueden pasar varias semanas o meses entre fallas de un solo servidor, lo que significa que los valores son suficientes para un clúster estable.