1. 节点启动和 Leader 选举.md

# Introduction

# 节点初始化 (NodeImpl::init())

首先初始化 4 个定时器

```c++
    CHECK_EQ(0, _vote_timer.init(this, options.election_timeout_ms + options.max_clock_drift_ms));
    CHECK_EQ(0, _election_timer.init(this, options.election_timeout_ms));
    CHECK_EQ(0, _stepdown_timer.init(this, options.election_timeout_ms));
    CHECK_EQ(0, _snapshot_timer.init(this, options.snapshot_interval_s * 1000));
```

> 注意这 4 个定时器只是 init 了，并没有 start。

启动 apply_queue 用于处理用户提交的 Task，处理函数是 `NoteImpl::execute_applying_tasks()`：

```c++
    if (bthread::execution_queue_start(&_apply_queue_id, NULL, execute_applying_tasks, this) != 0) {
        LOG(ERROR) << "node " << _group_id << ":" << _server_id 
                   << " fail to start execution_queue";
        return -1;
    }
```

* 如果 conf 不为空，就调用 `NodeImpl::step_down()` ==将自己的状态改为 Follower 并启动 `ElectionTimer`==；

* 如果 conf 里面只有自己一个 server，就会立马调用 `NodeImpl::elect_self()` 成为 Leader。

当 ElectionTimer 超时的时候会调用 `NodeImpl::handle_election_timeout()` 函数，该函数重置当前 Leader 为空，并发起 pre_vote。

## Timer

上面 4 个定时器的超时执行函数分别是：

* **VoteTimer**：`NodeImpl::handle_vote_timeout()`，该函数会根据配置再次发起 pre_vote 或者直接 elect_self 发起选举，在 pre_vote 开始后启动
* **ElectionTimer**：`NodeImpl::handle_election_timeout()` ，超时后发起 pre_vote，这也是系统第一个启动的定时器
* **StepdownTimer**：`NodeImpl::handle_stepdown_timeout()`
* **SnapshotTimer**：`NodeImpl::handle_snapshot_timeout()`

# Leader 选举

## pre_vote

与论文不同，在 braft 代码中，选举之前会有一次预选举（pre_vote）的过程，来源于 raft 作者的博士论文。

在基础的 raft 算法中，当一个 Follower 节点与其他节点发生网络分区时，由于心跳超时，会主动发起一次选举，每次选举时会把 term 加 1。由于网络分区的存在，每次 RequestVote RPC 都会超时，结果是，一直不断地发起新的选举，term 会不断增大。

在网络分区恢复，重新加入集群后，其 term 值会被其他节点知晓，导致其他节点更新自己的 term，并变为 Follower。然后触发重新选举，但被隔离的节点日志不是最新，并不会竞选成功，整个集群的状态被该节点扰乱。

pre_vote 算法是 raft 作者在其博士论文中提出的，在节点发起一次选举时，会先发起一次 pre_vote 请求，判断是否能够赢得选举，赢得选举的条件与正常选举相同。如果可以，则增加 term 值，并发起正常的选举。

其他投票节点同意发起选举的条件是（同时满足下面两个条件）：

- 没有收到有效 Leader 的心跳，至少有一次选举超时
- Candidate 的日志足够新（log term 更大，或者 term 相同 index 更大）

### 发起 PreVoteRPC (NodeImpl::pre_vote())

ElectionTimer 超时的时候会调用 `NodeImpl::handle_election_timeout()` 函数处理超时事件，然后调用 `NodeImpl::pre_vote()` 函数发起 pre_vote 请求。

pre_vote 和 request_vote 使用同一个 request ，定义如下：

```protobuf
message RequestVoteRequest {
    required string group_id = 1;
    required string server_id = 2;
    required string peer_id = 3;
    required int64 term = 4;					// next term, current_term + 1
    required int64 last_log_term = 5;			// 注意区分 log term 和 current_term
    required int64 last_log_index = 6;
    optional TermLeader disrupted_leader = 7;	// pre_vote not used (只会在 transfer leader 中用到)
};
```

pre_vote 的主要流程如下：

1. 获取当前最新的 LogId（包括未提交的）

   ```c++
       lck->unlock();
       const LogId last_log_id = _log_manager->last_log_id(true);
       lck->lock();
   ```

