El consenso Raft explicado: elección de líder y replicación del log

Todo clúster de Kubernetes guarda su estado en etcd, y etcd se pone de acuerdo sobre ese estado con Raft. También lo hacen Consul, CockroachDB, TiKV, las quorum queues de RabbitMQ y, desde que Kafka 4.0 eliminó ZooKeeper, los propios controladores de Kafka. Si operas alguno de ellos, Raft explica comportamientos que de otro modo parecen arbitrarios: por qué un clúster de tres nodos deja de aceptar escrituras cuando fallan dos, por qué las escrituras se detienen un segundo durante un cambio de líder y por qué un cuarto nodo encarece el clúster sin hacerlo más seguro.

Este artículo explica Raft con un diagrama de la replicación del log en un clúster de cinco nodos: mandatos, elección de líder, AppendEntries, la regla de commit, los fallos, el dimensionamiento del clúster, las lecturas y los cambios de pertenencia.

El modelo: un log replicado

Raft construye una máquina de estados replicada. Cada servidor mantiene un log de comandos. Si todos los servidores aplican los mismos comandos en el mismo orden, terminan en el mismo estado. El trabajo de Raft es mantener los logs idénticos, incluso cuando los servidores caen y los mensajes se pierden o se retrasan.

Cada servidor está en uno de tres estados: seguidor, candidato o líder. El tiempo se divide en mandatos (terms), numerados 1, 2, 3 y así sucesivamente; cada mandato empieza con una elección y tiene como mucho un líder. Un servidor que ve un mandato mayor que el suyo actualiza su mandato y pasa a seguidor, así que un líder obsoleto se retira en cuanto tiene noticias del más reciente.

Raft solo necesita dos RPC, más una para los snapshots:

El diseño viene del artículo In Search of an Understandable Consensus Algorithm, de Diego Ongaro y John Ousterhout, publicado en USENIX ATC 2014.

Elección de líder

Un seguidor espera heartbeats regulares del líder. Si no llega ninguno dentro de su timeout de elección, supone que el líder ha desaparecido:

1. Incrementa su mandato, se convierte en candidato y se vota a sí mismo.
2. Envía RequestVote a todos los demás servidores, con el índice y el mandato de su última entrada del log.
3. Cada servidor concede como mucho un voto por mandato, y solo a un candidato cuyo log esté al menos tan actualizado como el suyo: gana el último mandato más alto y, a igual mandato, gana el log más largo.
4. El candidato que reúne votos de una mayoría se convierte en líder y empieza a enviar heartbeats.

Si dos candidatos se reparten los votos, nadie gana y el mandato termina sin líder. Raft hace que esto sea raro aleatorizando los timeouts; el artículo sugiere valores como de 150 a 300 ms, de modo que normalmente un servidor agota su timeout primero y gana antes de que empiecen los demás.

Los sistemas en producción eligen los timeouts según su red. etcd usa por defecto un heartbeat de 100 ms y un timeout de elección de 1000 ms, y su documentación dice que el timeout de elección debería ser al menos diez veces el tiempo de ida y vuelta entre miembros. Esas cifras explican por qué un plano de control de Kubernetes puede tardar un segundo o más en volver a aceptar escrituras tras perder a su líder de etcd.

Replicación del log

Una vez elegido, el líder gestiona todas las escrituras:

1. Un cliente envía un comando al líder, por ejemplo SET x=5.
2. El líder lo añade a su propio log como una entrada nueva con el mandato actual, digamos el índice 7 en el mandato 3.
3. El líder envía a cada seguidor un AppendEntries con la entrada nueva, más el índice y el mandato de la entrada inmediatamente anterior (índice 6, mandato 3).
4. Un seguidor solo acepta si su log tiene una entrada en el índice 6 con el mandato 3. Esta comprobación de coherencia garantiza que, si dos logs coinciden en una posición, coinciden en todo lo anterior.
5. Cuando una mayoría de servidores, incluido el líder, guarda la entrada, el líder la marca como confirmada (committed), la aplica a su máquina de estados y responde al cliente.
6. Los seguidores conocen el nuevo índice de commit en el siguiente AppendEntries y también aplican la entrada.

