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

This paper introduces CD-Raft, an optimized Raft protocol that reduces cross-domain consensus latency by strategically positioning the leader node and optimizing round-trip times, achieving significant improvements in average and tail latency while maintaining strong consistency verified via TLA+.

The Gist

Imagine you are running a massive, global pizza chain. You have kitchens (data centers) in Beijing, Shanghai, and Guangzhou. Every time a customer orders a pizza (a data request), the order needs to be written down in a master logbook to ensure every kitchen knows exactly what to make, so everyone agrees on the menu. This agreement process is called Consensus.

In the old days, using a standard system like Raft, here's how it worked:

1. A customer in Guangzhou calls the "Head Chef" (the Leader) in Beijing.
2. The Head Chef writes the order in his book, then calls the sous-chefs in Shanghai and Guangzhou to say, "Hey, write this down too."
3. The sous-chefs write it down and call the Head Chef back to say, "Done!"
4. Only when the Head Chef hears back from the majority does he call the customer in Guangzhou and say, "Order confirmed!"

The Problem:
Because the Head Chef is in Beijing and the customer is in Guangzhou, the phone call takes time (network latency). The Head Chef has to wait for the confirmation from the other kitchens before telling the customer. This creates a long, frustrating wait time, especially when the internet connection between cities is slow. It's like waiting for a fax to come back from another country before you can tell your friend you ordered lunch.

The Solution: CD-Raft
The authors of this paper, Yangyang Wang and his team, invented a new system called CD-Raft to fix this. They introduced two main ideas:

1. The "Fast Return" Strategy (The Local Proxy)

Instead of making the customer wait for the Head Chef in Beijing to finish the whole process, CD-Raft gives every city its own Local Manager (Domain Leader).

Here is the new flow:

• The customer in Guangzhou calls the Local Manager in Guangzhou.
• The Local Manager immediately tells the Head Chef in Beijing: "Hey, we got a new order!"
• Crucially, the Local Manager doesn't wait for the Head Chef to finish talking to everyone else. As soon as the Head Chef says, "Okay, I've told the other cities and we are safe," the Local Manager in Guangzhou immediately tells the customer, "Order confirmed!"

The Analogy: Think of it like a local bank branch. You don't wait for the bank's headquarters in New York to approve your withdrawal before the teller gives you cash. The teller (Local Manager) checks with headquarters, gets a "green light," and hands you the money instantly. You don't wait for the round-trip signal to go all the way back to New York and return to you. This cuts the waiting time in half.

2. The "Optimal Leader" Strategy (The Smart Seat Selection)

In the old system, the Head Chef was often picked randomly or stuck in one place. But what if 80% of your customers are in Shanghai, but your Head Chef is in Beijing? Everyone has to make that long phone call to Beijing.

CD-Raft uses a smart algorithm to constantly ask: "Where is the busiest group of customers right now?" and moves the Global Head Chef to that city.

• If most orders come from Shanghai, the Head Chef moves to Shanghai.
• Now, the local managers in Beijing and Guangzhou still talk to the Head Chef, but the Head Chef is closer to the majority of the action.

The Analogy: Imagine a teacher in a classroom. If the teacher stands at the back of the room, the students in the front have to shout to be heard. CD-Raft is like the teacher sensing that 80% of the class is sitting in the front row and moving their desk there. Now, communication is faster for everyone.

The Results

The researchers tested this new system against the old one using a famous benchmark (YCSB) that simulates real-world internet traffic.

• Speed: CD-Raft was 33% faster on average.
• The "Bad" Days: Sometimes, internet traffic gets clogged, and things get really slow (this is called "tail latency"). CD-Raft was 49% faster even during these worst-case scenarios.
• Safety: Even though it's faster, it's just as safe. If one city's internet goes down, the system still works because the "Head Chef" and the "Local Managers" ensure that at least two different cities have the correct logbook before confirming an order.

Summary

CD-Raft is like upgrading a slow, bureaucratic mail system to a high-speed courier service with local hubs.

• Old Way: You wait for the package to go to the central hub, get stamped, go to the local hub, and come back to you.
• CD-Raft Way: The local hub gets the stamp from the central hub and hands it to you immediately. Plus, the central hub moves to wherever the most people are, so the trip is shorter.

This makes massive AI systems and global databases much snappier, ensuring that when you click a button, the result happens almost instantly, no matter where you are in the world.

Technical Summary

Here is a detailed technical summary of the paper "CD-Raft: Reducing the Latency of Distributed Consensus in Cross-Domain Sites."

1. Problem Statement

The rapid growth of massive AI workloads and data-intensive applications has necessitated frequent state synchronization across geographically distributed data centers (cross-domain sites). While strong consistency is required for data accuracy, traditional leader-based consensus protocols (like Raft) face a critical performance bottleneck in these environments: high cross-domain Round-Trip Time (RTT).

• The Bottleneck: In standard Raft, a write request from a client in Domain B to a leader in Domain A requires two cross-domain RTTs:
  1. Client $\leftrightarrow$ Leader (Request/Ack).
  2. Leader $\leftrightarrow$ Followers in other domains (Consensus confirmation).
