Raft e Multi-Paxos são algoritmos de consenso distribuído que garantem que múltiplos nós concordem sobre um valor. Abaixo estão os fluxos detalhados para alcençar o consenso. ### Fluxo do Algoritmo Raft

Raft divide o consenso em três subproblemas: eleição de líder, replicação de log e segurança. #### 1. Eleição de Líder

• Papéis: Coordenador (líder), Seguidor, Candidato - Processo: 1. Inicialmente, todos os nós são seguidores. 2. Se um seguidor não receber um "batimento cardíaco" do líder dentro de um tempo limite (geralmente 150-300ms), ele se torna candidato. 3. O candidato inicia uma eleição: - Incrementa o número da época atual (epoch). - Vota em si mesmo. - Envia RPCs SolicitarVoto a outros nós. 4. Condições de sucesso na eleição: - Recebe votos de mais da metade dos nós. - Dentro da mesma época, só pode haver um único líder. 5. O novo líder envia regularmente batimentos cardíacos para manter sua autoridade. #### 2. Replicação de Log

Cliente → Coordenador → Seguidores → Confirmar → Aplicar

1. Solicitação do cliente: O cliente envia um comando ao coordenador. 2. Adição ao log: O coordenador adiciona o comando como uma nova entrada no log local. 3. Replicação paralela: O coordenador envia o log através de RPCs AnexarEntradas a todos os seguidores. 4. Confirmação dos seguidores: - Verifica consistência do log (índice anterior e época correspondentes). - Anexa o log e retorna sucesso. 5. Confirmação pelo coordenador: - Após receber confirmações da maioria, submete essa entrada. - Atualiza o índice de confirmação. 6. Notificação aos seguidores: Nas batidas cardíacas subsequentes, inclui o índice de confirmação; os seguidores confirmam e aplicam ao estado da máquina. 7. Repsosta ao cliente: O coordenador retorna o resultado da execução ao cliente. #### 3. Mecanismos de Segurança

• Restrições de eleição: O candidato deve conter todas as entradas de log já confirmadas. - Regras de submissão: O líder só pode submeter entradas do log da época atual. ### Fluxo do Algoritmo Multi-Paxos

Multi-Paxos otimiza o Paxos básico por meio da eleição de um líder estável, evitando submissões de duas fases para cada proposta. #### 1. Eleição de Líder (Fase Prepare)

1. Seleção do número de proposta n: Gera um número global único crescente. 2. Envio de solicitações Prepare: Envia Preparar(n) a todos os aceitadores. 3. Compromisso do aceitador: - Se n > maior número de proposta respondido, compromete-se a não aceitar propostas com números <n. a="" aceita="" com="" da="" de="" existir="" fato.="" l="" maior="" maioria="" o="" proponente="" proposta="" respostas="" retorna="" se="" torna="">2. Replicação de Log (Fase Accept - Otimizada) ```

Cliente → Líder → Aceitadores → Aprender → Aplicar

1. \*\*Pular fase Prepare\*\*: Em períodos estáveis, o líder vai diretamente à fase Accept. 2. \*\*Alocação de índices de log\*\*: O líder aloca slots contínuos no log para comandos do cliente. 3. \*\*Envio de solicitações Accept\*\*: Envia `Aceitar(n, índice, valor)`, onde n é o número da proposta. 4. \*\*Aceitação do aceitador\*\*: - Se não tiver feito promessas para números maiores, aceita a proposta. - Armazena persistentemente (número da proposta n, índice, valor). 5. \*\*Consenso alcançado\*\*: - Após receber a aceitação da maioria, o valor nessa posição é fixado. - O líder notifica os aprendizes (podendo ser em lotes). 6. \*\*Aprendiazdo pelos aprendizes\*\*: Os aprendizes obtêm o valor escolhido e aplicam ao estado da máquina. #### 3. Tratamento de Falhas

- \*\*Falha do líder\*\*: Novo proponente inicia Prepare com número maior. - \*\*Lacunas no log\*\*: Novo líder coleta propostas aceitas via Prepare para preencher lacunas. ### Comparação Crucial

| \*\*Aspecto\*\* | \*\*Raft\*\* | \*\*Multi-Paxos\*\* | |---|---|---| | \*\*Autoridade\*\* | Forte líder, única porta de escrita | Líder fraco, sujeito a revogação | | \*\*Continuidade do log\*\* | Forçada, sem lacunas | Permite lacunas, requer tratamento especial | | \*\*Modo de comunicação\*\* | Baseado em batimentos cardíacos, RPC de anexação de log | Baseado em números de proposta, otimização de duas fases | | \*\*Complexidade\*\* | Fácil de entender e implementar | Complexo teoricamente, diversificado em otimizações | | \*\*Aplicações reais\*\* | etcd, Consul etc. | Google Chubby etc. | ### Garantias de Consenso

Ambos satisfazem: 1. \*\*Segurança\*\*: Logs confirmados não podem ser alterados. 2. \*\*Atividade\*\*: Eventualmente atingem consenso. 3. \*\*Princípio da maioria\*\*: Necessário funcionamento de N/2+1 nós. Raft simplifica o estado do sistema através de um líder forte, enquanto Multi-Paxos oferece espaço de otimização mais flexível. No mundo real, Raft é mais popular devido à facilidade de compreensão e implementação, enquanto Multi-Paxos ainda mantém vantagens em cenários de alto desempenho específicos. </n.></div>