Si un seguidor rechaza una entrada porque su log diverge, el líder retrocede de índice en índice, o más rápido con optimizaciones, hasta que los logs coinciden, y después sobrescribe las entradas en conflicto del seguidor con las suyas. Solo se sobrescriben entradas no confirmadas, lo cual es seguro porque a nadie se le dijo que hubieran tenido éxito.

La regla de commit y su parte sutil

«Confirmada en cuanto la guarda una mayoría» tiene una excepción, y es el detalle más famoso del artículo. Un líder nuevo no debe contar réplicas para confirmar entradas que quedaron de mandatos anteriores. Las confirma de forma indirecta, confirmando encima una entrada de su propio mandato. Sin esta regla, una entrada guardada en una mayoría todavía podría ser sobrescrita por un líder posterior. En la práctica, un líder nuevo añade una entrada vacía no-op al empezar su mandato para confirmar rápido todo lo anterior.

La restricción de elección completa el argumento de seguridad: como un candidato necesita los votos de una mayoría y toda entrada confirmada está en una mayoría, cualquier ganador posible ya tiene todas las entradas confirmadas.

Lo que aguanta un clúster

Un clúster de n servidores necesita una mayoría para elegir líder y confirmar escrituras, así que tolera el fallo de menos de la mitad:

Cuatro servidores toleran un fallo, igual que tres, pero ahora cada escritura espera tres confirmaciones en lugar de dos. Por eso los clústeres tienen tamaños impares. Cinco es la elección habitual cuando quieres sobrevivir a un fallo mientras otro nodo está en mantenimiento planificado.

La latencia sigue la misma aritmética. Cada escritura espera a que el líder llegue a la mayoría más rápida y a que esos servidores persistan la entrada en disco. En un clúster repartido en tres regiones, cada escritura cuesta al menos un viaje de ida y vuelta a la otra región más cercana. Los discos lentos hacen tanto daño como las redes lentas, y por eso la documentación de etcd dedica tanto espacio a la latencia de fsync como a los timeouts.

Fallos en la práctica

• El líder cae. Los seguidores agotan su timeout, uno gana una elección y las escrituras se reanudan. Las peticiones en vuelo pueden haberse confirmado o no, así que los clientes deben reintentar, y los comandos que reintentan deberían ser idempotentes.
• Una partición de red. El lado con mayoría elige un líder y continúa. Un líder antiguo en el lado minoritario no puede confirmar nada; cuando se cura la partición, ve el mandato más alto y se retira.
• Un seguidor lento. Los commits no lo esperan. Si se queda muy atrás, el líder le envía un snapshot en lugar de reproducir todo el log.
• Un servidor perturbador. Un servidor aislado del líder sigue agotando su timeout y subiendo su mandato, lo que puede forzar elecciones innecesarias cuando vuelve. El pre-vote, de la tesis doctoral de Ongaro, permite a un candidato comprobar que podría ganar antes de incrementar su mandato.

Las lecturas no son gratis

Un líder no puede responder lecturas a ciegas desde su propio estado: puede que se haya elegido un líder nuevo al otro lado de una partición, y el antiguo devolvería datos obsoletos. Las lecturas linealizables necesitan o bien una ronda de heartbeats para confirmar el liderazgo antes de responder (el ReadIndex de Raft), o bien un lease de líder basado en el tiempo, que depende de que la deriva de los relojes esté acotada. Los seguidores también pueden servir lecturas, pero solo tras comprobar el índice de commit del líder o aceptando resultados obsoletos. etcd lo hace explícito: etcdctl get es linealizable por defecto, y --consistency=s pide una lectura serializable más rápida y posiblemente obsoleta.

Cambiar la pertenencia

Añadir o quitar servidores cambia lo que es una mayoría, y cambiar de configuración sin cuidado puede crear dos mayorías a la vez. Raft lo resuelve con joint consensus o cambiando un servidor cada vez. Muchas implementaciones también añaden los servidores nuevos como learners sin voto, como hace etcd, para que un nodo nuevo se ponga al día con el log antes de contar para la mayoría.