2. 遍历所有 peer，向它们发送 pre_vote RPC 请求，回调为 `OnPreVoteRPCDone`（在 RPC 返回后会调用 `NodeImpl::handle_pre_vote_response()`）。

   ```c++
           OnPreVoteRPCDone* done = new OnPreVoteRPCDone(*iter, _current_term, _pre_vote_ctx.version(), this);
           done->cntl.set_timeout_ms(_options.election_timeout_ms);
           done->request.set_group_id(_group_id);
           done->request.set_server_id(_server_id.to_string());
           done->request.set_peer_id(iter->to_string());
           done->request.set_term(_current_term + 1); // next term
           done->request.set_last_log_index(last_log_id.index);
           done->request.set_last_log_term(last_log_id.term);
   ```
   
3. 最后投票给自己（grant_self）

   ```c++
   grant_self(&_pre_vote_ctx, lck);
   ```

> **Tips**:
>
> ==pre_vote 不会增加自己的 term==，而是把 `_current_term + 1` 直接赋值给 `request::term`；request_vote 会先增加自己的 term 然后发起投票请求。

#### GrantSelf

```c++
void NodeImpl::grant_self(VoteBallotCtx* vote_ctx, std::unique_lock<raft_mutex_t>* lck) {
    // If follower lease expired, we can safely grant self. Otherwise, we wait util:
    // 1. last active leader vote the node, and we grant two votes together;
    // 2. follower lease expire.
    int64_t wait_ms = _follower_lease.votable_time_from_now();
    if (wait_ms == 0) {
        vote_ctx->grant(_server_id);
        if (!vote_ctx->granted()) {
            return;
        }
        if (vote_ctx == &_pre_vote_ctx) {
            elect_self(lck);
        } else {
            become_leader();
        }
        return;
    }
    vote_ctx->start_grant_self_timer(wait_ms, this);
}
```

1. 计算下一次可以投票的时间，即 Lease 是否过期。
2. 如果可以立即投票，就马上投票给自己
3. 否则等待 wait_ms 再次检查（`NodeImpl::handle_grant_self_timedout()` 会再次调用 `NodeImpl::grant_self()`）

#### FollowerLease

每个 Node 使用 FollowerLease 对象维护当前 Leader 的信息，在收到 Leader 的合法的 AppendEntries RPC 后会调用 `FollowerLease::renew()` 更新 `_last_leader` 和 `_last_leader_timestamp`。==在 Leader Lease 未过期的情况下，不能进行投票，目的是为了避免网络分区后当前 Leader 不断被更高 term 打断的情况==。

```c++
class FollowerLease {
public:
    FollowerLease()
        : _election_timeout_ms(0), _max_clock_drift_ms(0)
        , _last_leader_timestamp(0)
    {}

    void init(int64_t election_timeout_ms, int64_t max_clock_drift_ms);
    void renew(const PeerId& leader_id);
    int64_t votable_time_from_now();
    const PeerId& last_leader();
    bool expired();
    void reset();
    void expire();
    void reset_election_timeout_ms(int64_t election_timeout_ms, int64_t max_clock_drift_ms);
    int64_t last_leader_timestamp();

private:
    int64_t _election_timeout_ms;
    int64_t _max_clock_drift_ms;
    PeerId  _last_leader;
    int64_t _last_leader_timestamp;
};

} // namespace braft
```

```c++
int64_t FollowerLease::votable_time_from_now() {
    if (!FLAGS_raft_enable_leader_lease) {
        return 0;
    }

    int64_t now = butil::monotonic_time_ms();
    int64_t votable_timestamp = _last_leader_timestamp + _election_timeout_ms +
                                _max_clock_drift_ms;
    if (now >= votable_timestamp) {
        return 0;
    }
    return votable_timestamp - now;
}
```

### 收到 PreVoteRPC (NodeImpl::handle_pre_vote_request())

pre_vote RPC 请求由 `RaftServiceImpl::pre_vote()` 处理，该函数最终会调用 `NodeImpl::handle_pre_vote_request()` 处理。

因为通常来说一个 RPC 服务里会有多个 Raft 复制组存在，这些 Raft Node 共用同一个端口，根据 peer_id 进行标识，所以 `RaftServiceImpl::pre_vote()` 会从 request 中解析出 peer_id，然后根据 peer_id 拿到 Node 实例：

