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

Il paper presenta CD-Raft, un protocollo Raft ottimizzato per ridurre la latenza del consenso nei siti cross-dominio attraverso la minimizzazione del RTT e il posizionamento strategico del leader, garantendo la coerenza forte e dimostrando sperimentalmente una significativa riduzione della latenza rispetto all'implementazione classica.

L'essenziale

Immagina di dover coordinare un gruppo di amici sparsi per il mondo intero per decidere dove andare a cena. Ognuno è in una città diversa (un "dominio" diverso) e deve comunicare con gli altri per essere sicuro che tutti siano d'accordo. Questo è esattamente il problema che affrontano i computer moderni quando devono sincronizzare dati enormi (come quelli per l'Intelligenza Artificiale) tra server situati in diversi paesi o continenti.

Ecco la spiegazione semplice del paper CD-Raft, raccontata come una storia.

Il Problema: La "Chiamata Internazionale" Lenta

Immagina che il tuo sistema informatico sia un'azienda con un Capo (il Leader) e molti Dipendenti (i Follower).
Per scrivere una nuova informazione (ad esempio, aggiornare il menu del ristorante), il processo classico (chiamato Raft) funziona così:

1. Il cliente chiama il Capo.
2. Il Capo deve chiamare tutti i dipendenti in altre città per dire: "Ehi, abbiamo un nuovo ordine, confermatelo!".
3. I dipendenti rispondono al Capo.
4. Il Capo risponde al cliente: "Tutto fatto!".

Il problema: Se il cliente è a Roma e il Capo è a New York, e i dipendenti sono a Tokyo, ci vogliono due lunghi viaggi di andata e ritorno (chiamati RTT) attraverso l'oceano. È come se dovessi aspettare che una lettera arrivi a New York, venga letta, e poi una risposta torni indietro, prima di poter dire "Ok" al cliente. In un mondo veloce come quello dell'AI, questo ritardo è enorme e rende tutto lento.

La Soluzione: CD-Raft (Il "Capo Locale" e il "Capo Globale")

Gli autori propongono CD-Raft, una versione intelligente e ottimizzata di questo sistema. Immagina di ristrutturare l'azienda con due nuovi ruoli:

1. Il Capo Globale: È il vero boss, ma vive in una città specifica.
2. I Capisettoria (Domain Leaders): Ogni città ha il suo "Capo Locale" che gestisce i dipendenti di quella zona.

La Magia: La Strategia "Ritorno Veloce" (Fast Return)

Ecco come CD-Raft risolve il problema della lentezza, usando un'analogia con un corriere espresso:

• Scenario Vecchio (Raft): Il cliente chiama il Capo Globale (New York). Il Capo chiama Tokyo. Tokyo risponde al Capo. Il Capo risponde al cliente. Troppo lento!
• Scenario Nuovo (CD-Raft):
  1. Il cliente (a Roma) chiama il Capo Globale (New York).
  2. Il Capo Globale chiama contemporaneamente tutti i Capisettoria (Roma, Tokyo, Londra).
  3. Il Capo Globale aspetta solo che uno dei Capisettoria (es. quello di Tokyo) gli dica: "Ho confermato con i miei dipendenti".
  4. Qui sta il trucco: Il Capo Globale dice al Caposettoria di Roma: "Ok, Tokyo ha confermato. Tu sei nella stessa città del cliente, rispondi subito al cliente!".

In pratica, il cliente riceve la risposta dal suo "Capo Locale" (Roma) invece di aspettare che la risposta torni da New York. Si salta un viaggio oceanico. Il tempo di attesa si dimezza quasi!

Il Segreto: Scegliere il Capo Giusto

C'è un'altra strategia chiamata Posizione Ottimale del Capo Globale.
Immagina che la maggior parte delle chiamate arrivi da Roma, ma il Capo sia a New York. È uno spreco. CD-Raft ha un "intelligenza artificiale" che guarda dove arrivano più richieste e sposta il Capo Globale nella città migliore (o sceglie quella giusta tra i Capisettoria) per minimizzare i viaggi. È come se il manager si trasferisse nella città dove vive la maggior parte dei clienti per risparmiare tempo di viaggio.

