Hispanopedia WikiRaft es un algoritmo de consenso diseñado como alternativa a la familia de algoritmos Paxos . Se concibió para ser más comprensible que Paxos mediante la separación de la lógica, pero también está formalmente probado como 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, asegurando que cada nodo del clúster esté de acuerdo con la misma serie de transiciones de estado. Cuenta con varias implementaciones de referencia de código abierto, con implementaciones de especificación completa en Go , C++ , Java , JavaScript y Scala . [ 2 ] Su nombre proviene de Reliable, Replicated, Redundant, And Fault-Tolerant (Confiable, Replicado, Redundante y Tolerante a Fallos). [ 3 ]
Raft no es tolerante a fallos bizantinos ; los nodos confían en el líder electo y el algoritmo asume que todos los participantes son dignos de confianza.
Lo esencial
Raft logra el consenso mediante un líder electo. Un servidor en un clúster Raft es líder o seguidor , y puede ser candidato en el caso específico de una elección (líder no disponible). El líder es responsable de la replicación de registros a los seguidores. Informa periódicamente a los seguidores de su existencia enviando un mensaje de latido. Cada seguidor tiene un tiempo de espera (normalmente entre 150 y 300 ms) durante el cual 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 e inicia una elección de líder . [ 1 ] [ 4 ]
Enfoque del problema del consenso en Raft
Raft implementa el consenso mediante un líder. El clúster cuenta con un único líder electo, responsable de gestionar la replicación de registros en los demás servidores. Esto significa que el líder puede decidir la ubicación de las nuevas entradas y establecer el flujo de datos entre él y los demás servidores sin necesidad de consultarlos. El líder permanece en el poder hasta que falla o se desconecta, momento en el que los servidores restantes eligen a un nuevo líder.
En Raft, el problema del consenso se descompone en dos subproblemas relativamente independientes que se enumeran a continuación.
Elección del líder
Cuando el líder actual falla o cuando se inicializa el algoritmo, es necesario elegir un nuevo líder.
En este caso, comienza un nuevo período en el clúster. Un período es un lapso de tiempo arbitrario en el servidor durante el cual se debe elegir un nuevo líder. Cada período comienza con la elección de un líder. Si la elección se completa con éxito (es decir, se elige un único líder), el período continúa con las operaciones normales coordinadas por el nuevo líder. Si la elección falla, comienza un nuevo período 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 denominado tiempo de espera electoral , por lo que asume que ya no hay un líder en funciones. Inicia la elección incrementando 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 del candidato actual, su elección es derrotada y el candidato se convierte en seguidor, reconociendo al líder como legítimo. Si un candidato recibe la mayoría de los votos, se convierte en el nuevo líder. Si no ocurre ninguna de las dos cosas, 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 con el fin de garantizar que los problemas de votación dividida se resuelvan rápidamente. Esto debería reducir la probabilidad de una votación dividida, ya que los servidores no se convertirán en candidatos al mismo tiempo: un solo servidor agotará el tiempo de espera, ganará las elecciones, se convertirá en líder y enviará mensajes de latido a los demás 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 consiste en un comando que deben ejecutar las máquinas de estado replicadas en el clúster. Tras añadirse al registro del líder como una nueva entrada, cada solicitud se reenvía a los seguidores como mensajes AppendEntries. En caso de que los seguidores no estén disponibles, el líder reintenta el envío de mensajes AppendEntries indefinidamente, hasta que la entrada del registro sea almacenada por todos los seguidores.
Una vez que el líder recibe la confirmación de la mitad o más de sus seguidores de que la entrada se ha replicado, aplica la entrada a su máquina de estados 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 se ha confirmado, aplica la entrada a su máquina de estados local. Esto garantiza la coherencia de los registros entre todos los servidores del clúster, asegurando que se respete la regla de seguridad de coincidencia de registros.
En caso de que falle el líder, los registros pueden quedar inconsistentes, y algunos registros del líder anterior no se replicarán completamente en el clúster. El nuevo líder gestionará entonces esta inconsistencia obligando a los seguidores a duplicar su propio registro. Para ello, para cada uno de sus seguidores, el líder comparará su registro con el del seguidor, encontrará la última entrada donde coinciden, eliminará todas las entradas posteriores a esta entrada crítica en el registro del seguidor y las reemplazará con sus propias entradas. Este mecanismo restablecerá la consistencia de los registros en un clúster que pueda sufrir fallos.
Seguridad
Normas de seguridad en balsas
Raft garantiza cada una de estas propiedades de seguridad:
- Seguridad electoral: como máximo, se puede elegir a un líder por mandato.
- El líder solo puede añadir entradas: un líder solo puede añadir 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.
- Integridad 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 ese período.
- Seguridad de la máquina de estados: si un servidor ha aplicado una entrada de registro específica a su máquina de estados, ningún otro servidor podrá aplicar un comando diferente para el mismo registro.
Las primeras cuatro reglas están garantizadas por los detalles del algoritmo descritos 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.
Seguridad de la máquina de estados
Esta regla se garantiza mediante una restricción sencilla: 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 la confirmación de registros, esto significa que cada entrada confirmada estará presente en al menos uno de los servidores con los que el candidato contacte.
Raft determina cuál de dos registros (almacenados en dos servidores distintos) está más actualizado comparando el término de índice de las últimas entradas de cada registro. Si los registros tienen una última entrada con términos diferentes, el registro con el término posterior está más actualizado. Si los registros terminan con el mismo término, el registro más largo 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 le niega su voto. Esta implementación garantiza la regla de seguridad de la máquina de estados.
El seguidor falla
Si un servidor seguidor falla, las solicitudes de AppendEntries y de votación enviadas por otros servidores no se procesarán. Estos fallos se gestionan intentando, de forma continua, conectarse con el servidor seguidor averiado. Si el servidor seguidor se reinicia, las solicitudes pendientes se completarán. Si la solicitud ya se había tenido en cuenta antes del fallo, el servidor seguidor reiniciado simplemente la ignorará.
Horarios y disponibilidad
En Raft, la sincronización es fundamental para elegir y mantener un líder estable a lo largo del tiempo, con el fin de lograr una disponibilidad perfecta del clúster. La estabilidad se garantiza respetando el requisito de sincronización del algoritmo.
broadcastTime << electionTimeout << MTBF
- broadcastTime es el tiempo promedio que tarda un servidor en enviar una solicitud a todos los servidores del clúster y recibir las respuestas. Este valor depende de la infraestructura utilizada.
- El MTBF (Tiempo Medio Entre Fallos) es el tiempo promedio entre fallos de un servidor. También es relativo a la infraestructura.
- electionTimeout es lo mismo que se describe en la sección de Elección de Líder. Es algo que el programador debe elegir.
Los valores típicos para broadcastTime oscilan entre 0,5 ms y 20 ms , lo que implica que el programador establece electionTimeout entre 10 ms y 500 ms. Pueden transcurrir varias semanas o meses entre fallos de un solo servidor, lo que significa que estos valores son suficientes para un clúster estable.
Cambios en la composición del clúster
Para abordar los problemas de cambio de membresía de clúster que pueden surgir en Raft, el algoritmo introduce el consenso conjunto, una fase de configuración transitoria. El consenso conjunto funciona de la siguiente manera: [ 5 ]
Dada la configuración del servidor C old , la configuración antigua del servidor, y C new , la nueva configuración: [ 5 ]
- Las entradas de registro se confirman en todos los servidores en C antiguo y C nuevo. [ 5 ]
- Cualquier servidor de C antiguo y C nuevo puede ser líder. [ 5 ]
- El acuerdo para las elecciones y las confirmaciones de entrada de registro requiere mayorías tanto de C antiguo como de C nuevo. [ 5 ]
Una vez que se logra el consenso conjunto (es decir, la nueva entrada de configuración especial de C se replica en los registros de la mayoría de los nuevos servidores C), el sistema realiza la transición completa a la nueva configuración. [ 5 ]
Sin embargo, existen tres problemas que surgen con esta nueva configuración, los cuales Raft aborda: [ 6 ]
- Servidores nuevos sin entradas de registro. Raft introduce una fase previa al cambio de configuración en la que los servidores sin entradas de registro no se consideran parte de la mayoría en las elecciones, pero se les replicarán las entradas. Esto sucede hasta que el servidor se pone al día con todas las entradas. [ 6 ]
- El líder del clúster no está en C nuevo . El líder del clúster dejará de ser líder y volverá al estado de seguidor. Específicamente, continuará replicando las entradas del registro, pero no se contará a sí mismo como mayoría. [ 6 ]
- Interrupciones de servidores en Cold . Si un servidor cree que existe un líder actual, se ignorarán todas las RPC RequestVote (RPC para recopilar votos para una elección de líder). [ 6 ]
Compactación de troncos
Una extensión de Raft es la compactación de registros, donde cada servidor toma instantáneas de sus entradas confirmadas y las guarda en almacenamiento estable , junto con el índice de su última entrada y el término en el registro de la instantánea. El líder ocasionalmente envía sus instantáneas a los servidores que están rezagados en su registro. Cuando el servidor recibe esta instantánea, descartará todo su registro si ha sido reemplazado por la instantánea, o solo las entradas hasta la más reciente en la instantánea. [ 7 ]
Asuntos
Si bien Raft pretende ser una alternativa a Paxos y más comprensible que este, surgen varios problemas.
Cuello de botella del líder
Raft utiliza un modelo de líder único, donde las solicitudes, lecturas y escrituras de los clientes, así como las replicaciones de registros, pasan por un único líder. Esto implica un único punto de fallo y un cuello de botella en el rendimiento. Además, no escala con el aumento de la carga de trabajo del servidor. [ 8 ]
Reconfiguración
El sistema de cambio de membresía de Raft no ha sido verificado formalmente. Esto significa que su implementación es muy arriesgada, ya que puede contener numerosos errores y fallos potenciales. Diego Ongaro, uno de los coautores, intentó crear una prueba de seguridad formal, pero no hay planes para continuar su desarrollo debido a su complejidad. [ 9 ] En 2014, se descubrió un fallo de seguridad relacionado con los cambios de membresía en un único servidor. [ 9 ]
Fallas bizantinas
Raft, al igual que otros algoritmos de consenso, garantiza que nunca puede haber un resultado incorrecto bajo ninguna condición no bizantina. [ 10 ] Esto significa que Raft no es un algoritmo tolerante a fallos bizantinos. Un estudio de 2023 encontró que los sistemas blockchain basados en Raft son vulnerables a ataques bizantinos debido a la falta de autenticación en el lado del cliente. [ 11 ]
Extensiones
La disertación “Consenso: Uniendo teoría y práctica” de uno de los coautores del artículo original describe extensiones al algoritmo original: [ 12 ]
- Pre-votación: cuando un miembro se reincorpora al clúster, dependiendo del momento, puede desencadenar una elección, aunque ya exista un líder. Para evitarlo, la pre-votación primero consulta con los demás miembros. Evitar elecciones innecesarias mejora la disponibilidad del clúster, por lo que esta extensión suele estar presente en implementaciones de producción.
- Transferencia de liderazgo: un líder que se retira de forma ordenada puede transferir explícitamente el liderazgo a otro miembro. Esto puede ser más rápido que esperar a que se complete un tiempo de espera. Además, un líder puede ceder el puesto cuando otro miembro sería más adecuado para el liderazgo, por ejemplo, si ese miembro utiliza un equipo más rápido.
Uso en producción de la balsa
- CockroachDB utiliza Raft en la capa de replicación. [ 13 ]
- Etcd utiliza Raft para gestionar un registro replicado de alta disponibilidad [ 14 ].
- Hazelcast utiliza Raft para proporcionar su subsistema CP, una capa fuertemente consistente para estructuras de datos distribuidas. [ 15 ]
- IBM MQ utiliza Raft para gestionar un registro replicado de alta disponibilidad. [ 16 ]
- MongoDB utiliza una variante de Raft en el conjunto de replicación.
- Neo4j utiliza Raft para garantizar la consistencia y la seguridad. [ 17 ]
- RabbitMQ utiliza Raft para implementar colas FIFO replicadas y duraderas. [ 18 ]
- ScyllaDB utiliza Raft para los metadatos (cambios de esquema y topología) [ 19 ].
- Splunk Enterprise utiliza Raft en un clúster de nodos de búsqueda (SHC) [ 20 ]
- TiDB utiliza Raft con el motor de almacenamiento TiKV. [ 21 ]
- YugabyteDB utiliza Raft en la replicación de DocDB [ 22 ]
- ClickHouse utiliza Raft para la implementación interna de un servicio similar a ZooKeeper [ 23 ].
- Redpanda utiliza el algoritmo de consenso Raft para la replicación de datos [ 24 ].
- Apache Kafka Raft (KRaft) utiliza Raft para la gestión de metadatos. [ 25 ]
- NATS Messaging utiliza el algoritmo de consenso Raft para la gestión de clústeres Jetstream y la replicación de datos [ 26 ].
- Camunda utiliza el algoritmo de consenso Raft para la replicación de datos [ 27 ].
Referencias
- 1 2 3 4 5 Ongaro, Diego; Ousterhout, John (2013). "En busca de un algoritmo de consenso comprensible" (PDF) .
- ↑ "Algoritmo de consenso Raft" . 2014.
- ↑ ¿Por qué el nombre "Raft"?
- 1 2 Ben B. Johnson. "Raft: Consenso distribuido comprensible" . Sitio web The Secret Lives of Data . Consultado el 4 de agosto de 2021 .
- 1 2 3 4 5 6 "En busca de un algoritmo de consenso comprensible (versión extendida)" (PDF) . raft.github.io . Consultado el 1 de octubre de 2025 .
- 1 2 3 4 "En busca de un algoritmo de consenso comprensible (versión extendida)" (PDF) . raft.github.io . Consultado el 1 de octubre de 2025 .
- ↑ "En busca de un algoritmo de consenso comprensible (versión extendida)" (PDF) . raft.github.io . Consultado el 1 de octubre de 2025 .
- ↑ Deyerl, Christian; Distler, Tobias (25 de marzo de 2019). «En busca de una arquitectura de replicación escalable basada en Raft» . Actas del 6.º Taller sobre Principios y Práctica de la Consistencia para Datos Distribuidos . PaPoC '19. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 1-7 . doi : 10.1145/3301419.3323968 . ISBN 978-1-4503-6276-4.
- 1 2 "Error en los cambios de membresía de un solo servidor" . groups.google.com . Consultado el 6 de octubre de 2025 .
- ↑ "En busca de un algoritmo de consenso comprensible (versión extendida)" (PDF) . raft.github.io . Consultado el 1 de octubre de 2025 .
- ↑ "Póster: Ataques bizantinos del lado del cliente al algoritmo Raft en blockchain" (PDF) .
- ↑ "CONSENSO: UNIENTAR LA TEORÍA Y LA PRÁCTICA" (PDF) .
- ↑ "Capa de replicación | Documentación de CockroachDB" . www.cockroachlabs.com . Consultado el 21 de junio de 2022 .
- ↑ "Raft README" . github.com . Consultado el 25 de agosto de 2022 .
- ↑ "Subsistema CP" . docs.hazelcast.com . Consultado el 24/12/2022 .
- ↑ "Alta disponibilidad nativa en la nube con IBM MQ" . community.ibm.com . 25 de marzo de 2021. Consultado el 25 de mayo de 2021 .
- ↑ "Liderazgo, enrutamiento y equilibrio de carga - Manual de operaciones" . Plataforma de datos de grafos Neo4j . Consultado el 30 de noviembre de 2022 .
- ↑ "Colas de quórum" . RabbitMQ . Consultado el 14 de diciembre de 2022 .
- ↑ "El camino de ScyllaDB hacia una consistencia sólida: un nuevo hito" . 4 de mayo de 2023.
- ↑ "Manejar problemas de Raft" . Splunk . 24 de agosto de 2022. Consultado el 24 de agosto de 2022 .
- ↑ "Raft y alta disponibilidad" . PingCAP . 1 de septiembre de 2021. Consultado el 21 de junio de 2022 .
- ↑ "Replicación | Documentación de YugabyteDB" . www.yugabyte.com . Consultado el 19 de agosto de 2022 .
- ↑ "ClickHouse Keeper" . clickhouse.com . Consultado el 26 de abril de 2023 .
- ↑ "Algoritmo de consenso Raft" .
- ↑ "Descripción general de KRaft | Documentación de Confluent" . docs.confluent.io . Consultado el 13 de abril de 2024 .
- ↑ "Agrupación JetStream" .
- ↑ "Protocolo de replicación y consenso de balsa" .
Enlaces externos
- Sitio web oficial
- Algoritmos distribuidos
- Sistemas informáticos tolerantes a fallos