Paxos e Raft

Paxos e Raft são os dois protocolos de consenso práticos mais influentes, fornecendo um acordo tolerante a falhas de travamento em um log replicado que sustenta sistemas de coordenação do mundo real.

Definition

Paxos e Raft são protocolos baseados em quórum que permitem que um conjunto de réplicas concorde em uma sequência ordenada de comandos (um log replicado) apesar de falhas de travamento, garantindo que as entradas confirmadas nunca sejam perdidas ou reordenadas, desde que a maioria das réplicas permaneça disponível.

Scope

Este tópico abrange a família Paxos — Paxos de decreto único, Multi-Paxos e seus refinamentos de engenharia — e o protocolo Raft, que reorganiza as mesmas garantias em torno de um líder explícito, replicação de log e mudança de associação para facilitar a compreensão. Ele aborda os papéis de proponentes/aceitadores e líderes/seguidores, interseção de quórum, eleição de líder e termos, correspondência de log e as preocupações práticas de snapshots e reconfiguração.

Core questions

• Como a interseção de quórum e a numeração de propostas mantêm Paxos seguro em diferentes rodadas e mudanças de líder?
• Como Raft decompõe o consenso em eleição de líder, replicação de log e segurança?
• Quais desafios de engenharia surgem ao transformar esses protocolos em sistemas de produção?

Key theories

Paxos de decreto único e Multi-Paxos

Paxos alcança acordo sobre um valor através de fases de preparação e aceitação governadas por números de proposta monotônicos e quóruns majoritários; Multi-Paxos amortece a fase de preparação em um fluxo de decisões lideradas por um líder estável para construir um log replicado.

Decomposição do Raft

Raft atinge a mesma segurança que Paxos ao eleger um único líder por termo, fazendo com que o líder anexe entradas que os seguidores replicam e impondo uma propriedade de correspondência de log, trocando deliberadamente a minimalidade pela compreensibilidade e facilidade de implementação.

Da especificação ao sistema em execução

A implantação de Paxos na prática exige o tratamento de falhas de disco, concessões de líder, compactação de log e reconfiguração, detalhes frequentemente ignorados no algoritmo original, mas essenciais para a correção e o desempenho.

Clinical relevance

Paxos e Raft são executados em serviços de coordenação amplamente utilizados, bancos de dados distribuídos e armazenamentos de configuração; compreendê-los é essencial para construir ou operar qualquer sistema que deva manter as réplicas fortemente consistentes através de falhas.

History

Lamport descreveu Paxos em seu artigo de 1998 'part-time parliament' e o esclareceu em 'Paxos made simple' (2001); Chandra e colegas relataram as realidades de torná-lo viável em escala em 2007; e Ongaro e Ousterhout introduziram Raft em 2014 para tornar garantias equivalentes muito mais fáceis de ensinar e implementar.

Debates

Compreensibilidade versus minimalidade em protocolos de consenso

Raft foi explicitamente projetado para ser mais fácil de entender do que Paxos, provocando debate sobre se sua estrutura adicional (um líder forte) sacrifica a flexibilidade; os proponentes argumentam que a compreensibilidade reduz os bugs de implementação, enquanto outros observam que as variantes de Paxos podem ser mais gerais.

Key figures

• Leslie Lamport
• Diego Ongaro
• John Ousterhout
• Tushar Chandra

Seminal works

• lamport1998
• ongaro2014
• chandra2007

Frequently asked questions

Paxos e Raft são algoritmos fundamentalmente diferentes?

Não — eles resolvem o mesmo problema com o mesmo núcleo de quórum majoritário e garantias de segurança equivalentes. Raft principalmente reorganiza Paxos em torno de um líder forte e um log explícito para tornar o protocolo mais fácil de entender e implementar.