Comprender el algoritmo de consenso de Raft: resumen de un artículo académico

Esta publicación resume el algoritmo de consenso de Raft presentado en el artículo En busca de un algoritmo de consenso comprensible de Diego Ongaro y John Ousterhout. Todas las citas extraídas se toman de ese documento.

Balsa:

Raft es un algoritmo de consenso distribuido. Fue diseñado para que se entienda fácilmente. Resuelve el problema de lograr que varios servidores acuerden un estado compartido incluso ante fallas. El estado compartido suele ser una estructura de datos respaldada por un registro replicado. Necesitamos que el sistema esté en pleno funcionamiento mientras la mayoría de los servidores estén activos.

Raft funciona eligiendo un líder en el grupo. El líder es responsable de aceptar las solicitudes de los clientes y administrar la replicación del registro en otros servidores. Los datos fluyen solo en una dirección: del líder a otros servidores.

Raft descompone el consenso en tres subproblemas:

  • Elección de líder: es necesario elegir un nuevo líder en caso de que falle uno existente.
  • Replicación de registros: el líder debe mantener los registros de todos los servidores sincronizados con los suyos a través de la replicación.
  • Seguridad: si uno de los servidores ha confirmado una entrada de registro en un índice en particular, ningún otro servidor puede aplicar una entrada de registro diferente para ese índice.

Lo esencial:

Cada servidor existe en uno de los tres estados: líder, seguidor o candidato.

En funcionamiento normal, hay exactamente un líder y todos los demás servidores son seguidores. Los seguidores son pasivos: no emiten solicitudes por sí mismos, simplemente responden a solicitudes de líderes y candidatos. El líder maneja todas las solicitudes de los clientes (si un cliente contacta a un seguidor, el seguidor lo redirige al líder). El tercer estado, candidato, se utiliza para elegir un nuevo líder.

Raft divide el tiempo en términosde longitud arbitraria, cada una comenzando con una elección. Si un candidato gana las elecciones, sigue siendo el líder durante el resto del período. Si la votación se divide, ese período termina sin un líder.

El término número aumenta monótonamente. Cada servidor almacena el número de término actualque también se intercambia en cada comunicación.

.. si el término actual de un servidor es menor que el del otro, entonces actualiza su término actual al valor mayor. Si un candidato o líder descubre que su mandato está desactualizado, inmediatamente vuelve al estado de seguidor. Si un servidor recibe una solicitud con un número de término obsoleto, rechaza la solicitud.

Raft hace uso de dos llamadas de procedimiento remoto (RPC) para llevar a cabo su operación básica.

  • Los candidatos utilizan RequestVotes durante las elecciones
  • Los líderes utilizan AppendEntries para replicar entradas de registro y también como un latido (una señal para verificar si un servidor está activo o no, no contiene ninguna entrada de registro)

Elección de líder

El líder envía periódicamente un latido a sus seguidores para mantener la autoridad. Una elección de líder se desencadena cuando un seguidor se agota después de esperar un latido del líder. Este seguidor pasa al estado candidato e incrementa su número de término . Después de votar por sí mismo, emite RequestVotes RPC en paralelo con otros en el clúster. Son posibles tres resultados:

  1. El candidato recibe votos de la mayoría de los servidores y se convierte en líder. Luego envía un mensaje de latido a otros en el clúster para establecer la autoridad.
  2. Si otros candidatos reciben AppendEntries RPC, verifican lanúmero de término. Si el número de términos es mayor que el suyo, aceptan al servidor como líder y regresan al estado de seguidor. Si el número de términos es menor, rechazan el RPC y siguen siendo candidatos.
  3. El candidato no pierde ni gana. Si más de un servidor se convierte en candidato al mismo tiempo, el voto puede dividirse sin una mayoría clara. En este caso, una nueva elección comienza después de que uno de los candidatos expira.
Raft utiliza tiempos de espera de elección aleatorios para garantizar que los votos divididos sean raros y que se resuelvan rápidamente. Para evitar votos divididos en primer lugar, los tiempos de espera de las elecciones se eligen al azar de un intervalo fijo (por ejemplo, 150–300 ms). Esto distribuye los servidores de modo que, en la mayoría de los casos, solo se agota el tiempo de espera de un servidor; gana las elecciones y envía latidos antes de que se agote el tiempo de espera de cualquier otro servidor. El mismo mecanismo se utiliza para gestionar los votos divididos. Cada candidato reinicia su tiempo de espera de elección aleatoria al comienzo de una elección, y espera que transcurra ese tiempo de espera antes de comenzar la siguiente elección; esto reduce la probabilidad de otra votación dividida en la nueva elección.

Replicación de registros:

Se supone que las solicitudes del cliente son de solo escritura por ahora. Cada solicitud consiste en un comando para ser ejecutado idealmente por las máquinas de estado replicadas de todos los servidores. Cuando un líder recibe una solicitud de un cliente, la agrega a su propio registro como una nueva entrada. Cada entrada en un registro:

  • Contiene el comando especificado por el cliente
  • Tiene un índice para identificar la posición de la entrada en el registro (el índice comienza desde 1)
  • Tiene un número de término para identificar lógicamente cuándo se escribió la entrada.

Necesita replicar la entrada a todos los nodos seguidores para mantener la coherencia de los registros. El líder emite AppendEntries RPC a todos los demás servidores en paralelo. El líder vuelve a intentarlo hasta que todos los seguidores replican de forma segura la nueva entrada.