```c++
    PeerId peer_id;
    if (0 != peer_id.parse(request->peer_id())) {
        cntl->SetFailed(EINVAL, "peer_id invalid");
        return;
    }

    scoped_refptr<NodeImpl> node_ptr = global_node_manager->get(request->group_id(), peer_id);
```

pre_vote 和 request_vote 使用同一个 response，定义如下：

```protobuf
message RequestVoteResponse {
    required int64 term = 1;				// 当前节点的 term
    required bool granted = 2;				// 是否同意投票
    optional bool disrupted = 3;			// Leader 被中断, 即当前收到 pre_vote 的节点是 Leader #262
    optional int64 previous_term = 4;		// pre_vote 中同 term #262
    optional bool rejected_by_lease = 5; 	// 如果拒绝了, 是否是因为 lease 的原因拒绝的 #262
};
```

`NodeImpl::handle_pre_vote_request()` 的流程如下：

1. 如果对方的 term 比自己的 term 小，则拒绝（granted = false）

2. 取本地最新的 LogId（包括未 Commit）

3. 比较本地 LogId 与接收到的 LogId

   * 如果对方的 Log 比自己的旧，则拒绝
   
   * ==**如果对方的 Log 比自己的新（>=），并不能直接就接受，而是需要根据 lease 判断现在是否可以投票**==
     
     * ==Follower Lease 未过期（ 距离上次收到 Leader 数据还没超过 election timeout），拒绝并设置 rejected_by_lease 标识==（在 #262 中引入，为了解决 transfer leader 失败的问题）
     * 否则接受
   
     
      ```c++
      		int64_t votable_time = _follower_lease.votable_time_from_now();        
      		bool grantable = (LogId(request->last_log_index(), request->last_log_term()) >= last_log_id);
              if (grantable) {
                  granted = (votable_time == 0);
                  rejected_by_lease = (votable_time > 0);
              }
      ```
   
4. response

   * ==如果当前节点的状态是 Leader，设置 disrupted 为 true==，返回 response。（在 #262 中引入，为了解决 transfer leader 失败的问题）
   * 设置 `RequestVoteResponse::previous_term` 的值为 `_current_term`
   
   ```c++
       response->set_term(_current_term);
       response->set_granted(granted);
       response->set_rejected_by_lease(rejected_by_lease);
       response->set_disrupted(_state == STATE_LEADER);
       response->set_previous_term(_current_term);
   ```

> **Tips**:
>
> * 第 3 步中判断 lease 的目的是	为了处理非对称网络分区中超时节点不断提高自己的 term 打断当前 leader lease 的场景，如果距离上一次收到 Leader 数据还没有超过 election timeout，说明 Leader 还活着，就不允许投票。详见： https://github.com/baidu/braft/blob/master/docs/cn/raft_protocol.md#asymmetric-network-partitioning
> * ==在 pre_vote 中，并没有处理 `request.term > current_term` 的情况，即在遇到这种情况的时候，并不会 step down。==
> * LogId 的比较：LogId 由 term 和 index 组成，重载了比较操作符，逻辑是如果 term 相同就比较 index，否则比较 term。
>* 本地最新 LogId 获取：`LogManager::last_log_id()`
> 
> ```c++
>LogId LogManager::last_log_id(bool is_flush) {
>     std::unique_lock<raft_mutex_t> lck(_mutex);
>     if (!is_flush) {
>         if (_last_log_index >= _first_log_index) {
>             return LogId(_last_log_index, unsafe_get_term(_last_log_index));
>         }
>         return _last_snapshot_id;
>     } else {
>         if (_last_log_index == _last_snapshot_id.index) {
>             return _last_snapshot_id;
>         }
>         LastLogIdClosure c;
>         CHECK_EQ(0, bthread::execution_queue_execute(_disk_queue, &c));
>         lck.unlock();
>         c.wait();
>         return c.last_log_id();
>     }
> }
> ```

### 收到 PreVoteRPC 回复 (NodeImpl::handle_pre_vote_response())

发起 pre_vote 的 node 在收到 RPC 响应后会调用回调，也就是 `NodeImpl::handle_pre_vote_response()` 。

