QuePaxa: escapando da tirania dos timeouts no consenso

Os protocolos de replicação de máquina de estados (SMR) mais usados, como Multi-Paxos e Raft, elegem um líder por vez, porque proposers simultâneos interferem de forma destrutiva, e substituem um líder que falhou por trocas de view disparadas por timeout. Os autores chamam os problemas que daí surgem de tirania dos timeouts. A liveness só vale sob sincronia parcial, então atraso alto, conectividade assimétrica ou um ataque de negação de serviço (DoS) ao líder podem reduzir ou parar o progresso. Os timeouts precisam ser conservadoramente grandes para evitar trocas de view falsas, o que deixa a recuperação lenta. E exigem ajuste manual, de modo que um líder lento, mas não a ponto de estourar o timeout, pode continuar no comando mesmo havendo líderes mais rápidos.

Este artigo do SOSP 2023 (Koblenz) vem da EPFL, do ISTA e Mysten Labs, do Trinity College e da UCL. Ele pergunta se um protocolo de SMR prático consegue manter a eficiência de caso normal de um desenho baseado em líder sem depender de timeouts. A resposta é o QuePaxa, apenas para falhas por parada (crash), com n ≥ 2f+1 réplicas.

Termos principais: os proposers conduzem o consenso e os recorders guardam estado de forma passiva, e toda réplica exerce os dois papéis. Um interval summary register (ISR) é a estrutura de espaço constante que um recorder mantém. O fast path é a confirmação em uma ida e volta por um líder designado. Um hedging schedule escalona quando os proposers entram em ação, e o ajuste por multi-armed bandit (MAB) escolhe líderes e atrasos.

Vale conhecer antes: quorums e SMR baseada em líder do Paxos Made Simple, eleição de líder por timeout como no Raft, e o resultado FLP, que diz que consenso determinístico é impossível em uma rede assíncrona e que o QuePaxa contorna com aleatoriedade. Dois pareamentos meus, não do artigo: as paralisações causadas por trocas de view falsas lembram os ciclos que se auto-sustentam de Metastable Failures in Distributed Systems, e o Ambulance, um artigo posterior, ataca o mesmo problema dos timeouts para falhas bizantinas.

• Um núcleo assíncrono randomizado. O protocolo abstrato executa rodadas sobre um broadcast por limiar idealizado (tcast). Cada réplica anexa uma prioridade aleatória à sua proposta, e três passos de tcast produzem os conjuntos de propostas existentes (E), comuns (C) e universais (U), com U ⊆ C ⊆ E em todas as réplicas. Uma réplica decide quando a melhor proposta de E é igual à melhor de U e, caso contrário, leva a melhor de C para a rodada seguinte. Os autores argumentam que uma rodada decide com probabilidade acima de 1/2 diante de um adversário de rede que não enxerga o conteúdo, ou seja, que pode atrasar e reordenar mensagens, mas não vê o conteúdo nem a memória das réplicas (TLS entre as réplicas satisfaz isso), então a terminação esperada leva menos de duas rodadas.
• Proposers e recorders. O protocolo concreto tem quatro fases por rodada, com step = 4 × rodada + fase, e cada passo custa uma ida e volta entre um proposer e uma maioria de recorders. Um recorder é um ISR: guarda o primeiro valor do passo atual e o máximo inteiro do passo anterior, e descarta valores obsoletos. Um proposer que vê um passo mais alto o alcança. Proposers concorrentes, portanto, cooperam, enquanto no Paxos um segundo prepare pode interromper o primeiro proposer indefinidamente.
• Um fast path de uma ida e volta. Na primeira rodada de um slot, o líder designado anexa uma prioridade máxima reservada. Se sua proposta chega primeiro a um quorum, ele decide depois de uma ida e volta, como um líder já preparado do Multi-Paxos ou do Raft. Só a primeira rodada é baseada em líder, porque um adversário forte que controla o escalonamento sempre consegue fazer uma rodada com líder falhar, e as rodadas seguintes não têm líder.
• Hedging no lugar de timeouts. Os proposers formam um schedule: o líder tem atraso zero, o próximo proposer tem atraso δ, o seguinte 2δ, e assim por diante. Um proposer só propõe se não viu progresso. Um δ pequeno demais causa esforço redundante, mas nunca perda de liveness, e com δ dentro de um fator constante do atraso real os autores argumentam que só um número constante de proposers se ativa por passo, o que mantém a comunicação em O(n).
• Ajuste automático. A escolha de líder e de schedule é tratada como um problema de MAB. Épocas de tamanho fixo têm cada uma um líder estável, as primeiras 2n+1 épocas alternam os líderes em round-robin, dando duas a cada réplica, e depois as réplicas são ordenadas pelo tempo médio observado de conclusão das épocas. O QuePaxa continua observando o líder e troca de líder se ele ficar abaixo do próximo do schedule.
• Uma otimização para LAN. Os submitters enviam os lotes a todas as réplicas e o consenso concorda em IDs de lote, como hashes, o que reduz a banda do líder. Os autores observam que o NOPaxos e o Rabia usam otimizações parecidas, específicas de data center.
• Garantias. Os apêndices B e C provam os protocolos abstrato e concreto, e modelos em Promela foram verificados quanto à segurança com o model checker SPIN.

O protótipo é escrito em Go 1.18, com 4.368 linhas medidas pelo CLOC, sobre TCP com Protobuf e gRPC, com batching nos submitters e nos proposers e com pipelining, mas sem reconfiguração. As bases de comparação são Multi-Paxos, Raft, EPaxos e Rabia. Os autores relatam que o código existente de Multi-Paxos e EPaxos não trata a falha do líder corretamente (um novo líder pula a fase prepare), então o EPaxos aparece só nas execuções de caso normal e os experimentos de falha usam o Multi-Paxos (2.743 linhas) e o Raft (2.802 linhas) novos, escritos por eles.

Os experimentos rodam na Amazon EC2, com réplicas c4.4xlarge e submitters c4.2xlarge, em uma configuração LAN (Norte da Virgínia) e uma WAN (Tóquio, Mumbai, Singapura, Irlanda, São Paulo). A aplicação é um key-value store de string para string, com requisições de 17 bytes e submitters Poisson em malha aberta. Cada execução dura um minuto e é repetida 3 vezes. Os experimentos cobrem latência e throughput de caso normal, escalabilidade de 3 a 13 réplicas, um adversário de rede simulado (5 réplicas, WAN), o efeito do atraso de hedging ou do timeout sobre a liveness e a recuperação (5 réplicas, tempo de ida e volta médio de 180 ms, carga constante de 25k comandos por segundo, líder derrubado aos 15 s) e a descoberta do melhor líder em cinco máquinas heterogêneas em Oregon, com 80k comandos por segundo. A configuração-base do model checking é de 2 proposers, 3 recorders e duas rodadas: o primeiro modelo em Promela foi verificado de forma exaustiva em menos de três minutos, e o segundo, com processos recorder separados, levou cerca de 24 horas com bitstate hashing, que pode deixar alguns caminhos sem explorar.

Estes são os resultados relatados pelos autores.

• Caso normal, LAN. O QuePaxa satura em 584k comandos por segundo sob um limite de latência mediana de 5,8 ms, contra 400k sob 5,6 ms do Multi-Paxos. Os autores atribuem a diferença à otimização de IDs de lote. O EPaxos sem execução chega a 699k (2% de conflitos), o que eles atribuem ao particionamento dos comandos entre instâncias, uma técnica ortogonal a este trabalho.
• Caso normal, WAN. O resumo do artigo informa 250k comandos por segundo, comparável ao Multi-Paxos. O EPaxos com execução tem latência mediana cerca de 400 ms maior que a do QuePaxa na faixa de 50k a 200k, e sem execução cerca de 60 ms maior na faixa de 0 a 150k. O throughput do Rabia na WAN cai para menos de 10 comandos por segundo, com latência acima de 2 s, o que os autores ligam à sua suposição de que o atraso das mensagens é pequeno em relação ao intervalo entre requisições.
• Escalabilidade. O QuePaxa cai de 584k com 3 réplicas para 467k com 13 (cerca de 20%) e fica em média 35% acima do Multi-Paxos, uma diferença que desaparece quando a otimização de IDs de lote é desligada. O EPaxos quebra com mais de 5 réplicas por causa de um array fixo no código.
• Ataque simulado. O adversário soma até 500 ms de latência de saída a uma minoria de réplicas, em épocas de 5 s. O QuePaxa sustenta pelo menos 75k comandos por segundo com latência mediana de 380 ms, enquanto Multi-Paxos e Raft saturam em 2,5k.
• Hedging contra timeouts. O QuePaxa mantém 25k comandos por segundo qualquer que seja o atraso de hedging, mesmo abaixo do tempo de ida e volta de 180 ms, e seu custo são mensagens extras de vários proposers. Multi-Paxos e Raft perdem throughput e depois a liveness quando o timeout se aproxima do tempo de ida e volta, e precisam de cerca de 1,8 vez esse valor (acima de 330 ms entregam 25k).
• Recuperação. Depois da queda do líder, o QuePaxa se recupera em 303 a 473 ms para todo atraso de hedging. Multi-Paxos e Raft levam ordens de grandeza a mais com timeouts próximos demais do tempo de ida e volta, não chegam a se estabilizar abaixo de 200 ms e, com atrasos acima de 500 ms, se recuperam em cerca de uma ida e volta mais o timeout.
• Melhor líder. Começando com a máquina mais fraca (t2.large) como líder, Multi-Paxos e Raft ficam em 5,2 ms porque ela nunca estoura o timeout. O QuePaxa converge para o melhor líder depois de 4 segundos e chega a 3,8 ms, 1,4 ms a menos.

