当前位置：首页 > news >正文

Raft-领导者选举

news 2025/7/13 14:50:46

1 概述

相比于Paxos，Raft最大的特性就是易于理解（Understandable）。为了达到这个目标， Raft主要做了两方面的事情：

1. 问题分解：把共识算法分为三个子问题，分别是领导者选举（leader election）、日志复制（log replication）、安全性（safety）

2. 状态简化：对算法做出一些限制，减少状态数量和可能产生的变动。具体来说，Basic Raft 不允许日志中出现空洞（holes），并且限制了日志之间出现不一致的方式。（注：ParallelRaft允许空洞）

本文主要探讨领导者选举。

2 Raft 的基本要点

2.1 状态转变

一个 Raft 集群 由多个服务器节点组成；常见的节点数为 5 个，这样系统可以容忍最多 两个节点故障。
在任意时刻，每个服务器都处于以下三种状态之一：leader、follower 或 candidate。
在正常运行期间，整个系统中只有一个 leader，其余的所有节点都是 followers。
Follower 是被动的：它们不会主动发起请求，只负责响应来自 leader 和 candidate 的请求。
Leader 处理所有来自客户端的请求（如果客户端请求了一个 follower，该 follower 会将请求重定向给 leader）。
第三种状态是 candidate，用于在 leader 选举过程中作为候选人。

图3.3：服务器状态（Server states）转变。Follower 只会响应来自其他服务器的请求。如果一个 follower 长时间没有接收到任何通信，它会变成 candidate 并发起一次选举。一个 candidate 如果获得了来自整个集群中多数节点（majority）的投票，就会成为新的 leader。Leader 通常会持续工作，直到其出现故障为止。

2.2 任期term

Raft 将时间划分为一段段称为 term（任期）的时间区间，如图 3.4 所示。
每个 term 都用一个连续递增的整数编号。每个 term 都从一次 选举（election） 开始，一个或多个 candidate 会尝试成为 leader（详见 3.4 节）。
如果某个 candidate 赢得了选举，那么它将担任该 term 剩余时间的 leader。
在某些情况下，选举可能出现 投票平分（split vote），此时该 term 会在没有 leader 的情况下结束；接下来会很快开始一个新的 term，并进行新的选举。
Raft 保证在同一个 term 中 最多只能有一个 leader。

图3.4：Raft 将时间划分为若干个 term（任期），每个 term 都以一次 选举（election） 开始。
一旦选举成功，就会有一个唯一的 leader 管理整个集群，直到该 term 结束。有些选举可能失败，在这种情况下，该 term 会在没有选出 leader 的情况下结束。

不同的服务器可能在不同时间观察到 term 的转换，有些时候甚至可能完全错过一个选举过程，甚至错过整个 term。
在 Raft 中，term 被用作一种逻辑时钟（logical clock），允许服务器识别过期的信息，例如已经失效的 leader。每个服务器维护一个 current term（当前任期） 变量，并保证该值单调递增。

每当服务器之间通信时，都会交换各自的 current term；如果发现对方的 term 更大，自己就会将 current term 更新为更大的值。如果一个 candidate 或 leader 发现自己的 term 落后了，就会立即转为 follower 状态。如果服务器收到一个包含旧 term 的请求，它会拒绝该请求。

2.3 内部通信RPC

Raft 服务器之间使用 远程过程调用（RPC，Remote Procedure Call） 进行通信。基本一致性算法中，仅需要两种类型的RPC。
（1）在选举过程中，candidate 发起 RequestVote RPC（请求投票）；
（2）而 leader 发起 AppendEntries RPC（附加日志），用于复制日志条目并提供一种 心跳（heartbeat）。
除了这两种RPC以外还有很多其他类型的RPC，例如：

快照安装
集群信息改变
领导权转移

等等。

使用 RPC 的形式来组织 Raft 中的通信，以简化通信模式。每种请求类型都有一个对应的响应类型，响应也作为该请求的 确认（acknowledgment）。Raft 假设 RPC 请求或响应可能在网络中丢失；因此，如果请求方在合理时间内没有收到响应，它需要 自行重试该 RPC。
为了获得最佳性能，服务器会并行发起 RPC 调用；同时，Raft 不假设网络中 RPC 的 顺序是有保障的（不保序）。

3 领导者选举

3.1 领导者选举发生时机

1. 系统启动时

所有服务器初始状态为 follower。
如果在随机的选举超时时间内 没有收到 leader 的心跳（AppendEntries RPC），则该 follower 会转变为 candidate 并启动选举。

