Algoritmo de consenso de balsa

Este artículo lo ayudará a brindar una breve historia sobre Raft, qué es el consenso, qué es el protocolo RAFT, cuáles son las ventajas, cómo es mejor que sus alternativas, cuáles son algunas limitaciones del protocolo RAFT.

Introducción

El protocolo Raft fue desarrollado por Diego Ongaro y John Ousterhout (Universidad de Stanford), lo que le valió a Diego su doctorado en 2014 (el enlace para el artículo se encuentra en la sección de Referencias al final del artículo). Raft fue diseñado para una mejor comprensión de cómo se puede lograr el Consenso (explicaremos qué es el consenso, en un momento) considerando que su predecesor, el Algoritmo Paxos, desarrollado por Lesli Lamport es muy difícil de entender e implementar. De ahí el título del artículo de Diego, ‘En busca de un algoritmo de consenso comprensible’. Antes de Raft, Paxos era considerado el santo grial para lograr el consenso.
Comencemos.

Consenso

Entonces, para entender Raft, primero veremos el problema que el protocolo Raft intenta resolver y que es lograr el Consenso. Consenso significa que múltiples servidores acuerdan sobre la misma información, algo imperativo para diseñar sistemas distribuidos tolerantes a fallas. Vamos a describirlo con la ayuda de un par de imágenes.
Entonces, primero definamos el proceso utilizado cuando un cliente interactúa con un servidor para aclarar el proceso.
Proceso : el cliente envía un mensaje al servidor y el servidor responde con una respuesta.

Un protocolo de consenso que tolera fallas debe tener las siguientes características:

Validez : si un proceso decide (leer/escribir) un valor, entonces debe haber sido propuesto por algún otro proceso correcto
Acuerdo : Todo proceso correcto debe estar de acuerdo en el mismo valor
Terminación : todo proceso correcto debe terminar después de un número finito de pasos.
Integridad : si todos los procesos correctos deciden sobre el mismo valor, entonces cualquier proceso tiene dicho valor.

Ahora, puede haber dos tipos de sistemas asumiendo solo un cliente (en aras de la comprensión):

Sistema de servidor único : el cliente interactúa con un sistema que tiene un solo servidor sin respaldo. No hay problema en lograr el consenso en tal sistema.

visual de balsa de un solo servidor

Sistema de múltiples servidores : el cliente interactúa con un sistema que tiene múltiples servidores. Dichos sistemas pueden ser de dos tipos:
- Simétrico: cualquiera de los múltiples servidores puede responder al cliente y se supone que todos los demás servidores se sincronizan con el servidor que respondió a la solicitud del cliente, y
- Asimétrico: solo el servidor líder elegido puede responder al cliente. Todos los demás servidores luego se sincronizan con el servidor líder.

Un sistema de este tipo en el que todos los servidores replican (o mantienen) datos similares (estado compartido) a lo largo del tiempo puede denominarse, por ahora, máquina de estado replicada.

Ahora definiremos algunos términos usados para referirnos a servidores individuales en un sistema distribuido.

Líder : solo el servidor elegido como líder puede interactuar con el cliente. Todos los demás servidores se sincronizan con el líder. En cualquier momento, puede haber como máximo un líder (posiblemente 0, que explicaremos más adelante)
Seguidor : los servidores seguidores sincronizan su copia de datos con la del líder después de cada intervalo de tiempo regular. Cuando el servidor líder deja de funcionar (por cualquier motivo), uno de los seguidores puede disputar una elección y convertirse en líder.
Candidato : al momento de disputar una elección para elegir el servidor líder, los servidores pueden pedir votos a otros servidores. De ahí que sean llamados candidatos cuando hayan solicitado votos. Inicialmente, todos los servidores están en estado Candidate.

Entonces, el sistema anterior ahora se puede etiquetar como en el siguiente complemento.

múltiples servidores etiquetados balsa visual

Teorema CAP El teorema CAP es un concepto que un sistema de base de datos distribuida solo puede tener 2 de los 3:

Coherencia : los datos son los mismos en todos los Nodes del servidor (líder o seguidor), lo que implica que el sistema tiene capacidades de sincronización casi instantáneas.
Disponibilidad : cada solicitud obtiene una respuesta (éxito/fracaso). Requiere que el sistema esté operativo el 100% del tiempo para atender las requests, y
Tolerancia de partición : el sistema continúa respondiendo, incluso después de que fallan algunos de los Nodes del servidor. Esto implica que el sistema mantiene todas las funciones de requests/respuestas de alguna manera.