A ideia é uma separação limpa: a aleatoriedade só ordena as propostas, então o líder passa a ser um privilégio e não uma exigência. O artigo admite vários limites.

• O hedging não é de graça. Um δ pequeno demais custa proposers redundantes, menos sucesso no fast path e, no pior caso, comunicação O(n²). Um adversário forte também consegue derrotar uma rodada com líder, então a liveness sob ataque depende das rodadas sem líder, mais lentas.
• Escopo. O protocolo cobre só falhas por parada, supõe um adversário que não enxerga o conteúdo (canais laterais ficam fora do escopo) e o protótipo não tem reconfiguração. O líder continua sendo um gargalo, que os autores ligam à queda de 20% no throughput com 13 réplicas, e o particionamento à la EPaxos, os quorums flexíveis, schedules melhores e a reexploração de réplicas que não são líderes ficam como trabalho futuro.
• Complexidade e revisão. Os autores dizem que a adaptabilidade custa alguma complexidade de protocolo, e que os apêndices (prioridades, provas, model checking, a comparação com o Rabia) não passaram pelo mesmo nível de revisão por pares que o corpo do artigo.

Os pontos a seguir são uma leitura das evidências, não afirmações do artigo.

• O ganho na LAN não vem do núcleo do consenso. A diferença de 584k contra 400k vem dos IDs de lote, e com essa otimização desligada os dois protocolos ficam praticamente iguais. O texto não relata Multi-Paxos nem Raft com a mesma otimização, então o núcleo é mostrado como equivalente a eles, não como melhor.
• As bases de comparação nas falhas são dos próprios autores. O Multi-Paxos e o Raft novos foram escritos para esses experimentos, e o artigo mostra como a recuperação é sensível à implementação: a recuperação do Multi-Paxos explode com um timeout 100 ms maior que o do Raft, o que os autores atribuem ao desenho de threads. Extrapolando a fórmula do próprio artigo (uma ida e volta mais um timeout) para um timeout bem ajustado de cerca de 330 ms, chega-se a mais ou menos 500 ms, a mesma ordem de grandeza dos 303 a 473 ms do QuePaxa. A vantagem principal passa a ser que atrasos pequenos são seguros, mais do que uma recuperação mais rápida com configurações iguais.
• O ataque é simulado e aleatório. A legenda da Figura 8 descreve ataques aleatórios a uma minoria de réplicas, em uma única configuração WAN com 5 réplicas. A ameaça que motiva a Seção 2, um atacante que acha cada novo líder por análise de tráfego e redireciona o ataque, não é descrita como testada, e nenhum DoS real nem sequestro de rota é executado.
• A adaptação é testada com diferenças estáticas. A Seção 1 promete reagir a condições que variam no tempo, mas o único experimento de ajuste automático tem heterogeneidade fixa de máquinas, cinco réplicas, um líder inicial e uma região. O tamanho da época não é informado, e nada se diz sobre a convergência em outros tamanhos de cluster ou depois que as condições mudam. A fase de exploração também é descrita como 2n+1 épocas com duas por réplica, o que soma 2n.
• O limite de liveness e o protótipo diferem. A probabilidade acima de 1/2 por rodada supõe prioridades de alta entropia, enquanto o protótipo usa um valor aleatório de baixa entropia mais o ID da réplica como desempate (Apêndice A.1), caso em que os autores dizem que a análise precisa de ajuste. A probabilidade ajustada não é dada, e o model checker cobre só a segurança, em uma configuração pequena.
• Detalhes de relato. O texto não dá a dispersão entre as três execuções de um minuto nem descreve armazenamento estável nas execuções medidas. A legenda da Figura 9 nomeia dois painéis, enquanto o texto usa um terceiro (passos por slot) como proxy do custo de banda. O EPaxos é dado como 16,5% acima do QuePaxa, mas 699k sobre 584k é cerca de 19,7%, e 16,5% é a diferença medida em relação ao EPaxos. O colapso do Rabia na WAN é contra um protocolo feito para LANs, o que os autores reconhecem, então diz pouco sobre consenso randomizado em geral.

• Quorums flexíveis no fast path, schedules de hedging melhores (iniciar os dois primeiros proposers juntos ou atribuir atrasos a partir de tempos medidos) e reexploração periódica das réplicas que não são líderes, tudo isso deixado pelos autores como trabalho futuro.
• Combinar o QuePaxa com desenhos particionados ou com vários líderes e com os objetivos que o artigo põe de lado, como localidade na WAN, erasure coding e tolerância a falhas bizantinas, em que o Ambulance é uma tentativa posterior de atacar o problema dos timeouts.
• Testar as partes adaptativas sob um atacante que acompanha o líder e sob condições que mudam, medindo a convergência em vários tamanhos de cluster e relatando o overhead do hedging em bytes.
• Comparar o fast path embutido com a abordagem de shim do Jetpack, um artigo posterior que adiciona um caminho de uma ida e volta ao redor de um protocolo sem modificá-lo, para ver o que cada caminho custa.