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, votedFor e 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):

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 NMaioriaFalhas toleradas
321
431
532
743

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

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çãoMediana até o primeiro líderPercentil 99Eleições fracassadas por execução
150 a 300 ms (variação de 150 ms)188 ms356 ms0,37
150 a 160 ms (quase igual)1 126 ms5 926 ms16,1
1 000 a 2 000 ms (longo)1 145 ms1 582 ms0,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.

  1. Um candidato precisa de uma maioria de votos, e um eleitor recusa um candidato cujo log esteja menos atualizado que o seu.
  2. 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:

É 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}:

PassoO que o líder fazQuem precisa concordar para confirmar
1Acrescenta 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}
2Enquanto 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
3Quando C(old,new) é confirmada, acrescenta C(new).2 de {S3, S4, S5}
4Quando 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:

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

8. Coisas a mencionar em uma entrevista

Resumo rápido

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

Pratique este tema: System Design System Design › Distributed systems

Mais guias