1. 项目概述最近几年分布式系统成了后端开发绕不开的话题而共识算法又是分布式系统的基石。Raft 算法因为其易于理解的特性成为了很多工程师学习分布式共识的入门选择。我自己在啃完 MIT 6.824 的课程后总觉得用 Go 语言实现一遍还不够过瘾毕竟 C 才是我的老本行用它来实现更能触及底层细节比如内存管理、线程模型和网络 I/O。所以就有了这个用 C 从零实现 Raft 共识算法的项目。这不是一个简单的翻译而是一个基于 C 现代特性和异步编程模型的重新设计目标是构建一个清晰、高效且易于理解的 Raft 库核心。这个实现的核心价值在于它剥离了具体的 RPC 框架和存储引擎将纯粹的 Raft 状态机逻辑封装起来。你只需要给它喂入 RPC 请求、回复和时钟滴答事件它就能输出状态变更和需要发送的 RPC。这种设计让算法核心与网络、存储解耦非常适合集成到现有的 C 系统中或者作为学习 Raft 内部运作机制的绝佳材料。无论你是想深入理解 Raft 论文中的每一个细节还是需要在你的 C 服务中嵌入一个可靠的共识模块这个项目都能提供一个扎实的起点。2. 核心架构与设计哲学2.1 为什么选择“纯算法核心”与“外部驱动”模型在阅读 Raft 论文时你会发现它的描述本身就是一个状态机接收特定输入选举请求、日志追加、超时根据当前状态Follower, Candidate, Leader和持久化状态任期、投票、日志产生相应的输出回复、新的 RPC 请求、提交日志。很多初学者实现时容易把网络收发、线程调度和算法逻辑 tightly coupled紧耦合导致代码混乱难以测试和复用。我的设计哲学很明确分离关注点。Raft类对应Raft.h/Raft.cc就是一个纯粹的状态机。它不关心消息是如何通过网络传来的也不关心时钟是谁触发的。它的接口是一组输入函数RequestVote(const RequestVoteArgs args): 外部 RPC Server 收到投票请求时调用。AppendEntries(const AppendEntriesArgs args): 外部 RPC Server 收到日志追加请求时调用。OnRequestVoteReply(const RequestVoteReply reply): 外部 RPC Client 收到投票回复时调用。OnAppendEntriesReply(const AppendEntriesReply reply): 外部 RPC Client 收到日志追加回复时调用。Tick(): 外部定时器比如一个EventLoop的定时回调周期性调用驱动选举超时和心跳。Propose(const std::string command): 上层应用提交新命令时调用。这种“外部驱动”模型带来了几个巨大优势可测试性极强你可以完全脱离网络环境编写单元测试通过模拟调用这些输入函数并检查Raft对象的输出比如它是否调用了某个发送 RPC 的回调来验证算法逻辑的正确性。网络框架无关你可以用 gRPC、Boost.Asio、甚至原生的 socket 来实现 RPC 层只要最后能转换成对Raft核心的调用即可。本项目选用我自己写的异步 RPC 框架jrpc但替换起来成本很低。便于处理真实世界的复杂性网络是不可靠的会出现消息重复、乱序、延迟。将 RPC 请求和回复视为独立的、无关联的事件输入可以很自然地处理这些情况。状态机内部维护必要的上下文如每个 follower 的nextIndex和matchIndex来决定如何处理一个迟到的回复。2.2 线程模型为什么是双 EventLoop在 Go 版本中goroutine 的轻量级特性让每个 RPC 处理、每个 follower 的日志复制都可以轻松地跑在独立的协程中。在 C 的世界里我们需要自己设计并发模型。我选择了“一个算法线程 一个 RPC Server 线程”的双EventLoop模型。EventLoop是 Reactor 模式的核心一个线程运行一个事件循环处理 IO 事件、定时器和任务队列。算法线程 (Raft Loop)这个线程的EventLoop负责运行Raft状态机的主逻辑。它定时执行Raft::Tick()来检查超时执行Raft::Step()内部状态转移函数来处理输入的事件。所有对Raft核心状态的访问都发生在这个线程天然保证了状态机的线程安全性无需使用复杂的互斥锁mutex来保护Raft对象的每一个成员变量。这极大地简化了并发编程。RPC Server 线程这个线程的EventLoop运行 RPC 服务器监听端口接收来自其他节点的请求。当收到请求时它会在自己的线程中解析、反序列化然后通过线程间通信例如使用EventLoop::queueInLoop()将一个任务投递到算法线程的任务队列中将调用Raft::RequestVote()或Raft::AppendEntries()的请求转发给算法线程去处理。注意为什么不把 RPC Client 也放在算法线程最初的设计确实考虑过。但 RPC 框架的异步回调可能在任意线程被调用。如果让算法线程同时等待和处理网络 IO可能会因为某个耗时的网络操作或回调调度延迟导致心跳无法及时发送从而引发不必要的选举。因此更稳健的做法是将 RPC Client 的发送和接收回调也放在一个独立的网络 IO 线程中或者复用 RPC Server 的线程。本实现中RPC Client 的调用由算法线程发起通过jrpc的异步接口但回复回调被安排到了算法线程中执行这需要 RPC 框架的支持。2.3 数据持久化与序列化权衡Raft 论文要求持久化三个关键数据当前任期currentTerm、投票给谁votedFor、日志条目log。在 Lab 中通常用一个简单的文件读写来模拟。在生产环境中这需要可靠的存储。我选择了LevelDB作为持久化引擎并将状态序列化为JSON格式后存储。这是一个在简单性和效率之间的折中为什么用 LevelDB因为它是一个轻量级、嵌入式的 KV 存储提供原子性的批操作WriteBatch非常适合持久化 Raft 的状态。我们可以把currentTerm、votedFor和整个日志序列化后分别存入不同的 key。LevelDB 的持久化保证简化了我们的工作。为什么用 JSON主要是为了可读性和调试方便。在开发阶段你可以直接用工具查看 LevelDB 里存的 JSON 文本直观地了解日志内容这对于调试共识过程非常有帮助。同时JSON 序列化库如 nlohmann/json在 C 中易用性很高。实操心得JSON 的性能陷阱与未来优化使用 JSON 进行日志的序列化/反序列化是明显的性能瓶颈尤其是在日志条目很大或很频繁时。每次追加日志、持久化状态、甚至发送 RPC如果直接传 JSON都会带来开销。在生产环境中这绝对应该被替换为 Protobuf、FlatBuffers 或 Cap‘n Proto 这类二进制序列化方案。我在代码中留下了// TODO: should use protobuf?的注释就是为了明确这一点。在学习和原型阶段JSON 的便利性压倒了一切但当你需要追求性能时这是第一个要动手改造的地方。3. Raft 核心算法实现详解3.1 状态定义与持久化首先我们定义 Raft 节点的核心状态。这些结构体严格遵循论文定义但用 C 风格进行了组织。// 日志条目 struct LogEntry { int term; // 该条目创建时的领导者任期 std::string command; // 状态机命令 // 可以添加索引等字段但索引通常由在vector中的位置隐含表示 }; // 持久化状态 struct PersistState { int currentTerm 0; int votedFor -1; // -1 表示未投票 std::vectorLogEntry log; // 注意论文中提交索引commitIndex和最后应用索引lastApplied是易失的不持久化 }; // Raft 节点状态易失性状态在领导者上需要为每个 follower 维护 struct VolatileState { // 所有服务器上易失的状态 int commitIndex 0; int lastApplied 0; // 领导者上易失的状态重新初始化 std::vectorint nextIndex; // 对于每个服务器下一个要发送的日志条目索引 std::vectorint matchIndex; // 对于每个服务器已知已复制的最高日志条目索引 };持久化操作被封装成两个函数savePersistState()和loadPersistState()。它们内部使用 JSON 库将PersistState结构体序列化/反序列化然后通过 LevelDB 的Put和Get进行存储和读取。关键点在于任何修改了currentTerm、votedFor或log的操作后都必须立即调用savePersistState()以防崩溃后状态丢失。3.2 领导者选举的实现细节选举是 Raft 中最激动人心的部分。在Raft::Tick()函数中我们会检查选举超时。void Raft::tick() { if (state_ State::FOLLOWER || state_ State::CANDIDATE) { electionElapsed_; if (electionElapsed_ randomizedElectionTimeout_) { // 选举超时开始新一轮选举 electionElapsed_ 0; resetRandomizedElectionTimeout(); // 重新随机化超时时间 if (state_ State::FOLLOWER) { becomeCandidate(); } else { // 已经是 Candidate 但超时直接开始新的选举 startElection(); } } } if (state_ State::LEADER) { // 领导者发送心跳 heartbeatElapsed_; if (heartbeatElapsed_ heartbeatTimeout_) { heartbeatElapsed_ 0; broadcastAppendEntries(); // 广播心跳或日志追加 } } }becomeCandidate()函数会做以下几件事转换状态为CANDIDATE。增加当前任期currentTerm。投票给自己votedFor id_。重置选举计时器。持久化新的任期和投票。向所有其他节点并行发送RequestVoteRPC。发送RequestVoteRPC 时需要构造参数其中包含候选人的最后日志索引和任期这是为了遵循Raft 的选举安全性限制只有拥有最新日志的候选人才可能赢得选举。void Raft::startElection() { // 构造 RequestVoteArgs RequestVoteArgs args; args.term currentTerm_; args.candidateId id_; args.lastLogIndex getLastLogIndex(); args.lastLogTerm getLastLogTerm(); // 并行发起 RPC 调用 for (每个peer) { rpcClient_-asyncCallRequestVoteReply(peer, Raft.RequestVote, args, [this, peer](const RequestVoteReply reply) { // 这个回调必须被调度到算法线程中执行 loop_-queueInLoop(std::bind(Raft::onRequestVoteReply, this, peer, reply)); }); } }处理投票回复onRequestVoteReply时需要小心处理任期过时的问题。如果回复的任期比自己的大就必须立刻退位为 Follower。只有任期相同且获得多数票时才能成为 Leader。注意事项RPC 回复的线程安全性这是异步编程的一个关键坑。RPC 框架的回调很可能在某个网络 IO 线程中被调用。此时如果直接修改Raft对象的状态就会和算法线程产生数据竞争。必须通过EventLoop::queueInLoop()将回调函数转移到算法线程的任务队列中执行。这是本实现中Node类封装的一个重要职责它确保了所有对Raft核心的访问都序列化在同一个线程中。3.3 日志复制与一致性检查日志复制是 Raft 保证状态机一致性的核心。领导者的broadcastAppendEntries()会为每个 follower 构造并发送AppendEntries消息。构造消息的关键在于nextIndex。对于每个 follower领导者从nextIndex开始发送之后的所有日志条目如果nextIndex大于领导者的最后日志索引则只发送心跳。消息中还包含prevLogIndex和prevLogTerm用于进行日志一致性检查。当 follower 的Raft::AppendEntries()被调用时它执行以下逻辑检查请求任期如果小于自己的currentTerm直接拒绝。检查本地日志在prevLogIndex处是否有条目且其任期是否等于prevLogTerm。如果不匹配回复 false并包含一些信息帮助领导者快速回退nextIndex论文中优化后的方案。如果匹配则进行日志冲突处理从prevLogIndex 1开始找到第一个与领导者发来的日志任期不匹配的位置删除从这个位置开始的所有本地日志然后追加领导者的新日志。如果领导者的leaderCommit大于自己的commitIndex则更新commitIndex min(leaderCommit, 新日志的最后索引)。领导者在收到成功的回复后会更新对应 follower 的matchIndex和nextIndex然后检查是否有日志条目可以被提交即被复制到多数节点。提交后通过一个回调通知上层应用。void Raft::onAppendEntriesReply(int peer, const AppendEntriesReply reply) { if (reply.term currentTerm_) { becomeFollower(reply.term); return; } if (reply.success) { // 更新 matchIndex 和 nextIndex matchIndex_[peer] reply.matchIndex; // 假设回复中携带了匹配的索引 nextIndex_[peer] matchIndex_[peer] 1; // 尝试更新 commitIndex tryUpdateCommitIndex(); } else { // 日志不一致回退 nextIndex // 一种简单的回退策略每次减1 --nextIndex_[peer]; // 更优的策略根据回复中的冲突信息conflictTerm, conflictIndex快速回退 // 这里实现了论文中的优化算法 if (reply.conflictTerm ! -1) { // 在本地日志中寻找 conflictTerm 的最后一次出现位置 int lastIndex findLastLogIndexForTerm(reply.conflictTerm); if (lastIndex 0) { nextIndex_[peer] lastIndex 1; } else { nextIndex_[peer] reply.conflictIndex; } } else { nextIndex_[peer] reply.conflictIndex; } // 确保 nextIndex 不小于 1 nextIndex_[peer] std::max(1, nextIndex_[peer]); } }实操心得日志匹配特性的威力与实现Raft 的“日志匹配特性”是它简洁性的来源。它保证了如果两个日志条目有相同的索引和任期那么它们的内容相同并且它们之前的所有日志条目也完全相同。在实现AppendEntries的一致性检查时深刻理解这一点至关重要。它允许 follower 在发生冲突时可以安全地删除冲突点之后的所有日志因为领导者发来的日志一定是从那个点开始唯一正确的历史。实现快速回退conflictTerm/conflictIndex能显著提升日志恢复速度尤其是在网络分区后恢复时一定要实现这个优化。4. 工程实现Node 封装与异步集成4.1 Node 类粘合一切的胶水用户不直接使用Raft类而是使用Node类。Node是连接 Raft 核心算法与外部世界网络、定时器、存储的桥梁。它的主要职责包括初始化与启动加载持久化状态初始化Raft核心对象启动算法线程和 RPC Server 线程。定时器驱动在算法线程的EventLoop中设置一个固定间隔的定时器例如每 10ms 触发一次在回调中调用raft_-tick()。RPC 消息路由注册 RPC 服务将Raft::RequestVote和Raft::AppendEntries方法暴露为 RPC。当 RPC Server 线程收到请求时它调用对应的Raft方法。但为了线程安全这个调用需要通过loop_-runInLoop()或queueInLoop()转移到算法线程执行。当需要发送 RPC如选举、日志复制时Node调用jrpc的异步接口。并为异步回复设置回调该回调同样会被调度到算法线程最终调用raft_-onRequestVoteReply或raft_-onAppendEntriesReply。向上层应用提供接口提供一个Propose(const std::string command)方法供客户端提交命令。这个方法内部也是将任务投递到算法线程调用raft_-propose(command)。状态机输出Raft核心在日志被提交后需要通过回调通知上层应用。Node会注册这个回调并在算法线程中执行用户提供的应用状态机应用函数。class Node { public: Node(int id, const std::vectorPeerInfo peers, const std::functionvoid(const LogEntry) applyFunc); ~Node(); void start(); void propose(const std::string command); // ... 其他方法如获取状态等 private: void onRpcRequestVote(const Json request, const RpcDoneCallback done); void onRpcAppendEntries(const Json request, const RpcDoneCallback done); void tick(); void handleApply(); std::unique_ptrRaft raft_; std::unique_ptrEventLoop raftLoop_; // 算法线程的 EventLoop std::unique_ptrEventLoop rpcLoop_; // RPC Server 线程的 EventLoop std::unique_ptrRpcServer rpcServer_; std::vectorstd::unique_ptrRpcClient rpcClients_; // ... 其他成员如持久化存储、线程等 };4.2 使用 jrpc 实现异步 RPCjrpc是一个简单的基于 JSON 的异步 RPC 框架。它的核心是“请求-响应”模型但调用是非阻塞的。// 发送异步 RPC 的示例 void Node::sendRequestVote(int peer, const RequestVoteArgs args) { Json jsonArgs args.toJson(); // 序列化 rpcClients_[peer]-asyncCall(Raft.RequestVote, jsonArgs, [this, peer](const Json response, bool isError) { // 这个回调可能在 jrpc 的网络线程中被调用 RequestVoteReply reply; if (!isError) { reply.fromJson(response); // 反序列化 } else { // 处理网络错误例如设置 reply.success false 并包含错误信息 } // 将回复处理转移到算法线程 raftLoop_-queueInLoop(std::bind(Raft::onRequestVoteReply, raft_.get(), peer, reply)); }); }异步模型避免了线程阻塞提高了并发能力但也使得错误处理和超时逻辑变得更加复杂。你需要为每个 RPC 调用设置超时并在超时后采取相应行动例如对于选举请求超时可能意味着需要开始新的选举对于日志追加可能需要重试。4.3 编译、运行与演示项目使用 CMake 构建并提供了build.sh脚本简化流程。它需要 C17 支持用于智能指针和标准库特性以及 LevelDB 开发库。# 安装依赖 sudo apt-get install -y g cmake libleveldb-dev # 克隆代码并初始化子模块jrpc git clone https://github.com/guangqianpeng/raft.git cd raft git submodule update --init --recursive # 编译并安装到本地目录 ./build.sh ./build.sh install # 进入构建目录 cd ../raft-build/Release-install/bin单节点演示单节点集群没有意义因为无法形成多数派。但演示程序会启动一个节点并周期性地尝试提交日志。由于没有其他节点响应它会不断在 Follower 和 Candidate 状态间切换选举超时无法成为稳定的 Leader。./raft_demo 0 9877 | grep raft\[输出会显示节点状态的不断切换这正符合预期一个节点无法达成共识。三节点集群演示这才是 Raft 发挥作用的场景。你需要打开三个终端分别运行# 终端1节点0 ./raft_demo 0 9877 9878 9879 | grep raft\[ # 终端2节点1 ./raft_demo 1 9877 9878 9879 | grep raft\[ # 终端3节点2 ./raft_demo 2 9877 9878 9879 | grep raft\[观察输出你会看到其中一个节点比如节点0成功当选 Leader并开始定期提交日志。其他节点作为 Follower 接收日志。你可以尝试CtrlC关闭 Leader 进程观察剩下的节点如何重新选举出新的 Leader。然后再重启旧的 Leader它会作为 Follower 重新加入集群并从新的 Leader 那里同步日志。5. 常见问题、调试技巧与性能考量5.1 调试与日志分析分布式共识的调试是出了名的困难因为涉及多个进程和不确定的网络时序。本项目的日志输出是调试的第一利器。理解日志格式日志行通常包含时间戳、节点IDraft[id]、状态变更如follower - candidate和关键动作如start log X,apply log [X]。通过 grep 过滤特定节点的日志可以清晰地跟踪其状态机变化。使用 LevelDB 工具检查持久化状态你可以使用leveldb::DB的接口或第三方工具如ldb直接查看持久化的 JSON 数据确认任期、投票和日志内容是否正确。这在排查持久化相关 bug 时非常有用。模拟网络故障在本地测试时可以手动杀死进程来模拟节点崩溃。观察剩余节点的日志看它们是否能正确恢复并继续工作。更高级的测试可以引入网络分区模拟比如使用iptables临时阻断节点间的通信。单元测试先行在集成网络之前务必为Raft核心类编写充分的单元测试。使用 Google Test 等框架模拟各种输入序列请求、回复、超时验证状态转换和输出是否符合论文预期。这是保证算法正确性的基石。5.2 典型问题与排查思路问题一集群无法选出 Leader所有节点都在不断超时和竞选。排查思路检查选举超时随机性确保每个节点的随机选举超时时间是在一个合理的范围内例如 150-300ms并且差异足够大。如果所有节点几乎同时超时很容易导致选票分散。检查 RPC 通信确认RequestVoteRPC 能够成功发送和接收。查看节点的日志看是否收到了其他节点的投票请求。如果网络不通自然无法获得选票。检查日志新旧程度一个节点的日志如果比其他节点旧它发出的投票请求会被拒绝。检查各节点持久化的日志索引和任期。一个刚重启的、日志空白的节点在已有数据的集群中可能永远无法获得选票。检查多数派Quorum计算确保集群的节点总数是奇数并且多数派 floor(n/2) 1计算正确。问题二Leader 无法复制日志Follower 的nextIndex一直回退。排查思路检查AppendEntries的一致性检查这是最常见的原因。在 Follower 端仔细打印prevLogIndex、prevLogTerm和本地日志的实际情况。确认领导者的prevLogIndex处日志是否真的匹配。实现并检查快速回退优化如果只实现了每次减1的回退策略在日志差异很大时恢复极慢。确保实现了基于conflictTerm和conflictIndex的快速回退逻辑并在日志中输出这些值以便调试。检查网络包序虽然 TCP 保证有序但在异步 RPC 模型中请求和回复的回调顺序可能因为线程调度而乱序。确保你的Raft状态机能够处理乱序和重复的 RPC 回复通过任期和索引来判断有效性。问题三已提交的日志没有被应用到状态机。排查思路检查commitIndex的更新逻辑领导者在更新了matchIndex后是否正确地遍历所有索引找到了被复制到多数节点的最大索引 N并且log[N].term currentTermRaft 领导特性要求将这个逻辑单独拿出来测试。检查应用回调Node类是否定期或在commitIndex更新后检查lastApplied commitIndex并调用用户注册的applyFunc应用函数本身是否有阻塞或异常查看统计信息演示程序每隔 5 秒会输出统计信息其中包含了commit索引。确认它是在增长的。5.3 性能优化与生产就绪考量目前的实现是一个教学和原型性质的版本。要用于生产环境需要考虑以下优化序列化如前所述将 JSON 替换为Protobuf。这能大幅减少网络传输和持久化的数据量并提升序列化/反序列化速度。批处理与流水线日志追加批处理上层应用可能高频提交命令。可以积累一小批命令例如 10ms 或达到一定大小再一次性 propose 给 Raft减少 RPC 次数。日志复制流水线领导者不必等待一个 follower 对前一条AppendEntries的回复就可以发送下一条。这能充分利用网络带宽显著提高吞吐量。实现时需要更精细地管理每个 follower 的发送状态。日志压缩Log Compaction这是 TODO 列表中的项。日志不能无限增长。需要实现快照Snapshot机制。当日志达到一定大小时将当前状态机状态持久化为快照并截断该快照点之前的日志。这涉及到快照的生成、传输和安装是 Raft 中较为复杂的一部分。成员变更目前集群配置是静态的。生产系统需要支持动态增删节点这需要实现 Raft 的联合共识Joint Consensus或单节点变更等安全算法。客户端协议实现线性化语义的客户端请求处理包括 Leader 重定向、请求去重和会话管理。实现这个 C Raft 的过程是一次对分布式共识理论扎实的工程化实践。它强迫你思考线程安全、异步 IO、状态机驱动和故障处理等实际问题。虽然距离一个像 etcd 中 Raft 模块那样工业级的实现还有距离但这个项目已经搭建起了所有核心骨架。你可以在此基础上沿着上述优化方向一步步将它打磨得更加强健和高效。
