O que é protocolo de consenso, Raft e etcd (parte 2)?

Com mencionei no primeiro artigo (https://medium.com/@mclortizz/o-que-%C3%A9-protocolo-de-consenso-raft-e-etcd-de9887743dd7) o intuito dessa série é explicar os principais conceitos sobre protocolo de consenso, Raft e etcd.

Na parte 1 vimos a ideia geral de um protocolo de consenso, as bases do raft (strong leader, leader election e membership changes), conceito sobre a máquina de estado e seu mecanismo de sincronismo, os estados que uma instância raft pode estar (candidate, leader ou follower) e o que é um term (tempo lógico do raft).

Na parte 2 vamos dar uma passada no algoritmo do raft, mecanismo de eleição, mecanismo de replicação dos logs e como funciona o as mudanças de configuração de um cluster (adição ou remoção de membros).

Ah, lembrando que a parte 1 e 2 dessa série é baseada no paper "In Search of an Understandable Consensus Algorithm" publicado em https://raft.github.io/raft.pdf. Apertem os cintos!

Algoritmo do Raft

Alguns pontos importantes para entender melhor o algoritmo do raft:

1. Sempre vamos ter um líder no cluster;
2. O líder é o responsável por gerenciar a replicação dos logs;
3. O líder recebe o comando do cliente, aplica o log nele mesmo, replica para os demais membros do cluster e, quando seguro (atingir o consenso) solicita para os membros aplicarem os logs em suas máquinas de estado;
4. Caso o líder tenha alguma falha ou seja desconectado do cluster, um novo líder é eleito.

O raft decompõe o problema do consenso em 3 subproblemas:

1. Leader Election: um novo líder deve ser escolhido quando o líder atual falha;
2. Log Replication: o líder deve receber a entrada de log dos clientes e replicar para os demais membros do cluster;
3. Safety: se um servidor aplicou um determinado log em sua máquina de estado, então nenhum outro deve aplicar um comando diferente para o mesmo log.

Abaixo um resumo do algoritmo de consenso do raft, retirado do paper já mencionado acima.

Resumo do algoritmo de consenso do Raft

Existem diversas implementações do raft, o mais conhecido é o etcd (vamos usar o etcd para demonstrar como isso tudo funciona na parte 3 dessa série de artigos). Consulte https://raft.github.io/ para maiores informações sobre as implementações disponíveis.

Eleição de um Líder

Como já mencionei é obrigatório termos um líder no cluster para o protocolo de consenso do raft.

Como isso funciona?

1. Quando os servidores iniciam, todos eles iniciam no estado de follower;
2. Se os follower não recebem mensagens de um líder (timeout), eles assumem que não existe um líder no cluster e iniciam uma eleição;
3. Para iniciar uma eleição um follower incrementa seu term atual (se esqueceu o que é um term consulte a parte 1 dessa série) e transiciona seu estado para candidate;
4. Então o candidate vota em si mesmo e faz a chamada RPC (RequestVote) em paralelo para os demais servidores do cluster;
5. Um candidato ganha a eleição se receber a maioria dos votos dos demais servidores (no mínimo 50% + 1) e se torna líder;
6. O líder envia mensagens de heartbeat para os demais servidores para garantir sua autoridade e previnir novas eleições.

Talvez com a animação abaixo fique ainda mais fácil de entender.

Replicação de Log

Antes de entendermos como funciona o mecanismo de replicação de log, vamos entender qual é a estrutura do log.

Estrutura do log

O log é composto por entradas, cada entrada contém:

1. Um índice (index) que é criado, sequencialmente, para identificar a posição exata do log. Na figura acima o indice é demonstrado pelos números 1 até 8, ou seja, o líder possui 8 entradas;
2. O term, que indica o relógio lógico do raft. Por exemplo, na figura acima temos os terms 1, 2 e 3. Lembre-se que sempre que ocorre uma eleição o term é incrementado. Então é possível afirmar que nesse exemplo tivemos 3 eleições;
3. O comando, que será executado na máquina de estado. Ou seja, para o índice 1, term 1, o comando foi x ← 3 (x recebe 3).

Agora vamos entender melhor como funciona o mecanismo de replicação (no final da explicação vamos ter uma animação também :)).

Em uma operação normal:

1. Uma vez o líder é eleito, ele começa a servir às requisições dos clientes;
2. Cada requisição do cliente contém um comando para ser executado pela máquina de estado;
3. O líder então adiciona o comando em seu log como uma nova entrada, chama o RPC (AppendEntries) em paralelo para cada servidor para replicar a entrada;
4. Quando a entrada for replicada com segurança, o líder aplica a entrada em sua máquina de estado e retorna o resultado da execução para o cliente.

Torcendo para que a animação abaixo ajude a entender:

Bom, já vimos o resumo do algoritmo do raft e os mecanismos de eleição e replicação de logs. Agora dá uma paradinha, respira um pouco e vamos entrar no último ponto desse artigo.

Mudança de Membros do Cluster

Ocasionalmente é necessário alterar a configuração do cluster, por exemplo, para substituir servidores com falhas, adicionar novos ou remover servidores.

E qual é o cuidado que devemos entender aqui? Trocar as configurações diretamente de uma configuração para outra pode ocasionar um ambiente de insegurança, pois os servidores podem trocar as configurações em tempos diferentes, o que pode criar falhas no consenso. Por exemplo, se tivemos 3 servidores e adicionarmos mais 2, o número do consenso muda e podemos ter um cluster com visões diferentes do número necessário para existir consenso, conforme mostra a figura abaixo:

Servidores com visões diferentes do número necessário para consenso

Então o raft propõe, para garantir a segurança, que a mudança de configuração ocorra em duas fases (joint consensus).

Essa abordagem (joint consensus) permite que os servidores transitem entre as configurações do cluster (velha e nova) em diferentes momentos sem comprometer a segurança.

Joint consensus é um estado intermediário onde é necessário obter a maioria tanto na configuração velha quando na nova para os processos de eleição e replicação de logs, como demonstra a figura abaixo.

Joint Consensus

Ufa, passamos pelas principais pontos do raft. Para mais informações, leiam o paper dos criadores do raft, Diego Ongaro e John Ousterhout em https://raft.github.io/raft.pdf.

O raft é usado em alguns produtos bem conhecidos no mercado, como no kubernetes (etcd), docker (swarm mode), Nomad, Redis e Apache Kudu (Hadoop). No próximo artigo da série (o terceiro e último, em breve) vamos demonstrar como isso tudo funciona em um cluster na AWS rodando o etcd.

Conclusão

Nesse artigo entramos em alguns detalhes do protocolo raft. Mostramos os conceitos das bases do raft, eleição de um líder, replicação de logs e mudanças de membros do cluster.

No próximo artigo (https://medium.com/@mclortizz/o-que-%C3%A9-protocolo-de-consenso-raft-e-etcd-parte-3-4ece5d158e9e), demonstramos esses conceitos na prática.

Até breve e obrigado!

Marcelo Ortiz, Engenheiro da Computação, mestrando em Ciência da Computação.