¿Qué es el protocolo Raft?

Raft es un algoritmo de consenso que está diseñado para ser fácil de entender. Es equivalente a Paxos en tolerancia a fallos y rendimiento. La diferencia es que se descompone en subproblemas relativamente independientes y aborda claramente todas las piezas principales necesarias para los sistemas prácticos. Esperamos que Raft ponga el consenso a disposición de una audiencia más amplia, y que esta audiencia más amplia pueda desarrollar una variedad de sistemas basados en el consenso de mayor calidad que los que están disponibles en la actualidad.

Algoritmo de consenso de balsa explicado

Para empezar, Raft establece que cada Node en una máquina de estado replicada (clúster de servidores) puede permanecer en cualquiera de los tres estados, a saber, líder, candidato, seguidor. La imagen a continuación proporcionará la ayuda visual necesaria.

En condiciones normales, un Node puede permanecer en cualquiera de los tres estados anteriores. Solo un líder puede interactuar con el cliente; cualquier solicitud al Node seguidor se redirige al Node líder. Un candidato puede pedir votos para convertirse en líder. Un seguidor solo responde a los candidatos o al líder.

Para mantener estos estados de servidor, el algoritmo Raft divide el tiempo en pequeños términos de longitud arbitraria. Cada término se identifica por un número monótonamente creciente, llamado número de término .
Número
de término Cada Node mantiene este número de término y se transmite durante las comunicaciones entre Nodes. Cada término comienza con una elección para determinar el nuevo líder. Los candidatos solicitan votos de otros Nodes del servidor (seguidores) para obtener la mayoría. Si se reúne la mayoría, el candidato se convierte en el líder del período actual. Si no se establece la mayoría, la situación se denomina voto dividido y el período termina sin líder. Por lo tanto, un término puede tener como máximo un líder.
Propósito de mantener el número de término
Las siguientes tareas se ejecutan observando el número de término de cada Node:

Los servidores actualizan su número de término si su número de término es menor que los números de término de otros servidores en el clúster. Esto significa que cuando comienza un nuevo período, los números del período se cuentan con el líder o el candidato y se actualizan para que coincidan con el último (del líder)
Candidato o Líder desciende al estado Seguidor si su número de término está desactualizado (menos que otros). Si en algún momento, cualquier otro servidor tiene un número de término más alto, puede convertirse en líder de inmediato.
Como decíamos anteriormente que también se comunica el número de plazo de los servidores, si se consigue una petición con un número de plazo caducado, dicha petición es rechazada. Básicamente, esto significa que un Node de servidor no aceptará requests del servidor con un número de término más bajo

El algoritmo Raft utiliza dos tipos de llamadas de procedimiento remoto (RPC) para llevar a cabo las funciones:

RequestVotes RPC es enviado por los Nodes Candidate para recopilar votos durante una elección
El Node líder utiliza AppendEntries para replicar las entradas de registro y también como un mecanismo de latido para verificar si un servidor aún está activo. Si se responde al latido, el servidor está activo; de lo contrario, el servidor está inactivo. Tenga en cuenta que los latidos del corazón no contienen ninguna entrada de registro.

Ahora, echemos un vistazo al proceso de elección de líder.

Elección de líder

Para mantener la autoridad como Líder del clúster, el Node Líder envía latidos para expresar dominio a otros Nodes Seguidores. Una elección de líder tiene lugar cuando un Node seguidor se agota mientras espera un latido del Node líder. En este momento, el Node agotado cambia su estado a estado Candidato, vota por sí mismo y emite RequestVotes RPC para establecer la mayoría e intentar convertirse en el líder. La elección puede ir de las siguientes tres maneras:

El Node Candidato se convierte en Líder al recibir la mayoría de los votos de los Nodes del clúster. En este momento, actualiza su estado a Líder y comienza a enviar latidos para notificar a otros servidores sobre el nuevo Líder.
El Node Candidato no recibe la mayoría de los votos en la elección y, por lo tanto, el período finaliza sin Líder. El Node Candidate vuelve al estado Seguidor.
Si el número de término del Node Candidate que solicita los votos es menor que el de otros Nodes Candidate en el clúster, se rechaza el RPC AppendEntries y los demás Nodes conservan su estado Candidate. Si el número de términos es mayor, el Node Candidato se elige como el nuevo Líder.

elección de líder de balsa

El siguiente extracto del documento de Raft (vinculado en las referencias a continuación) explica un aspecto importante de los tiempos de espera del servidor.