1. 首先是各种 check
   1. 确认当前节点还是 Follower 状态，因为收到 response 时当前节点状态可能已经改变
   2. 确认当前的 term 仍然是发送 pre_vote 时的 term，防止收到之前 term 的 pre_vote response
   3. 如果 response 的 term 比自己的 term 大，直接 step_down 退化成 Follower，并更新自己的 term 值
2. ==如果拒绝了，且不是因为 lease 的原因，结束处理==（由于 lease 的原因而拒绝的情况下面会单独处理）
3. 如果 response 中 disrupted 为 true，记录下这个节点的 peer_id 和 previous_term（即这个节点的 current_term）
4. ==对于由于 lease 拒绝的节点，记录下该节点的 id，不计入投票，直到确认 disrupted 才计入投票（认为 granted 了）==。
5. 剩下的情况就是节点 granted 的情况了
6. 如果超过半数 granted 了，就发起选举

上面步骤 3 - 6 的代码如下：

```c++
    if (response.disrupted()) {
        _pre_vote_ctx.set_disrupted_leader(DisruptedLeader(peer_id, response.previous_term()));
    }    
	std::set<PeerId> peers;
    if (response.rejected_by_lease()) {
        // Temporarily reserve the vote of follower because the lease is
        // still valid. Until we make sure the leader can be disrupted,
        // the vote can't be counted.
        _pre_vote_ctx.reserve(peer_id);
        _pre_vote_ctx.pop_grantable_peers(&peers);
    } else {
        _pre_vote_ctx.pop_grantable_peers(&peers);
        peers.insert(peer_id);
    }
    for (std::set<PeerId>::const_iterator it = peers.begin(); it != peers.end(); ++it) {
        _pre_vote_ctx.grant(*it);
        if (*it == _follower_lease.last_leader()) {
            _pre_vote_ctx.grant(_server_id);
            _pre_vote_ctx.stop_grant_self_timer(this);
        }
    }
    if (_pre_vote_ctx.granted()) {
        elect_self(&lck);
    }
```

首先，==如果是因为 lease 的原因拒绝了 pre_vote，说明这个节点的 term 和 index 检查是通过的==，并不是简单的认为是拒绝了，而是 reserve 这个节点的 peer_id 暂时不计入投票。`VoteBallotCtx::pop_grantable_peers()` 在没有收到过 disrupted response 之前都会返回空集合；在收到 disrupted response 并 set_disrupted_leader 后，会取出所有 reserve 的 peer_id，这些节点会被当作 granted 的节点参与 grant 流程，关于 disrupted 的作用，详见 #262。

> **关于 VoteBallotCtx 和 Ballot**：
>
> VoteBallotCtx 用于 pre_vote 和 request_vote 中处理是否 granted 的逻辑。在 NodeImpl 中定义了两个 VoteBallotCtx，分别为 _pre_vote_ctx 和 _vote_ctx，VoteBallotCtx 调用 Ballot 来判断是否 granted 了。
>
> ```c++
> class VoteBallotCtx {
>     // ... ...
>     private:
>      bthread_timer_t _timer;
>      Ballot _ballot;
>      // Each time the vote ctx restarted, increase the version to avoid
>      // ABA problem.
>      int64_t _version;
>      GrantSelfArg* _grant_self_arg;
>      bool _triggered;
>      std::set<PeerId> _reserved_peers;
>      DisruptedLeader _disrupted_leader; // 默认 DisruptedLeader::term 是 -1
>      LogId _last_log_id;
> };
> 
> void NodeImpl::VoteBallotCtx::set_disrupted_leader(const DisruptedLeader& peer) {
>  	_disrupted_leader = peer;
> }
> 
> void NodeImpl::VoteBallotCtx::reserve(const PeerId& peer) {
>  	_reserved_peers.insert(peer);
> }
> 
> void NodeImpl::VoteBallotCtx::pop_grantable_peers(std::set<PeerId>* peers) {
>      peers->clear();
>      if (_disrupted_leader.term == -1) {	// 没有 set 过 _disrupted_leader, 说明没收到过 disrupted 
>          return;
>  	}
>  _reserved_peers.swap(*peers);
> }
> ```

## Leader 选举

### 发起选举 (NodeImpl::elect_self())

接下来就进入正式的选举环节了，选举由函数 `NodeImpl::elect_self` 发起，函数原型如下：

