Pesto: preparando consultas BFT de alto desempenho

O jeito usual de construir um banco de dados tolerante a falhas bizantinas (BFT) é ordenar cada operação com um protocolo de consenso BFT, como PBFT ou HotStuff, e alimentar um motor de banco com o log. Esse desenho abre mão do paralelismo da carga de trabalho, exige várias idas e vindas para cada requisição de uma transação interativa e, depois de particionado em shards, empilha o two-phase commit sobre o consenso. O Basil, um key-value store BFT recente, evita a ordenação total integrando replicação, controle de concorrência otimista e two-phase commit em uma única camada, mas só oferece GET e PUT. Os autores dão um exemplo: um join de duas tabelas com um milhão de linhas cada, que se sobrepõem em uma única chave, exige um milhão de leituras em cada tabela no cliente para devolver uma só linha.

Este artigo do SOSP 2025 (Seul), de Florian Suri-Payer, Neil Giridharan, Liam Arzola, Shir Cohen, Lorenzo Alvisi e Natacha Crooks, da Cornell University, da UC Berkeley e da UC San Diego, estende o Basil no Pesto, que oferece transações SQL interativas sem ordem total. Há dois problemas a resolver. Uma consulta agora roda no servidor, então seu resultado precisa ser confiável mesmo que as réplicas deliberadamente não sejam mantidas idênticas, e o controle de concorrência otimista costuma ir mal em consultas de intervalo.

Cinco termos sustentam o artigo. Byz-serializability significa que todos os participantes corretos observam um estado consistente com uma execução sequencial das transações, e independência bizantina significa que nenhum grupo de participantes defeituosos consegue decidir sozinho o resultado de uma operação. Replicação inconsistente significa que as réplicas processam as requisições em qualquer ordem. Uma range read é qualquer consulta que não seja uma busca de uma linha pela chave primária, e SemanticCC é a verificação de concorrência que usa os predicados das consultas.

Vale conhecer antes: consenso e replicação de máquina de estados (o Paxos Made Simple cobre a versão para falhas por parada; as referências BFT do próprio artigo são PBFT e HotStuff, não Paxos), leituras fantasma e serializabilidade (o A Critique of ANSI SQL Isolation Levels, que o artigo cita para o caso dos fantasmas) e o Spanner, que o artigo cita como exemplo de armazenamento tolerante a falhas por parada construído sobre máquinas de estados replicadas.

• Sem ordenação, execução guiada pelo cliente. As réplicas processam as requisições em qualquer ordem e em paralelo, e os clientes orquestram a execução e o commit. O modelo é de sincronia parcial, com n = 5f+1 réplicas, das quais até f podem ser defeituosas, e qualquer número de clientes defeituosos. Os autores precisam de 5f+1 para a independência bizantina, porque num protocolo com líder e 3f+1 um cliente bizantino e o líder poderiam combinar para se antecipar às transações (front-run).
• Dois tipos de leitura. Uma point read (uma linha pela chave primária) usa o GET do Basil: pergunta a pelo menos 2f+1 réplicas, espera f+1 respostas e fica com a versão válida mais recente, em que uma versão commitada traz um certificado de commit e uma preparada precisa vir de f+1 réplicas. Toda outra consulta é uma range read enviada a pelo menos 3f+1 réplicas. As escritas ficam em buffer no cliente, e uma escrita condicional faz antes uma leitura de reconhecimento (reconnaissance read) para achar as linhas a alterar. O Calvin usa o mesmo termo para uma leitura preliminar que descobre os conjuntos de leitura e escrita, mas o artigo não cita o Calvin.
• Sincronização de snapshot. Se as respostas não batem, o cliente coleta votos de snapshot: os ids das transações por trás das linhas que cada réplica leu. Ele mantém os ids que aparecem em f+1 votos e propõe esse snapshot. As réplicas buscam com os votantes as transações que faltam, junto com um certificado, e reexecutam. É preciso acordo apenas sobre as linhas ativas, as que satisfazem o predicado da consulta. Um snapshot só pode conter transações que alguma réplica correta possui, então um cliente defeituoso só consegue travar a própria consulta. As réplicas podem ler uma versão commitada mais fresca do que a do snapshot, preferindo frescor à consistência.
• SemanticCC. Uma consulta vira uma árvore de operadores cujos scans carregam predicados de filtro, e as réplicas devolvem esses predicados junto com o resultado. A validação aborta uma transação apenas se uma escrita concorrente satisfaz um de seus predicados ou torna obsoleta uma versão ativa. Isso evita o lock lógico da tabela inteira que a validação otimista simples exigiria para impedir fantasmas, e é inspirado nos precision locks.
• Monotonicidade de escrita. Reverificar todas as escritas passadas de uma tabela seria impraticável, então cada predicado carrega uma versão da tabela, o timestamp da última escrita quando ele rodou, e um escritor com timestamp abaixo de um limiar aborta, com um período de tolerância para escritores atrasados. Isso obriga os quorums das range reads a se intersectarem com os de commit, então os clientes pegam a menor versão de tabela entre pelo menos 3f+1 réplicas. Os snapshots a reduzem para logo abaixo da versão ignorada mais antiga.
• Commit herdado do Basil. Validação ordenada por timestamp, com escritas preparadas visíveis de forma otimista e dependências de leitura rastreadas. Um commit precisa de 3f+1 votos de commit e um abort precisa de f+1 votos de abort. Com 5f+1 votos de commit a transação termina em uma ida e volta, senão um segundo estágio registra a decisão em um shard. A recuperação de clientes que falham é herdada do Basil.

O Pesto é um protótipo em C/C++ que parte do código aberto do Basil, com Protobuf sobre TCP, assinaturas ed25519, HMAC-SHA256 e hashing Blake3. Sua camada de consultas adapta o Peloton. As bases de comparação são o Peloton sem replicação, o Peloton sobre HotStuff (Peloton-HS) e sobre BFT-SMaRt (Peloton-Smart), o Postgres sozinho e com um backup síncrono (Postgres-PB) e o CockroachDB, sem replicação e em memória. As duas bases de SMR são relaxadas de propósito: as réplicas executam em paralelo sem determinismo e um primário responde, o que os autores dizem não ser tolerante a falhas, mas um limite superior.

Tudo roda em memória com isolamento serializável em máquinas m510 do CloudLab (8 núcleos, 64 GB, ping de 0,15 ms), com clientes em laço fechado, f = 1 e execuções de 60 segundos, incluindo 15 segundos de aquecimento e de resfriamento. As cargas são o TPC-C com 20 warehouses, o AuctionMark, o SEATS e um microbenchmark baseado no YCSB com 10 tabelas de 1M de chaves, uniforme ou Zipfian com coeficiente 1,1. Os experimentos cobrem desempenho geral, comparação com o Basil e sharding, falhas forçadas do caminho eager e falha de réplica.

Estes são os resultados relatados pelos autores.

• TPC-C. O Pesto chega a 1784 tx/s, contra 1777 do Peloton, 1781 do Postgres, 758 do Peloton-HS, 785 do Peloton-Smart e 1257 do Postgres-PB. A latência fica abaixo de 1,5× a do Peloton e a do Postgres (igual sob carga alta) e é 3,9× e 2,7× menor que a do Peloton-HS e a do Peloton-Smart. As point reads levam uma ida e volta, assim como 99,9% das range reads, e 97% dos commits seguem o caminho rápido.
• Por que iguala o sem replicação. As leituras vão apenas a um quorum, então no TPC-C, cheio de point reads, o Pesto distribui a carga e pode superar a própria variante sem replicação, que bate num gargalo de CPU em 1379 tx/s.
• AuctionMark e SEATS. O Pesto fica a até 1,36× e 1,22× do Peloton sem replicação e a até 1,94× do Postgres. A latência é 5× e 3× menor que a do Peloton-HS e a do Peloton-Smart no AuctionMark, e 4,6× e 3,4× no SEATS, com ganhos de throughput de 1,1× e 1,2× porque tudo é limitado por CPU.
• Contra as point reads do Basil. A transação Stock-level do TPC-C, com muitos scans, fica mais de 11× mais rápida. Em um microbenchmark de scan o ganho é de 16,6× para 10 mil linhas, e de 110× quando o predicado casa com 1 linha em 100.
• Sharding. O TPC-C escala 1,64× com dois shards e 2,21× com três, a até 1,23× dos 4862 tx/s relatados pelo Basil, apesar de uma pilha SQL completa. O CockroachDB tem 4,46× menos throughput com um shard, e seu pico, com até 9 shards, fica 2,91× abaixo do Pesto.
• Estresse. Na carga uniforme, falhar o caminho eager em toda transação custa cerca de 9% de throughput e eleva a latência em 1,38×, e a inconsistência simulada (escritas omitidas ou atrasadas em um terço das réplicas) custa cerca de 5%. Na Zipfian custam 32% e 48%, porque leituras mais lentas ampliam as janelas de conflito.
• Falha de réplica. Nenhuma interrupção de progresso, porque a coordenação é guiada pelo cliente, mas o caminho rápido se perde. Na uniforme, o throughput cai 14% com o caminho rápido desligado e 24% com um timeout de cerca de 4 ms, e a latência sobe 1,59× e 2,7×. Na Zipfian o custo é de 5% e 1,25× sem o caminho rápido e de 36% e 2,5× com o timeout.

A ideia é bem argumentada: só se precisa de consistência nas linhas que a consulta toca, e os números do TPC-C sugerem que as réplicas em geral já concordam. O artigo e seu apêndice admitem vários limites.

• Range reads podem falhar e repetir. O sucesso não é determinístico, já que commits mais frescos em algumas réplicas ou snapshots remendados fazem as respostas divergirem. A terminação é argumentada apenas depois de um ponto livre de contenção, e o artigo diz que nenhum sistema interativo pode prometer commits sob contenção.
• A contenção é o ponto fraco. As execuções de estresse Zipfian perdem 32% e 48% do throughput, o que os autores atribuem a janelas de conflito maiores.
• Escopo do protótipo. O texto principal assume que cada consulta atinge um único shard. O apêndice deixa consultas entre shards fora do protótipo, assume que toda réplica tem uma contraparte operada pela mesma autoridade de confiança nos outros shards e deixa em aberto a execução sem essa confiança. Consultas aninhadas podem exigir reescrita ou snapshots mais grossos. Clientes bizantinos autenticados ainda podem corromper dados por meio de transações legítimas, e as provas estão em um suplemento rotulado como não revisado por pares.

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

• "Iguala o sem replicação" é um resultado do TPC-C. No AuctionMark e no SEATS o Pesto fica abaixo do Peloton e do Postgres, e no TPC-C ele iguala em parte por distribuir as leituras entre seis réplicas por shard, contra uma máquina nos sistemas sem replicação. O throughput por máquina não é relatado. O CockroachDB roda sem replicação, então mostra escalabilidade, não uma comparação de tolerância a falhas.
• As bases de SMR são um espantalho relaxado. Remover determinismo e tolerância a falhas as favorece, o que é justo como limite superior, mas um motor paralelo determinístico de verdade não é avaliado. Os ganhos de 2,3× e de 2,7× a 3,9× são em boa parte idas e vindas de consenso numa LAN com ping de 0,15 ms, e implantações de longa distância não são medidas.
• As falhas são só paradas, e não há base de comparação. As réplicas são paradas ou tornadas inconsistentes por omissão. O comportamento bizantino ativo, como votos forjados ou propostas obsoletas, é argumentado em provas, não medido. A Figura 9 mostra apenas variantes do Pesto, então a vantagem sobre uma troca de líder é afirmada, não comparada.
• Não há ablação do SemanticCC. O artigo diz que predicados de filtro só raramente abortam sem necessidade, mas nenhum experimento o compara com validação no nível da tabela nem varia os períodos de tolerância, cujos valores o texto não informa.
• O tamanho do quorum é fácil de ler errado. A Seção 5.5 descreve f+1 respostas iguais para as range reads, enquanto a Seção 6.1.3 o eleva para 3f+1 quando a monotonicidade de escrita é adicionada, e a avaliação e o apêndice usam 3f+1. O protocolo final é o de 3f+1.
• "SQL completo" se apoia no Peloton. O artigo não relata teste de conformidade nem lista de recursos sem suporte, e só o TPC-C é particionado em shards.

• Consultas entre shards sem réplicas contrapartes da mesma autoridade, e consultas aninhadas entre shards, que o apêndice deixa em aberto.
• Snapshots mais baratos e mais frescos: gossip de transações preparadas, ajuste de quantas versões os votos carregam, coleta de 4f+1 votos e compressão dos ids de transação de hashes de 256 bits para algo próximo de timestamps, como o apêndice esboça.
• Comparação com BFT baseado em líder sob falhas e lentidões, tema em que o Ambulance, artigo posterior de autores em comum que o Pesto não cita, estuda líderes lentos na replicação de máquina de estados BFT.
• Ablações do SemanticCC e dos níveis de tolerância, execuções de longa distância e medições com réplicas e clientes ativamente bizantinos.