Cosa hanno scoperto? (I Risultati)

Gli scienziati hanno costruito un prototipo e fatto delle prove vere, simulando scenari reali con dati che viaggiano tra città cinesi (Pechino, Shanghai, ecc.).

I risultati sono stati impressionanti:

• Velocità: CD-Raft è stato circa il 33% più veloce nella media rispetto al sistema vecchio.
• Nessun "Collo di bottiglia": Nei casi peggiori (quando il sistema è molto carico), CD-Raft ha ridotto i ritardi estremi del 49%. Significa che anche quando tutto è intasato, il sistema non si blocca quasi mai.
• Sicurezza: Nonostante sia più veloce, è sicuro. Se una città va in tilt (es. un blackout a Shanghai), il sistema continua a funzionare perché ha confermato i dati in almeno due città diverse.

In Sintesi

CD-Raft è come trasformare una catena di montaggio lenta e burocratica in un team agile.
Invece di far viaggiare ogni messaggio fino all'altro capo del mondo e indietro due volte, crea una rete intelligente dove:

1. Il "Capo" coordina tutto da lontano.
2. I "Capisettoria" locali rispondono subito ai clienti della loro zona.
3. Il sistema sceglie sempre la posizione migliore per il Capo.

Il risultato? Un mondo digitale dove i dati si sincronizzano quasi istantaneamente, anche quando si trovano a migliaia di chilometri di distanza, permettendo all'Intelligenza Artificiale di lavorare molto più velocemente.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del paper "CD-Raft: Reducing the Latency of Distributed Consensus in Cross-Domain Sites" in lingua italiana.

1. Il Problema

Con l'aumento dei carichi di calcolo AI su larga scala, la sincronizzazione dei dati tra diversi siti (data center distribuiti geograficamente) è diventata critica. I protocolli di consenso distribuito basati su leader, come Raft, affrontano gravi colli di bottiglia in ambienti cross-domain (tra diversi domini di rete o regioni geografiche) a causa dell'alta latenza di rete.

In uno scenario tipico cross-domain:

• Un client e il leader si trovano spesso in domini diversi.
• Una richiesta di scrittura richiede due Round-Trip Time (RTT) cross-domain:
  1. Tra il client e il leader (invio e conferma).
  2. Tra il leader e i follower negli altri domini per raggiungere il consenso e la conferma della consistenza.
• Questo doppio RTT aumenta significativamente la latenza di risposta, degradando le prestazioni complessive del sistema, specialmente sotto carichi di scrittura intensi.

2. Metodologia: CD-Raft

Gli autori propongono CD-Raft, un protocollo di consenso ottimizzato per siti cross-domain che mantiene la consistenza forte (strong consistency) riducendo drasticamente la latenza. La soluzione si basa su due strategie chiave e un'architettura a due livelli di leader:

A. Architettura a Due Leader

CD-Raft introduce due ruoli distinti:

1. Domain Leader (DL): Gestisce il consenso all'interno del proprio dominio locale.
2. Global Leader (GL): Uno dei Domain Leader che coordina il consenso tra tutti i Domain Leader.

B. Strategia "Fast Return" (Ritorno Rapido)

Questa è l'innovazione principale per ridurre i RTT.

• Flusso Operativo: Quando un client invia una richiesta di scrittura, il Global Leader la distribuisce a tutti i Domain Leader.
• Esecuzione Parallela: Il Global Leader avvia il consenso nel proprio dominio in parallelo alla propagazione della richiesta agli altri domini.
• Risposta Diretta: Una volta che la maggioranza dei nodi nel dominio del client (gestito dal suo Domain Leader) ha sincronizzato i dati e ricevuto l'acknowledgment dal Global Leader, il Domain Leader locale risponde direttamente al client.
• Risultato: Il client riceve la risposta dopo un solo RTT cross-domain (il tempo necessario per la comunicazione iniziale tra client e GL e la propagazione ai DL), invece dei due RTT richiesti da Raft classico. La sicurezza è garantita perché i dati sono confermati in almeno due domini (quello del GL e quello del client).

C. Strategia "Optimal Global Leader Position"