Cuando la entrada es replicada en la mayoría de los servidores por el líder que la creó, se considera comprometida. Todas las entradas anteriores, incluidas las creadas por líderes anteriores, también se consideran comprometidas. El líder ejecuta la entrada una vez que está comprometida y devuelve el resultado al cliente.

El líder mantiene el índice más alto que sabe que está comprometido en su registro y lo envía con las RPC de AppendEntries a sus seguidores. Una vez que los seguidores descubren que la entrada se ha comprometido, aplica la entrada a su máquina de estado en orden.

Raft mantiene las siguientes propiedades, que juntas constituyen la propiedad de coincidencia de registros • Si dos entradas en registros diferentes tienen el mismo índice y término, entonces almacenan el mismo comando. • Si dos entradas en registros diferentes tienen el mismo índice y término, entonces el los registros son idénticos en todas las entradas anteriores.

Al enviar un RPC de AppendEntries, el líder incluye el número de término y el índice de la entrada que precede inmediatamente a la nueva entrada. Si el seguidor no puede encontrar una coincidencia para esta entrada en su propio registro, rechaza la solicitud de agregar la nueva entrada.

Esta verificación de coherencia permite al líder concluir que siempre que AppendEntries regresa exitosamente de un seguidor, tienen registros idénticos hasta el índice incluido en el RPC.

Pero los registros de líderes y seguidores pueden volverse inconsistentes ante las fallas de líderes.

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

El líder intenta encontrar el último índice donde su registro coincide con el del seguidor, elimina las entradas adicionales, si las hay, y agrega las nuevas.

El líder mantiene un nextIndex para cada seguidor, que es el índice de la siguiente entrada de registro que el líder enviará a ese seguidor. Cuando un líder llega al poder por primera vez, inicializa todos los valores de nextIndex en el índice justo después del último en su registro.

Siempre que AppendRPC regresa con una falla para un seguidor, el líder disminuye el nextIndexy emite otra RPC AppendEntries. Eventualmente, nextIndexalcanzará un valor donde los registros converjan. AppendEntries tendrá éxito cuando esto suceda y puede eliminar entradas extrañas (si las hay) y agregar nuevas del registro de líderes (si las hay). Por lo tanto, un AppendEntries exitoso de un seguidor garantiza que el registro del líder es consistente con él.

Con este mecanismo, un líder no necesita tomar ninguna acción especial para restaurar la consistencia de los registros cuando se trata de poder. Simplemente comienza la operación normal y los registros convergen automáticamente en respuesta a fallas en la verificación de coherencia de las entradas adjuntas. Un líder nunca sobrescribe ni elimina entradas en su propio registro.

La seguridad:

Raft se asegura de que el líder de un período haya comprometido entradas de todos los términos anteriores en su registro. Esto es necesario para garantizar que todos los registros sean coherentes y que las máquinas de estado ejecuten el mismo conjunto de comandos.

Durante una elección de líder, RequestVote RPC incluye información sobre el registro del candidato. Si el votante encuentra que su registro está más actualizado que el candidato, no vota por él.

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

Membresía del clúster:

Para que el mecanismo de cambio de configuración sea seguro, no debe haber ningún punto durante la transición en el que sea posible que dos líderes sean elegidos para el mismo período. Desafortunadamente, cualquier enfoque en el que los servidores cambien directamente de la configuración anterior a la nueva configuración no es seguro.

Raft utiliza un enfoque de dos fases para modificar la membresía del clúster. Primero, cambia a una configuración intermedia llamada consenso conjunto. Luego, una vez que se confirma, cambia a la nueva configuración.

El consenso conjunto permite a los servidores individuales realizar la transición entre configuraciones en diferentes momentos sin comprometer la seguridad. Además, el consenso conjunto permite que el clúster continúe atendiendo las solicitudes de los clientes durante todo el cambio de configuración.

El consenso conjunto combina las configuraciones nuevas y antiguas de la siguiente manera:

  • Las entradas de registro se replican en todos los servidores en ambas configuraciones
  • Cualquier servidor antiguo o nuevo puede convertirse en líder
  • El acuerdo requiere mayorías separadas de las configuraciones nuevas y antiguas

Cuando un líder recibe un mensaje de cambio de configuración, almacena y replica la entrada para unirse al consenso C ew>. Un servidor siempre usa la última configuración en su registro para tomar decisiones incluso si no está comprometido. Cuando se compromete el consenso conjunto, solo los servidores con C < antiguo, nuevo> en sus registros pueden convertirse en líderes.

Ahora es seguro para el líder crear una entrada de registro que describa C y replicarla en el clúster. Nuevamente, esta configuración entrará en vigencia en cada servidor tan pronto como se vea. Cuando la nueva configuración se ha confirmado bajo las reglas de C, la configuración anterior es irrelevante y los servidores que no están en la nueva configuración se pueden apagar.

Puede encontrar una visualización fantástica de cómo funciona Raft aquí.

Puede encontrar más material como charlas, presentaciones, artículos relacionados e implementaciones de código abierto aquí.

Solo he profundizado en los detalles del algoritmo básico que compone Raft y las garantías de seguridad que proporciona. El artículo contiene muchos más detalles y es muy accesible, ya que el objetivo principal de los autores fue la comprensión. Definitivamente te recomiendo que lo leas, incluso si nunca antes has leído ningún otro artículo.

Si te gustó este artículo, presiona el botón de aplaudir a continuación para que más personas lo vean. Gracias.

PD: si llegaste hasta aquí y te gustaría recibir un correo cada vez que publique una de estas publicaciones, regístrate aquí.