Algoritmos de consenso

1) O que é o consenso e o que é necessário

Consenso: alinhamento do mesmo valor/seqüência de valores entre vários nós em casos de falhas e atrasos. Tradicionalmente, o desafio de replicar o estado (SMR, State Machine Replicação) é que há uma máquina de estado determinada e uma ordem geral de operações.

• Consenso (SMR): ordem total unificada de comandos → armazenamento/registro linear, metadados de cluster, coordenadores de transação.
• Operações quórum sem ordem total (Dinamo-similares, CRDT): permite a divergência e posterior fusão; não substituem o consenso onde a serialização global é necessária.

2) Modelo de tempo e falhas

2. 1 Modelo de tempo

Rede Asincrona: atrasos são ilimitados; o teorema FLP ⇒ não pode ser garantido por safety e liveness sem suposições adicionais.
Parcialmente sincronizado (muitas vezes na prática): Depois do desconhecido T, o sistema «age» em sincronia - a maioria dos algoritmos (Raft, Paxos) depende disso.
Sincronizado: limites de tempo rígidos por canal (raramente vendidos, exceto redes especiais/PTP).

2. 2 Modelo de falha

Crash-fault tolerant (CFT): Os nódulos podem cair/pendurar, mas não são maliciosos.
Byzantine-fault tolerant (BFT): nós podem mentir/falsificar mensagens. São necessários 3f + 1 nós para tolerância f bizantino.

3) Propriedades de consenso

Safety (segurança): inadequado (dois nódulos corretos não resolvem valores diferentes).
Liveness: Se a rede for «saudável», a solução será alcançada.
Linearização (linearidade): As operações são «vistas» como atômicas em ordem unificada.
Durabilidade: decisões tomadas não são revertidas (proteção por revista/quórum).

4) Quórum, maioria e cruzamento

No mundo CFT clássico: quórum> N/2. Os registos e as eleições do líder usam o cruzamento de quórum, por isso duas operações «validas» não são conflitantes.
No mundo BFT: quorum 2f + 1 de 3f + 1 permite a interseção de um mínimo de f + 1 nós honestos.

Regra de cruzamento: Qualquer quórum de dois deve ter um nó genérico genérico (CFT) ou (BFT).

5) Replicar estado (registro + aplicação)

• Seaschots (corte de estado após o qual as gravações iniciais podem ser removidas/compiladas).
• Compactuação de revista e loga-triim.
• Verificações de determinismo (versão idêntica do código/configs).

6) Esquemas de liderança e não-idêntico

Líder (Raft, Multi-Paxos, ZAB): um líder serializa as gravações de forma → mais simples mentalmente e operacionalmente, melhor latency em um líder estável.
Ilimitados/multilidéricos (EPaxos, Caestar): mais paralelismo e tolerância com o líder, mas mais difícil implementação e conflito-solução; o lucro é visível em pequenos conflitos de comandos.

7) Algoritmos CFT clássicos

7. 1 Paxos/Multi-Paxos (e práticas)

A ideia é duas fases (prepare/propose), promessas de aceitadores, quórum majoritário. A Multi-Paxos deixa um «líder estável» e transforma as operações em gravações de uma só rodada (para novos registros) depois de «aquecer».

• Modelo flexível, mas difícil de implementar.
• Configurações de r através de gravações especiais (joint consensus).
• Na prática, bibliotecas/motores (Chubby/Spanner-geração).

7. 2 Raft

Descompromisso para aprendizado: seleção de líder, replicação de logs, configuração de ré.

Elation: temporizações aleatórias, votação de termos; um líder para o mandato.
AppendEntries: O líder estoura as gravações, monitora a correspondência do prefixo (índice/termo), o comit de fixação majoritária.
Read-path: lease-reads (com um líder forte) ou read-index para leitura linear.
Reconfig: «configuração compartilhada» (joint) - Os nós votam em dois clusters antes da transição.

Mais fácil de desenvolver/debag, invariantes fortes da ordem. O líder é um ponto de pressão.

7. 3 ZAB (ZooKeeper Atomic Broadcast) / Viewstamped Replication (VRR)

ZAB: Líder divulga transações, fase de recuperação, zxid (era + índice).
VRR: «vistas» (views) com replicante primário, semelhante ao Multi-Paxos de espírito.

