最近在看RocketMQ 的raft实现，名字叫Dledger。找了一篇源码分析的博客发现其中很多细节都解释的不是很清晰。Dledger 选主过程

首先我们要知道RocketMQ Dledger有哪些特性，在github官网上我们可以看到Dledger实现了很多原论文In search of an understandable consensus algorithm中没有的的特性。因为我暂时没有找到官方的设计文档，代码中的注释也暂时不是很完整，因此理解这些特性对于理解源代码有很重要的意义。其中最重要的是Pre-vote 机制。

本文需要读者对Raft算法的原论文有一定的熟悉程度。

Pre-vote机制是在原作者的258页博士论文Ongaro Phd
第九章中提过的，其目标是解决在网络分区发生时，处于少数分区的节点不会一直增加Term, 更具体的应用可以在原论文中搜索得到。

Pre-vote的思想简单来说就是，在Candidate increase term之前，要先在不增加term的情况下看自己是否满足 比majority数量的node要 more up-to-date。如果一个Candidate知道自己一定不可能被选为Leader，那么就会自觉的increase term的值。这是Pre-vote。

而DLedger的实现里还有一个很大和原论文不同的地方。Dledger 会产生更多的Candidate节点。举例来说，当Leader得知有更大term的voting process正在进行，或者具有更大term的leader已经被选举出来之后，Leader并不会退化为follower，而是退化为 "尚未进行pre-vote的Candidate“。 这个体现了Dledger 不同的node有不同的leader preference(使用者可能希望leader 大多数情况都在某一个node上)。而这样的设计可以使以前的Leader能够在因为某些暂时意外原因stepped down之后有机会尽快恢复继续当leader。

主要的handleVote方法

