Optimizing Consistency in Distributed Data Services: The CP-Raft Protocol for High-Performance and Fault-Tolerant Replication

The data consistency protocol is a core component of distributed data services that provide fault-tolerance and data consistency across distributed data centers and even edge networks. Raft is a popular approach due to its ease of implementation and superior performance. However, Raft adopts a sequential log entry processing strategy, where log entries without dependencies are not allowed to be processed in parallel, limiting system performance in high-concurrency scenarios. To address this challenge, researchers propose Raft-based protocols that support <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><u>o</u>ut-of-<u>o</u>rder <u>apply</u></i> (OOApply), which is called OORaft. Existing OORaft protocols adopt the Paxos-style election and replication process to merge missing entries on leader candidates. It leads to problems such as extra overhead on dependency analysis, availability when the network is partitioned, and incomplete correctness verification. This paper proposes a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><u>c</u>oncise <u>p</u>aralleled <u>Raft</u></i> protocol called CP-Raft, which is the first OORaft protocol to focus on dependency analysis overhead and to use full TLA<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^+$</tex-math></inline-formula> validation for the leader election process. Specifically, 1) CP-Raft proposes a Raft-aligned three-step election method that significantly simplifies the difficulty of understanding and solves the availability problem when the network is partitioned. 2) CP-Raft applies a leader-side bitmap-based dependency analysis and representation method to break through the performance bottleneck caused by the high overhead of dependency analysis. 3) CP-Raft discusses why existing methods cannot achieve OORaft correctness verification using TLA<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^+$</tex-math></inline-formula> in a limited time and uses phased verification methods to ensure its correctness. Finally, we implement CP-Raft based on an open-source Raft protocol and discuss its potential performance bottlenecks in various scenarios. The experimental results under high dependency strength workloads demonstrate that CP-Raft achieves 1.5× transaction per second (TPS) performance of DP-Raft and 2× of ParallelRaft-CE. It also provides better availability than state-of-the-art OORaft protocols.