8) CFT ilíder/multilídeo

8. 1 EPaxos

Sem um líder permanente, qualquer nó pode iniciar um comando.
Comandos de conflito recebem ordem parcial; Sem conflito - compactuado em 1-2 RPT localmente.
Ganhos na distribuição geográfica com baixa conflitância, mas complexos códigos de dependências/gráficos.

8. 2 Caesar, Mencius

Variações que otimizam atrasos/balanceamento e trabalho na WAN.

9) algoritmos BFT e família PoS

9. 1 PBFT (Practical BFT)

Três fases (pré-prepare/predare/commit), necessita de 3f + 1 nós.
Baixa latência em redes locais, caminhos multifacetados e mensagens de O (N ²).

9. 2 Tendermint (estilo BFT-PoS)

Rodadas com proposal e duas vozes (predote/precomit).
Um detector detector, temporais, sincronia parcial.
Bom para as redes permissioned/PoS com dezenas/centenas de validadores.

9. 3 HotStuff (e derivados)

O esquema de três fases foi unificado em «pacotes» com certificados de quórum (QC).
A complexidade linear das comunicações, o suporte a pacotes e a pipinização paralela são fáceis de implementar em blockchain (por exemplo, o ecossistema Diem/Move).
Com liminares (threshold signaturas), o tráfego diminui.

9. 4 PoW/consenso de poupança (resumo)

Não a BFT no sentido mais rigoroso, mas a convergência provável (a cadeia com mais trabalho). Virtudes: simplicidade/abertura; falhas: energia, £ segundos a minutos até a finalidade.

10) Leituras: lineares, sequenciais e em dinheiro

Leituras lineares: um líder com lease ativo ou através do read-index (Raft) → a confirmação através do quórum.
Sequenciais: pode ser lido a partir de qualquer nó, mas sem garantia de frescura.
Follower reads: Permitidos quando exigências fracas; Para o dinheiro, está bem.

11) Configuração de re (mudar a composição do cluster)

Requer duas configurações sobrepostas (joint consensus): qualquer comitiva passa por quórum de ambas as configurações sem «buracos».
Adicione/remova um, cumpra o tamanho do quórum.
A transferência de liderança (liderança transfer) reduz as quedas.

12) Desempenho e sintonização

12. 1 Atrasos

Algoritmos de liderança: 1 PTT por gravação (com um líder estável) + replicação.
Distribuição Geoespacial: WAN RENAULT domina → use regiões locais + replicagem regional cruzada ou abordagens EPaxos/HotStuff.

12. 2 Largada de banda

Batching (agrupamento de comandos), AppendEntries paralelos, edição-kesh do diário, aplicações paralelas (quando as operações são trocadas).
Disco: NVMe/Registro em um dispositivo separado, 'O _ DIRECTION '/AIO, grande' fsync '- interdição com restrições SLA (comprometimento durability/latency).

12. 3 Caudas p99

Evite os nós quentes (líder sempre sozinho): rotação periódica ou read-offload para os folkers.
Controle as pausas GC (JVM/Go), pinos CPU, NUMA.

13) Geografia e topologia

1 região, 3 zonas: cluster CFT clássico (N = 3/5).
2 regiões: evite - Não há quórum confiável para separar 1-1.
3 + regiões: líder no «meio» ou algoritmos ilimitados; é possível ter proxy/frentes locais com uma revista asincrona.

14) Questões práticas de exploração

14. 1 Snapshots e recuperação

Limite de tamanho de registro/número de operações.
Transferir o sistema para novos nós; Verificação de quantias de controle.

14. 2 Monitoramento

Liderança: Quem é o líder, quanto tempo (term/epoch) mudou.
Лаги: `append_latency`, `commit_index - applied_index`.

Saúde Quórum: «A maioria está viva/2f + 1?»

Tamanho do registro/taxa de compactação, fila de snapshots.
Para o BFT: proporção de votos, afastamento de signatários, atrasos de QC.

14. 3 Segurança/coerência do código

Versão do protocolo no fio, migração com compatibilidade de registro.
(Consulte «Bloqueios distribuídos»): prazo de liderança (term) para CRON/jobs.

15) Anti-pattern

