Consenso e Quóruns

Às 10:00:03, três segundos depois de abertas as vendas, a máquina que roda o primário PostgreSQL do inventory congela. Seu standby síncrono está saudável. Alguém — ou algo — precisa decidir que o primário antigo está morto, promover o standby e fazer todas as réplicas do inventory escreverem no novo. Agora imagine que o primário antigo não estava morto, só pausado por oito segundos por um soluço no armazenamento: ele acorda, ainda acredita que é o primário e aceita uma reserva do assento A-12 que o novo primário já tinha dado a outra pessoa. Dois primários ao mesmo tempo é o que se chama de split brain, e em um sistema de ingressos isso significa assentos vendidos duas vezes.

Decidir "quem é o primário agora" é uma instância do problema de consenso: fazer um grupo de nós concordar sobre um único valor — apesar de mensagens perdidas e atrasadas e apesar de alguns nós falharem. O consenso é a base da eleição de líder, dos locks distribuídos, da configuração replicada (o etcd por trás de todo cluster Kubernetes) e de todo banco de dados replicado fortemente consistente.

Consenso e máquinas de estado replicadas

A forma mais útil de consenso é concordar sobre um log: uma sequência ordenada de comandos. Se todo nó começa no mesmo estado e aplica os mesmos comandos na mesma ordem, todo nó termina no mesmo estado — uma máquina de estado replicada:

flowchart LR
    C([clientes]) --> L
    subgraph L["líder"]
        LL["log: reserva A-12 · reserva B-3 · libera A-12"] --> LS[("estado")]
    end
    subgraph F1["seguidor 1"]
        F1L["mesmo log"] --> F1S[("mesmo estado")]
    end
    subgraph F2["seguidor 2"]
        F2L["mesmo log"] --> F2S[("mesmo estado")]
    end
    L -->|"replica entradas"| F1
    L -->|"replica entradas"| F2

Um algoritmo de consenso correto garante:

Segurança (safety) — "nada de ruim acontece" : Todos os nós que decidem, decidem o mesmo valor (a mesma entrada do log em cada posição), e esse valor foi proposto por alguém.

Vivacidade (liveness) — "algo de bom acaba acontecendo" : Nós que não falharam eventualmente decidem.

Por que é difícil: FLP

O resultado de impossibilidade FLP (Fischer, Lynch e Paterson, 1985)¹ prova que, em um sistema totalmente assíncrono — sem limite para o atraso das mensagens —, nenhum algoritmo determinístico consegue garantir consenso se mesmo um nó pode cair: alguma sequência azarada de atrasos o mantém indeciso para sempre. A saída, usada pelo Paxos e pelo Raft, é nunca comprometer a segurança e garantir progresso só quando a rede se comporta "bem o bastante" (sincronia parcial), usando timeouts para suspeitar de falhas. Um timeout pode estar errado (o nó só estava lento), e por isso os algoritmos precisam continuar seguros mesmo quando as suspeitas são falsas.

Maiorias: por que clusters têm 3 ou 5 nós

O truque central é o quórum de maioria: uma decisão só é válida se mais da metade dos N nós a aceitar. Quaisquer duas maiorias do mesmo cluster têm pelo menos um nó em comum — então duas decisões conflitantes nunca podem ambas reunir uma maioria: o nó em comum teria de votar nas duas, e o protocolo proíbe isso.

O que a maioria compra em disponibilidade? Se cada nó está no ar com probabilidade \(a\) (de forma independente), o cluster está no ar quando pelo menos uma maioria está:

Com nós a 99% cada, um nó dá 2 noves, dois nós dão menos (98,01% — os dois precisam estar no ar), três nós dão ≈ 99,97% e cinco ≈ 99,999%. A hipótese de independência é otimista — nós na mesma zona, na mesma versão ou sobrecarregados pelo mesmo tráfego falham juntos —, e por isso os nós são espalhados por domínios de falha.

Split brain, e por que a maioria o impede

Uma partição divide um cluster de 5 nós em 3/2. Só o lado com 3 nós consegue formar uma maioria, eleger um líder e confirmar escritas; o lado com 2 sabe que é minoria e para de aceitar escritas:

flowchart LR
    subgraph maj ["Lado majoritário (3 de 5)"]
        n1[nó 1: líder] --- n2[nó 2]
        n2 --- n3[nó 3]
    end
    subgraph min ["Lado minoritário (2 de 5)"]
        n4[nó 4] --- n5[nó 5]
    end
    n3 -.-|partição| n4
    maj -->|"consegue eleger e confirmar"| ok([continua vendendo assentos])
    min -->|"não alcança 3 votos"| ko([rejeita escritas: 503])

É exatamente o comportamento CP do CAP: o lado minoritário fica indisponível, e assim o sistema permanece consistente.

Raft

O Raft (Ongaro e Ousterhout, 2014)² foi projetado para ser compreensível, e é o algoritmo de consenso que você tem mais chance de encontrar: etcd (Kubernetes), Consul, CockroachDB, TiKV, YugabyteDB e o controlador KRaft do Kafka o usam. Ele divide o problema em três partes:

1. Eleição de líder — exatamente um líder por termo; todas as escritas passam por ele.
2. Replicação do log — o líder acrescenta comandos ao seu log e os replica para os seguidores.
3. Segurança — uma entrada confirmada por uma maioria (committed) nunca é perdida nem sobrescrita.

Papéis e termos

Cada nó é um seguidor (follower), um candidato (candidate) ou o líder (leader). O tempo é dividido em termos (terms) numerados 1, 2, 3…, cada um começando com uma eleição; um termo tem no máximo um líder. Os termos funcionam como um relógio lógico (Tempo e Relógios): qualquer nó que vê uma mensagem com termo maior que o seu atualiza o próprio termo e volta a ser seguidor — é assim que um líder desatualizado, ao acordar depois de uma pausa, descobre que foi substituído.

stateDiagram-v2
  state "Seguidor" as Follower
  state "Candidato" as Candidate
  state "Líder" as Leader
  [*] --> Follower
  Follower --> Candidate : election timeout (sem heartbeat)
  Candidate --> Leader : votos de uma maioria
  Candidate --> Follower : vê um líder ou um termo maior
  Candidate --> Candidate : votos divididos, novo timeout
  Leader --> Follower : vê um termo maior

Eleição de líder

O líder envia heartbeats periódicos (mensagens AppendEntries vazias). Um seguidor que não ouve nada durante um election timeout supõe que o líder morreu, incrementa o termo, vota em si mesmo e pede votos aos outros:

sequenceDiagram
  participant N1 as nó 1 (seguidor)
  participant N2 as nó 2 (seguidor)
  participant N3 as nó 3 (líder antigo, congelado)
  Note over N1,N3: termo 4: o nó 3 para de enviar heartbeats
  N1->>N1: election timeout: termo 5, candidato, vota em si mesmo
  N1->>N2: RequestVote(term 5, last log index 812, term 4)
  N1->>N3: RequestVote(term 5, ...)
  N2-->>N1: voto concedido (meu log não é mais novo que o seu)
  Note over N1: 2 de 3 votos: líder do termo 5
  N1->>N2: AppendEntries(term 5, heartbeat)
  N1->>N3: AppendEntries(term 5, heartbeat)
  Note over N3: acorda, vê termo 5 > 4: volta a ser seguidor

Três regras a tornam segura:

• Um voto por nó por termo — então no máximo um candidato consegue reunir uma maioria em um termo.
• Restrição de eleição — um nó só vota em um candidato cujo log esteja pelo menos tão atualizado quanto o seu. Como toda entrada confirmada está em uma maioria, e o vencedor precisa de votos de uma maioria, o novo líder certamente tem todas as entradas confirmadas.
• Election timeouts aleatórios (o artigo sugere 150–300 ms) — se todos os seguidores dessem timeout juntos, dividiriam os votos para sempre; com timeouts aleatórios, normalmente um dispara primeiro e vence antes de os outros começarem.

Por quanto tempo as escritas ficam indisponíveis quando um líder morre? Aproximadamente election timeout + uma rodada de votação. Os padrões do etcd são heartbeat de 100 ms e election timeout de 1.000 ms³ (ajustados para cima por causa da latência entre zonas), então a queda de um líder significa cerca de um a dois segundos sem escritas — um número a lembrar quando o timeout de um cliente é menor do que isso.

Replicação do log

sequenceDiagram
  participant C as inventory
  participant L as líder
  participant F1 as seguidor 1
  participant F2 as seguidor 2
  C->>L: reservar A-12 para o fã 42
  L->>L: acrescenta ao log no índice 813 (termo 5)
  L->>F1: AppendEntries(index 813, prev = 812/term 4)
  L->>F2: AppendEntries(index 813, prev = 812/term 4)
  F1-->>L: OK (gravado em disco)
  Note over L: 2 de 3 têm a entrada: confirmada, aplica ao estado
  L-->>C: OK, assento reservado
  F2-->>L: OK (mais tarde)
  L->>F1: o próximo heartbeat leva o commit index 813

• O líder só responde ao cliente depois que uma maioria (contando ele mesmo) gravou a entrada de forma durável: entradas confirmadas sobrevivem à perda de qualquer minoria.
• Cada AppendEntries leva o índice e o termo da entrada anterior; um seguidor a rejeita se seu log não coincide ali, e o líder volta atrás até os logs concordarem, então sobrescreve o sufixo divergente e não confirmado do seguidor. Essa correspondência de logs (log matching) mantém todos os logs idênticos até o commit index.
• Os seguidores aprendem o commit index em mensagens posteriores e aplicam as entradas à sua própria máquina de estado.

O protocolo inteiro, ao vivo — eleição, replicação, um líder que cai e uma partição:

Paxos, em um parágrafo

