【PR】修复PreVote流程的疑似bug？

[shiftyman]

最近鄙人也在做Raft的研究和实现，看到贵团队开源的Java版Raft库，大喜若狂，遂连夜品读代码，收获良多。

但是，预投票流程看着好像有点问题，根据我理解的Raft，预投票的关键是2点：
1.预投票请求报文中的term，应该是发起预投票者的term，不需要term+1（因为prevote的出现就是解决网络分区后节点不断增加term扰乱全局而增加的优化流程）
2.收到预投票请求的节点，应该检查lastLeaderTimestamp是否超过了最小的election超时时间，如果否，则认为当前的leader依然有效，拒绝该preVote（保证稳定性）

而JRaft的实现中，感觉有点问题，也可能是鄙人不理解造成的：
1.发起者以term+1发起预投票，原因何在？
2.接收者，handlePreVoteRequest方法中，具体问题看下面代码中间的中文注释部分：

     do {
        if (request.getTerm() < this.currTerm) {
            LOG.info("Node {} ignore PreVote from {} in term {} currTerm {}", this.getNodeId(),
                request.getServerId(), request.getTerm(), this.currTerm);
            // A follower replicator may not be started when this node become leader, so we must check it.
            checkReplicator(candidateId);
            break;
        } else if (request.getTerm() == this.currTerm + 1) {

               //！！！！！此判断开始往后就根据log的term和index判断是否投赞成票！！！！
               //这样的话，不管当前节点是Follower还是leader，遇到prevote只要没有更新的log，都会赞成
               //这违背了preVote的初衷。
			
            // A follower replicator may not be started when this node become leader, so we must check it.
            // check replicator state
            checkReplicator(candidateId);
        }
        doUnlock = false;
        this.writeLock.unlock();

        final LogId logId = this.logManager.getLastLogId(true);

        doUnlock = true;
        this.writeLock.lock();
        final LogId requestLastLogId = new LogId(request.getLastLogIndex(), request.getLastLogTerm());
        granted = (requestLastLogId.compareTo(logId) >= 0);

        LOG.info(
            "Node {} received PreVote from {} in term {} currTerm {} granted {}, request last logId: {}, current last logId: {}",
            this.getNodeId(), request.getServerId(), request.getTerm(), this.currTerm, granted,
            requestLastLogId, logId);
    } while (false);

    final RequestVoteResponse.Builder responseBuilder = RequestVoteResponse.newBuilder();
    responseBuilder.setTerm(this.currTerm);
    responseBuilder.setGranted(granted);
    return responseBuilder.build();

这里是困惑之处，如果是鄙人眼拙，希望指教下阁下的思路。

鄙人按照自己的理解，修改了下源码，请求PR，主要改动有几个：
1.handlePreVoteRequest方法：前面增加if(Utils.nowMs()-lastLeaderTimestamp<=options.getElectionTimeoutMs())的判断（实现刚刚提到的论文核心要点2）
2.handlePreVoteRequest方法：如果是leader，且赞成此次preVote（term > currTerm && req.log不旧），则stepdown
3.handleElectionTimeout方法(调用preVote前)：if(Utils.nowMs()-lastLeaderTimestamp<=options.getElectionTimeoutMs())的判断去掉，因为这段貌似多余，因为electionTimout了已经，而且这段逻辑应该放到接收者才对。
4.preVote方法：req.setTerm(this.currTerm);不加1！

不知道鄙人理解是否有问题，还望阁下指教！~
如果没问题，希望接受此PR，以贡献小弟绵薄之力。

[killme2008]

你好，感谢你的关注。针对你的问题回复如下：

1. prevote 本质上是一种探测，prevote 请求将 term+1 作为探测请求，并非发起请求的节点自身 term +1 了。只有当探测结果，majority 同意你可以发起 vote 请求， node 才将自身 term+1 ，发起 vote 流程(electSelf方法)。这块的实现大家都是一样，具体可以参见 etcd 的分析文章等，例如这篇。

2. 是否拒绝 prevote 的关键不是时间，而是 prevote 请求带过来的 lastLogIndex 和 lastLogTerm 与当前节点的 log/term 做对比，日志是否更“大”。更“大”，才会允许请求的节点发起 vote 请求。但是这里确实可以优化，如果当前是 leader，如果当前存在 leader，并且租约还没有过期，可以直接拒绝请求，不用对比 log 大小，这个优化是可以做的，能提升集群稳定性，欢迎提 PR。

[fengjiachun]

Hi @shiftyman 感谢关注，如 @killme2008 回复，这里确实可以优化

有这样一种情况：
就是集群长时间没有新写入，一个游离的 follower 又回归后发起 pre-vote， 由于集群长时间无写入，它的 logIndex 与 leader 一样新，这就会导致集群重新选主，所以在比较 logIndex 之前增加租约的判断确实是可以做的（我们假设时钟漂移相对罕见）

以上，如果你愿意提一个 PR， 我们非常欢迎