El diagrama de replicación del log

Cómo leerlo:

• El cliente envía un comando al líder, S1, en el mandato 3. El líder lo escribe en el índice 7.
• Cada tabla es el log de un servidor: índice, mandato y comando. Las filas que coinciden entre tablas son la misma entrada.
• Las aristas AppendEntries van del líder a los cuatro seguidores. S2 y S3 confirman el índice 7.
• S4 va retrasado en el índice 6 y S5 es inalcanzable en el índice 5. Ninguno de los dos bloquea el commit.
• La nota muestra la regla de commit: tres de cinco servidores guardan la entrada 7, así que está confirmada y el cliente recibe su respuesta.

Dibujar diagramas de consenso que enseñen

• Muestra los logs, no solo los servidores. Las garantías de Raft son afirmaciones sobre logs. Un diagrama con cinco cajas y flechas esconde todo lo interesante.
• Escribe el mandato junto a cada entrada. Los mandatos explican las elecciones, los conflictos y la regla de commit.
• Dibuja un clúster con problemas. Un seguidor retrasado o aislado muestra por qué importan las mayorías mejor que un clúster perfecto.
• Usa un diagrama por escenario: una elección, la replicación normal y la reparación de un conflicto tras un failover merecen cada una su propio dibujo.

Para ver cómo encaja la replicación en las arquitecturas de bases de datos en general, consulta el diagrama de replicación de bases de datos. El diagrama de arquitectura de Kubernetes muestra dónde está etcd en un plano de control, y el diagrama de arquitectura de Kafka trata los controladores KRaft. Sistemas como CockroachDB ejecutan un grupo Raft por cada rango de datos, lo que conecta el consenso con las ideas del diagrama de sharding de bases de datos.

Constrúyelo en Archboard

1. Inicia sesión con Google o GitHub y crea un diagrama.
2. Añade un Marco del pack Básico para el clúster y etiquétalo con el mandato actual.
3. Añade dentro cinco nodos Tabla del pack Básico, uno por servidor, con columnas para índice, mandato y comando. Pon el líder en el centro.
4. Añade fuera del marco una Caja del pack Básico para el cliente y conéctala al líder con el comando.
5. Dibuja aristas AppendEntries del líder a cada seguidor, con aristas discontinuas de confirmación de vuelta desde los seguidores que guardaron la entrada. Marca el seguidor inalcanzable con una arista discontinua en un color de aviso.
6. Añade un bloque Markdown del pack Básico con la regla de commit y una Nota junto al líder con el índice de commit.

El ejemplo usa 8 nodos de diagrama, dentro del plan Free.

Preguntas frecuentes

¿Por qué los clústeres Raft tienen un número impar de nodos? Un clúster necesita una mayoría para funcionar. Añadir un cuarto nodo a tres sube la mayoría de dos a tres sin tolerar más fallos, así que los tamaños pares cuestan latencia y dinero sin añadir tolerancia a fallos.

¿Qué pasa con las escrituras durante una elección de líder? Esperan o fallan hasta que se elige un líder nuevo, normalmente en uno o dos timeouts de elección. Los clientes deberían reintentar con peticiones idempotentes, porque una escritura que agotó su timeout puede haberse confirmado.

¿Qué diferencia hay entre Raft y Paxos? Resuelven el mismo problema con garantías parecidas. Raft se diseñó para ser más fácil de entender e implementar: usa un líder fuerte, separa la elección de la replicación y especifica los cambios de pertenencia.

¿Los seguidores pueden servir lecturas en Raft? Sí, si antes confirman el índice de commit del líder o si la aplicación acepta datos posiblemente obsoletos. Leer el estado local de un seguidor sin comprobación puede devolver valores antiguos.

¿Raft protege frente a nodos maliciosos? No. Raft tolera caídas, reinicios y mensajes perdidos o retrasados, pero da por hecho que los servidores siguen el protocolo. La tolerancia a fallos bizantinos necesita otros algoritmos y más réplicas.

Empieza gratis — un puesto, sin tarjeta de crédito.