O Paxos (Lamport, 1989/1998; "Paxos Made Simple", 2001)⁴ é o algoritmo de consenso original, com as mesmas garantias. Sua forma de decisão única concorda sobre um valor em duas fases (prepare/promise, depois accept/accepted) entre proponentes e aceitadores com cédulas numeradas; sistemas de produção rodam o Multi-Paxos — um líder estável que pula a primeira fase —, que se parece muito com o Raft. O Paxos é comprovado e amplamente usado (Chubby e Spanner, do Google), mas famoso por ser difícil de implementar; a contribuição do Raft não foram garantias novas, e sim uma estrutura que engenheiros conseguem seguir. O ZooKeeper usa um protocolo aparentado, o ZAB (ZooKeeper Atomic Broadcast).

Quóruns em armazenamentos sem líder: R + W > N

Bancos sem líder da família Dynamo (Cassandra, ScyllaDB, Riak) usam quóruns por requisição, sem líder. Com N réplicas de cada chave, uma escrita espera W confirmações e uma leitura consulta R réplicas e fica com a versão mais nova:

Quando R + W > N, pelo menos uma réplica em qualquer conjunto de leitura tem a última escrita confirmada. Com N = 3:

Três mecanismos fazem as réplicas sem líder convergirem: read repair (uma leitura que vê uma versão antiga grava de volta a mais nova), hinted handoff (uma escrita destinada a um nó morto fica com outro e é entregue depois — um quórum relaxado (sloppy quorum) que quebra a garantia de sobreposição nesse meio-tempo) e anti-entropia (comparação das réplicas em segundo plano usando árvores de Merkle)⁵.

Leases, locks e fencing tokens

Um uso comum de consenso é um lock distribuído ou lease: "só uma réplica do scheduler envia o push das 09:55 as vendas abrem em breve". Você obtém um lease do etcd/ZooKeeper/Consul com um tempo de vida e o renova enquanto estiver vivo. Mas quem tem o lock pode pausar — uma coleta de lixo longa, a migração de uma VM — e continuar trabalhando depois de o lease expirar e outro processo tê-lo obtido⁶:

sequenceDiagram
    participant A as worker A
    participant LK as serviço de lock (etcd)
    participant B as worker B
    participant S as armazenamento
    A->>LK: obtém o lease
    LK-->>A: concedido, fencing token 33
    Note over A: pausa de GC de 15 s: o lease expira
    B->>LK: obtém o lease
    LK-->>B: concedido, fencing token 34
    B->>S: escrita (token 34)
    S-->>B: OK, maior token visto = 34
    Note over A: acorda, ainda acha que tem o lock
    A->>S: escrita (token 33)
    S-->>A: rejeitada: 33 < 34

A solução é um fencing token: um número que aumenta a cada concessão (a revisão do etcd, o zxid do ZooKeeper), enviado com toda escrita; o armazenamento rejeita qualquer token menor do que o maior que já viu. A mesma ideia — uma época ou termo monotonicamente crescente — protege o failover do PostgreSQL da história de abertura: o primário antigo, isolado (suas escritas rejeitadas, ou sua máquina desligada à força — "STONITH", shoot the other node in the head), não consegue corromper o novo.

-- The storage enforces the fence: a write carrying an old token changes nothing
UPDATE scheduled_jobs
   SET last_run_at = now(), fencing_token = :token
 WHERE job_id = 'onsale-reminder-42'
   AND fencing_token <= :token;     -- 0 rows updated → a newer token exists: we are a stale holder

Na prática: use, não construa

Experimente. O cenário db-failover é a história do início da página, medida: checkout a 1.500 req/s, metade delas escritas, num cluster com um primário e um seguidor replicado de forma assíncrona. Em t = 90 s o primário morre, e promover o seguidor leva 30 s — mais ou menos o TTL da chave de líder do Patroni acima. Aperte Run e leia escritas perdidas e disponibilidade na barra de metas. Depois clique em orders-db e mude um botão por vez: Replicação sync (ou quorum com 2 seguidores por shard), Tempo de failover 5 s, Shards 2.

Como se conecta

flowchart LR
    MAJ["quóruns de maioria<br/>sem split brain"] --> RAFT["Raft / Paxos<br/>log replicado"]
    RAFT --> ETCD["etcd · ZooKeeper · KRaft"]
    ETCD --> LE["eleição de líder<br/>(failover do banco, scheduler)"]
    ETCD --> LOCK["leases e locks"]
    LOCK --> FT["fencing tokens"]
    RAFT --> NEWSQL["Spanner · CockroachDB<br/>(consenso por faixa)"]
    NEWSQL --> TX2["2PC sobre grupos de consenso<br/>→ Transações Distribuídas"]
    Q["R + W > N<br/>quóruns sem líder"] --> TUNE["consistência ajustável<br/>(Cassandra, Dynamo)"]
    TERMS["termos / épocas"] --> FT
    TERMS -.-> CLK["relógios lógicos<br/>→ Tempo e Relógios"]

Componentes da paleta que dependem de consenso: kafka (controlador KRaft, líderes de partição) · sql (failover com Patroni + etcd) · nosql (quóruns) · scheduler (um líder executa os jobs). Continua em: Transações Distribuídas, Cloud-native — Kubernetes (etcd), Compute — trabalho assíncrono (eleição de líder do scheduler).

Pontos-chave