Poiché la latenza di rete varia tra i domini e il volume delle richieste non è uniforme, la posizione del Global Leader influenza la latenza globale.

• CD-Raft calcola dinamicamente la posizione ottimale del Global Leader basandosi sulla distribuzione del traffico (letture/scritture per dominio) e sulla latenza di rete tra i domini ($l_{ij}$).
• L'obiettivo è minimizzare la latenza globale totale ($L_s$) scegliendo il dominio che riduce al minimo i costi di comunicazione cross-domain.

D. Sicurezza e Tolleranza ai Guasti

• Linearizzabilità: Il protocollo garantisce la linearizzabilità (P1 e P2) assicurando che le letture vedano solo dati committati e che l'ordine delle operazioni sia rispettato.
• Tolleranza ai Guasti: Il sistema rimane disponibile anche in caso di guasti di nodi o partizioni di rete, purché non falliscano contemporaneamente più della metà dei nodi in due domini diversi (incluso quello del Global Leader). La validazione formale è stata effettuata utilizzando TLA+.

3. Contributi Chiave

1. Identificazione del collo di bottiglia: Analisi dettagliata del perché i protocolli leader-based falliscono in termini di latenza in scenari cross-domain (doppio RTT).
2. Progettazione di CD-Raft: Introduzione di un nuovo protocollo che riduce il RTT cross-domain da 2 a 1 attraverso la strategia "Fast Return" e l'ottimizzazione della posizione del leader.
3. Verifica Formale: Dimostrazione della correttezza del protocollo e della consistenza forte tramite specifiche formali in TLA+.
4. Implementazione e Valutazione: Sviluppo di un prototipo in Go e valutazione estensiva utilizzando il benchmark YCSB (Yahoo! Cloud Serving Benchmark) in un ambiente reale su Huawei Cloud (4 domini: Pechino, Shanghai, Guangzhou, Guiyang).

4. Risultati Sperimentali

Gli esperimenti hanno confrontato CD-Raft con Raft classico, PigPaxos, Mencius, GeoLM e una versione parziale di CD-Raft (solo Fast Return).

• Riduzione della Latenza Media:
  • Rispetto a Raft, CD-Raft riduce la latenza media del 32,90% in carichi bilanciati (50% letture, 50% scritture).
  • In carichi di sola scrittura, la riduzione è del 39,81%.
• Riduzione della Latenza "Tail" (99° percentile):
  • La latenza di coda (99th percentile) è ridotta del 49,24% in carichi bilanciati e del 49,44% in carichi di sola scrittura rispetto a Raft.
• Robustezza:
  • CD-Raft mantiene prestazioni superiori in diverse topologie geografiche e con diverse distribuzioni di carico (es. scenari sbilanciati 80-10-10).
  • Rispetto ai protocolli senza leader come EPaxos, CD-Raft mostra una stabilità superiore in presenza di conflitti di dati, con riduzioni della latenza media fino al 57,49% quando i conflitti sono alti.
• Scalabilità: Le prestazioni di CD-Raft migliorano all'aumentare del numero di domini, poiché richiede solo la conferma di due domini per il commit, a differenza di Raft che richiede la maggioranza dei nodi totali.

5. Significato e Impatto

Il lavoro di CD-Raft è significativo perché risolve il problema fondamentale della latenza nei sistemi distribuiti geograficamente senza sacrificare la consistenza forte.

• Efficienza Operativa: Permette di eseguire carichi di lavoro AI e database distribuiti su regioni geografiche distanti con tempi di risposta quasi equivalenti a quelli di un singolo data center.
• Generality: A differenza di altre soluzioni che richiedono reti specializzate o hanno limitazioni di generalità (come EPaxos o Speculative Paxos), CD-Raft è un protocollo generico che può essere integrato in sistemi esistenti.
• Futuro: Offre una base solida per lo sviluppo di sistemi di database e storage distribuiti che devono operare su scala globale, riducendo i costi di latenza e migliorando l'esperienza utente finale.

In sintesi, CD-Raft rappresenta un avanzamento sostanziale nell'ottimizzazione dei protocolli di consenso per l'era dei data center distribuiti globalmente, trasformando un collo di bottiglia critico in un processo efficiente e scalabile.