2. Follower 超时（Election Timeout）

一个 follower 在超时时间内 没有收到任何有效的 RPC（例如来自 leader 的心跳），就认为 leader 已失效，转为 candidate 并发起选举。

3.2 领导者选举流程

Raft 使用心跳机制（heartbeat mechanism）来驱动 leader 选举。当服务器启动时，它们最初处于 follower 状态。只要服务器持续接收到来自 leader 或 candidate 的有效 RPC，它就会保持在 follower 状态。Leader 会周期性地向所有 followers 发送心跳消息（即不携带日志条目的 AppendEntries RPC），以维持其领导地位。如果某个 follower 在一段时间内未收到任何通信（这段时间称为 选举超时（election timeout）），它就会假设当前没有可用的 leader，并发起一次选举来选出新的 leader。

为了开始一次选举，follower 会将自己的 current term（当前任期）加一，并转换为 candidate 状态。接着，它会 投票给自己（votes for itself），并并行向集群中的其他所有服务器发送 RequestVote RPC 请求。Candidate 会持续处于该状态，直到以下三种情况之一发生：
(a) 它赢得选举，
(b) 另一个服务器成为 leader，
(c) 又一次选举超时过去，但没有选出 leader。

Candidate 如果在同一个任期内获得了来自集群中大多数（majority）服务器的投票，就 赢得选举（wins an election）。每个服务器在某个 term 中 最多只能投票给一个 candidate，采用 先到先得（first-come-first-served） 的方式。这个多数投票规则确保了在同一任期内最多只能有一个 candidate 胜选。一旦 candidate 赢得选举，它就成为新的 leader，随后会向所有其他服务器发送 heartbeat messages（心跳消息），以建立自己的领导权并防止新的选举发生。

在等待投票期间，candidate 可能会收到来自其他服务器的 AppendEntries RPC，对方声称自己是 leader。
如果该 RPC 中附带的 term（任期） 大于或等于 candidate 当前的 current term，那么 candidate 会承认该 leader 的合法性，并回退为 follower 状态。
如果 RPC 中的 term 小于 candidate 的 current term，那么 candidate 会拒绝该 RPC，并继续维持 candidate 状态。

第三种可能的选举结果是，某个 candidate（候选人） 既未胜选，也未失败：
当多个 follower（追随者） 同时变为 candidate 时，投票可能会被平分（split vote），导致没有任何 candidate 获得多数票（majority）。
当出现这种情况时，每个 candidate 会在 选举超时（timeout） 后再次发起新一轮选举：它们会将自己的 term（任期）加一，并重新发起一轮 RequestVote RPC（请求投票）。
然而，如果没有额外机制来打破僵局，这种 平票情况（split votes） 可能会 无限重复下去。

为什么会没有获胜者？比如有多个follower同时成为candidate，得票太过分散，没有任何一个candidate得票超过半数。

如何避免得票太过分散呢？

Raft 使用随机化的选举超时机制（randomized election timeouts），以确保平票（split vote）情况很少发生，并且即使发生也能快速解决。
为了从一开始就避免平票，选举超时时间会从一个固定区间中随机选取（例如 150–300ms）。
这种随机化会将服务器的超时事件分散开来（spread out），从而使得大多数情况下只有一个服务器先超时、发起选举并胜出，并能在其他服务器超时前发送心跳，确立其 leader 身份。
同样的机制也用于应对已发生的平票。
每当 candidate 发起选举时，都会重新启动一个随机化的选举超时计时器，并等待该超时结束后才启动下一轮选举；这可以降低新一轮选举中再次发生平票的概率。

4 源码分析

本部分分析NuRaft库的领导者选举模块。

4.1 `raft_server::start_server`

如果配置了start_server_in_constructor，则会在raft_server的构造函数中启动server。

raft_server::start_server(bool skip_initial_election_timeout) 是 NuRaft 启动 Raft 节点的关键入口函数之一，负责：

初始化后台线程（如日志追加、日志提交）+ 设置选举相关的定时器机制。

raft_server::start_server中关于选举的内容：

1.如果配置了skip_initial_election_timeout，则当前节点在启动时不主动进行选举。

2.服务器状态不允许超时选举，则不主动进行选举

3.通过1，2后进行restart_election_timer。

关于第二点，在NuRaft中，每个raft的节点都有一个srv_state来记录当前的状态，其中srv_state中主要包含任期号，是否允许选举定时器等。

