Consensus algorithms: Paxos, Raft e quando importam

1. O Problema do Consenso em Sistemas Distribuídos

Em sistemas distribuídos, o problema do consenso surge quando múltiplos nós precisam concordar em um único valor (ou sequência de valores) mesmo diante de falhas de nós, partições de rede ou latência imprevisível. Este problema é central para a replicação de estado (state machine replication), onde cada nó mantém uma cópia do estado do sistema e deve aplicar as mesmas operações na mesma ordem.

No cenário clássico, imagine um banco de dados replicado em três servidores. Um cliente envia uma atualização: "atualizar saldo da conta X para 1000". Se um servidor recebe a requisição e os outros não, ou se dois servidores recebem ordens diferentes, o estado do sistema diverge. O consenso resolve isso garantindo que todos os servidores concordem em qual operação aplicar e em qual ordem.

Os desafios fundamentais incluem:
- Falhas de rede: mensagens podem ser perdidas ou atrasadas
- Partições: o sistema pode ser dividido em grupos que não se comunicam
- Latência: a ordem de chegada das mensagens pode variar
- Nós maliciosos: em ambientes não confiáveis, o problema se torna byzantine fault tolerance (BFT), mas aqui focamos em falhas não-byzantinas (crash-stop)

2. Paxos: O Algoritmo Clássico e sua Complexidade

Paxos, proposto por Leslie Lamport em 1989, é o algoritmo de consenso mais conhecido e provado formalmente. Ele define três papéis:

  • Proposer: propõe um valor
  • Acceptor: decide se aceita ou rejeita propostas
  • Learner: aprende o valor decidido (opcional para a lógica principal)

O protocolo ocorre em duas fases:

Fase 1 (Prepare/Promise): O proposer envia uma requisição prepare(n) com um número de proposta n a um quórum de acceptors. Cada acceptor responde com promise(n) se nunca aceitou uma proposta com número maior ou igual a n, prometendo ignorar propostas futuras com número menor.

Proposer -> Acceptors: prepare(1)
Acceptor 1 -> Proposer: promise(1, last_accepted_n=0, last_accepted_value=null)
Acceptor 2 -> Proposer: promise(1, last_accepted_n=0, last_accepted_value=null)

Fase 2 (Accept/Accepted): Se o proposer recebe promises de um quórum, ele envia accept(n, value) para os acceptors. O valor escolhido é o last_accepted_value da resposta com maior last_accepted_n, ou um valor novo se nenhum foi aceito. Os acceptors aceitam se não tiverem prometido a um número maior.

Proposer -> Acceptors: accept(1, "valor_X")
Acceptor 1 -> Proposer: accepted(1, "valor_X")
Acceptor 2 -> Proposer: accepted(1, "valor_X")

Críticas e trade-offs: Paxos é notoriamente difícil de implementar corretamente. Sua complexidade levou a implementações frágeis e a uma barreira de entendimento. Além disso, em cenários reais, múltiplos proposers podem levar a livelocks (nenhuma proposta avança), exigindo mecanismos de leader election externos.

3. Raft: Consenso Projetado para Compreensão e Implementação

Raft, proposto por Diego Ongaro e John Ousterhout em 2013, foi projetado especificamente para ser mais compreensível que Paxos, mantendo as mesmas garantias de segurança. Ele decompõe o problema em subproblemas gerenciáveis:

  • Eleição de líder: um nó é eleito líder por termo (term), usando heartbeats para manter sua autoridade
  • Replicação de log: o líder recebe comandos dos clientes e os replica para os seguidores
  • Segurança: regras que garantem consistência mesmo em falhas

O ciclo básico:

# Cliente envia comando para o líder
Cliente -> Líder: SET X=10

# Líder adiciona ao log local e envia AppendEntries para seguidores
Líder -> Seguidor1: AppendEntries(term=3, entries=[{index=5, command="SET X=10"}])
Líder -> Seguidor2: AppendEntries(term=3, entries=[{index=5, command="SET X=10"}])

# Seguidores respondem
Seguidor1 -> Líder: AppendEntriesResponse(success=true, matchIndex=5)
Seguidor2 -> Líder: AppendEntriesResponse(success=true, matchIndex=5)

# Líder confirma commit e notifica seguidores
Líder -> Seguidor1: AppendEntries(term=3, entries=[], commitIndex=5)
Líder -> Seguidor2: AppendEntries(term=3, entries=[], commitIndex=5)

