基于Raft算法的DLedger-Library分析（一）-京东云开发者社区

### 1 背景

在分布式系统应用中，高可用、一致性是经常面临的问题，针对不同的应用场景，我们会选择不同的架构方式，比如master-slave、基于ZooKeeper选主。随着时间的推移，出现了基于Raft算法自动选主的方式，Raft是在Paxos的基础上，做了一些简化和限制，比如增加了日志必须是连续的，只支持领导者、跟随者和候选人三种状态，在理解和算法实现上都相对容易许多。

1）DLedger 是openMessaging发布的一个基于 Raft 实现的JAVA类库，可以方便引用到系统中，满足其高可用、高可靠、强一致的需求，其中在RocketMQ中作为消息Broker存储高可用实现的一种解决方案。

2）Raft将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选人（Candidate）：

- Leader：接受客户端请求，定时发送心跳包，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。
- Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。
- Candidate：Leader选举过程中的临时角色，该状态下的节点会发起投票，尝试选择自己为主节点，选举成功后，不会存在该状态下的节点

![](//img1.jcloudcs.com/developer.jdcloud.com/d5abb3c6-5b1b-4652-81b6-ecc4ba62ef1e20220601145209.png)

### 2 DLedger架构设计

DLedger 的实现大体可以分为以下两个部分：

-  选举 Leader 
-  日志复制

其整体架构如下图

<center>![](//img1.jcloudcs.com/developer.jdcloud.com/3b18ccff-55df-412c-8926-3f13b042ec5420220601145230.png)

注：图引用官网</center>
从上面的架构图中，有两个核心类：DLedgerLeaderElector 和 DLedgerStore，选举和文件存储。选出 leader 后，再由 leader 去接收数据的写入，同时同步到其他的 follower，这样就完成了整个 Raft 的写入过程

### 3 DLedger选主源码分析

#### 3.1 下载源码

从gitGub下载代码（https://github.com/openmessaging/dledger ），idea引入后，我们发现整个代码量很小，在分析代码时比较容易.

![](//img1.jcloudcs.com/developer.jdcloud.com/14d6e348-a5ce-4efe-8893-91480e1149ab20220601145322.png)

#### 3.2 选主流程分析

##### 3.2.1 原理

raft的选主过程实际是一个状态机的流转，在集群启动时每个节点的等待超时时间时随机的，在第一个节点超时时间到来，则主动向其他节点发起投票，在收到半数以上的投票后晋升为leader（投票过程是个循环的过程），同时发送心跳请求，其他候选节点收到主节点的请求后，改变自己为follower节点。

- term: 任期，每一轮投票都是一个任期，默认从0开始
- Quorum机制：简单说就是少说半数以上，比如3个节点，2个同意即可
- 超时时间： 在选举时，每个节点的超时时间在一定范围内是随机的，这样可以保证能够顺利选举

##### 3.2.2 代码分析

整个状态机的驱动，由线程每个10ms反复执行DLedgerLeaderElector.maintainState()方法。下面重点来分析其状态的驱动：

进入到核心方法maintainAsCandidate() ：

###### 1.step1 初始化

- term : 投票轮次。
- ledgerEndTermLeader: 节点当前的投票轮次。
- ledgerEndIndex: 当前日志的最大序列，即下一条日志的开始 index
- nextTimeToRequestVote： 下次发起投票的时间（随机的）
- needIncreaseTermImmediately：是否立即投票，在后面中会说明

在DLedger中每个节点的初始状态WAIT_TO_REVOTE，所以第一轮只是做了初始化。其中只有 memberState.nextTerm()这个代码会更改投票轮次

![](//img1.jcloudcs.com/developer.jdcloud.com/67e22531-5680-4d9f-97a9-c8c7eeb6219820220601145435.png)

###### 2.step2 投票

进入到核心方法handleVote()，这个方法主要是判断其他节点请求来后，根据自己的term和请求者的等判断是否投赞成票

![](//img1.jcloudcs.com/developer.jdcloud.com/2b81ea3c-4b54-4ac1-8350-69d390331b8120220601145503.png)

- ledgerEndIndex因为在日志复制过程中，每个节点的进度有可能是不一样的，所以在新的一轮选举时，这时不能投赞成票的
- 被选举者 term 小于 选举者的term，返回拒绝
- 被选举者 term 大于 选举者的term，则选举者进行下面操作：
- - 变成candidate(或者保持candidate)
- - 把needIncreaseImmediately设置为true。
- - 返回 REJECT_TERM_NOT_READY，这个在后面提到。
- 这里补充说明：
选举者 的下一次状态循环会进入到maintainAsCandidate()函数，然后因为needIncreaseImmediately为true，所以把term更新，同时重置计时器。 但是并没有立刻发出投票(此时选举者 的CurrVoteFor还是null，使得接下来给之前的voting candidate 投赞成票可能)

![](//img1.jcloudcs.com/developer.jdcloud.com/312e8e55-5d6b-456e-a663-61115533761a20220601145738.png)

获取所有node投票结果后开始计算票数：

![](//img1.jcloudcs.com/developer.jdcloud.com/d1cf1fe1-e694-444f-a922-de95b3b7bf6c20220601145759.png)

###### 3.step3 仲裁

在收到所有节点的投票结果计数后，进行仲裁，这里主要说明下图中这个条件

![](//img1.jcloudcs.com/developer.jdcloud.com/85e1efa7-bb12-4a29-a98a-76bb0c91f4a120220601145825.png)

- acceptNum：同意的数量
- notReadyTermNum：未准备好的数量（即结果为REJECT_TERM_NOT_READY）

这里没有重置nextTimeToRequestVote的时间，即刻再发起一次投票。结合上面的说明，这样保证了被选者能尽快去拿到这些notRead的节点的赞成票。

![](//img1.jcloudcs.com/developer.jdcloud.com/393a3fa1-e037-45e7-9b68-083b005e03ae20220601145849.png)

最终经过多次投票后，当一个node节点获取到半数以上投票后，更新自己未leader角色，同时向其他node节点发送heartBeat，其他节点在收到心跳信息后，将自己从candidate 变为follower。

#### 3.3 单元测试验证

##### 3.3.1 编写单元测试

![](//img1.jcloudcs.com/developer.jdcloud.com/a7664058-2aa6-4056-88d9-ec8ac122159620220601145953.png)

##### 3.3.2 日志分析

![](//img1.jcloudcs.com/developer.jdcloud.com/871a6198-6b95-44db-ab9e-a4a1805a901520220601150020.png)

#### 3.4 应用场景

1. DLedger 作为 RocketMQ （ version>=4.5.0）的消息存储已经发布
2. 基于DLedger 实现多节点的缓存同步更新
3. 基于日志复制的副本容错处理

### 4 总结

1. 这里只简单分析了选主过程，在阅读源码过程中会涉及很多java的基础及netty的使用，比如AQS、CompletableFuture等，有助于提高我们的编码能力。
2. DLedger在初始化时是将节点角色设置为candidate而不是follower 这个和原Raft是不同的地方，在节点角色转换过程中也稍有差别。

#### 参考文献

- https://github.com/openmessaging/dledger/wiki
- https://www.usenix.org/system/files/conference/atc14/atc14-paper-ongaro.pdf

------------

###### 自猿其说Tech-JDL京东物流技术与数据智能部
###### 作者：郭庆海