class srv_state {
......
/**
* Term.
*/
std::atomic<ulong> term_;
/**
* Server ID that this server voted for.
* `-1` if not voted.
*/
std::atomic<int> voted_for_;
/**
* `true` if election timer is allowed.
*/
std::atomic<bool> election_timer_allowed_;
/**
* true if this server has joined the cluster but has not yet
* fully caught up with the latest log. While in the catch-up status,
* this server will not receive normal append_entries requests.
*/
std::atomic<bool> catching_up_;
/**
* `true` if this server is receiving a snapshot.
* Same as `catching_up_`, it must be a durable flag so as not to be
* reset after restart. While this flag is set, this server will neither
* receive normal append_entries requests nor initiate election.
*/
std::atomic<bool> receiving_snapshot_;
/**
* Custom callback function for increasing term.
* If not given, term will be increased by 1.
*/
std::function< ulong(ulong) > inc_term_cb_;
};

服务器状态一般会持久化到磁盘，启动时从磁盘中加载。如果是第一次启动，则无服务器状态的记录。

std::this_thread::sleep_for(std::chrono::milliseconds(params->rpc_failure_backoff_));

在启动前会等待一段时间（rpc_failure_backoff_ 毫秒），这是一个 启动退避时间，避免所有节点同时启动、同时选举；

然后启动选举计时器：如 follower 在超时时未收到 heartbeat，将发起投票。

最后一部分的内容就是设置其他辅助定时器。

priority_change_timer_.reset();
vote_init_timer_.set_duration_ms(params->grace_period_of_lagging_state_machine_);
vote_init_timer_.reset();

priority_change_timer_：

通常用于实现 priority-based election 的策略（如 etcd 里的 pre-vote + 优先级降级机制）；
这里重置它表示初始状态下无特殊选举优先级。

vote_init_timer_：

控制选举中某些限制条件（如 follower 落后时可能延迟参与选举）；
grace_period_of_lagging_state_machine_ 表示：如果状态机落后太多，在这段时间内先暂缓投票行为。

4.2 raft_server::restart_election_time

1.阻止不适合启动选举的状态：

if (state_->is_catching_up() || role_ == srv_role::leader) {
return;
}

如果当前节点正在 catch-up 日志，即新加入的 follower 正在同步历史数据，则不允许触发选举；
如果当前节点已经是 leader，也不需要定时器（leader 是通过心跳维持地位的）；

2.创建新的选举 timer task（如果没有）

election_task_ = cs_new<timer_task<void>>(election_exec_, timer_task_type::election_timer);

选举定时任务在raft_server的构造函数中绑定到election_exec_。

3.调度新任务 + 使用随机选举超时：

schedule_task(election_task_, rand_timeout_());

使用之前绑定的 rand_timeout_() 生成一个 [election_timeout_lower_bound, upper_bound] 范围内的随机整数（单位毫秒）；
将选举任务（request_vote 逻辑）延迟该随机时长后执行。

4.3 随机选举时间生成器

随机选举时间生成器在raft_server的构造函数中初始化。

election_timeout_lower_bound，election_timeout_upper_bound是通过配置文件中的值。如果没有配置这两个参数，则会使用一个默认值。

4.4 任务调度器处理流程

void raft_server::schedule_task(ptr<delayed_task>& task, int32 milliseconds) {
if (stopping_) return;
if (!scheduler_) {
std::lock_guard<std::mutex> l(ctx_->ctx_lock_);
scheduler_ = ctx_->scheduler_;
}
if (scheduler_) {
scheduler_->schedule(task, milliseconds);
}
}

核心部分为scheduler_->schedule(task, milliseconds);

asio_service继承于delayed_task_scheduler，所以最终完成调度的是asio_service。

asio_service的schedule，它负责使用 Boost.Asio 或 std::asio 的 steady_timer，将一个 delayed_task 延迟 milliseconds 毫秒后执行。

void asio_service::schedule(ptr<delayed_task>& task, int32 milliseconds) {
if (task->get_impl_context() == nilptr) {
task->set_impl_context( new asio::steady_timer(impl_->get_io_svc()),
&_free_timer_ );
}
// ensure it's not in cancelled state
task->reset();
asio::steady_timer* timer = static_cast<asio::steady_timer*>
( task->get_impl_context() );
timer->expires_after
( std::chrono::duration_cast<std::chrono::nanoseconds>
( std::chrono::milliseconds(milliseconds) ) );
timer->async_wait( std::bind( &_timer_handler_,
task,
std::placeholders::_1 ) );
}

