Balsa (algoritmo)

Algorthim de consenso

Balsa

La mascota del algoritmo de consenso de la balsa.
Clase	Algoritmo de consenso

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 por medio de 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 estado a través de un grupo de sistemas informáticos, asegurando que cada nodo en el 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 especificación completa en Go , C ++ , Java y Scala . ^[2]Lleva el nombre de confiable, replicado, redundante y tolerante a fallas. ^[3]

Raft no es un algoritmo tolerante a fallas bizantino : los nodos confían en el líder elegido. ^[1]

Lo esencial

Raft logra el consenso a través de un líder electo. Un servidor en un grupo de balsa 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 regularmente a los seguidores de su existencia mediante el envío de 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]}

Aproximación al problema del consenso en Raft

Raft implementa el consenso mediante un enfoque de líder. El clúster tiene uno y solo un líder electo que es totalmente responsable de administrar la replicación de registros en los otros 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.

Elección de líder

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 que se debe elegir un nuevo líder. Cada término 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 período continúa con las operaciones normales orquestadas por el nuevo líder. Si la elección es un fracaso, comienza un nuevo mandato, con una nueva elección.

Una elección de 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 las elecciones., por lo que asume que ya no hay un 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 un 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 nada, por ejemplo, debido a una votación dividida, entonces comienza un nuevo período y comienza una nueva elección. ^[1]

Raft utiliza un tiempo de espera de elección aleatorio para garantizar que los problemas de voto dividido 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á las elecciones, 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]

Replicación de registros

El líder es responsable de la replicación del registro. Acepta solicitudes de clientes. Cada solicitud de cliente consta de un comando que ejecutarán 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 de AppendEntries. En caso de que los seguidores no estén disponibles, el líder reintenta 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 la mayoría de sus seguidores de que la entrada ha sido replicada, el líder aplica la entrada a su máquina estatal local y la solicitud se considera comprometida . ^{[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 asegura 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 el caso de una falla del líder, los registros pueden dejarse inconsistentes, y algunos registros del líder anterior no se replican por completo en el clúster. El nuevo líder 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, buscará la última entrada donde esté de acuerdo, luego borrará todas las entradas que vienen después de esta entrada crítica en el registro del seguidor y la reemplazará con su propias entradas de registro. Este mecanismo restaurará la coherencia del registro en un clúster sujeto a fallas.

La seguridad

Reglas de seguridad en Raft

Raft garantiza cada una de estas propiedades de seguridad:

• Seguridad electoral: como máximo se puede elegir un líder en un período determinado.
• Solo para agregar líderes: un líder solo puede agregar nuevas entradas a sus registros (no puede sobrescribir ni eliminar entradas).
• Coincidencia de registros: si dos registros contienen una entrada con el mismo índice y término, entonces los registros son idénticos en todas las entradas hasta el índice dado.
• Completitud del líder: si una entrada de registro se confirma en un período determinado, estará presente en los registros de los líderes desde este período.
• Seguridad de la máquina de estado: si un servidor ha aplicado una entrada de registro en particular a su máquina de estado, ningún otro servidor puede aplicar un comando diferente para el mismo registro.

Las primeras cuatro reglas están garantizadas por los detalles del algoritmo descrito en la sección anterior. La seguridad de las máquinas estatales está garantizada por una restricción en el proceso de elección.

Seguridad de la máquina de estado

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 ponerse en contacto con la mayoría del clúster y, dadas las reglas para que los registros se confirmen, significa que cada entrada comprometida estará presente en al menos uno de los servidores que contactan los candidatos.

Raft determina cuál de los dos registros (transportados por dos servidores distintos) está más actualizado al comparar 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 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 votante niega su voto al candidato. Esta implementación asegura la regla de seguridad de la máquina estatal.

El seguidor se bloquea

Si un seguidor falla, AppendEntries y las solicitudes de voto enviadas por otros servidores fallarán. Tales fallas son manejadas por los servidores que intentan indefinidamente llegar al seguidor caído. Si el seguidor se reinicia, se completarán las solicitudes pendientes. Si la solicitud ya se ha tenido en cuenta antes de la falla, el seguidor reiniciado simplemente la ignorará.

Calendario y disponibilidad

El tiempo es fundamental en Raft para elegir y mantener un líder constante a lo largo del tiempo, con el fin de tener una disponibilidad perfecta del clúster. La estabilidad se garantiza respetando el requisito de tiempo del algoritmo:

broadcastTime << choiceTimeout << MTBF

• broadcastTime es el tiempo promedio que tarda un servidor en enviar una solicitud a todos los servidores del clúster y recibir respuestas. Es relativo a la infraestructura utilizada.
• MTBF (tiempo medio entre fallos) es el tiempo medio entre fallos de un servidor. También es relativo a la infraestructura.
• choiceTimeout es el mismo que se describe en la sección Elección de líder. Es algo que el programador debe elegir.

El número típico de estos valores puede ser de 0,5 ms a 20 ms para broadcastTime , lo que implica que el programador establece el choiceTimeout en algún lugar entre 10 ms y 500 ms. Pueden pasar varias semanas o meses entre las fallas de un solo servidor, lo que significa que los valores son suficientes para un clúster estable.

Referencias

1. Ongaro, Diego; Ousterhout, John (2013). "En busca de un algoritmo de consenso comprensible" (PDF) .
2. "Algoritmo de consenso de balsa" . 2014.
3. ¿Por qué el nombre de "Balsa"?
4. Ben B. Johnson. "Balsa: Consenso distribuido comprensible" . El sitio web Secret Lives of Data . Consultado el 4 de agosto de 2021 .

enlaces externos

• Página web oficial
• Lista de implementaciones