Raft es un algoritmo de consenso diseñado como una alternativa a la familia de algoritmos Paxos . Estaba destinado a ser 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 grupo de sistemas informáticos, asegurando que cada nodo del grupo esté de acuerdo con la misma serie de transiciones de estado. Tiene una serie de implementaciones de referencia de código abierto, con implementaciones de especificaciones completas en Go , C++ , Java y Scala . [2] Lleva el nombre de Confiable, 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 electo. [1]
Raft logra el consenso a través de un líder electo. Un servidor en un grupo de balsas 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 para los seguidores. Informa periódicamente a sus 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 reinicia 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 gestionar la replicación de registros en los demás servidores del clúster. Significa que el líder puede decidir la ubicación de las nuevas entradas y el establecimiento del flujo de datos entre él y los otros servidores sin consultar a otros servidores. Un líder lidera hasta que falla o se desconecta, en cuyo caso se elige 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 término en el clúster. Un término 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 fracasa, comienza un nuevo mandato, con una nueva elección.
Un servidor de candidatos inicia una elección de líder . 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 ningún líder en funciones. Comienza la elección aumentando el contador de términos, 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 período, 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, entonces 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 la mayoría de votos, se convierte en el nuevo líder. Si no ocurre ninguna de las dos cosas, por ejemplo debido a una votación dividida, entonces comienza un nuevo mandato y una nueva elección. [1]
Raft utiliza un tiempo de espera electoral aleatorio 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 expirará, 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 solicitudes de 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 que los seguidores no estén disponibles, el líder vuelve a intentar los mensajes AppendEntries indefinidamente, hasta que todos los seguidores finalmente almacenen la entrada del registro.
Una vez que el líder recibe la confirmación de más de la mitad de sus seguidores de que la entrada ha sido replicada, 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 se ha confirmado una entrada de registro, aplica la entrada a su máquina de estado local. Esto garantiza la coherencia de los registros entre todos los servidores del clúster, garantizando que se respete la regla de seguridad de Log Matching.
En el caso de una falla del líder, los registros pueden quedar inconsistentes y algunos registros del líder anterior no se replican completamente en el clúster. El nuevo líder entonces manejará la inconsistencia obligando a los seguidores a duplicar su propio registro. Para hacerlo, para cada uno de sus seguidores, el líder comparará su registro con el registro del seguidor, encontrará la última entrada en la que están de acuerdo, luego eliminará todas las entradas que vienen después de esta entrada crítica en el registro de seguidores y la reemplazará con su propias entradas de registro. Este mecanismo restaurará la coherencia de los registros 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 estatal está garantizada por una restricción en el proceso electoral.
Esta regla está garantizada por una simple restricción: un candidato no puede ganar una elección a menos que su registro contenga todas las entradas comprometidas. Para ser elegido, un candidato debe comunicarse con la mayoría del clúster y, dadas las reglas para los registros que se deben confirmar, significa que cada entrada confirmada estará presente en al menos uno de los servidores con los que los candidatos contactan.
Raft determina cuál de dos registros (transportados por dos servidores distintos) está más actualizado comparando el término de índice de las últimas entradas en 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, el registro que sea más largo estará 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 registro del candidato, el elector niega su voto al candidato. Esta implementación garantiza la regla de seguridad de la máquina de estado.
Si un seguidor falla, AppendEntries y las solicitudes de voto enviadas por otros servidores fallarán. Estos fallos son manejados por los servidores que intentan indefinidamente llegar al seguidor caído. Si el seguidor se reinicia, las solicitudes pendientes se completarán. Si la solicitud ya se tuvo en cuenta antes del error, el seguidor reiniciado simplemente la ignorará.
El tiempo es fundamental en Raft para elegir y mantener un líder estable en el tiempo, con el fin de tener una perfecta disponibilidad del clúster. La estabilidad se garantiza respetando el requisito de temporización del algoritmo:
tiempo de transmisión << tiempo de espera de elección << MTBF
Los números típicos para estos valores pueden ser de 0,5 ms a 20 ms para broadcastTime , lo que implica que el programador establece el elecciónTimeout 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.