每个 delayed_task 背后都需要一个 asio::steady_timer 来驱动；
如果当前任务没有绑定 timer 对象，就创建一个新的 timer；
使用 impl_->get_io_svc()（Asio 的 IO 上下文）构造 timer；
_free_timer_ 是析构清理函数（确保 timer 在 task 销毁时释放）；
设置超时点：timer->expires_after(std::chrono::milliseconds(milliseconds));
设置异步回调：timer->async_wait(std::bind(&_timer_handler_, task, std::placeholders::_1)
- 在超时点到达后，由 IO 线程异步调用 _timer_handler_；
- _timer_handler_ 是一个统一的调度函数，会调用 task->exec() 或你注册的回调函数；
- 这个过程是非阻塞的，真正的延迟执行由 Asio 的事件循环负责。

而对于我们选举任务来说，这个task就是handle_election_timeout：

4.5 选举流程

函数 raft_server::handle_election_timeout() 是 Raft 节点处理选举（Election Timeout） 的主入口。

1. 下台计数 steps_to_down_，初始启动时它默认为0

if (steps_to_down_ > 0) {
if (--steps_to_down_ == 0) {
// 停止选举定时器，退出集群
state_->allow_election_timer(false);
ctx_->state_mgr_->save_state(*state_);
cancel_schedulers();
return;
}
restart_election_timer();
return;
}

用于强制节点在若干次未收到心跳后退出选举流程；

2. 特殊状态跳过选举

if (state_->is_catching_up()) return;
if (out_of_log_range_) return;
if (state_->is_receiving_snapshot()) return;

catch-up 阶段、日志滞后、正在接收 snapshot → 都 不允许选举；
避免半同步状态下的错误选举。

4.正在处理请求或不满足最小超时时间，跳过

if (serving_req_ ||
time_ms < ctx_->get_params()->election_timeout_lower_bound_)
{
return;
}

5.如果当前已是 leader，跳过

6.发起选举（只有 voting member）

7.如果经过以上6步，选举未成功（或还未完成），继续设置下一轮定时器

以下详细说明发起选举的具体流程，对应上述的第6步：

4.5.1 Pre Vote阶段

为什么需要Pre Vote阶段呢？

用于处理经典的非对称网络分区现象。

假设我们有5台server: S1 to S5, 并且S1 是当前的leader。假设当前存在网络分区（某些节点相互之间不能正常通信）， {S1, S2, S3}, {S2, S3, S5}, {S4, S5}, 以及{S1, S4} 集合内的元素之间可以相互通信。

S1----S4
| \    |
|  S3  |
| /  \ |
S2----S5

由于网络分区，因为S5 不能接收到来自S1的heartbeat ,所以它将用一个更新的term来开启新一轮的leader election。

因为S5 多数派的投票（{S2, S3, S5}集合内节点可以相互通信），所以s5可能当选新leader。在那之后， S1 不能接收到来自新leader S5的 heartbeat ;所以它会尝试新一轮的eader election。这一系列事件最终会不断互相干扰。

需要注意的是，尽管 S2、S3 和 S4 拒绝了来自 S1 或 S5 的投票请求，但这仍然存在问题，因为投票请求会提升它们的任期（term），导致它们拒绝当前领导者的追加日志（append_entries）请求。一旦领导者发现存在更高的任期（领导者是如何发现的呢？下文源码分析介绍），它会立即转变为跟随者（follower），从而引发新一轮的领导者选举。

为了解决上述问题，每个节点在发起正式投票（actual vote）前会先发送预投票请求（pre-vote request）。预投票的目的很简单：检查投票节点当前是否仍能感知到活跃的领导者，防止集群term进行波动，导致的leader的频繁上下台，破坏集群的稳定性。

如果某个投票节点在选举超时（election timer）到期前仍持续收到领导者的心跳，说明领导者可能仍然存活。此时，该节点会拒绝预投票请求，而发起预投票的节点也不会继续推进选举流程。因此，节点的任期（term）将保持不变。

反之，若投票节点的选举超时已到期，它会认为领导者已经失效，因此接受预投票请求。一旦发起预投票的节点获得多数服务器的认可，它才会正式递增自己的任期，并发起实际投票（actual vote）。

现在让我们重新审视之前的问题：

S5 会先发起预投票。
由于 S2、S3 和 S4 持续收到来自 S1 的心跳，它们会始终拒绝预投票请求，整个系统因此不会受到干扰。

以下分析NuRaft库中的request_prevote的流程：

1.通过get_quorum_for_election获取多数派的size，根据这个函数的实现来看，在没有配置custom_election_quorum_size时，返回值是 多数派-1

int32 raft_server::get_quorum_for_election() {
ptr<raft_params> params = ctx_->get_params();
int32 num_voting_members = get_num_voting_members();
if ( params->custom_election_quorum_size_ <= 0 ||
params->custom_election_quorum_size_ > num_voting_members ) {
return num_voting_members / 2;
}
return params->custom_election_quorum_size_ - 1;
}

TODO：图中两个分支的意义。

2.标记hb_alive_ = false，表示未收到心跳包

3.设置role_ = srv_role::candidate

4.设置pre_vote_的信息，设置自己的dead++

struct pre_vote_status_t {
pre_vote_status_t()
: quorum_reject_count_(0)
, no_response_failure_count_(0)
, busy_connection_failure_count_(0)
{ reset(0); }
void reset(ulong _term) {
term_ = _term;
done_ = false;
live_ = dead_ = abandoned_ = connection_busy_ = 0;
}
ulong term_;
std::atomic<bool> done_;
std::atomic<int32> live_;
std::atomic<int32> dead_;
std::atomic<int32> abandoned_;
std::atomic<int32> connection_busy_;
/**
* Number of pre-vote rejections by quorum.
*/
std::atomic<int32> quorum_reject_count_;
/**
* Number of pre-vote failures due to non-responding peers.
*/
std::atomic<int32> no_response_failure_count_;
/**
* Number of pre-vote failures due to busy connections.
*/
std::atomic<int32> busy_connection_failure_count_;
};

5.发送pre_vote_request

NuRaft在pre vote阶段是如何规避网络分区的影响呢？

假设此时{s1,s2,s3,s4}在一个网络分区，{s2,s3,s4,s5}在另一个网络分区.

由于网络分区的缘故，s5感知不到leader的存在，所以在一个超时选举时间之后就会开始发起prevote请求。此时s2,s3,s4（假设s2,s3,s4）接收到s5的prevote请求之后开始处理prevote req：

此时，s2，s3，s4仍然能够接收到 s1 的append entry rpc所以hb_alive_为true。之后不走resp->accept(log_store_->next_slot())，表示这个请求不被接收。

还有一个问题就是：那么hb_alive_是在什么时候设置为true的呢？

刚刚已经提到了在follower接收到append enrty rpc时候，我们来看下具体的设置位置：

会在update_target_priority中设置hb_alive_为true。表示当前节点还能够感知到leader。

设置 hb_alive_ = true;

当s2,s3,s4处理完s5的prevote req之后，发送prevote response请求给s5。

handle_prevote_resp中，对于当前这种情况，对于三个节点的回复都会执行pre_vote_.live_++;

之后直到pre_vote_.live_ >= election_quorum_size，election_quorum_size就是选举多数派的值。后续选举流程也不再推动。

再回想以下发起prevote req的节点会pre_vote_.dead_++ 还是会pre_vote_.live_++？

答案是pre_vote_.dead_++，因为他都发起选举了，那么就已经感受不到leader的存在了。

4.5.2 Vote阶段

通过prevote阶段之后就会正式进入投票选举阶段。

initiate_vote主要：自增term，转化状态为candidate，设置投票为-1，表示没给谁投票。之后发送vote request。

vote req的主要内容为：当前节点的任期号，上一个日志term以及对于的log index。

对于接收到request_vote_request的节点，如果req中的term大于当前节点的term，则调整自己为follower并且更新自己的term。

在handle_vote_req中，要满足以下条件才会进行投票：

首先，这些判断的意图为：要求候选人的日志不能“落后于自己”，才能投票给它。

第一部分：判断候选人日志是否“足够新”

bool log_okay =
req.get_last_log_term() > log_store_->last_entry()->get_term() ||
( req.get_last_log_term() == log_store_->last_entry()->get_term() &&
log_store_->next_slot() - 1 <= req.get_last_log_idx() );

（1）候选人的最后日志 term 更大 ⇒ 日志更新 ⇒ 合格。

（2）如果 term 相等，再比较 最后的日志索引（index）：

如果 候选人最后日志 index >= 自己的最后日志 index ⇒ 合格。

（3）否则就是“落后于我” ⇒ 拒绝投票。

第二部分：是否可以 grant（投票同意）