Fazer um consenso para a moda, onde um DPD ou leitura quórum é suficiente sem ser seriado.
Misturar COP e AP sem limites claros (CAP) → um UX imprevisível.
Superestimar PoW/PoS para tarefas corporativas com dezenas de nós (difícil/caro).
Ignorar a configuração e os «quóruns que se cruzam» quando a composição é alterada.
Falta de read-barrier (lease/read-index) → leitura «suja».
Executar clusters de 2 nós (sem maioria).
Subestimar discos e fsync: «Tudo voa na memória» - antes do primeiro reinício.

16) Folha de cheque de seleção

1. O modelo de falha é CFT ou BFT?
2. Geografia: uma região/três zonas ou WAN? A RPT decide.
3. Semântica de leitura: Você precisa de leitura linear? Lease/read-index/folhetim-rids.
4. Carga: espera de p50/p99, throughput; se precisa de uma liderança multi.
5. Complexidade operacional: biblioteca/motor pronto (etcd/ZK/Consul/Raft-liba) vs sua própria implementação.
6. Reconfiguração frequente? Precisamos de uma joint consensus e ferramentas de migração.
7. Integração: Efeitos secundários externos - Há fencing por epoch/term?
8. Segurança: autenticação de nós, criptografia de canal, controle de versões de protocolo.
9. Playbooks de teste: partition, GC-stop, líder kill, slow disk, clock skew.
10. Observabilidade: métricas de líder/laje/registro e alertas configuradas.

17) Mini-guia: quando pegar

etcd/Raft-cluster para configurações/bloqueios/coordenação dentro da DC.
ZooKeeper/ZAB para serviços já amarrados em ZK (pilhas antigas, filas, liderança).
Multi-Paxos através de um serviço/biblioteca pronto em sistemas restritos.
ePaxos para distribuição geográfica e baixa conflitância de comandos.
Tendermint/HotStuff para redes permissionadas/leitor PoS com dezenas a centenas de validadores e exigências de finalidade.
Dínamo-similares/CRDT quando o consenso não é necessário, mas é importante disponibilidade/escala posterior à fusão.

18) Exemplos de interface (pseudo)

18. 1 Composição de gravação (estilo Raft)

pseudo client -> leader: Propose(cmd)
leader. appendLog(cmd)
leader. replicateToQuorum()
if quorum_acked:
leader. commit(index)
leader. apply(index)
leader. reply(client, ok)

18. 2 Read-index para leitura linear (Raft)

pseudo client -> any: LinearizableRead node -> leader: ReadIndex?
leader -> quorum: Heartbeat (barrier)
leader -> node: ReadIndex=commit_index node. wait_until(applied_index >= ReadIndex)
node. reply(client, state_at(ReadIndex))

18. 3 Configuração conjunta

pseudo old_conf + new_conf # quorums must intersect commit (entries under joint)
switch_to(new_conf)

18. 4 BFT (HotStuff-próximo)

pseudo propose(block)
collect votes -> QC lock on highest QC commit when have consecutive QCs across phases

19) FAQ

Porque não usamos dois nódulos e um tai breaker?
A: Dois nódulos sem um terceiro árbitro não dão quórum na separação. É preciso ≥3 (CFT) ou 3f + 1 (BFT).

Q: Do que Raft «mais fácil» Paxos?
A: Descomposição clara, invariantes compreensíveis do logo e configuração; mais fácil de implementar e acompanhar.

Como ler rápido sem carregar o líder?
A: Follower-reads (sequenciais) para não-ríticos ou lease-reads/read-index para lineares; armazenem-no.

O que mata o p99?
A: WAN-PTT, fsync disk, pés GC, líder superaquecido, grandes snapshots em «hora de ponta».

Q: O consenso é necessário para o cachê/catálogo?
A: Se houver consistency evolutiva suficiente, não. Se você precisar de invariantes transacionais, sim.

20) Resultado

O consenso é uma ferramenta de coerência e ordenamento rigorosos. Escolha um algoritmo com base no modelo de falha e geografia; forneça cruzamentos quórum, configuração de ré, leituras lineares onde for crítico e observabilidade. Não se esqueça de fencing para efeitos externos, snapshots e disciplina de revistas. Então a replicação do estado será previsível e os incidentes raros e compreensíveis.