```c++
    // elect self to candidate
    // If old leader has already stepped down, the candidate can vote without 
    // taking account of leader lease
    void elect_self(std::unique_lock<raft_mutex_t>* lck, 
                    bool old_leader_stepped_down = false);
```

elect_self 的第二个参数 `old_leader_stepped_down`  目前只用在主动 transfer leader 的逻辑中，默认值是 false，在当前场景下使用默认值，因此在下面的代码分析中我们忽略相关的处理逻辑（`_vote_ctx.set_disrupted_leader()` 和 `RequestVoteRequest:: disrupted_leader` 的设置）。

发起选举的流程和 pre_vote 很像：

1. 如果当前是 Follower 状态，则停止 ElectionTimer：

   ```c++
       // cancel follower election timer
       if (_state == STATE_FOLLOWER) {
           _election_timer.stop();
       }
   ```

2. reset 本地保存的 Leader 信息

   ```c++
       // reset leader_id before vote
       const PeerId old_leader = _leader_id;
       const int64_t leader_term = _current_term;
       PeerId empty_id;
       butil::Status status;
       status.set_error(ERAFTTIMEDOUT, "A follower's leader_id is reset to NULL "
                                       "as it begins to request_vote.");
       reset_leader_id(empty_id, status);
   ```

3. 状态改成 Candidate，==自增 term==，投票给自己（_voted_id 记录了本轮投票的信息，如果投票过了，就不能再投给别人了）

   ```c++
       _state = STATE_CANDIDATE;
       _current_term++;
       _voted_id = _server_id;
   ```

4. ==启动 VoteTimer，超时后会重新发起 pre_vote 或直接发起选举==

   ```c++
      _vote_timer.start();
   ```

5. 接下来的步骤和 pre_vote 类似，获取当前最新的 LogId，然后对每个 peer 发起 RPC 请求，区别在于回调是 `OnRequestVoteRPCDone`，最终会调用 `NodeImpl::handle_request_vote_response()` 来处理 response。

6. 投票给自己（grant_self）

### 收到 RequestVoteRPC (NodeImpl::handle_request_vote_request())

`RaftServiceImpl::request_vote()` 接收到 RPC 请求后，获取 Node 实例，然后调用 `NodeImpl::handle_pre_vote_request()` 完成接下来的工作。

1. disrupted_leader_id 相关的处理（在这里我们先忽略，当前流程中没有设置 disrupted_leader，不会有该情况出现）

2. 如果对方的 term 比自己小（`request->term() < _current_term`），就拒绝（直接跳到最后一步，granted 的判断中，`request->term() == _current_term`  为 `false`）

3. 比较接收到的 LogId 和本地最新的 LogId（这里的逻辑和 pre_vote 中一样）

   1. 如果本地日志比较新，就拒绝（直接跳到最后一步，granted 的判断中，`_voted_id == candidate_id` 为 `false`）；

   2. 否则根据 lease 判断当前是否能投票，不能投票就设置 `rejected_by_lease` 为 true 然后跳到最后；

      ```cpp
              // get last_log_id outof node mutex
              lck.unlock();
              LogId last_log_id = _log_manager->last_log_id(true);
              lck.lock();
      
      				bool log_is_ok = (LogId(request->last_log_index(), request->last_log_term()) >= last_log_id);
              int64_t votable_time = _follower_lease.votable_time_from_now();
      
              // if the vote is rejected by lease, tell the candidate
              if (votable_time > 0) {
                  rejected_by_lease = log_is_ok;
                  break;
              }
      ```

4. ==如果对方的 term 比自己大，就 step down==（回退到 Follower 状态并重启 ElectionTimeer，==然后继续下面的投票流程==，注意在 pre_vote 中并没有这个逻辑）

   ```c++
           // increase current term, change state to follower
           if (request->term() > _current_term) {
               butil::Status status;
               status.set_error(EHIGHERTERMREQUEST, "Raft node receives higher term "
                       "request_vote_request.");
               disrupted = (_state <= STATE_TRANSFERRING);
               step_down(request->term(), false, status);
           }
   ```

