Consenso Raft explicado: eleição de líder e replicação do log

Todo cluster Kubernetes guarda o próprio estado no etcd, e o etcd entra em acordo sobre esse estado com o Raft. O mesmo vale para Consul, CockroachDB, TiKV, as quorum queues do RabbitMQ e, desde que o Kafka 4.0 removeu o ZooKeeper, os próprios controladores do Kafka. Se você opera qualquer um deles, o Raft explica comportamentos que, de outro jeito, parecem arbitrários: por que um cluster de três nós para de aceitar gravações quando dois nós caem, por que as gravações pausam por um segundo durante uma troca de líder e por que um quarto nó deixa o cluster mais caro sem deixá-lo mais seguro.

Este post explica o Raft com um diagrama da replicação do log em um cluster de cinco nós: mandatos, eleição de líder, AppendEntries, a regra de commit, falhas, dimensionamento do cluster, leituras e mudanças de membros.

O modelo: um log replicado

O Raft constrói uma máquina de estados replicada. Cada servidor mantém um log de comandos. Se todos os servidores aplicam os mesmos comandos na mesma ordem, terminam no mesmo estado. O trabalho do Raft é manter os logs idênticos, mesmo quando servidores caem e mensagens se perdem ou atrasam.

Cada servidor está em um de três estados: seguidor, candidato ou líder. O tempo é dividido em mandatos (terms), numerados 1, 2, 3 e assim por diante; cada mandato começa com uma eleição e tem no máximo um líder. Um servidor que vê um mandato maior que o seu atualiza o próprio mandato e vira seguidor, então um líder desatualizado sai de cena assim que ouve falar do mais novo.

O Raft precisa de só duas RPCs, mais uma para snapshots:

O projeto vem do artigo In Search of an Understandable Consensus Algorithm, de Diego Ongaro e John Ousterhout, publicado no USENIX ATC 2014.

Eleição de líder

Um seguidor espera heartbeats regulares do líder. Se nenhum chega dentro do seu timeout de eleição, ele assume que o líder sumiu:

1. Ele incrementa o mandato, vira candidato e vota em si mesmo.
2. Envia RequestVote para todos os outros servidores, com o índice e o mandato da sua última entrada do log.
3. Cada servidor concede no máximo um voto por mandato, e só para um candidato cujo log esteja pelo menos tão atualizado quanto o seu: ganha o último mandato mais alto e, em caso de empate, ganha o log mais longo.
4. O candidato que junta votos de uma maioria vira líder e começa a enviar heartbeats.

Se dois candidatos dividem os votos, ninguém ganha, e o mandato termina sem líder. O Raft torna isso raro sorteando os timeouts; o artigo sugere valores como de 150 a 300 ms, de modo que normalmente um servidor estoura o timeout primeiro e ganha antes que os outros comecem.

Sistemas em produção escolhem os timeouts de acordo com a rede. O etcd usa por padrão um heartbeat de 100 ms e um timeout de eleição de 1.000 ms, e a documentação dele diz que o timeout de eleição deve ser pelo menos dez vezes o tempo de ida e volta entre os membros. Esses números explicam por que um control plane do Kubernetes pode levar um segundo ou mais para voltar a aceitar gravações depois de perder o líder do etcd.

Replicação do log

Depois de eleito, o líder trata todas as gravações:

1. Um cliente envia um comando ao líder, por exemplo SET x=5.
2. O líder o adiciona ao próprio log como uma entrada nova com o mandato atual, digamos o índice 7 no mandato 3.
3. O líder envia a cada seguidor um AppendEntries com a entrada nova, mais o índice e o mandato da entrada logo anterior (índice 6, mandato 3).
4. Um seguidor só aceita se o log dele tiver uma entrada no índice 6 com o mandato 3. Essa verificação de consistência garante que, se dois logs concordam em uma posição, eles concordam em tudo o que vem antes.
5. Quando uma maioria dos servidores, incluindo o líder, guarda a entrada, o líder a marca como confirmada (committed), a aplica à sua máquina de estados e responde ao cliente.
6. Os seguidores ficam sabendo do novo índice de commit no próximo AppendEntries e também aplicam a entrada.