[shiftyman]

关于preVote的request.term是否应该+1再传输的问题，就论文看，我认为其初衷是不+1的。但是+1也不是说就有问题，只要在handlerPreVoteRequest时，对request.term == my.term + 1的情况做好处理即可。

就像etcd的实现，它为什么+1，我认为是因为其在处理请求时，它将preVote和vote放在一起的，所以preVote的term+1跟vote保持一致也不足为奇。以下代码摘自ectd：

func (r *raft) Step(m pb.Message) error {
	// Handle the message term, which may result in our stepping down to a follower.
	switch {
	...
	//#1
	case m.Term > r.Term:
		if m.Type == pb.MsgVote || m.Type == pb.MsgPreVote {
			force := bytes.Equal(m.Context, []byte(campaignTransfer))
			inLease := r.checkQuorum && r.lead != None && r.electionElapsed < r.electionTimeout
			if !force && inLease {
				// If a server receives a RequestVote request within the minimum election timeout
				// of hearing from a current leader, it does not update its term or grant its vote
				r.logger.Infof("%x [logterm: %d, index: %d, vote: %x] ignored %s from %x [logterm: %d, index: %d] at term %d: lease is not expired (remaining ticks: %d)",
					r.id, r.raftLog.lastTerm(), r.raftLog.lastIndex(), r.Vote, m.Type, m.From, m.LogTerm, m.Index, r.Term, r.electionTimeout-r.electionElapsed)
				return nil
			}
		}
...

我认为Raft论文阐述的最正统的raft应该是不加1，以下摘自《In Search of an Understandable Consensus Algorithm》第5章“Rules for Servers”:

All Servers:
•If RPC request or response contains term T > currentTerm: set currentTerm = T, convert to follower (§5.1)

如上，节点间所有rpc请求的接收者当收到的term>currentTerm，都需要stepdown，这是个公共行为（不因节点角色不同而改变），所以handleVoteRequest时尽管候选人的log可能是陈旧的，leader一样会stepdown。为了应对@fengjiachun提到的情况，才提出了preVote流程。当然，在《Consensus Bridging Theory and Practice》论文第9.6章中，只是提及preCandidate的currTerm不加1，并没有对request.term做出明确说明，这个如何实现，见仁见智。如果把handlePreVoteRequest过程特殊化，不实现“If RPC request or response contains term T > currentTerm: set currentTerm = T, convert to follower (§5.1)”，也是可以的。其实raft里的很多细节我们都可以有细微的修改，只要最终能够自圆其说而不出漏洞即可，但个人而言倾向于正统的做法，减少出错机会。

如上，preVote的目的，就是针对@fengjiachun刚才说的场景的。对于@killme2008 说的第1点，我认为preVote的确是种探测，但是没必要做request.term=currTerm+1去探测。是否拒绝preVote的关键，log/term对比这个是基本的，但是我认为更重要的是“时间”（看看是否还处于当前leader的租期中），因为vote（正式投票）也会判断log/term，preVote的根本目的是“防止网络分区后的节点发起投票使活生生的leader退位”，光看log/term是不够的，还要看leader是否还活着。

鄙人愚见，不知道理解到不到位，还望指教。
PR周末可以提一个，如果能接受鄙人非常荣幸，或者你们enhance一下也是ok的哈。^^

[killme2008]

感谢回复。

1. jraft 更多还是参考 braft 和 etcd 实现而来，这块实现并没有完全遵循论文去做。探测是否 term+1 我觉的是一个技术决策和实现细节，并不影响最终结果的正确性。jraft 在 term+1 = currentTerm 的情况下或者链接重连后会主动 checkReplicator，强制发送心跳或者 entries 给“回归”的 follower，来尽力阻止他发起选举。

2. 这里和 @fengjiachun 讨论后，在日志变更较少或者没有（纯选举）的场景下，确实存在这种不必要的 leader 波动，但是同样，在存在时钟漂移的情况下，时间的判断本身是不准确，也会出现可能 leader 选举延迟的情况。考虑到大部分此类应用是在局域网下运行，时钟的同步是相对有保证的，加上这个 leader 有效期判断更为合理，并且较为符合 prevote 的初衷，我们会做下改进。欢迎提出 PR，如果不方便，我们会在开发分支做个修正。

感谢这么仔细的代码分析和反馈。

[shiftyman]

感谢答复释疑，鄙人收获良多。
PR方便，举手之劳且深感荣幸。
后续或许还有更多的issue，还望赐教指导。
再次感谢。

[fengjiachun]

@shiftyman 由于 Lease read 的处理在 jraft 中存在不严谨的地方，已经由 @killme2008 紧急 fix 了，恰好又覆盖了这个 issue；不管如何，还是非常感谢你提的 PR，欢迎继续

[shiftyman]

我看了那个fix，感觉可能还有问题？
@killme2008 大神加了这个代码：

do {
   if (this.leaderId != null && !this.leaderId.isEmpty() && isLeaderLeaseValid()) {
	 LOG.info(
		"Node {} ignore PreVote from {} in term {} currTerm {}, because the leader {}'s lease is still valid.",
		this.getNodeId(), request.getServerId(), request.getTerm(), this.currTerm, this.leaderId);
	 break;
 }
 ...

但是leader还是会投同意票，因为这里leader调用isLeaderLeaseValid会返回false。
考虑3节点，1节点网络隔离然后恢复之后，发起prevote，leader会投赞成，因此此节点得2票，发起vote。。。
——————————————————————————————————————————————
我周末提的PR是这么考虑的，你们再看下：

 ...
else if (request.getTerm() == this.currTerm + 1) {
	// As a leader, it will not agree this pre-vote if no higher term received.
	if (this.state == State.STATE_LEADER) {
		LOG.info("Node {} ignore PreVote from {} in term {} currTerm {} because it's a leader",
			this.getNodeId(), request.getServerId(), request.getTerm(), this.currTerm);

		// A follower replicator may not be started when this node become leader, so we must check it.
		// check replicator state
		checkReplicator(candidateId);
		break;
	} else {
		// Any node except leader should check whether the current leader has exceeded it's lease first.
		// This judgment needs to be made only during the same term, because when the initiator's term is higher, the current leader must also be untrustworthy.
		if (Utils.monotonicMs() - this.lastLeaderTimestamp < options.getElectionTimeoutMs()) {
			LOG.info("Node {} ignore PreVote from {} in term {} currTerm {} because there is currently a leader",
			this.getNodeId(), request.getServerId(), request.getTerm(), this.currTerm);
			break;
		}
	}
}
...

我认为，当发起者的term=接收者的term，这是最常规且需要特殊处理的情况。
此时，leader直接拒绝且checkReplicator；而其他角色的节点，检查leader的租期，租期未过则拒绝。

另外，当发起者的term>接收者的term，我没有加这些判断，因为我认为此时不管是leader，还是follower，接收到更高的term的prevote，都应该无条件服从，因为当前term的leader一定是不可信赖的。比如有这种情况：
5节点集群，term=1时，leader+1个follower 和 另外3个follower 发生网络分区，此时3节点在term=2选举出新的leader。当那个term=2的leader挂掉，term=2的1个follower发起选举。此时刚好网络恢复，那么term=1的follower节点可能会拒绝此选举（因为仍然受到term=1的leader心跳），这样可能会造成一些情况。

@fengjiachun @killme2008 两位大神再看看，如果觉得合理，小弟可以再把PR提回去。

PS: TravisCI报的这个错误是怎么回事？

$ sh ./.middleware-common/check_format.sh
Please commit your change before run this shell, un commit files:
M jraft-core/src/main/java/com/alipay/sofa/jraft/core/NodeImpl.java
./.middleware-common/check_format.sh: 7: exit: Illegal number: -1
The command "sh ./.middleware-common/check_format.sh" exited with 2.

[fengjiachun]

"但是leader还是会投同意票，因为这里leader调用isLeaderLeaseValid会返回false。"

@shiftyman 是的，你说的这个问题存在，我们可不可以简单一点？leader节点在 checkDeadNodes()方法中更新 lastLeaderTimestamp ?

[fengjiachun]

checkDeadNodes() 是由定时器调度的，我们可以把调度时间缩小的 ET 的一半，这样不管 leader 还是 follower 都使用 isLeaderLeaseValid 的判断逻辑？ @shiftyman 你觉得如何？

[shiftyman]

这个可以的，但是我在上面还提及一种很奇葩的场景：

5节点集群，term=1时，leader+1个follower（命名为groupA） 和 另外3个follower（命名为groupB） 发生网络分区，此时groupB在term=2选举出新的leader。随后，groupB的leader挂掉，groupB的1个follower发起term=3的prevote。此时如果groupB和groupA中的follower网络恢复，那么groupA的follower节点仍然会拒绝此选举（因为仍然接收groupA的leader心跳），只有当groupA的leader和groupB的网络连通，才能选举成功。

当然这种场景概率极小，如果不考虑，用你刚刚提及的方式改下就ok啦，代码的确会简单点。

[killme2008]

@shiftyman 你说的这个极端情况不会出现的，因为 groupA 的 leader 也有 step down timeout 的定时器，他在检测到没有超过半数节点 alive 的情况下，会主动 step down。

[killme2008]

@shiftyman 在 stepdown 定时器中更新这个时间戳，我和 @fengjiachun 讨论下来是比较好的方案，侵入最小，条件判断也更为统一。欢迎你来提这个改动，不好意思，因为上次看到你暂时没有提出 PR，我就越俎代庖先做了修复。

[shiftyman]

没关系，前两天比较忙不好意思。
之前没细看step down定时器处的逻辑，刚才补充了下，学习了^^

[fengjiachun]

@shiftyman 非常感谢这么细致的分析以及 PR