dledger原理源码分析系列(三)-选主

简介

       dledger是openmessaging的一个组件， raft算法实现，用于分布式日志，本系列分析dledger如何实现raft概念，以及dledger在rocketmq的应用

      本系列使用dledger v0.40

      本文分析dledger的选主

关键词

Raft

Openmessaging

心跳/选主

参考资料

In Search of an Understandable Consensus Algorithm  raft论文简版

选主

         选主是dledger的关键特性，主节点承担处理Client请求，复制日志到跟随者节点，dledger通过心跳发起选举。

关键属性

本节介绍关键属性，为下面分析准备

• term 任期/轮次

任期: 新的选举开始到下一个选举开始，左闭右开的时间区间，包括选举期和工作期两部分

轮次：任期内选举的轮次，任期内可多轮不提升term选举

• needIncreaseTermImmediately

需要立即增加term的设置，只提升任期，但不对其他节点发起投票请求，用于term落后的节点

• nextTimeToRequestVote

下次请求投票时间

System.currentTimeMillis() + minVoteIntervalMs + random.nextInt(maxVoteIntervalMs - minVoteIntervalMs)

dledger根据情况有不同的设定，下次发起选举时间的差异正是选举的关键

• currVotedFor

本节点投票给谁了，该值提升term时设置为null；该值设置地方只有一处，处理投票handlerVote，即，不提升term节点，投票给谁不会改变

• currTerm

节点当前所处任期

• ledgerEndTerm/ledgerEndIndex

已写入日志的term；已写入日志的索引

两个数据是节点成为leader的关键数据，作为leader已写入日志的term/已写入日志的索引越多越好

分析

选举分3块，第一投票邀请；第二投票；第三投票统计，部署下一步操作，其中

投票邀请

候选者定时维护状态，maintainAsCandidate方法发起投票邀请，邀请其他节点(包括自己)为自己投票

1 检查是否符合投票条件，投票时间到 或者 设置了需要立即提升term

2 double check 节点处于候选者角色

3 是否提升term

lastParseResult是上一轮发起投票分析结果，参考后面投票统计

只需提升term，追赶上该轮投票的term，不发起投票邀请

4 获取节点的已写入的term/index

5 重置needIncreaseTermImmediately

term落后，设置该标记为true，提升term后，恢复默认

6 邀请节点投自己一票，邀请也发给自己

投票

节点，包括发起投票的领导者，处理投票请求

1 投票发起者的合法性检查

投票请求的leader是发起者，投票实际是拉票，邀请其他节点投自己一票

1.1 leader是否组内的节点

目前版本不知道集群变更，实际不会出现

1.2 不应该出现的leader

参看问题分析

-----------------------------------------分割线------------------------------------------

2 检查已写入日志term和index

这个好理解，想做leader，写入的日志应该比我多；比我少的，没资格让我投你票

-----------------------------------------分割线------------------------------------------

term相关检测

3  请求节点的term < 本节点term，拒绝投票，请求节点的term落后了

4  term一致

4.1 currVoteFor为空，还没投票

后面的检测没问题的话，本节点投票给发起节点

4.2  currVoteFor不为空，已投票，而且投的是发起节点

4.3  currVoteFor不为空，投票给其他节点了

下面继续细分，本节点是否已有leader，这里考虑一个问题，有无可能currVoteFor为空，并且有leader?

不可能，分两种情况，

1. 本节点是跟随者，本节点未进入本term选举，本节点term小于发起者term
2. 本节点是候选者，提升term置空currVoteFor，成为候选者要置空leader

4.4 本节点term落后了

设置needIncreaseTermImmediately，提升term，但不发起投票请求

5 发起节点term与本节点已写入日志term比较

与2相同，发起节点资格不够，不能投你

-----------------------------------------分割线------------------------------------------

6 本节点用户设置优先当领导，而且条件符合，不投票给发起节点，自己优先

7 最后，投票给请求节点

投票统计

7 首先准备好统计量

-----------------------------------------分割线------------------------------------------

统计不详细分析，看注释便清楚

-----------------------------------------分割线------------------------------------------

7.3 提早通过latch等待，3个条件

1. 已有选出leader

2. 票数已过半，自己将成为leader

3. 本节点未够票，剩下的票不过半，即，也没有其他人选上

7.4 统计所有节点数

总数达到allNum.get() == memberState.peerSize()，所有心跳请求返回(包括连接不上)，退出

* memberState.peerSize() 实为 memberState.peerSize()+1-1，peerSize从0开始，数量需+1，排除自己，数量-1

部署下一论投票行动

8 投票统计结果决定下一步投票行动

8.1 本节点term落后了

提升任期，再发起投票请求，这点跟投票者不一样，投票者term落后设置needIncreaseTermImmediately=true，即只提升，不发起投票请求，这样做容易理解，选出主节点，需要争票的少，投票的多，投票发起节点只有一个，投票的节点多个

8.2 集群已有leader，无需再发起投票，但不立即转为follower，延长下次投票，等待下一个leader的心跳，调整为正确的leader，便进入正常工作

8.3 有效返回节点数过少，通常是网络原因，只有等

8.4 除去日志比自身完整的节点，还不够票数当选，让贤，延迟下次投票邀请的时间，让其他节点发起投票

8.5 当选leader

8.6 加上term落后的节点够票数让本节点当选

此时，term落后的节点提升term，立即选举增加本节点当选的几率，但REVOTE_IMMEDIATELY实际没使用

8.7 选票分散，提升任期，投票

9 选上了，赶快坐上宝座当领导

总结：行动的目标是尽快选到领导者，策略上尽量逼近目标无疑是正确的。

有效性

本节去掉异常情况，只看选举的主体流程，分析一下选主的有效性，dledger的规则/逻辑怎样让分布节点获得过半票数

去掉的异常情况

1 本节点term落后

2 有效返回过少

3 写入日志term/index比投票节点小

4 投票节点term小于本节点

选举主体：

1 已经选出领导者

2 获得投票过半

3 投票分散，未能选为领导者

1/2 两种情况选举完成

3，提升term；设置下次投票时间，投票时间有范围的随机值，只要有不多于2个节点率先发起投票，其他节点投票，这就可以选出主节点

问题

选举未分析出来的点

不是预期的leader

目前没有分析出怎么出现这种情况

系列文章

• 架构，核心组件和rpc组件 完成
• 心跳和选举 完成
• 日志写入/复制和存储 TBD  包括日志写入和复制，日志存储组件
• 集成rocketmq rocketmq使用dledger实现消息存储复制；broker控制器 元数据复制
• 快照/状态机
• 集群成员变更  成员变更管理，节点的上线下线发现，dledger v0.4未实现，但计划中，未来版本实现
• jraft   “double check”  多重分析，jraft比较忠实实现了raft算法，在dledger基础上，再深入研究jraft对raft更深入的认识