Raft utiliza tiempos de espera de elecciones aleatorios para garantizar que los votos divididos sean raros y que se resuelvan rápidamente. En primer lugar, para evitar votos divididos, los tiempos de espera de las elecciones se eligen aleatoriamente a partir de un intervalo fijo (p. ej., 150–300 ms). Esto distribuye los servidores para que, en la mayoría de los casos, solo se agote el tiempo de espera de un único servidor; gana la elección y envía latidos antes de que se agote el tiempo de espera de cualquier otro servidor. El mismo mecanismo se utiliza para manejar votos divididos. Cada candidato reinicia su tiempo de espera de elección aleatorio al comienzo de una elección y espera a que transcurra ese tiempo de espera antes de comenzar la siguiente elección; esto reduce la probabilidad de otro voto dividido en la nueva elección.

Replicación de registros

En aras de la simplicidad, al explicar a la audiencia de nivel principiante, restringiremos nuestro alcance al cliente que solo realiza requests de escritura. Cada solicitud realizada por el cliente se almacena en los Registros del Líder. Este registro luego se replica a otros Nodes (Seguidores). Por lo general, una entrada de registro contiene las siguientes tres informaciones:

Comando especificado por el cliente para ejecutar
Índice para identificar la posición de entrada en el registro del Node. El índice está basado en 1 (comienza desde 1).
Número de término para determinar la hora de entrada del comando.

El Node líder activa los RPC de AppendEntries a todos los demás servidores (seguidores) para sincronizar/coincidir sus registros con el líder actual. El líder sigue enviando los RPC hasta que todos los seguidores replican de manera segura la nueva entrada en sus registros.

Hay un concepto de compromiso de entrada en el algoritmo. Cuando la mayoría de los servidores del clúster copian con éxito las nuevas entradas en sus registros, se considera confirmado. En este punto, el líder también confirma la entrada en su registro para mostrar que se ha replicado con éxito. Todas las entradas anteriores en el registro también se consideran comprometidas por razones obvias. Una vez confirmada la entrada, el líder ejecuta la entrada y responde con el resultado al cliente.
Cabe señalar que estas entradas se ejecutan en el orden en que se reciben.

Si dos entradas en registros diferentes (Líder y Seguidores) tienen un índice y término idénticos, se garantiza que almacenarán el mismo comando y los registros son idénticos hasta ese punto (Índice).

Sin embargo, en caso de que el líder falle, los registros pueden volverse inconsistentes. Citando el artículo de Raft:

En Raft, el líder maneja las inconsistencias al obligar a los registros de los seguidores a duplicar los suyos. Esto significa que las entradas en conflicto en los registros de los seguidores se sobrescribirán con las entradas del registro del líder.

El Node líder buscará el último número de índice coincidente en el líder y el seguidor, luego sobrescribirá cualquier entrada adicional más allá de ese punto (número de índice) con las nuevas entradas proporcionadas por el líder. Esto ayuda a hacer coincidir el registro del seguidor con el líder. AppendEntries RPC enviará iterativamente los RPC con números de índice reducidos para que se encuentre una coincidencia. Cuando se encuentra la coincidencia, el RPC tiene éxito.

La seguridad

Para mantener la coherencia y el mismo conjunto de Nodes de servidor, el algoritmo de consenso de Raft garantiza que el líder tendrá todas las entradas de los términos anteriores comprometidos en su registro.

Durante una elección de líder, RequestVote RPC también contiene información sobre el registro del candidato (como el número de mandato) para determinar cuál es el último. Si el candidato que solicita el voto tiene datos menos actualizados que el Seguidor al que solicita el voto, el Seguidor simplemente no vota por dicho candidato. El siguiente extracto del artículo original de Raft lo aclara de manera similar y profunda.

Raft determina cuál de los dos registros está más actualizado al comparar el índice y el término de las últimas entradas en los registros. Si los registros tienen últimas entradas con diferentes términos, entonces el registro con el último término está más actualizado. Si los registros terminan con el mismo término, el registro que sea más largo estará más actualizado.

Reglas para la seguridad en el protocolo
Raft El protocolo Raft garantiza la siguiente seguridad contra el mal funcionamiento del consenso en virtud de su diseño:

Seguridad de elección de líder : como máximo un líder por mandato)
Seguridad de coincidencia de registros (si varios registros tienen una entrada con el mismo índice y término, se garantiza que esos registros serán idénticos en todas las entradas hasta el índice dado.
Completitud del líder : las entradas de registro comprometidas en un período determinado siempre aparecerán en los registros de los líderes que siguen a dicho período)
Seguridad de la máquina de estado : si un servidor ha aplicado una entrada de registro particular a su máquina de estado, ningún otro servidor en el clúster de servidores puede aplicar un comando diferente para el mismo registro.
El líder es solo para agregar: un Node líder (servidor) solo puede agregar (no se permiten otras operaciones como sobrescribir, eliminar, actualizar) nuevos comandos a su registro
Bloqueo del Node seguidor : cuando el Node seguidor falla, se ignoran todas las requests enviadas al Node bloqueado. Además, el Node bloqueado no puede participar en la elección del líder por razones obvias. Cuando el Node se reinicia, sincroniza su registro con el Node líder

Membresía del clúster y consenso conjunto

Cuando cambia el estado de los Nodes en el clúster (cambia la configuración del clúster), el sistema se vuelve susceptible a fallas que pueden romper el sistema. Entonces, para evitar esto, Raft usa lo que se conoce como un enfoque de dos fases para cambiar la membresía del clúster. Entonces, en este enfoque, el clúster primero cambia a un estado intermedio (conocido como consenso conjunto ) antes de lograr la nueva configuración de membresía del clúster. El consenso conjunto hace que el sistema esté disponible para responder a las requests de los clientes incluso cuando se está produciendo la transición entre configuraciones. De esta manera, aumentar la disponibilidad del sistema distribuido, que es un objetivo principal.

Cuáles son sus ventajas/Características

El protocolo Raft está diseñado para ser fácilmente comprensible teniendo en cuenta que la forma más popular de lograr un consenso sobre los sistemas distribuidos fue el algoritmo Paxos, que fue muy difícil de entender e implementar. Cualquier persona con conocimientos básicos y sentido común puede comprender partes importantes del protocolo y el trabajo de investigación publicado por Diego Ongaro y John Ousterhout.
Es comparativamente más fácil de implementar que otras alternativas, principalmente Paxos, debido a un segmento de casos de uso más específico, suposiciones sobre el sistema distribuido. Muchas implementaciones de código abierto de Raft están disponibles en Internet. Algunos están en Go , C++ , Java
El protocolo Raft se ha descompuesto en subproblemas más pequeños que se pueden abordar de forma relativamente independiente para una mejor comprensión, implementación, depuración y optimización del rendimiento para un caso de uso más específico.
El sistema distribuido que sigue el protocolo de consenso de Raft permanecerá operativo incluso cuando falle una minoría de los servidores. Por ejemplo, si tenemos un clúster de 5 Nodes de servidor, si fallan 2 Nodes, el sistema aún puede funcionar.
El mecanismo de elección de líder empleado en Raft está diseñado de tal manera que un Node siempre obtendrá la mayoría de los votos en un máximo de 2 mandatos.
Raft emplea RPC (llamadas a procedimientos remotos) para solicitar votos y sincronizar el clúster (usando AppendEntries). Por lo tanto, la carga de las llamadas no recae en el Node líder del clúster.
Raft se diseñó recientemente, por lo que emplea conceptos modernos que aún no se entendían en el momento de la formulación de Paxos y protocolos similares.
Cualquier Node del clúster puede convertirse en líder. Por lo tanto, tiene un cierto grado de equidad.
Muchas implementaciones de código abierto diferentes para diferentes casos de uso ya están disponibles en GitHub y lugares relacionados
¡Compañías como MongoDB, HashiCorp, etc. lo están usando!

Alternativas de balsa

Paxos – Variantes: – multi-paxos, paxos baratos, paxos rápidos, paxos generalizados
Algoritmo práctico de tolerancia a fallas bizantinas (PBFT)
Algoritmo de prueba de participación (PoS)
Algoritmo de prueba de participación delegada (DPoS)

Limitaciones

Raft es estrictamente un protocolo líder único. Demasiado tráfico puede ahogar el sistema. Existen algunas variantes del algoritmo de Paxos que abordan este cuello de botella.
Se considera que hay muchas suposiciones que actúan, como la no ocurrencia de fallas bizantinas, lo que reduce la aplicabilidad en la vida real.
Raft es un enfoque más especializado hacia un subconjunto de problemas que surgen al lograr el consenso.
Cheap-paxos (una variante de Paxos) puede funcionar incluso cuando solo hay un Node funcionando en el clúster de servidores. Para generalizar, los servidores replicados K+1 pueden tolerar el apagado/fallo en los servidores K.

Explora Raft más a fondo

Siga la ruta recomendada a continuación para obtener más información sobre Raft:

Referencias

Publicación traducida automáticamente

Artículo escrito por Parikshit Hooda y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA