CD-Raft: Reducing the Latency of Distributed Consensus in Cross-Domain Sites

O artigo propõe o CD-Raft, um protocolo Raft otimizado para reduzir significativamente a latência de consenso em sites de domínios cruzados através da minimização do tempo de ida e volta (RTT) e do posicionamento estratégico do nó líder, garantindo consistência forte e demonstrando reduções de latência média e de cauda em testes empíricos.

O essencial

Imagine que você tem uma rede de escritórios espalhados por diferentes cidades (ou até países) e todos eles precisam manter um registro de contabilidade perfeitamente sincronizado. Se um escritório em São Paulo anota uma venda, os escritórios no Rio, em Nova York e em Tóquio precisam saber disso imediatamente para que ninguém tente vender o mesmo produto duas vezes.

O problema é que a internet entre essas cidades não é instantânea. Leva tempo para a mensagem viajar (chamado de "latência"). Se o sistema for lento, o cliente espera, o sistema trava e a experiência fica ruim.

É aqui que entra o CD-Raft, a solução proposta neste artigo. Vamos explicar como funciona usando analogias do dia a dia.

1. O Problema: A "Corrida de Correspondência" Lenta

Antes do CD-Raft, os sistemas usavam um protocolo chamado Raft. Imagine que o Raft funciona assim:

• Você (o cliente) manda uma carta para o Chefe (o líder do sistema).
• O Chefe recebe a carta, copia para seus ajudantes e espera que a maioria deles confirme que recebeu.
• Só depois de receber todos os "OKs", o Chefe diz: "Tudo certo, pode prosseguir".

Onde está o gargalo?
Se você está em um país e o Chefe está em outro, a carta vai e volta duas vezes antes mesmo de ser processada pelos ajudantes. É como se você tivesse que enviar uma carta para o chefe, esperar ele responder, e só então ele pudesse enviar para os outros. Em tempos de "Big Data" e Inteligência Artificial, onde os dados são gigantes (como modelos de IA de 7 bilhões de parâmetros), essa espera é enorme.

2. A Solução: O CD-Raft (O "Chefe Regional" e o "Chefe Global")

Os autores criaram o CD-Raft para resolver essa lentidão. Eles mudaram a hierarquia da empresa:

• Antes: Havia apenas um Chefe Global.
• Agora (CD-Raft): Existe um Chefe Global e vários Chefes Regionais (um para cada cidade/país).

A Estratégia do "Retorno Rápido" (Fast Return)

Esta é a mágica principal. Vamos ver como funciona quando você envia um pedido:

1. O Pedido: Você envia o pedido para o Chefe Global (que pode estar longe).
2. A Divisão: O Chefe Global não espera tudo terminar para te responder. Ele imediatamente manda o pedido para os Chefes Regionais de todas as cidades.
3. O Trabalho Paralelo:
   • O Chefe Regional da sua cidade (onde você está) começa a organizar os ajudantes locais.
   • O Chefe Regional da cidade do Chefe Global também organiza os ajudantes dele.
   • Eles fazem isso ao mesmo tempo.
4. O Truque: Assim que o Chefe Regional da sua cidade confirma que a maioria dos ajudantes locais recebeu a informação, ele te responde imediatamente: "Pronto! Está salvo aqui!".
   • Você não precisa esperar o Chefe Global confirmar com os outros países.
   • O Chefe Global continua trabalhando nos bastidores para garantir que os outros países também tenham os dados, mas você já recebeu sua confirmação.

Analogia: É como pedir um pizza. Em vez de esperar o dono da pizzaria (longe) confirmar com todos os entregadores antes de te dizer "sua pizza está pronta", o entregador da sua rua confirma que recebeu o pedido da cozinha e já te avisa. A cozinha continua enviando a pizza para as outras filiais, mas você já sabe que a sua está garantida.

3. A Estratégia do "Chefe no Lugar Certo" (Posição Otimizada)

O segundo grande avanço é inteligente: o sistema não escolhe o Chefe Global aleatoriamente. Ele calcula matematicamente onde colocar o Chefe Global para que a soma total das distâncias seja a menor possível.

• Analogia: Imagine que você tem clientes em todo o Brasil. Se você colocar o escritório central em Manaus, a maioria dos clientes do Sudeste terá que esperar muito. O CD-Raft analisa onde estão a maioria dos pedidos e coloca o Chefe Global na cidade que minimize o tempo de viagem para todos. Se o tráfego de pedidos mudar, ele pode até mudar o escritório central para um lugar melhor.

4. Segurança: E se algo der errado?

Você pode se perguntar: "Se o Chefe Regional da minha cidade responde rápido, e a internet cai, os dados somem?"

Não. O sistema é projetado para ser à prova de falhas (disaster tolerance):

• Para confirmar um dado, é necessário que a maioria dos ajudantes em pelo menos duas cidades diferentes tenham o registro.
• Se uma cidade inteira cair (como se o escritório local pegasse fogo), o sistema ainda funciona porque a outra cidade tem a cópia.
• O sistema garante que, mesmo com falhas, ninguém perca dados e ninguém leia informações desatualizadas.

5. O Resultado na Prática

Os autores testaram esse sistema em uma simulação real com servidores em quatro cidades chinesas (Beijing, Xangai, Guangzhou e Guiyang).

• Redução de Tempo: O CD-Raft foi 33% mais rápido na média e quase 50% mais rápido nos casos piores (quando a rede está muito lenta) comparado ao sistema antigo.
• Estabilidade: Funciona bem mesmo quando há muitos pedidos de leitura e escrita ao mesmo tempo, ou quando há conflitos de dados.

Resumo Final

O CD-Raft é como transformar uma burocracia lenta, onde você precisa de carimbos de vários países para fazer uma transação simples, em um sistema eficiente onde o funcionário local já te dá o "OK" enquanto o escritório central continua processando o resto nos bastidores.

Isso permite que sistemas de Inteligência Artificial e bancos de dados globais funcionem muito mais rápido, mesmo quando os servidores estão espalhados pelo mundo todo, sem perder a segurança dos dados.

Resumo técnico

Resumo Técnico: CD-Raft

1. Problema Identificado

O crescimento massivo de cargas de trabalho de computação em IA exige sincronização frequente de dados e estado entre diferentes data centers (sítios). Em ambientes distribuídos que abrangem múltiplos domínios geográficos (cross-domain), a latência de rede torna-se um gargalo crítico para a performance do sistema.

O protocolo de consenso Raft, amplamente utilizado, enfrenta desafios específicos em cenários cross-domain:

• Dupla RTT (Round-Trip Time) Cross-Domain: Quando o cliente e o líder (Leader) estão em domínios diferentes, uma operação de escrita exige duas viagens de ida e volta de longa distância:
  1. Cliente $\leftrightarrow$ Líder (solicitação e confirmação).
  2. Líder $\leftrightarrow$ Seguidores em outros domínios (confirmação de consistência).
• Posicionamento Subótimo do Líder: Em protocolos baseados em líder, a escolha aleatória ou fixa do líder pode não considerar a distribuição de tráfego ou as latências entre domínios, resultando em latência global desnecessariamente alta.
• Impacto na Performance: Essa latência adicional degrada significativamente o tempo de resposta (latência média e latência de cauda/99º percentil), especialmente em cargas de trabalho intensivas em escrita.

2. Metodologia e Proposta (CD-Raft)

Os autores propõem o CD-Raft, uma versão otimizada do Raft projetada especificamente para sítios cross-domain. A arquitetura adota um design em camadas e introduz dois papéis de líder e duas estratégias principais:

A. Arquitetura de Líderes Duplos:

• Líder de Domínio (Domain Leader): Gerencia o consenso dentro de seu próprio domínio (similar ao líder do Raft tradicional).
• Líder Global (Global Leader): Coordenador eleito entre os Líderes de Domínio, responsável por orquestrar o consenso entre todos os domínios.

B. Estratégias Chave:

1. Fast Return (Retorno Rápido):

   • Reduz a latência de escrita de duas RTTs cross-domain para uma única RTT cross-domain.
   • Mecanismo: Quando um cliente envia uma solicitação, o Líder Global distribui a solicitação para todos os Líderes de Domínio. O Líder de Domínio onde o cliente reside inicia o consenso localmente. Assim que a maioria dos nós desse domínio local confirma a replicação, o Líder de Domínio responde diretamente ao cliente (dentro do mesmo domínio, sem latência cross-domain).
   • O Líder Global apenas precisa receber a confirmação de um outro domínio para considerar o commit seguro, garantindo tolerância a falhas em pelo menos dois domínios.

2. Posicionamento Ótimo do Líder Global (Optimal Global Leader Position):

   • Utiliza um modelo matemático para calcular a latência global total baseada no volume de requisições de cada domínio ($W_i, R_i$) e na latência entre domínios ($l_{ij}$).
   • O sistema seleciona dinamicamente o domínio que minimiza a latência global total como a localização do Líder Global, adaptando-se a mudanças na distribuição de tráfego.

C. Garantia de Segurança e Consistência:

• Condição de Commit: Os dados são commitados apenas quando a maioria dos nós no domínio do Líder Global E a maioria dos nós em pelo menos um outro domínio possuem os dados.
• Linearizabilidade: Garantida através da ordem estrita de índices de log e propriedades de visibilidade e integridade.
• Verificação Formal: A correção do protocolo foi provada mecanicamente usando a especificação formal TLA+, garantindo consistência forte e tolerância a falhas (incluindo cenários de partição de rede e falha de nós).

3. Principais Contribuições

1. Identificação de Gargalos: Análise detalhada de como a latência cross-domain afeta protocolos baseados em líder, especificamente o custo de duas RTTs.
2. Novo Protocolo (CD-Raft): Introdução de uma arquitetura de dois líderes e estratégias de Fast Return e Posicionamento Ótimo que reduzem a latência de escrita para uma única RTT cross-domain.
3. Prova Formal: Validação da correção do protocolo e da consistência forte através de TLA+.
4. Implementação e Avaliação Empírica: Desenvolvimento de um protótipo em Go e avaliação extensiva usando o benchmark YCSB em um ambiente real de nuvem (Huawei Cloud) com nós em quatro cidades chinesas (Beijing, Shanghai, Guangzhou, Guiyang).

4. Resultados Experimentais

Os testes compararam o CD-Raft com Raft clássico, PigPaxos, Mencius, GeoLM e uma versão básica do CD-Raft (apenas Fast Return).

• Redução de Latência Média:
  • Em cargas de trabalho balanceadas (leitura/escrita), o CD-Raft reduziu a latência média em 32,90% em comparação ao Raft clássico.
  • Em cargas de escrita exclusiva, a redução foi de 39,81%.
• Redução de Latência de Cauda (Tail Latency - 99º percentil):
  • Redução de 49,24% em cargas balanceadas.
  • Redução de 49,44% em cargas de escrita exclusiva.
• Comparação com Outros Protocolos:
  • O CD-Raft superou consistentemente o Raft, PigPaxos, Mencius e GeoLM em todas as métricas.
  • Em comparação com o protocolo sem líder EPaxos, o CD-Raft demonstrou maior estabilidade e menor latência à medida que a taxa de conflito de dados aumentava (de 0% a 100%), onde o EPaxos degradou significativamente.
• Escalabilidade: O desempenho do CD-Raft melhorou à medida que o número de domínios aumentou, pois ele requer apenas dois domínios para commit, enquanto o Raft requer maioria de nós (o que se torna mais difícil de manter com a expansão geográfica).

5. Significado e Impacto

O CD-Raft representa um avanço significativo para sistemas distribuídos que exigem consistência forte em ambientes geograficamente dispersos (como data centers multi-regionais para IA e bancos de dados globais).

• Eficiência: Ao reduzir a latência de consenso de duas RTTs para uma, o protocolo torna viável o uso de consistência forte em aplicações sensíveis à latência que operam entre continentes ou regiões distantes.
• Tolerância a Desastres: Mantém a resiliência contra falhas de domínios inteiros (desastres regionais) sem sacrificar a performance.
• Aplicabilidade: Oferece uma solução prática e comprovada para o desafio de sincronização de dados massivos em tempo real, essencial para a próxima geração de aplicações de IA e serviços em nuvem global.

Em resumo, o CD-Raft resolve o dilema clássico entre consistência forte e latência em redes de longa distância, oferecendo um protocolo robusto, formalmente verificado e empiricamente validado com ganhos de performance substanciais.