CS Fundamentals Trainer · Guias
Consenso: Raft, eleição de líder e replicação de log
Como um grupo de máquinas concorda sobre um log apesar de quedas: quóruns, os termos do Raft, eleições aleatorizadas, replicação e a regra de commit, partições e o que sobrevive a elas, com uma simulação, injeção de falhas e duas animações passo a passo.
30 min de leitura
Um único servidor é simples: ele decide, e todos os outros acreditam. No momento em que você copia dados para vários servidores para sobreviver a falhas (veja replicação), precisa de uma resposta para uma pergunta difícil: quando os servidores discordam ou alguns deles não podem ser alcançados, qual resposta é a verdade? Consenso é a família de protocolos que faz um grupo de máquinas concordar sobre um valor, ou uma sequência de valores, mesmo quando algumas delas caem e as mensagens se atrasam ou se perdem. É o que está por baixo do etcd (e, portanto, do Kubernetes), do ZooKeeper, do Consul e dos metadados de muitos bancos de dados e filas.
Este guia explica o consenso por meio do Raft, o protocolo projetado para ser compreensível, e o mostra funcionando. Escrevi uma pequena simulação do Raft (eleição, replicação de log, quedas e partições) e a executei milhares de vezes; o código está no apêndice.
Leia isto primeiro: isto é uma simulação, não uma implementação de produção. Tudo o que é medido abaixo (tempos de eleição, a execução de segurança com 0 violações) vem de um modelo em Python de cerca de 150 linhas, em tempo simulado. Ele deixa de fora, de propósito, o que torna um deployment real do Raft seguro e utilizável: estado durável (
currentTerm,votedFore o log precisam ser gravados em disco antes de um nó responder), snapshots e compactação do log, mudanças de membros, pre-vote e transferência de liderança, leituras linearizáveis seguras, além de redes e discos reais (falhas parciais, discos lentos, saltos de relógio). A seção 5 lista esses pontos, e a seção 5.1 percorre a mudança de membros, por ser a que mais costuma ser feita errado. Os números mostram como o protocolo se comporta; não dizem nada sobre a velocidade ou a segurança de nenhum sistema real.
1. O problema: uma máquina de estados replicada
A forma padrão de construir um serviço tolerante a falhas é uma máquina de estados replicada: todo nó começa no mesmo estado e aplica os mesmos comandos na mesma ordem. Se os comandos são determinísticos, os estados permanecem idênticos. O consenso é como os nós concordam sobre esse log de comandos.
Diagram: A replicated log feeds identical state machines
O que um protocolo de consenso promete (os nomes dos livros didáticos):
- Acordo (agreement, segurança): dois nós nunca decidem valores diferentes para a mesma posição do log.
- Validade (validity): um valor decidido foi proposto por algum cliente; não é inventado.
- Terminação (termination, vivacidade): se nós suficientes funcionam e a rede se comporta bem o bastante por tempo suficiente, o sistema continua decidindo.
Há um limite bem conhecido: o resultado FLP (Fischer, Lynch e Paterson, 1985) prova que, em uma rede totalmente assíncrona, onde um nó lento não se distingue de um morto, nenhum protocolo determinístico consegue garantir que sempre termina se até um único nó puder cair. Os protocolos reais aceitam isso: eles permanecem sempre seguros e só progridem quando a rede é razoavelmente pontual (os timeouts aleatorizados do Raft são exatamente como ele contorna o FLP na prática). É a mesma troca do guia de CAP: quando não consegue alcançar uma maioria, um sistema de consenso escolhe a consistência e para de responder, em vez de arriscar duas respostas.
2. Quóruns: por que uma maioria
A ideia central é o quórum. Uma decisão precisa do acordo de uma maioria dos N nós, isto é, mais de N/2. Quaisquer duas maiorias compartilham pelo menos um nó, então uma maioria posterior sempre contém alguém que soube da decisão anterior. Essa sobreposição é o que impede que as duas metades de um cluster dividido decidam coisas diferentes.
| Nós N | Maioria | Falhas toleradas |
|---|---|---|
| 3 | 2 | 1 |
| 4 | 3 | 1 |
| 5 | 3 | 2 |
| 7 | 4 | 3 |
Duas consequências que você deve lembrar. Um número par de nós não ajuda: quatro nós ainda toleram apenas uma falha, como três, e precisam de uma maioria maior. E mais nós tornam as escritas mais lentas, não mais rápidas: toda escrita espera por uma maioria, então adicionar nós acrescenta trabalho de replicação e latência de cauda. Clusters de produção costumam ter 3 ou 5 membros; mais é para tolerar mais falhas simultâneas, não para escalar.
3. O Raft em uma página
O Raft divide o problema em eleição de líder, replicação de log e segurança. A cada momento cada nó é um seguidor (follower), um candidato (candidate) ou o líder (leader), e o tempo é dividido em termos numerados. Há no máximo um líder por termo.
Diagram: The three roles of a Raft node
- Todas as escritas passam pelo líder, que as acrescenta ao seu log e as replica.
- O líder envia heartbeats (mensagens AppendEntries vazias) para provar que está vivo.
- Um seguidor que não ouve nada durante um timeout de eleição aleatório presume que o líder se foi e inicia uma eleição.
- Toda mensagem carrega o termo do remetente. Um nó que vê um termo maior passa imediatamente a seguidor, e uma mensagem de um termo menor é rejeitada. Os termos são o relógio lógico do Raft; eles impedem que um líder antigo e confuso cause danos.
Eleição de líder
Quando o temporizador de um seguidor expira, ele incrementa seu termo, torna-se candidato, vota em si mesmo e pede votos aos outros. Um nó concede um voto por termo, por ordem de chegada, e só se o log do candidato estiver pelo menos tão atualizado quanto o seu (compare o termo da última entrada e depois o tamanho). Um candidato com votos de uma maioria torna-se o líder e começa a enviar heartbeats.
Percorra uma eleição depois que o líder cai. Ligue a opção para ver um voto dividido:
Interactive animation: raft election
Se dois candidatos dividem os votos, ninguém ganha, os temporizadores expiram de novo e começa um novo termo. A razão de os temporizadores serem aleatórios é tornar isso improvável. Testei isso na simulação: cinco nós, atrasos de mensagem de 5 a 15 ms, um heartbeat a cada 50 ms e 500 execuções para cada configuração do timeout de eleição, medindo o tempo desde o início até existir um primeiro líder:
| Faixa do timeout de eleição | Mediana até o primeiro líder | Percentil 99 | Eleições fracassadas por execução |
|---|---|---|---|
| 150 a 300 ms (variação de 150 ms) | 188 ms | 356 ms | 0,37 |
| 150 a 160 ms (quase igual) | 1 126 ms | 5 926 ms | 16,1 |
| 1 000 a 2 000 ms (longo) | 1 145 ms | 1 582 ms | 0,05 |
Uma faixa aleatória larga o suficiente torna as eleições rápidas e raramente repetidas. Uma faixa estreita demais faz os nós expirarem juntos e dividirem o voto repetidamente (16 eleições fracassadas por execução em média, e quase 6 segundos no percentil 99). Uma faixa longa demais quase nunca divide, mas o cluster fica sem líder por um segundo ou mais toda vez que precisa de um novo. A regra prática do artigo do Raft: o timeout deve ser muito maior que o tempo de broadcast (para os heartbeats chegarem a tempo) e muito menor que o tempo entre falhas. As implementações reais o ajustam à rede: por exemplo, 1 segundo dentro de um data center, mais entre regiões.
Quando derrubei o líder de um cluster de cinco nós 300 vezes, um novo líder era conhecido após uma mediana de 195 ms e 540 ms no percentil 99, e nenhuma das 300 escritas confirmadas foi perdida. Durante esse tempo o cluster não consegue aceitar escritas: a pausa do failover faz parte do design, e seus clientes precisam de retries com backoff (veja padrões de resiliência).
Replicação de log
O líder acrescenta um comando de cliente ao seu log como uma nova entrada (marcada com o termo atual) e depois a envia aos seguidores em mensagens AppendEntries. Cada mensagem nomeia a entrada que precede as novas (índice e termo); um seguidor só aceita se o seu próprio log tiver essa entrada (a verificação de log matching) e, caso contrário, recusa, e o líder recua e envia entradas anteriores até os logs concordarem. Uma entrada é confirmada (committed) quando o líder a guardou em uma maioria. Só então o líder a aplica à sua máquina de estados e responde ao cliente; os seguidores ficam sabendo do índice de commit por mensagens posteriores e aplicam a entrada também.
Interactive animation: raft replication
Com os cinco nós alcançáveis, a entrada é confirmada quando o líder e dois seguidores a guardam. Ligue a opção: com três nós isolados, o líder alcança apenas um seguidor, 2 de 5 não é maioria e a entrada nunca é confirmada. O lado minoritário precisa parar. Se continuasse, os dois lados de uma partição poderiam aceitar escritas e os dados divergiriam.
Diagram: Replicating one write through a leader and two followers
Note a regra sutil no passo de commit: um líder conta réplicas para confirmar apenas entradas do seu próprio termo. Entradas de termos anteriores são confirmadas indiretamente, quando uma entrada posterior do termo atual é confirmada depois delas. O artigo do Raft explica com uma figura por que confirmar uma entrada de termo antigo apenas contando réplicas poderia permitir que ela fosse sobrescrita depois; implementações como o etcd fazem o líder acrescentar uma entrada no-op assim que é eleito por esse motivo.
4. Por que é seguro
A segurança do Raft se apoia em duas regras que se encaixam.
- Um candidato precisa de uma maioria de votos, e um eleitor recusa um candidato cujo log esteja menos atualizado que o seu.
- Uma entrada só é confirmada depois que uma maioria a guardou.
Como quaisquer duas maiorias se sobrepõem, todo possível vencedor de uma eleição posterior estava na maioria que guardou cada entrada confirmada, então deve ter essa entrada, e a verificação de "atualizado" só o deixa vencer se ele as tiver todas. Entradas confirmadas nunca se perdem, e o log do vencedor é aquele com o qual todo seguidor é alinhado.
O experimento da partição
Cortei um cluster de cinco nós em uma minoria de dois (o líder antigo e um seguidor) e uma maioria de três, e enviei uma escrita a cada lado:
minority leader 0: log [(term 1, a=1), (term 1, lost=1)] commit index 1
majority leader 2: log [(term 1, a=1), (term 2, b=2)] commit index 2
after healing, node 0: log [(term 1, a=1), (term 2, b=2)] role: follower
O líder antigo continuou acreditando que era o líder e aceitou lost=1, mas não alcançou uma maioria, então nunca a confirmou e o cliente nunca recebeu sucesso. A maioria elegeu um novo líder no termo 2 e confirmou b=2. Quando a partição se desfez, o líder antigo viu o termo maior, passou a seguidor e sua entrada não confirmada foi sobrescrita pelo log da maioria. Esse é o resultado correto: a escrita que não foi confirmada desaparece, e tudo o que foi confirmado continua lá. A lição para os clientes: um timeout ou uma conexão perdida em uma escrita significa "desconhecido", não "falhou"; use comandos idempotentes ou uma chave de idempotência (veja os limites das chaves de idempotência).
Injeção de falhas
Um único cenário prova pouco, então deixei a simulação rodar aleatoriamente: 200 execuções de 60 passos, cada passo uma mistura aleatória de derrubar um nó (nunca abaixo de uma maioria viva), reiniciar um, cortar enlaces aleatórios, curar ou propor um comando. Depois de cada passo conferi duas propriedades: no máximo um líder por termo e os prefixos confirmados dos logs de todos os nós concordam. Resultado: 0 violações, com 4 917 entradas confirmadas no total. Isso é um teste de uma implementação simplificada, não uma prova, e o protocolo real foi especificado e verificado formalmente (os autores do Raft publicaram uma especificação em TLA+, e Paxos e Raft foram verificados em ferramentas como Verdi e Ivy); mas mostra o tipo de teste de que os protocolos distribuídos precisam. Ferramentas como o Jepsen existem para fazer isso contra sistemas reais.
5. O que a minha simulação deixa de fora
Ela tem cerca de 150 linhas e mantém o coração do Raft. Uma implementação real também precisa de:
- Persistência:
currentTerm,votedFore o log precisam chegar ao disco (fsync) antes de um nó responder. Se um nó esquecesse seu voto depois de uma reinicialização, poderia votar duas vezes no mesmo termo e quebrar a regra de um líder. Esse é também o motivo de a latência do disco ser o piso da latência de escrita do consenso. - Snapshots e compactação do log, para que o log não cresça sem limite e um nó que ficou ausente por muito tempo possa se atualizar recebendo um snapshot.
- Mudanças de membros, adicionar ou remover nós com segurança (mudanças de um servidor por vez ou o método de consenso conjunto).
- Pre-vote e transferência de liderança: sem o pre-vote, um nó que ficou isolado por uma partição continua aumentando seu termo e, quando volta, seu termo alto força um líder saudável a renunciar. Com o pre-vote, ele primeiro pergunta se poderia ganhar.
- Leituras linearizáveis: um líder recém-deposto pode não saber disso. Para responder a uma leitura com segurança, ele confirma a liderança com uma rodada de heartbeats (ReadIndex) ou conta com um lease baseado em deriva de relógio limitada. Ler de um seguidor é mais rápido, mas pode ser obsoleto.
- Batching, pipelining e controle de fluxo para vazão.
É por isso que você não deve escrever o seu próprio consenso. Use uma implementação testada (a biblioteca Raft do etcd, o HashiCorp Raft, o ZAB do ZooKeeper, um serviço gerenciado) e gaste seu esforço em usá-la corretamente.
5.1 Um exemplo trabalhado: mudando os membros com consenso conjunto
Adicionar ou remover servidores parece inofensivo e é uma das operações mais perigosas de um cluster, porque nós diferentes ficam sabendo de uma nova configuração em momentos diferentes. Se alguns nós contam votos com a lista antiga de membros e outros com a nova, duas maiorias diferentes podem existir ao mesmo tempo e, com elas, dois líderes no mesmo termo.
A falha. Um cluster de três (S1, S2, S3) cresce para cinco (S1 a S5) em um único passo. A entrada de configuração chega primeiro a S4, S5 e S3; S1 e S2 estão lentos e ainda usam a lista antiga. Agora S1 pede um voto a S2 e vence com 2 de 3, a maioria da configuração antiga. No mesmo instante, S3 pede a S4 e S5 e vence com 3 de 5, a maioria da nova. Dois líderes, mesmo termo, e ambos podem confirmar entradas diferentes. Verifiquei isso por força bruta sobre todos os subconjuntos de nós (script no apêndice): ['S1', 'S2'] e ['S3', 'S4', 'S5'] são maiorias da configuração antiga e da nova sem nenhum nó em comum. Trocar {S1, S2, S3} por {S3, S4, S5} tem o mesmo problema (['S1', 'S2'] e ['S3', 'S4']).
O consenso conjunto (o método do artigo do Raft) evita isso com uma configuração intermediária, C(old,new), na qual uma decisão precisa de uma maioria dos membros antigos e de uma maioria dos membros novos. Para a troca de {S1, S2, S3} por {S3, S4, S5}:
| Passo | O que o líder faz | Quem precisa concordar para confirmar |
|---|---|---|
| 1 | Acrescenta C(old,new) ao seu log e o replica. Cada nó usa uma configuração assim que ela aparece no seu log, confirmada ou não. | 2 de {S1, S2, S3} e 2 de {S3, S4, S5} |
| 2 | Enquanto C(old,new) está em vigor, eleições e entradas também exigem as duas maiorias. Nem a antiga nem a nova sozinha pode decidir nada. | as duas maiorias |
| 3 | Quando C(old,new) é confirmada, acrescenta C(new). | 2 de {S3, S4, S5} |
| 4 | Quando C(new) é confirmada, os membros antigos que não estão no novo conjunto (S1, S2) deixam de ser necessários. Um líder que não está em C(new) renuncia depois de confirmá-la. |
A força bruta confirma a propriedade que importa: na fase conjunta, todo quórum possível se sobrepõe tanto aos quóruns só da configuração antiga quanto aos só da nova, e também a todos os outros quóruns conjuntos (todos os 64 quóruns conjuntos, 4 só da antiga e 16 só da nova no caso de três para cinco, sem nenhum par disjunto). Em nenhum momento dois líderes podem ser eleitos em configurações diferentes.
Se o líder cair no meio: se C(old,new) não tinha chegado a uma maioria, o novo líder nunca a vê e a mudança simplesmente se perde (tente de novo). Se ela tinha sido confirmada, qualquer nó que possa vencer uma eleição precisa tê-la (a regra de eleição exige um log atualizado), então o novo líder termina a mudança acrescentando C(new). Os dois desfechos são seguros porque toda decisão envolve sempre uma maioria dos membros antigos até que C(new) seja confirmada.
Mudanças de um servidor por vez são a alternativa mais simples, usada pela maioria das implementações hoje: adicionar ou remover um servidor de cada vez. Uma maioria de N nós e uma maioria de N+1 (ou N-1) sempre compartilham um nó, então não é preciso uma fase conjunta. A força bruta verificou todos os tamanhos de 1 a 8 nas duas direções e não encontrou nenhum par disjunto. A regra, portanto, é: nunca mude mais de um membro votante por passo e espere cada mudança ser confirmada antes de começar a próxima. Ir de três para cinco nós são duas mudanças, não uma.
O que o exemplo não cobre: servidores novos devem entrar primeiro como aprendizes sem voto (learners) e se atualizar (caso contrário, um nó novo e lento pode travar as confirmações enquanto é contado), e um servidor removido que não foi avisado pode atrapalhar o cluster com eleições, a menos que se use pre-vote ou uma regra de check-quorum. Esses são os detalhes que as bibliotecas reais implementam e que a minha simulação não implementa.
6. Onde o consenso se encaixa e onde não
O consenso é lento e sensível em comparação com a replicação comum: cada decisão custa uma ida e volta a uma maioria e um flush de disco, e o líder é um gargalo. Por isso é usado para dados pequenos e críticos, o plano de controle, e não para o plano de dados em volume:
- Eleição de líder e locks distribuídos para outros sistemas (veja o fencing token abaixo).
- Configuração e descoberta de serviços (etcd, Consul, ZooKeeper).
- Metadados de bancos de dados e filas: qual nó é dono de qual shard (veja sharding), a atribuição de tópicos e partições de um broker.
- Bancos de dados fortemente consistentes, como CockroachDB, TiDB, Spanner e YugabyteDB, executam um grupo de consenso (Raft ou Paxos) por faixa ou shard e assim escalam executando muitos grupos pequenos.
Para a replicação em volume, um banco de dados costuma usar uma replicação baseada em líder mais simples e barata, que não é consenso (o guia de replicação mostra o que um seguidor assíncrono pode perder).
Fencing tokens: um lock não basta
Um bug comum: o cliente A obtém um lock de um serviço apoiado em consenso, pausa (uma longa pausa de coleta de lixo, uma parada da VM), o lock expira, o cliente B o obtém, e então A acorda e escreve, acreditando que ainda tem o lock. A correção é um fencing token: o serviço de locks distribui um número que aumenta a cada concessão, o cliente o envia com cada escrita, e o armazenamento recusa qualquer token menor que um já visto. O consenso lhe dá um serviço de locks correto; ele não consegue impedir que um cliente pausado aja com base em uma crença obsoleta, então a verificação precisa acontecer no recurso.
Raft, Paxos e os outros
O Paxos (Lamport) resolve o mesmo problema e veio primeiro; sua forma básica concorda sobre um único valor, e o Multi-Paxos o repete para um log. É mais difícil de explicar e de implementar por completo, e essa foi a motivação do Raft. O ZAB (ZooKeeper) e a Viewstamped Replication são parentes próximos. Todos esses assumem que os nós caem e param; não defendem contra nós que mentem ou estão comprometidos. Sobreviver a isso exige protocolos tolerantes a falhas bizantinas (PBFT e os protocolos por trás dos blockchains), que precisam de 3f+1 nós para tolerar f defeituosos e são muito mais caros.
7. Erros comuns
- Executar dois ou quatro nós: dois não toleram nada, quatro toleram o mesmo que três.
- Espalhar um cluster pequeno por regiões sem pensar na latência: cada escrita espera a ida e volta até a maioria mais próxima, e perder uma região pode perder a maioria.
- Tratar uma escrita que deu timeout como falha e repetir um comando não idempotente.
- Ler de um seguidor e esperar a última escrita.
- Locks sem fencing tokens, ou leases que supõem que os relógios nunca derivam.
- Usar o armazenamento de consenso como banco de dados ou fila de uso geral: alguns megabytes de metadados são a escala certa.
- Timeouts de eleição muito curtos em um host carregado ou virtualizado: eleições espúrias e liderança instável.
- Discos lentos sob o log: o
fsyncestá no caminho crítico de toda escrita. - Reinicializações em sequência de uma maioria ao mesmo tempo.
8. Coisas a mencionar em uma entrevista
- A ideia da máquina de estados replicada: concordar sobre o log, aplicar de forma determinística.
- Quóruns de maioria e por que quaisquer dois se sobrepõem; por que 3 ou 5 nós e por que tamanhos pares não ajudam.
- Os papéis e termos do Raft; timeouts de eleição aleatorizados e o voto dividido; a regra de voto "log pelo menos tão atualizado".
- A regra de commit, o lado minoritário da partição parando enquanto a maioria continua, e a sobrescrita de entradas não confirmadas.
- O FLP em uma frase, e que o Raft é sempre seguro, mas só vivo quando a rede é pontual.
- Para que o consenso é usado (metadados, eleição de líder, locks) e para que não é (dados em volume).
- Fencing tokens; leituras linearizáveis; a pausa do failover como custo de disponibilidade.
Resumo rápido
- O consenso faz um grupo de nós concordar sobre um log apesar de quedas e perda de mensagens; uma máquina de estados replicada o aplica de forma idêntica em todo lugar.
- As decisões precisam de uma maioria, porque quaisquer duas maiorias se sobrepõem: 3 nós toleram 1 falha, 5 toleram 2, e um número par não acrescenta nada.
- Raft: um líder por termo, timeouts de eleição aleatorizados, um voto por termo e só para um log atualizado; commit quando uma maioria guardou a entrada.
- Na simulação, as eleições levaram uma mediana de 188 ms com uma boa faixa de timeout e falharam repetidamente com uma faixa estreita; as quedas de líder foram curadas em cerca de 195 ms e não perderam nenhuma escrita confirmada; 200 execuções aleatórias de falhas não tiveram nenhuma violação de segurança.
- O lado minoritário de uma partição para, e suas entradas não confirmadas são sobrescritas depois da cura, então uma escrita não confirmada significa desconhecido.
- Use uma implementação comprovada para dados pequenos e críticos, acrescente fencing tokens aos locks e espere uma pequena pausa a cada failover.
Apêndice: o código dos experimentos
Um arquivo Python 3 sem dependências. Ele simula cinco nós em tempo simulado (milissegundos) com atrasos de mensagem aleatórios, de modo que cada execução é repetível a partir da sua semente. Implementa a eleição de líder com timeouts aleatorizados, a regra do log atualizado, o AppendEntries com a verificação de log matching, a regra de commit (apenas entradas do termo do próprio líder são confirmadas contando réplicas) e a sobrescrita de sufixos de log conflitantes. Não implementa persistência, snapshots, mudanças de membros, pre-vote nem leituras, e seus nós nunca perdem o estado quando caem (um nó reiniciado mantém seu termo, voto e log, o que um nó real precisa garantir gravando em disco antes de responder). Os números do guia vêm da seção __main__; serão idênticos na sua máquina porque tudo usa semente.
Uma simulação do Raft: eleições, replicação, partições e injeção de falhas
"""A small Raft simulation: leader election, log replication and failures, in simulated time (milliseconds)."""
import heapq, random, itertools
class Sim:
def __init__(self, n=5, seed=0, timeout=(150, 300), delay=(5, 15), heartbeat=50):
self.n, self.rnd, self.timeout, self.delay, self.hb = n, random.Random(seed), timeout, delay, heartbeat
self.t = 0; self.q = []; self.seq = itertools.count()
self.term = [0]*n; self.voted = [None]*n; self.role = ['follower']*n; self.log = [[] for _ in range(n)] # entries: (term, command)
self.commit = [0]*n; self.alive = [True]*n; self.deadline = [0]*n; self.votes = [set() for _ in range(n)]
self.next = [[1]*n for _ in range(n)]; self.match = [[0]*n for _ in range(n)]
self.cut = set() # pairs (a,b) that cannot talk
self.leaders = {} # term -> set of leaders (safety check: at most one per term)
self.elections = 0; self.first_leader_at = None; self.applied = [[] for _ in range(n)]
for i in range(n): self.reset_timer(i)
for i in range(n): self.at(self.deadline[i], ('tick', i))
def at(self, when, ev): heapq.heappush(self.q, (when, next(self.seq), ev))
def reset_timer(self, i): self.deadline[i] = self.t + self.rnd.uniform(*self.timeout)
def send(self, a, b, msg):
if (a, b) in self.cut or (b, a) in self.cut: return
self.at(self.t + self.rnd.uniform(*self.delay), ('msg', b, a, msg))
def last(self, i): return (self.log[i][-1][0] if self.log[i] else 0, len(self.log[i]))
def become_follower(self, i, term):
if term > self.term[i]: self.term[i] = term; self.voted[i] = None
self.role[i] = 'follower'
def start_election(self, i):
self.term[i] += 1; self.role[i] = 'candidate'; self.voted[i] = i; self.votes[i] = {i}; self.elections += 1
self.reset_timer(i)
for j in range(self.n):
if j != i: self.send(i, j, ('vote?', self.term[i], self.last(i)))
def become_leader(self, i):
self.role[i] = 'leader'; self.leaders.setdefault(self.term[i], set()).add(i)
if self.first_leader_at is None: self.first_leader_at = self.t
self.next[i] = [len(self.log[i]) + 1]*self.n; self.match[i] = [0]*self.n; self.match[i][i] = len(self.log[i])
self.broadcast(i)
def broadcast(self, i):
if not self.alive[i] or self.role[i] != 'leader': return
for j in range(self.n):
if j == i: continue
prev = self.next[i][j] - 1; pt = self.log[i][prev-1][0] if prev else 0
self.send(i, j, ('append', self.term[i], prev, pt, self.log[i][prev:], self.commit[i]))
self.at(self.t + self.hb, ('beat', i, self.term[i]))
def propose(self, cmd):
for i in range(self.n):
if self.alive[i] and self.role[i] == 'leader':
self.log[i].append((self.term[i], cmd)); self.match[i][i] = len(self.log[i]); return i
def advance_commit(self, i):
for idx in range(len(self.log[i]), self.commit[i], -1):
if self.log[i][idx-1][0] == self.term[i] and sum(m >= idx for m in self.match[i]) > self.n // 2:
self.commit[i] = idx; break
def handle(self, i, src, msg):
kind = msg[0]
if kind in ('vote?', 'append') and msg[1] > self.term[i]: self.become_follower(i, msg[1])
if kind == 'vote?':
_, term, (lt, ll) = msg
ok = term == self.term[i] and self.voted[i] in (None, src) and (lt, ll) >= self.last(i) # candidate's log at least as up to date
if ok: self.voted[i] = src; self.reset_timer(i)
self.send(i, src, ('vote', self.term[i], ok))
elif kind == 'vote':
_, term, ok = msg
if term > self.term[i]: self.become_follower(i, term)
elif self.role[i] == 'candidate' and term == self.term[i] and ok:
self.votes[i].add(src)
if len(self.votes[i]) > self.n // 2: self.become_leader(i)
elif kind == 'append':
_, term, prev, pt, entries, lc = msg
if term < self.term[i]: self.send(i, src, ('ack', self.term[i], False, 0)); return
self.role[i] = 'follower' if self.role[i] != 'leader' else self.role[i]; self.reset_timer(i)
if prev > len(self.log[i]) or (prev and self.log[i][prev-1][0] != pt): self.send(i, src, ('ack', self.term[i], False, prev)); return
self.log[i] = self.log[i][:prev] + list(entries) # overwrite any conflicting suffix
self.commit[i] = max(self.commit[i], min(lc, len(self.log[i])))
self.send(i, src, ('ack', self.term[i], True, prev + len(entries)))
elif kind == 'ack':
_, term, ok, idx = msg
if term > self.term[i]: self.become_follower(i, term); return
if self.role[i] != 'leader' or term != self.term[i]: return
if ok: self.match[i][src] = max(self.match[i][src], idx); self.next[i][src] = self.match[i][src] + 1; self.advance_commit(i)
else: self.next[i][src] = max(1, self.next[i][src] - 1)
def run(self, until):
while self.q and self.q[0][0] <= until:
when, _, ev = heapq.heappop(self.q); self.t = when
if ev[0] == 'tick':
i = ev[1]
if self.alive[i]:
if self.role[i] != 'leader' and self.t >= self.deadline[i]: self.start_election(i)
self.at(self.t + 10, ('tick', i))
elif ev[0] == 'beat':
_, i, term = ev
if self.alive[i] and self.role[i] == 'leader' and self.term[i] == term: self.broadcast(i)
elif ev[0] == 'msg':
_, dst, src, msg = ev
if self.alive[dst]: self.handle(dst, src, msg)
self.t = until
def leader(self):
ls = [i for i in range(self.n) if self.alive[i] and self.role[i] == 'leader']
return max(ls, key=lambda i: self.term[i]) if ls else None
def crash(self, i): self.alive[i] = False; self.role[i] = 'follower'
def restart(self, i): self.alive[i] = True; self.role[i] = 'follower'; self.reset_timer(i)
def safety(s):
one_leader_per_term = all(len(v) <= 1 for v in s.leaders.values())
# committed prefixes must agree on every node
ok = True
for a in range(s.n):
for b in range(s.n):
k = min(s.commit[a], s.commit[b])
if s.log[a][:k] != s.log[b][:k]: ok = False
return one_leader_per_term, ok
if __name__ == "__main__":
# 1. time to elect a leader from a cold start, by election timeout range
for rng in ((150, 300), (150, 160), (1000, 2000)):
ts = []; splits = 0
for seed in range(500):
s = Sim(seed=seed, timeout=rng); s.run(6000); ts.append(s.first_leader_at); splits += s.elections > 1 and s.first_leader_at is not None and (s.elections - 1)
ts = sorted(t for t in ts if t is not None)
print(f"timeout {rng}: median first leader {ts[len(ts)//2]:.0f} ms, 99th percentile {ts[int(len(ts)*.99)]:.0f} ms, worst {ts[-1]:.0f} ms, failed elections before the first leader, per run {splits/500:.2f}")
# 2. crash the leader: how long until a new leader is known, and does a committed write survive?
outage = []; lost = 0
for seed in range(300):
s = Sim(seed=seed); s.run(1000); l = s.leader(); s.propose("x=1"); s.run(1300)
assert s.commit[l] == 1 # the write is committed on the leader
s.crash(l); t0 = s.t
while s.leader() is None and s.t < t0 + 5000: s.run(s.t + 5)
outage.append(s.t - t0); s.run(s.t + 1000)
nl = s.leader(); lost += nl is None or s.log[nl][:1] != [(s.log[nl][0][0], "x=1")]
assert all(safety(s))
outage.sort(); print(f"leader crash: new leader after median {outage[150]:.0f} ms, 99th percentile {outage[297]:.0f} ms; committed writes lost: {lost} of 300")
# 3. a partition: the minority side cannot commit, the majority can, and after healing the minority's entries are overwritten
s = Sim(seed=3); s.run(1000); old = s.leader(); s.propose("a=1"); s.run(1200)
minority = {old, (old + 1) % 5}; majority = set(range(5)) - minority
for a in minority:
for b in majority: s.cut.add((a, b))
s.propose("lost=1"); s.run(1800) # the old leader accepts a write it can only reach one follower with
print("minority leader", old, "log", s.log[old], "commit", s.commit[old])
for _ in range(200):
l = max((i for i in majority if s.role[i] == 'leader'), key=lambda i: s.term[i], default=None)
if l is not None: break
s.run(s.t + 20)
l = max((i for i in majority if s.role[i] == 'leader'), key=lambda i: s.term[i]); s.log[l].append((s.term[l], "b=2")); s.match[l][l] = len(s.log[l]); s.run(s.t + 600)
print("majority leader", l, "log", s.log[l], "commit", s.commit[l])
s.cut.clear(); s.run(s.t + 1500)
print("after healing: old leader's log", s.log[old], "role", s.role[old], "term", s.term[old], safety(s))
# 4. fault injection: random crashes, partitions and writes; check the two safety properties all along
bad = 0; committed_total = 0
for seed in range(200):
s = Sim(seed=1000 + seed); rnd = random.Random(seed); k = 0
for step in range(60):
s.run(s.t + rnd.uniform(20, 200))
r = rnd.random()
if r < .15:
v = rnd.randrange(5)
if sum(s.alive) > 3 and s.alive[v]: s.crash(v)
elif r < .3:
for v in range(5):
if not s.alive[v]: s.restart(v); break
elif r < .4: s.cut = {(a, b) for a in range(5) for b in range(5) if a < b and rnd.random() < .4}
elif r < .5: s.cut = set()
else: k += 1; s.propose(f"c{k}")
if not all(safety(s)): bad += 1
committed_total += max(s.commit)
print(f"fault injection: 200 runs x 60 steps, safety violations: {bad}, entries committed in total: {committed_total}")
# 5. quorum arithmetic
for n in (3, 5, 7): print(f"{n} nodes: majority {n//2+1}, tolerates {n - (n//2+1)} failures")
Por que mudanças de membros exigem cuidado: uma verificação por força bruta da sobreposição de quóruns
Roda em uma fração de segundo com a biblioteca padrão. Enumera todas as maiorias das configurações antiga, nova e conjunta e procura duas que não compartilhem nenhum nó.
"""Why a cluster cannot switch configuration in one step, and how joint consensus and
single-server changes avoid the problem. Brute force over all subsets of nodes."""
from itertools import combinations
def majorities(cfg):
need = len(cfg) // 2 + 1
return [set(c) for k in range(need, len(cfg) + 1) for c in combinations(sorted(cfg), k)]
def disjoint_pair(qs_a, qs_b):
for a in qs_a:
for b in qs_b:
if not (a & b):
return sorted(a), sorted(b)
return None
def report(title, qa, qb):
r = disjoint_pair(qa, qb)
print(f"{title}: {'DISJOINT quorums exist, e.g. ' + str(r[0]) + ' and ' + str(r[1]) if r else 'every pair of quorums overlaps'}")
old = {"S1", "S2", "S3"}
new = {"S1", "S2", "S3", "S4", "S5"}
# 1. direct switch: some nodes still use the old configuration, others already the new one
report("direct switch 3 -> 5 nodes (old config vs new config)", majorities(old), majorities(new))
# 2. joint consensus: during C_old,new a decision needs a majority of C_old AND a majority of C_new
joint = [a | b for a in majorities(old) for b in majorities(new)]
report("joint phase vs old config alone", joint, majorities(old))
report("joint phase vs new config alone", joint, majorities(new))
report("joint phase vs joint phase", joint, joint)
# 3. replacing 3 nodes by 3 other nodes
old2, new2 = {"S1", "S2", "S3"}, {"S3", "S4", "S5"}
report("direct switch {S1,S2,S3} -> {S3,S4,S5}", majorities(old2), majorities(new2))
joint2 = [a | b for a in majorities(old2) for b in majorities(new2)]
report("joint {S1,S2,S3}+{S3,S4,S5} vs old alone", joint2, majorities(old2))
report("joint {S1,S2,S3}+{S3,S4,S5} vs new alone", joint2, majorities(new2))
# 4. single-server changes (one node added or removed at a time)
for n in range(1, 8):
a = {f"S{i}" for i in range(n)}
bigger = a | {f"S{n}"}
r1 = disjoint_pair(majorities(a), majorities(bigger))
print(f"single-server change {n} -> {n+1} nodes: {'DISJOINT' if r1 else 'overlap'}", end=" | ")
if n > 1:
smaller = set(sorted(a)[:-1])
r2 = disjoint_pair(majorities(a), majorities(smaller))
print(f"{n} -> {n-1}: {'DISJOINT' if r2 else 'overlap'}")
else:
print()
# 5. two changes at once (3 -> 5) is exactly the unsafe case from step 1
print("sizes of quorum sets: old", len(majorities(old)), "new", len(majorities(new)), "joint", len(joint))
Fontes
- Diego Ongaro e John Ousterhout, In Search of an Understandable Consensus Algorithm (USENIX ATC 2014), e a tese de doutorado de Ongaro, Consensus: Bridging Theory and Practice (2014), que cobre mudanças de membros, snapshots, pre-vote e a interação com clientes.
- O site do Raft, com a visualização e a lista de implementações.
- Leslie Lamport, Paxos Made Simple (2001), e The Part-Time Parliament (1998).
- Michael Fischer, Nancy Lynch e Michael Paterson, Impossibility of Distributed Consensus with One Faulty Process (JACM, 1985).
- Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly), capítulo 9, "Consistency and Consensus", e seu ensaio How to do distributed locking, sobre fencing tokens.
- A documentação do etcd sobre sua implementação do Raft, nós learner e a tabela de tolerância a falhas; as análises do Jepsen em jepsen.io.
- Diego Ongaro e John Ousterhout, In Search of an Understandable Consensus Algorithm, seção 6 (mudanças na composição do cluster, consenso conjunto), e a tese de doutorado de Ongaro, capítulo 4 (mudanças de um servidor por vez).
Pratique este tema: System Design System Design › Distributed systems