Se um seguidor rejeita uma entrada porque o log dele diverge, o líder volta um índice por vez, ou mais rápido com otimizações, até os logs baterem, e então sobrescreve as entradas conflitantes do seguidor com as suas. Só entradas não confirmadas são sobrescritas, o que é seguro, porque ninguém foi informado de que elas deram certo.

A regra de commit e a parte sutil

“Confirmada assim que uma maioria a guarda” tem uma exceção, e ela é o detalhe mais famoso do artigo. Um líder novo não pode contar réplicas para confirmar entradas que sobraram de mandatos anteriores. Ele as confirma indiretamente, confirmando por cima uma entrada do próprio mandato. Sem essa regra, uma entrada guardada em uma maioria ainda poderia ser sobrescrita por um líder posterior. Na prática, um líder novo adiciona uma entrada vazia no-op no início do mandato para confirmar rapidamente tudo o que veio antes.

A restrição de eleição completa o argumento de segurança: como um candidato precisa dos votos de uma maioria e toda entrada confirmada está em uma maioria, qualquer vencedor possível já tem todas as entradas confirmadas.

O que um cluster aguenta

Um cluster de n servidores precisa de uma maioria para eleger um líder e confirmar gravações, então ele tolera a falha de menos da metade:

Quatro servidores toleram uma falha, como três, mas agora cada gravação espera três confirmações em vez de duas. É por isso que os clusters têm tamanhos ímpares. Cinco é a escolha usual quando você quer sobreviver a uma falha enquanto outro nó está em manutenção planejada.

A latência segue a mesma conta. Cada gravação espera o líder alcançar a maioria mais rápida e esses servidores gravarem a entrada em disco. Em um cluster espalhado por três regiões, cada gravação custa pelo menos uma ida e volta até a outra região mais próxima. Discos lentos atrapalham tanto quanto redes lentas, e é por isso que a documentação do etcd dedica tanto espaço à latência de fsync quanto aos timeouts.

Falhas na prática

• O líder cai. Os seguidores estouram o timeout, um ganha uma eleição e as gravações voltam. Requisições em andamento podem ou não ter sido confirmadas, então os clientes precisam tentar de novo, e os comandos que eles repetem devem ser idempotentes.
• Uma partição de rede. O lado com a maioria elege um líder e segue em frente. Um líder antigo no lado minoritário não consegue confirmar nada; quando a partição se resolve, ele vê o mandato mais alto e sai de cena.
• Um seguidor lento. Os commits não esperam por ele. Se ele ficar muito para trás, o líder envia um snapshot em vez de reproduzir o log inteiro.
• Um servidor perturbador. Um servidor isolado do líder continua estourando o timeout e aumentando o mandato, o que pode forçar eleições desnecessárias quando ele volta. O pre-vote, da tese de doutorado de Ongaro, deixa um candidato verificar se conseguiria ganhar antes de incrementar o mandato.

Leituras não são de graça

Um líder não pode responder leituras às cegas a partir do próprio estado: um novo líder pode ter sido eleito do outro lado de uma partição, e o antigo devolveria dados desatualizados. Leituras linearizáveis exigem ou uma rodada de heartbeats para confirmar a liderança antes de responder (o ReadIndex do Raft), ou um lease de líder baseado em tempo, que depende de um desvio de relógio limitado. Os seguidores também podem atender leituras, mas só depois de conferir o índice de commit do líder, ou aceitando resultados desatualizados. O etcd deixa isso explícito: etcdctl get é linearizável por padrão, e --consistency=s pede uma leitura serializável mais rápida e possivelmente desatualizada.

Mudar os membros

Adicionar ou remover servidores muda o que é uma maioria, e trocar de configuração sem cuidado pode criar duas maiorias ao mesmo tempo. O Raft resolve isso com joint consensus ou mudando um servidor por vez. Muitas implementações também adicionam servidores novos como learners sem direito a voto, como faz o etcd, para que um nó novo alcance o log antes de contar para a maioria.