5. 接下来进入正式的投票流程（进入这里表示对方的 term 比自己的大或者相等）

   1. 如果==对方的 Log 比自己新==并且==本轮还没投票给别人==（`log_is_ok && _voted_id.is_empty()`），就回退到 Follower 并给 candidate 投票（`_voted_id = candidate_id`）

      ```c++
              // save
              if (log_is_ok && _voted_id.is_empty()) {
                  butil::Status status;
                  status.set_error(EVOTEFORCANDIDATE, "Raft node votes for some candidate, "
                          "step down to restart election_timer.");
                  step_down(request->term(), false, status);
                  _voted_id = candidate_id;
                  //TODO: outof lock
                  status = _meta_storage->
                          set_term_and_votedfor(_current_term, candidate_id, _v_group_id);
                  if (!status.ok()) {
                      LOG(ERROR) << "node " << _group_id << ":" << _server_id
                                 << " refuse to vote for " << request->server_id()
                                 << " because failed to set_votedfor it, error: "
                                 << status;
                      // reset _voted_id to response set_granted(false)
                      _voted_id.reset(); 
                  }
              }
      ```

   2. 否则直接拒绝（跳到最后一步）

6. 回复 response，注意 granted 的判断条件是 `request->term() == _current_term && _voted_id == candidate_id`

   ```c++
       response->set_disrupted(disrupted);
       response->set_previous_term(previous_term);
       response->set_term(_current_term);
       response->set_granted(request->term() == _current_term && _voted_id == candidate_id);
       response->set_rejected_by_lease(rejected_by_lease);
   ```

### 收到 RequestVoteRPC 回复 (NodeImpl::handle_request_vote_response())

发起 pre_vote 的 node 在收到 RPC 响应后会调用回调，也就是 `NodeImpl::handle_request_vote_response()`。

1. 首先是各种 check

   1. 确认当前节点还是 Candidate 状态，因为收到 response 时当前节点可能已经选举成功，节点已经成为 Leader 了
   2. 确认当前的 term 仍然是发送 vote request 时的 term，防止收到之前 term 的 response
   3. 如果 response 的 term 比自己的 term 大，直接 step_down 退化成 Follower，并更新自己的 term 值

2. 如果拒绝了，且不是因为 lease 的理由，结束处理

3. 如果赢得了选举，就调用 `NodeImpl::become_leader()`；==对于那些因为 lease 的原因而拒绝的节点，重新发送投票请求==。

   ```c++
       if (response.disrupted()) {
           _vote_ctx.set_disrupted_leader(DisruptedLeader(peer_id, response.previous_term()));
       }
       if (response.granted()) {
           _vote_ctx.grant(peer_id);
           if (peer_id == _follower_lease.last_leader()) {
               _vote_ctx.grant(_server_id);
               _vote_ctx.stop_grant_self_timer(this);
           }
           if (_vote_ctx.granted()) {
               return become_leader();
           }
       } else {
           // If the follower rejected the vote because of lease, reserve it, and
           // the candidate will try again after it disrupt the old leader.
           _vote_ctx.reserve(peer_id);
       }
       retry_vote_on_reserved_peers();
   ```

   ```c++
   void NodeImpl::retry_vote_on_reserved_peers() {
       std::set<PeerId> peers;
       _vote_ctx.pop_grantable_peers(&peers);
       if (peers.empty()) {
           return;
       }
       request_peers_to_vote(peers, _vote_ctx.disrupted_leader());
   }
   ```

### 投票超时 (VoteTimer)

在 `NodeImpl::elect_self()` 中，会启动 VoteTimer 来处理投票超时的情况，`VoteTime::Run()` 会调用 ` NodeImpl::handle_vote_timeout()` 处理。

```c++
void NodeImpl::handle_vote_timeout() {
    std::unique_lock<raft_mutex_t> lck(_mutex);

    // check state
    if (_state != STATE_CANDIDATE) {
    	return;
    }
    if (FLAGS_raft_step_down_when_vote_timedout) {
        // step down to follower
        LOG(WARNING) << "node " << node_id()
                     << " term " << _current_term
                     << " steps down when reaching vote timeout:"
                        " fail to get quorum vote-granted";
        butil::Status status;
        status.set_error(ERAFTTIMEDOUT, "Fail to get quorum vote-granted");
        step_down(_current_term, false, status);
        pre_vote(&lck, false);
    } else {
        // retry vote
        LOG(WARNING) << "node " << _group_id << ":" << _server_id
                     << " term " << _current_term << " retry elect";
        elect_self(&lck);
    }
}
```

