Tiga: acelerando transações geodistribuídas com relógios sincronizados

Bancos de dados transacionais geo-replicados como o Spanner dividem os dados em shards, replicam cada shard entre regiões e prometem transações com serializabilidade estrita por cima. A construção usual empilha um protocolo de controle de concorrência (por exemplo, bloqueio e commit em duas fases) sobre um protocolo de consenso (por exemplo, Multi-Paxos), e essa pilha pode custar vários round trips de longa distância (WRTTs) por commit. Os trabalhos anteriores que a encurtam gastam CPU com rastreamento de dependências e detecção de ciclos, ou só chegam ao ótimo em casos especiais, como transações comutativas.

Este artigo do SOSP 2025 (Seul), de Jinkun Geng e Shuai Mu (Stony Brook University), Anirudh Sivaraman (New York University) e Balaji Prabhakar (Stanford University), pergunta se um protocolo tolerante a falhas consegue confirmar mais transações em 1 WRTT com menos overhead. A resposta é o Tiga, que ordena as transações por timestamps futuros obtidos de relógios sincronizados.

Quatro termos sustentam o artigo. O headroom é a estimativa de atraso somada ao horário de envio de uma transação para formar seu timestamp futuro. O fast path confirma em 1 WRTT quando um super quorum de réplicas de cada shard envolvido relata o mesmo estado, e o slow path acrescenta uma sincronização de log conduzida pelo leader, com 1,5 a 2 WRTTs segundo o resumo. O acordo de timestamp é a troca entre os leaders dos shards que fixa um timestamp por transação. A inversão de timestamp é a armadilha em que a ordenação por timestamp dá serializabilidade, mas perde a ordem em tempo real que a serializabilidade estrita exige.

Vale conhecer antes: linearizabilidade versus serializabilidade estrita (a primeira é local a um shard, a segunda abrange vários shards), o Multi-Paxos do Paxos Made Simple, o Calvin, cuja ordenação determinística está por trás da base de comparação Calvin+, e, para a linha de ordenação pela rede que os trabalhos relacionados discutem, o NOPaxos, o Eris e o Hydra. A lista de sistemas OLTP distribuídos que abre o artigo também inclui o FoundationDB e o TiDB. Um pareamento meu, não do artigo: o Raft não é citado, mas é a replicação de log baseada em leader mais conhecida e fica próximo dos leaders por shard do Tiga.

• Consolidação. Controle de concorrência e consenso viram um só protocolo, então uma única rodada de mensagens executa a transação com serializabilidade estrita e a replica. Cada shard tem 2f + 1 réplicas, uma delas o leader do shard. O artigo mira transações one-shot, escritas como stored procedures com conjuntos de leitura e escrita conhecidos, e trata as interativas por uma técnica de decomposição descrita em seu relatório técnico.
• Ordenação proativa. O coordenador carimba a transação com o horário de envio mais um headroom: o maior atraso de ida medido do coordenador até um super quorum de réplicas de cada shard envolvido, mais uma margem de 10 ms na implementação. Um super quorum tem 1 + f + ⌈f/2⌉ réplicas, as mais próximas do coordenador. Os servidores guardam as transações em uma fila de prioridade e as liberam quando o relógio local passa do timestamp, então ordens de chegada diferentes ainda resultam em uma única ordem de processamento.
• Detecção de conflitos e execução. Dois mapas registram, por chave, o timestamp da última transação liberada, e uma transação que chega com timestamp menor que o de uma transação conflitante já liberada não pode entrar na fila. O leader então eleva o timestamp para seu relógio local, enquanto o follower o mantém e espera a sincronização de log do leader. Os leaders executam as transações liberadas sobre dados multiversão, e os followers apenas as acrescentam ao log.
• A verificação do fast path. As respostas rápidas trazem o timestamp da transação e um hash XOR incremental do log da réplica (SHA-1 de 160 bits por entrada). Uma transação é confirmada no fast path em um shard quando o coordenador recebe respostas coincidentes de um super quorum que inclui o leader, e no todo quando todos os leaders usaram o mesmo timestamp. Como no Fast Paxos, um quorum simples de f + 1 não deixaria um novo leader distinguir transações confirmadas das não confirmadas.
• Acordo de timestamp. Os leaders trocam seus timestamps e tomam o máximo. Se todos coincidem, o custo é de 0,5 WRTT. Se um leader usou o máximo mas os outros não, ele espera mais uma rodada de 0,5 WRTT antes de liberar, o que evita a inversão de timestamp (a Figura 5 mostra como três transações quebrariam a ordem em tempo real sem isso). Se um leader usou um valor menor, ele revoga a execução, um desfazer interno que não é rollback da aplicação, adota o máximo e executa de novo.
• Modos, slow path e recuperação. Quando os leaders estão na mesma região, como na replicação total, o acordo roda antes da execução (preventivo) e custa só latência de LAN. Quando nenhum grupo de leaders fica dentro de um limiar como 10 ms, a execução vem primeiro e é verificada depois (detectivo). Um gerenciador de views replicado, que poderia ser construído sobre o ZooKeeper, conduz as trocas de view e prefere leaders na mesma região. Um novo leader reconstrói seu log a partir de f + 1 réplicas: o maior prefixo sincronizado mais as entradas mantidas por ⌈f/2⌉ + 1 delas. Os coordenadores não guardam estado e checkpoints aceleram a recuperação.

O Tiga é construído sobre o código do Janus, então as bases de comparação compartilham biblioteca de RPC e runtime. Os autores acrescentaram o Tiga, o Detock e o Calvin+, uma variante do Calvin que troca a camada de Paxos pelo Nezha (um protocolo de consenso baseado em relógios, de parte dos mesmos autores, cujo multicast ordenado por prazo inspirou o Tiga) e assim economiza pelo menos 1 WRTT. No total o Tiga é comparado com 8 bases: 2PL+Paxos com wound-wait, OCC+Paxos, Tapir, Janus, Calvin+, Detock (alterado para replicar de forma síncrona entre regiões), NCC e NCC+, que coloca o NCC sobre uma camada de Paxos porque o NCC sozinho não tolera falha de servidor. O código é aberto.

O MicroBench pré-popula cada shard com 1 milhão de pares chave-valor, e cada transação incrementa 3 pares em shards diferentes, com chaves sorteadas por uma distribuição Zipfiana cujo fator de skew define a contenção. O TPC-C implementa os 5 tipos de transação, com Payment e Order-Status como multi-shot. Os experimentos rodam em VMs n2-standard-16 do Google Cloud, com dados em 3 regiões (Carolina do Sul, Finlândia, Brasil), 2 coordenadores em cada uma e mais 2 coordenadores em uma região remota, Hong Kong. O MicroBench usa 3 shards (9 servidores) e o TPC-C 6 shards (18 servidores). A carga é open-loop, com um teto de transações em andamento, e cada teste é repetido 5 vezes, com a mediana relatada. Outros experimentos variam o skew com carga fixa, derrubam um leader, colocam os leaders em regiões diferentes rotacionando os ids de shard e de réplica, deslocam o headroom em até 50 ms para cada lado e comparam quatro configurações de relógio: ntpd, chrony, Huygens e uma fonte NTP deliberadamente instável.

Estes são os resultados relatados pelos autores.

• Destaque, baixa contenção. Com fator de skew 0,5, perto da saturação de cada protocolo, o Tiga tem throughput de 1,3× a 7,2× maior e latência mediana de 1,4× a 4,6× menor que todas as bases. A Tabela 1 dá o throughput máximo do MicroBench: 157,3 mil txns/s para o Tiga, contra 119,6 mil do Calvin+, 77,8 mil do Janus, 47,4 mil do NCC, 44,2 mil do Tapir, 34,5 mil do Detock, 22,9 mil do 2PL+Paxos e 21,8 mil do OCC+Paxos.
• Contenção crescente. Com a carga fixa em 8 mil txns/s por coordenador e o skew indo de 0,5 a 0,99, todas as bases degradam, exceto o Calvin+, cuja latência é 33% maior que a do Tiga. Nas curvas do MicroBench, os autores atribuem a queda à computação de grafos no Janus e no Detock, aos aborts por divergência de ordem no Tapir e ao controle de tempo de resposta no NCC.
• Região remota. Em Hong Kong, onde não há servidores na mesma região, Janus, Tapir e Calvin+ precisam de pelo menos 2 WRTTs, enquanto o Tiga fica em 1 WRTT nas duas regiões.
• TPC-C. O Tiga chega a 21,6 mil txns/s, contra 13,3 mil do Detock, 10,8 mil do Janus e 6,1 mil do Calvin+, enquanto 2PL+Paxos, OCC+Paxos, Tapir e NCC ficam entre 0,86 mil e 2,1 mil. Contra Detock, Janus e Calvin+, os autores relatam throughput de 1,6× a 3,5× maior e latência mediana de 1,5× a 3,7× menor.
• Falha de leader. Depois que um leader de um shard é derrubado a 80 mil txns/s no total, o Tiga conclui a troca global de view e volta ao mesmo throughput em 3,8 segundos. A latência então sobe porque esse shard fica com apenas f + 1 = 2 servidores, então as transações que o tocam seguem o slow path, mas os coordenadores de Hong Kong ainda superam a latência dos outros protocolos na Figura 8.
• Leaders separados. Colocar os leaders em regiões diferentes reduz o throughput máximo do Tiga em 9,7%, para 141,9 mil txns/s, e aumenta sua latência mediana nessa carga em 34,0%. Ele ainda supera as bases, e a latência do Calvin+ sobe 162%. Com skew alto, algumas transações precisam de um WRTT extra para fazer rollback.
• Headroom. O headroom estimado fica perto do ótimo. Deslocamentos menores aumentam rollbacks e latência, maiores removem os rollbacks mas seguram as transações por mais tempo, e usar só o horário de envio (0-Hdrm) é o pior nos dois.
• Relógios. Os erros de sincronização relatados são de 0,012 ms no Huygens, 4,54 ms no chrony, 16,45 ms no ntpd e 62,55 ms na fonte instável, com throughput entre 154,7 mil e 158,1 mil txns/s nos quatro. A latência é parecida com chrony e Huygens, já que os atrasos entre regiões vão de 60 a 150 ms, maior com o ntpd e substancialmente maior com a fonte instável.

A ideia é atraente: troca um palpite sobre a ordem de chegada por um palpite sobre o atraso e mantém uma alternativa para quando o palpite falha. O artigo admite o seguinte.

• A ordenação proativa é de melhor esforço. Perda de pacotes, retransmissão ou erro de relógio podem fazer uma transação chegar depois de seu timestamp, e o slow path leva então de 1,5 a 2 WRTTs. Os relógios também não têm limite de erro determinístico (até o Huygens pode errar arbitrariamente, em teoria), e é por isso que o acordo de timestamp existe.
• A coordenação muda de lugar em vez de sumir. O acordo entre leaders bloqueia as transações conflitantes atrás da cabeça da fila por 0,5 a 1 RTT, o que os autores chamam de custoso quando os leaders estão espalhados entre regiões sob alta contenção. Os resultados com leaders separados, acima, mostram seu tamanho.
• Vários refinamentos ficam em aberto. O timestamp inicial pode tornar o fast path mais lento que o slow path quando um quorum simples fica perto do coordenador e o resto está longe, então os autores sugerem estimar os dois caminhos e escolher. O sharding dinâmico é planejado. Uma variante sem coordenação entre leaders, que exige um limite de erro de relógio conhecido, é apenas esboçada.

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

• As implantações avaliadas favorecem o desenho. Cada região guarda uma cópia completa dos dados, então os leaders ficam na mesma região e o modo preventivo roda em tudo, exceto nos experimentos de separação e de headroom, em que os leaders são afastados rotacionando ids. A replicação parcial assumida na seção de contexto não é avaliada. Com 3 réplicas por shard (f = 1), a fórmula do super quorum dá 3, então uma confirmação rápida exige que toda réplica de todo shard envolvido responda. Essa conta é minha, não uma afirmação do artigo.
• O tratamento de falhas é pouco medido. O único experimento de falha derruba um leader. Um follower que caiu ou ficou lento (o que, com f = 1, empurra seu shard para o slow path), a falha de um coordenador, o gerenciador de views e partições de rede não são medidos, e os 3,8 segundos vêm desse cenário único.
• "A maioria" e "raros" não são quantificados no texto. O resumo diz que a maioria das transações segue o fast path, mas o texto não dá a fração do fast path, a do slow path nem a taxa de rollback. Isso aparece só em gráficos (taxa de commit nas Figuras 7 a 9, taxa de rollback na Figura 13), então não é citado aqui.
• As bases são portes dos próprios autores, com algum viés nos dois sentidos. Todas rodam no código do Janus, o que mantém a comparação consistente, mas Calvin+ (com Nezha), Detock (tornado síncrono), NCC+ e o próprio Tiga são trabalho dos autores. A coluna do NCC é a variante sem tolerância a falhas e com servidores em uma só região, o que favorece o NCC. Os resultados do TPC-C também são moldados por conflitos no nível de coluna, vindos do armazenamento por colunas do Janus, o que os autores registram e que provavelmente prejudica mais os protocolos baseados em aborts.
• A Tabela 4 é uma comparação qualitativa. Sua coluna de aborts diz None para o Tiga, mas o texto de trabalhos relacionados diz "poucos ou nenhum" abort e a nota 2 limita a ausência de aborts a transações one-shot com leaders na mesma região, enquanto a avaliação relata rollbacks quando os leaders estão separados. As contagens de WRTT são suposições declaradas, e nenhum sistema de produção como o Spanner ou o FoundationDB é medido, só protocolos de pesquisa reimplementados em uma única base de código.
• A evidência de corretude fica fora do artigo. As provas estão em um relatório técnico e há uma especificação em TLA+ com link, mas o artigo não diz o que a especificação verifica nem com quais limites. Para um protocolo cuja parte sutil é a inversão de timestamp, o próprio artigo oferece o exemplo da Figura 5 e o argumento da Seção 3.6.
• Pequenas inconsistências. A introdução diz que o bloqueio costuma custar 0,5 WRTT, enquanto a discussão diz de 0,5 a 1 RTT e o acordo do Case-2 leva um WRTT inteiro, então o valor do corpo é o mais seguro. A Seção 3.1 diz que os erros do Huygens são de poucos microssegundos, enquanto a Tabela 3 informa 0,012 ms. Nenhuma das duas muda uma conclusão.

• Sharding dinâmico para transformar transações multi-shard em transações de um só shard, que não precisam de acordo de timestamp, como os autores planejam.
• Sincronização com limite de erro determinístico, como o hardware ao estilo do Spanner ou do Sundial, que permitiria ao Tiga abandonar o acordo entre leaders do modo que a discussão esboça.
• Uma escolha por transação entre super quorum e quorum simples, com base na latência estimada de cada caminho, como a discussão sugere.
• Medir o que o artigo deixa em aberto: replicação parcial com leaders distantes, falhas de followers e de partição, e a fração do fast path e a taxa de rollback sob rajadas e picos de atraso.