O diagrama de replicação do log

Como ler:

• O cliente envia um comando ao líder, S1, no mandato 3. O líder o grava no índice 7.
• Cada tabela é o log de um servidor: índice, mandato e comando. Linhas iguais entre as tabelas são a mesma entrada.
• As arestas AppendEntries vão do líder aos quatro seguidores. S2 e S3 confirmam o índice 7.
• S4 está atrasado no índice 6 e S5 está inacessível no índice 5. Nenhum dos dois bloqueia o commit.
• A nota mostra a regra de commit: três de cinco servidores guardam a entrada 7, então ela está confirmada e o cliente recebe a resposta.

Desenhar diagramas de consenso que ensinam

• Mostre os logs, não só os servidores. As garantias do Raft são afirmações sobre logs. Um diagrama com cinco caixas e setas esconde tudo o que é interessante.
• Escreva o mandato ao lado de cada entrada. Os mandatos explicam as eleições, os conflitos e a regra de commit.
• Desenhe um cluster com problemas. Um seguidor atrasado ou isolado mostra por que as maiorias importam melhor do que um cluster perfeito.
• Use um diagrama por cenário: uma eleição, a replicação normal e o reparo de um conflito depois de um failover merecem, cada um, a própria figura.

Para ver como a replicação se encaixa nas arquiteturas de banco de dados de modo geral, veja o diagrama de replicação de banco de dados. O diagrama de arquitetura do Kubernetes mostra onde o etcd fica em um control plane, e o diagrama de arquitetura do Kafka cobre os controladores KRaft. Sistemas como o CockroachDB rodam um grupo Raft por faixa de dados, o que liga o consenso às ideias do diagrama de sharding de banco de dados.

Monte no Archboard

1. Entre com Google ou GitHub e crie um diagrama.
2. Adicione uma Moldura do pack Básico para o cluster e rotule-a com o mandato atual.
3. Adicione dentro dela cinco nós Tabela do pack Básico, um por servidor, com colunas para índice, mandato e comando. Coloque o líder no meio.
4. Adicione fora da moldura uma Caixa do pack Básico para o cliente e ligue-a ao líder com o comando.
5. Desenhe arestas AppendEntries do líder para cada seguidor, com arestas tracejadas de confirmação voltando dos seguidores que guardaram a entrada. Marque o seguidor inacessível com uma aresta tracejada em uma cor de alerta.
6. Adicione um bloco Markdown do pack Básico com a regra de commit e uma Nota ao lado do líder informando o índice de commit.

O exemplo usa 8 nós de diagrama e fica dentro do plano Free.

Perguntas frequentes

Por que os clusters Raft têm um número ímpar de nós? Um cluster precisa de uma maioria para funcionar. Adicionar um quarto nó a três sobe a maioria de dois para três sem tolerar mais falhas, então tamanhos pares custam latência e dinheiro sem acrescentar tolerância a falhas.

O que acontece com as gravações durante uma eleição de líder? Elas esperam ou falham até um novo líder ser eleito, normalmente dentro de um ou dois timeouts de eleição. Os clientes devem tentar de novo com requisições idempotentes, porque uma gravação que estourou o timeout pode ter sido confirmada.

Qual é a diferença entre Raft e Paxos? Eles resolvem o mesmo problema com garantias parecidas. O Raft foi projetado para ser mais fácil de entender e implementar: usa um líder forte, separa a eleição da replicação e especifica as mudanças de membros.

Os seguidores podem atender leituras no Raft? Sim, se primeiro confirmarem o índice de commit do líder, ou se a aplicação aceitar dados possivelmente desatualizados. Ler o estado local de um seguidor sem verificação pode devolver valores antigos.

O Raft protege contra nós maliciosos? Não. O Raft tolera quedas, reinícios e mensagens perdidas ou atrasadas, mas pressupõe que os servidores seguem o protocolo. A tolerância a falhas bizantinas exige outros algoritmos e mais réplicas.

Comece grátis — um assento, sem cartão de crédito.