如果设置了 `raft_step_down_when_vote_timedout`，就回退到 Follower 开始新的 pre_vote，否则就直接开始新的选举。

## Summary

### PreVote 的作用

braft 的实现中，相比 raft 论文增加了 pre_vote 的流程，用来解决网络分区中的问题。

网络分区会导致某个节点的数据与集群最新数据差距拉大，但是 term 因为不断尝试选主而变得很大。==网络恢复之后，Leader 向其进行 replicate 就会导致 Leader 因为 term 较小而 stepdown==。这种情况可以引入 pre-vote 来避免。Follower 在转变为 Candidate 之前，先与集群节点通信，获得集群 Leader 是否存活的信息，如果当前集群有 Leader 存活，Follower 就不会转变为 Candidate，也不会增加 term。

可以看到，request_vote 和 pre_vote 的流程非常相似，但还是有一些区别：

* 发起 pre_vote 时不会增加自己的 term，发起 vote 时会先自增自己的 term
* 节点在收到 pre_vote request 后，不会处理对方节点 term 比自己大的情况；而 vote 中如果对方节点比自己大，会直接 step down

### Asymmetric network partitioning

原始的 RAFT 论文中对非对称的网络划分处理不好，比如 S1、S2、S3 分别位于三个 IDC，其中 S1 和 S2 之间网络不通，其他之间可以联通。==这样一旦 S1 或者是 S2 抢到了 Leader，另外一方在超时之后就会触发选主，例如 S1 为 Leader，S2 不断超时触发选主，S3 提升 Term 打断当前 Lease，从而拒绝 Leader 的更新==。==这个时候可以增加一个 trick 的检查，每个 Follower 维护一个时间戳记录收到 Leader 上数据更新的时间，只有超过 ElectionTImeout 之后才允许接受 Vote 请求==。这个类似 Zookeeper 中只有 Candidate 才能发起和接受投票，就可以保证 S1 和 S3 能够一直维持稳定的 quorum 集合，S2 不能选主成功。

<img src="https://littleneko.oss-cn-beijing.aliyuncs.com/img/asymmetric_partition.png" alt="!img" style="zoom:67%;" />

### Issue #262

https://github.com/baidu/braft/pull/262

https://github.com/baidu/braft/commit/3cfb1f110682d30f75dc1c750033575b36ef7801

vote/transfer leader is difficult to succeed, if leader lease is enabled and quorum > 2.

Here is an example:

- A Raft group has five peers, {peer_a, peer_b, peer_c, peer_d, peer_e}, and peer_a is the current leader;
- Transfer leader from peer_a to peer_b;
- After peer_b catch up all logs, peer_a send TimeoutNowRequest to peer_b;
- peer_b become the candidate, and ask for other peers to vote;
- peer_a step down, vote peer_b, but peer_c, peer_d, peer_e reject peer_b since the follower lease is still valid;
- peer_b can't get enough ballots.

The solution is that, if a candidate get the vote of last leader, expire the follower lease.

为了修复该问题对代码的改动（可能有部分代码涉及到 transfer leader 的逻辑，我们暂时不关注）：

1. RequestVoteResponse 中增加 disrupted、previous_term、rejected_by_lease 三个字段，其中 disrupted 在老 Leader 收到 transfer 的新节点 vote 请求后设置为 true。

<img src="https://littleneko.oss-cn-beijing.aliyuncs.com/img/image-20220220001119070.png" alt="image-20220220001119070" style="zoom:50%;" />

2. 在收到 PreVote 回复后，对于因为 lease 而拒绝的节点，暂时保留；等到收到 disrupted 即原 Leader 的确认时，就认为 lease 已经无效了，这些因为 lease 而拒绝的节点就可以认为是同意投票了。

3. 对于主动 transfer leader 的场景，在 Follower 收到 Leader 的 Timeout RPC 后会开始选举流程，然后会记录 Leader 信息到 `RequestVoteRequest::disrupted_leader` 中，表示本次选举是一个 transfer leader。

4. 收到 RequestVote 请求后，如果是一个 transfer leader 产生的 vote，就直接 expire lease

   <img src="https://littleneko.oss-cn-beijing.aliyuncs.com/img/image-20220220003424660.png" alt="image-20220220003424660" style="zoom:50%;" />

5. 在收到 RequestVote 回复后，也有 PreVote 中类似的判断逻辑