Propriedades de segurança:
- Election Safety: no máximo um líder por termo
- Leader Append-Only: o líder nunca sobrescreve ou apaga entradas do log
- Log Matching: se dois logs têm a mesma entrada no mesmo índice e termo, são idênticos até aquele ponto
- State Machine Safety: se um nó aplica um comando em um índice, nenhum outro nó aplica um comando diferente no mesmo índice

4. Comparação Prática: Paxos vs. Raft

Aspecto Paxos Raft
Simplicidade Difícil de implementar e entender Projetado para ser compreensível
Eleição de líder Não embutida (requer extensão) Embutida (leader election)
Replicação Duas fases (prepare/accept) Uma fase (AppendEntries) com heartbeats
Performance Similar em throughput, mas maior latência em cenários de contenção Menor latência de commit devido a liderança forte
Casos de uso Sistemas legados, bancos customizados etcd, Consul, TiKV, MongoDB (Raft-based)

Exemplo de implementação de eleição em Raft (pseudocódigo):

# Nó detecta timeout de eleição
if currentRole == FOLLOWER and electionTimeout elapsed:
    currentTerm++
    currentRole = CANDIDATE
    voteForSelf()
    send RequestVote to all peers

    if received majority of votes:
        currentRole = LEADER
        send heartbeats to all peers
    elif received vote from higher term:
        currentRole = FOLLOWER
        updateTerm(higherTerm)

5. Quando o Consenso Realmente Importa na Arquitetura

Sistemas que exigem forte consistência:
- Bancos de dados relacionais replicados (ex.: CockroachDB usa Raft)
- Sistemas de locking distribuído (ex.: ZooKeeper)
- Service discovery e configuração (ex.: etcd, Consul)
- Coordenação de transações distribuídas

Sistemas que podem relaxar consenso:
- Sistemas com consistência eventual (ex.: Cassandra, DynamoDB)
- CRDTs (Conflict-free Replicated Data Types)
- Protocolos gossip (ex.: Redis Cluster)

Armadilhas comuns:
- Usar consenso onde assincronia é tolerável: aumenta latência e custo de rede
- Ignorar custo operacional: clusters de 3 ou 5 nós exigem monitoramento de eleições e split-brain
- Subestimar a complexidade de implementação: implementar Paxos ou Raft do zero é raramente justificável

6. Implementação e Padrões Arquiteturais

Na prática, a maioria das aplicações não implementa consenso do zero. Bibliotecas e sistemas prontos oferecem integração:

  • etcd: armazenamento chave-valor baseado em Raft, usado pelo Kubernetes
  • ZooKeeper: baseado em Zab (protocolo similar a Paxos), usado por Kafka e HBase
  • Consul: service discovery com Raft

Padrões de deploy:
- Clusters de 3 nós toleram 1 falha; clusters de 5 nós toleram 2 falhas
- Quórum: mínimo de (n/2) + 1 nós para decisões
- Prevenção de split-brain: usar heartbeats e timeouts configuráveis

Métricas de monitoramento:
- Tempo de eleição (election latency)
- Latência de commit (commit latency)
- Número de termos (term changes)
- Tamanho do log (log size)

7. Conclusão e Próximos Passos

Paxos e Raft resolvem o mesmo problema fundamental, mas com abordagens diferentes. Paxos é o padrão teórico, mas Raft é a escolha prática para a maioria dos sistemas modernos devido à sua compreensibilidade e implementações maduras.

Quando escolher cada um:
- Paxos: sistemas legados, ambientes onde a prova formal é crítica, ou quando você precisa de variantes como Multi-Paxos
- Raft: novos projetos, sistemas que exigem manutenibilidade, ecossistemas como Kubernetes/etcd
- Alternativas: considere CRDTs ou gossip se consistência eventual for suficiente

Conexão com temas vizinhos:
- Consenso se relaciona com transações distribuídas (2PC, Sagas) e cache invalidation
- Raft é frequentemente combinado com distributed transactions para garantir atomicidade

Exercício prático (Architecture Kata):
Projete um sistema de configuração distribuída para microsserviços usando Raft. Justifique: (1) necessidade de forte consistência (configurações não toleram divergência), (2) cluster de 3 nós para tolerância a falhas, (3) uso de etcd como implementação pronta, (4) monitoramento de eleições para detectar partições de rede.

Referências