public CompletableFuture<VoteResponse> handleVote(VoteRequest request, boolean self) {
        //hold the lock to get the latest term, leaderId, ledgerEndIndex
        synchronized (memberState) {
            // PRECONDITION CHECk
            ...

            if (request.getTerm() < memberState.currTerm()) {
                return CompletableFuture.completedFuture(new VoteResponse(request).term(memberState.currTerm()).voteResult(VoteResponse.RESULT.REJECT_EXPIRED_VOTE_TERM));
            } else if (request.getTerm() == memberState.currTerm()) {
                if (memberState.currVoteFor() == null) {
                    //just let it go
                } else if (memberState.currVoteFor().equals(request.getLeaderId())) {
                    //repeat just let it go
                } else {
                    if (memberState.getLeaderId() != null) {
                        return CompletableFuture.completedFuture(new VoteResponse(request).term(memberState.currTerm()).voteResult(VoteResponse.RESULT.REJECT_ALREADY_HAS_LEADER));
                    } else {
                        return CompletableFuture.completedFuture(new VoteResponse(request).term(memberState.currTerm()).voteResult(VoteResponse.RESULT.REJECT_ALREADY_VOTED));
                    }
                }
            } else {
                changeRoleToCandidate(request.getTerm());
                needIncreaseTermImmediately = true;
                return CompletableFuture.completedFuture(new VoteResponse(request).term(memberState.currTerm()).voteResult(VoteResponse.RESULT.REJECT_TERM_NOT_READY));
            }
            
            ...
            // Check if candidate is more up-to-date than current node

            memberState.setCurrVoteFor(request.getLeaderId());
            return CompletableFuture.completedFuture(new VoteResponse(request).term(memberState.currTerm()).voteResult(VoteResponse.RESULT.ACCEPT));
        }

一个全新的cluster启动

我们假设有4个 node， node 0, 1, 2 从follower转变为candidate的timeout 时间由小到大排序, 优先级由高到低。node 2 和 node 3 优先级可认为相同。

1.刚启动时，根据代码里的定义

2. 假设node0 的vote请求最先到达其他节点, 因为node0的初始lastParseResult为WAIT_TO_REVOTE, node0并不会将term + 1。，根据代码, node 1,2,3 分别

• 判断request.term() 是否等于 currTerm，发现相等
• 判断currVoteFor 是否是null ，发现是，于是进入接下来的more up-to-date 判断逻辑
• more up-to-date 判断逻辑 通过，设置currVotedFor为node0, 并返回同意请求。

node0 成为leader，此时状态为

3. node 123收到来自node0的心跳包之后，发现

• request.getTerm() == memberState.currTerm()
• memberState.getLeaderId() == null
  两个条件都满足，根据代码，node 123 退化为 follower 状态。
  此时状态为

4. 假设经过一段比较长的时间，所有的通讯全都畅通无阻，没有发生leader选举，心跳正常，log复制进度完全相同, 因此所有的其他candidate会。 连。

5. 突然node0完全宕机, 丢失所有通讯，并且确保不会重连。这个时候node1 最先因为timeout变为Candidate状态。

6. node1 发出vote() 请求，curVotedFor变成子集，因为是WAIT_TO_REVOTE 状态，并不会将 term + 1。但由于此时 node2, node3 都还认为 leader 仍然在，因此会拒绝node 1 发出的请求。这样的状况一直持续到node 2, node 3 都timeout并变成candidate的状态。这时他们的状态是

7. 这个情况和刚开始的情况非常相似，但是我们会发现currVotedFor不再是null了。这个时候我们还是认为node 1 先在maintainAsCandidate() 中提出投票请求.

node1 在统计所有的response之后，(使用如下代码)

lastVoteCost = DLedgerUtils.elapsed(startVoteTimeMs);
VoteResponse.ParseResult parseResult;
if (knownMaxTermInGroup.get() > term) {
    parseResult = VoteResponse.ParseResult.WAIT_TO_VOTE_NEXT;
    nextTimeToRequestVote = getNextTimeToRequestVote();
    changeRoleToCandidate(knownMaxTermInGroup.get());
} else if (alreadyHasLeader.get()) {
    parseResult = VoteResponse.ParseResult.WAIT_TO_VOTE_NEXT;
    nextTimeToRequestVote = getNextTimeToRequestVote() + heartBeatTimeIntervalMs * maxHeartBeatLeak;
} else if (!memberState.isQuorum(validNum.get())) {
    parseResult = VoteResponse.ParseResult.WAIT_TO_REVOTE;
    nextTimeToRequestVote = getNextTimeToRequestVote();
} else if (memberState.isQuorum(acceptedNum.get())) {
    parseResult = VoteResponse.ParseResult.PASSED;
} else if (memberState.isQuorum(acceptedNum.get() + notReadyTermNum.get())) {
    parseResult = VoteResponse.ParseResult.REVOTE_IMMEDIATELY;
} else if (memberState.isQuorum(acceptedNum.get() + biggerLedgerNum.get())) {
    parseResult = VoteResponse.ParseResult.WAIT_TO_REVOTE;
    nextTimeToRequestVote = getNextTimeToRequestVote();
} else {
    parseResult = VoteResponse.ParseResult.WAIT_TO_VOTE_NEXT;
    nextTimeToRequestVote = getNextTimeToRequestVote();
}

// 原文链接：https://blog.csdn.net/prestigeding/article/details/99697323

发现都不满足, 因此走到最后一个默认的else branch里，将lastParseResult 设置成WAIT_TO_VOTE_NEXT。

8. 假设node 1 再一次进入maintainAsCandidate() 方法，这时因为是WAIT_TO_VOTE_NEXT, 所以要把term + 1 后再发起vote,之后状态变为

9. 注意此时node 2， 3 虽然是candidate，但都还没投过票 而node 2, 3 在收到来自node 1 的vote 请求时，发现

• request.term() > memberState.currTerm()

发现term 不consistent，于是要拒绝，并且执行以下语句

这里我没怎么懂，为什么必须要term 相同才能投票嘞（可能处于性能优化的考虑？）

// 
changeRoleToCandidate(request.getTerm());
needIncreaseTermImmediately = true;

这里changeRoleToCandidate 的作用主要是更新knownMaxTermInGroup的值，needIncreaseTermImmediately 是使得下一次maintainAsCandidate()的时候要把currTerm

• 如果 knownMaxTermInGroup > currTerm， 则更新为knownMaxTermInGroup
• 如果 knownMaxTermInGroup = currTerm， 则更新为currTerm + 1

而此时 两件事情发生了

• node 1 收到 node2 的 REJECT 回复，发现memberState.isQuorum(acceptedNum.get() + notReadyTermNum.get() 成立，parse结果是REVOTE_IMMEDIATELY。立刻再次进入maintainAsCandidate() 方法，准备开始投票

• node 2 进入maintainAsCandidate() , 因为 needIncreaseTermImmediately 是true，因此要立马把currTerm 更新 1，并且准备开始投票

由于node 2 和node 3 对称，可认为node 3和 node 2 采取了相同的动作。

在大家都还未投票前（也没给自己投票前），此时状态为

那现在发生的事情就很奇怪了，第一种情况，假设 node1 的 vote 请求先到达 node 2 node 3。由于term增加后并没有把 currVotedFor 清空，这会导致node 2， node 3 不能同意该请求，node 1 被拒绝。

第二种情况， 假设node1 的请求在node 2， node 3 先给自己投票之后发出，那么node1 的vote 请求在到达node 2, 3 的时候会看到这样一个状态。node 1 无论如何都没法成功成为leader。

对于node 2，3情况类似。

我认为出现这种情况的主要原因在于：

• 如果candidate 的 term 大于接收者的 term，那么接收者会返回NOT_READY_TO_VOTE
• 而当candidate 的 term 等于接收者的 term时，会发现接收者的currVotedFor 要么是接收者自己，要么是上一个term的投票结果（因此是没有意义的结果），反正不会是Candidate自己（即使是也是错误的语义），也会被拒绝。

问题

• alreadyHasLeader.get() 似乎可以被优化。如果等到所有的follower 都认为没有leader了，有可能中途已经有半数的同意票了但是因为有一个follower还有lead使得再次等待。

• 每次更新term的时候，votedFor 也应该同时被修改，被改成null，否则就不make sense了。

• commit 值要怎么保证永远不回退？ （找到超过半数的node中所有commit的最大值）

首先所有都被初始化为Candiddate，currTerm是0, curVoted 是null.

• currentTerm
• votedFor: 很有可能和原论文中定义不同，follower的votedFor可能是null。
• commitLogs

volatile states:
commitIndex: index of highest log entry to be commited
lastApplied: index of highest log entry applied to state machine

volatile stats on leaders:

nextIndex: for each server, index of the next log entry to send to that server
matchIndex: for each server, index of highest log entry known to be replicated on server

https://blog.csdn.net/prestigeding/article/details/99697323