Papers
In Search of an Understandable Consensus Algorithm
Diego Ongaro, John Ousterhout · USENIX Annual Technical Conference (ATC) 2014, 2014
O problema: consenso distribuído difícil de entender e de implementar
Sistemas distribuídos que precisam sobreviver a falhas de máquina normalmente replicam um mesmo log de comandos em vários servidores e usam um algoritmo de consenso para garantir que todos concordem na mesma sequência, mesmo quando algumas réplicas caem ou a rede falha. Antes do Raft, Paxos era o algoritmo de referência para esse problema, e é comprovadamente correto, mas os autores argumentam que ele é notoriamente difícil de entender: sua formulação original resolve apenas o consenso sobre um único valor de forma abstrata, e a tarefa de compor isso em um log prático, com múltiplas decisões, troca de membros do cluster e desempenho aceitável, fica largamente a cargo de quem implementa — o que historicamente levou a implementações divergentes e ad hoc. Ongaro e Ousterhout decidiram tratar a compreensibilidade como objetivo de design de primeira classe, no mesmo nível de correção e eficiência, e não apenas como um efeito colateral desejável. Para validar essa meta empiricamente, os autores conduziram um estudo com 43 alunos de duas universidades, que aprenderam Raft e Paxos e depois responderam questionários sobre ambos: os alunos pontuaram cerca de 23% melhor nas perguntas sobre Raft do que nas sobre Paxos, e 33 dos 43 avaliaram Raft como mais fácil de entender.
A ideia central: um líder único, mandatos (terms) e dois tipos de RPC
Para tornar o problema mais tratável, Raft decompõe o consenso em três subproblemas relativamente independentes: eleição de líder, replicação de log e segurança. Diferente de esquemas simétricos, Raft elege sempre um único líder por vez, que passa a ter responsabilidade exclusiva por aceitar comandos dos clientes, anexá-los ao próprio log e replicá-los aos demais servidores (seguidores). O tempo é dividido em mandatos (terms), números inteiros crescentes que funcionam como uma espécie de relógio lógico: cada mandato tem no máximo um líder, e comparar números de mandato permite que os servidores detectem informação obsoleta, como um líder antigo que ainda acredita estar no comando. A eleição é disparada por um temporizador aleatório: se um seguidor não recebe nenhuma mensagem do líder dentro desse intervalo, ele se torna candidato, incrementa seu mandato e solicita votos aos demais via uma RPC chamada RequestVote. A comunicação entre líder e seguidores usa apenas dois tipos de RPC no total: RequestVote, para eleições, e AppendEntries, usada tanto para replicar entradas de log quanto, quando vazia, como sinal de heartbeat que impede novas eleições enquanto o líder está ativo. O intervalo de tempo de eleição sugerido no paper fica entre 150 e 300 milissegundos, justamente para reduzir a chance de duas eleições ocorrerem ao mesmo tempo (split vote).
Replicação de log e a garantia de consistência entre réplicas
Quando um cliente envia um comando, o líder primeiro o anexa ao próprio log e então dispara RPCs AppendEntries em paralelo para replicá-lo nos seguidores. Uma entrada é considerada 'comprometida' (committed) assim que o líder confirma que ela foi replicada com sucesso em uma maioria dos servidores do cluster — a partir daí, é seguro aplicá-la à máquina de estados, e todas as entradas anteriores no log também passam a ser consideradas comprometidas. Para manter os logs coerentes entre si, Raft se apoia na Propriedade de Correspondência de Log (Log Matching): se duas réplicas têm uma entrada com o mesmo índice e o mesmo mandato, então seus logs são idênticos em todas as entradas até aquele índice. Isso é garantido porque cada AppendEntries inclui o índice e o mandato da entrada imediatamente anterior, e um seguidor rejeita a mensagem se esses dados não baterem com seu próprio log; quando há divergência, o líder força o log do seguidor a convergir para o seu, sobrescrevendo entradas conflitantes. Há uma sutileza importante nas regras de commit: o líder não pode concluir que uma entrada de um mandato anterior está comprometida apenas contando réplicas dela — ele só pode tratar entradas antigas como comprometidas depois que uma entrada do seu próprio mandato atual for replicada em maioria.
Segurança: a restrição de eleição e a Propriedade de Completude do Líder
Para garantir que uma entrada já comprometida nunca seja perdida, Raft restringe quem pode se tornar líder: ao responder a um RequestVote, um servidor nega o voto a um candidato cujo log esteja 'menos atualizado' que o seu próprio, comparando primeiro o mandato da última entrada e, em caso de empate, o comprimento do log. Essa restrição de eleição garante que qualquer candidato capaz de vencer uma eleição (isto é, obter voto de maioria) já contém, em seu próprio log, todas as entradas comprometidas até aquele momento. Esse resultado é formalizado pela Propriedade de Completude do Líder: se uma entrada foi comprometida em determinado mandato, ela estará presente nos logs de todos os líderes de mandatos posteriores. Essa propriedade é uma de cinco garantias de segurança que o paper enuncia e prova formalmente: Segurança de Eleição (no máximo um líder eleito por mandato), Líder Apenas-Anexa (um líder nunca sobrescreve ou apaga entradas do próprio log, só anexa), Correspondência de Log, Completude do Líder, e Segurança da Máquina de Estados (se um servidor já aplicou uma entrada em determinado índice à sua máquina de estados, nenhum outro servidor aplicará um comando diferente nesse mesmo índice). Juntas, essas garantias são o que permite a Raft manter um log replicado consistente mesmo diante de líderes que falham no meio do processo.
Extensões práticas e legado: reconfiguração de cluster e adoção em sistemas reais
Além do núcleo do algoritmo, o paper trata de dois problemas práticos que qualquer implementação real de consenso replicado precisa resolver. O primeiro é a mudança de composição do cluster (por exemplo, trocar servidores ou mudar o tamanho da maioria necessária) sem parar o sistema; Raft resolve isso com um mecanismo de consenso conjunto (joint consensus), em que o cluster passa por uma configuração de transição que exige maioria tanto na configuração antiga quanto na nova antes de finalizar a troca, evitando uma janela em que dois líderes independentes poderiam ser eleitos simultaneamente em configurações diferentes. O segundo é o crescimento ilimitado do log ao longo do tempo, resolvido por compactação via snapshotting: um servidor pode periodicamente salvar o estado completo da máquina de estados e descartar o log anterior a esse ponto. O objetivo declarado dos autores — priorizar compreensibilidade sem abrir mão de correção — teve efeito prático mensurável: hoje Raft é o algoritmo de consenso por trás de diversos sistemas de infraestrutura distribuída amplamente usados em produção, como etcd, Consul, CockroachDB e TiKV, que dependem dele como motor central de replicação.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.