• Impact: This double latency significantly increases response times, particularly under write-heavy workloads, degrading overall system performance and user experience.
• Secondary Issue: The position of the elected leader is often random. In cross-domain scenarios, a poorly positioned leader can exacerbate latency due to uneven request distribution and varying inter-domain network delays.

2. Methodology: CD-Raft Design

The authors propose CD-Raft, an optimized Raft protocol specifically designed for cross-domain sites. It introduces a layered architecture and two core strategies to reduce latency while maintaining strong consistency and cross-domain disaster tolerance.

A. Dual-Leader Architecture

CD-Raft introduces two distinct leader roles:

1. Domain Leader: Manages consensus operations within a specific domain.
2. Global Leader: Elected from among the Domain Leaders, it coordinates consensus across all domains.

B. Key Strategies

1. Fast Return Strategy:

   • Mechanism: When a client sends a write request to the Global Leader (in a different domain), the Global Leader forwards the request to all Domain Leaders and initiates in-domain consensus in parallel.
   • Optimization: Once the Global Leader's domain achieves consensus and receives acknowledgment from any other domain, the Global Leader instructs the Domain Leader in the client's domain to commit. The Domain Leader then directly responds to the client.
   • Result: This reduces the write path from two cross-domain RTTs to one. The client only waits for the round-trip between the client and the Global Leader (plus the internal domain consensus), effectively hiding the second cross-domain hop.

2. Optimal Global Leader Position:

   • Mechanism: The system continuously monitors client request volumes ($W_i, R_i$) and inter-domain latencies ($l_{ij}$). It calculates the total global latency ($L_s$) for potential leader locations.
   • Optimization: The protocol periodically migrates the Global Leader to the domain that minimizes the total weighted latency, rather than relying on random election.
   • Formula: The system minimizes $L_s = \sum L_i$, where $L_i$ is the latency for domain $i$ based on whether the client is in the same domain as the leader or a different one.

C. Safety and Fault Tolerance

• Commit Condition: Data is committed only when a majority of nodes in the Global Leader's domain AND a majority of nodes in at least one other domain hold the data.
• Disaster Tolerance: The system remains available even if the Global Leader's domain fails, provided no more than two domains fail simultaneously. It supports "brain-split" prevention by requiring a non-empty intersection of nodes between election and consensus sets.
• Linearizability: Proven via TLA+ formal specification, ensuring that read operations see all committed writes and no uncommitted writes.

3. Key Contributions

1. Identification of Bottlenecks: Clearly identified that leader-based protocols suffer from double cross-domain RTTs in distributed environments.
2. Protocol Innovation (CD-Raft): Proposed a novel dual-leader architecture with Fast Return (reducing write RTTs to 1) and Optimal Global Leader Position (dynamic leader placement).
3. Formal Verification: Verified the correctness and linearizability of CD-Raft using TLA+, providing a mathematical guarantee of safety.
4. Comprehensive Evaluation: Implemented a prototype in Go and evaluated it against state-of-the-art protocols (Raft, PigPaxos, Mencius, GeoLM, EPaxos) using the YCSB benchmark.

4. Experimental Results

The authors evaluated CD-Raft on a real cross-domain network (Beijing, Shanghai, Guangzhou, Guiyang) using the Huawei Cloud Platform.

• Latency Reduction (vs. Classic Raft):
  • Average Latency: Reduced by 32.90% (read/write balanced) and 39.81% (write-only).
  • Tail Latency (99th percentile): Reduced by 49.24% (read/write balanced) and 49.44% (write-only).
• Comparison with Other Protocols:
  • CD-Raft consistently outperformed PigPaxos, Mencius, and GeoLM across all workloads (Load, A, B, C).
  • In write-heavy scenarios, CD-Raft reduced average write latency by 39–41% compared to Raft/PigPaxos/Mencius.
  • Compared to the leaderless protocol EPaxos, CD-Raft showed superior stability as key-value conflict rates increased, reducing latency by up to 57.49% at 100% conflict rates.
• Scalability: Performance advantages increased as the number of domains grew (2 to 4 domains), as CD-Raft only requires two domains to commit, whereas Raft requires a majority of all nodes.

5. Significance

• AI and Big Data Enablement: CD-Raft directly addresses the latency challenges of synchronizing massive AI models (e.g., 7B parameter models requiring 28GB transfers) across geographically dispersed data centers.
• Practical Deployment: Unlike some theoretical optimizations that rely on specialized networks or lack generality, CD-Raft maintains strong consistency and generality while significantly cutting latency.
• Cost-Efficiency: By reducing the number of cross-domain RTTs, the protocol lowers network overhead and improves throughput, which is critical for cloud providers managing multi-region clusters.

In conclusion, CD-Raft represents a significant advancement in distributed consensus for cross-domain environments, successfully balancing the trade-off between strong consistency, fault tolerance, and low latency through architectural innovation and dynamic optimization.