[OSPP开源之夏] 结合 NWR 实现 Flexible raft，用于自定义 Quorum 的大小

1294566108 commented 1 year ago

OSPP开源之夏官网课题链接：

https://summer-ospp.ac.cn/org/prodetail/2395a0390?list=org&navpage=org

背景：

JRaft是一个基于RAFT一致性算法的生产级高性能Java实现，它运行过程分为两个阶段，即Leader选举和日志复制。在原始的RAFT算法中，Leader选举和日志复制都需要获得多数派成员的支持。而NWR模型则可以在动态调整一致性强度的场景中使用，它需要满足W+R>N，以保证强一致性。JRaft将RAFT和NWR结合起来，使得用户可以根据不同的业务需求来动态调整Quorum的数量。例如，在一个写多读少的场景中，用户可以将多数派的数量从3调整为2，以降低达成共识的条件，从而提高写请求的效率。同时，为了保证RAFT的正确性，写Quorum的调整需要付出代价，即读Quorum的数量也需要相应调整。JRaft支持成员变更，因此用户可以配置(0,1]范围内的小数来计算W和R的具体值。通过使用JRaft，用户可以根据自己的业务需求来灵活地调整一致性强度，使得分布式系统在不同场景下都可以获得最佳的性能和正确性。

项目产出要求：

为 JRaft 实现自定义 Quorum 动态调节 Quorum 的参数
为自定义 Quorum 的场景增加 Jepsen Case。

难度：

进阶

导师：

刘源远 gege87417376@qq.com

项目技术要求：

掌握 RAFT 算法协商过程
基于 RAFT 设计 NWR 模型，编写具体设计文档

Quorum设计思路：

抽离出抽象父类Quorum作为MajorityQuorum（多数派确认模型，原Ballot类）和NWRQuorum（NWR模型）的模板。
用户首先需要在NodeOptions类中决定是否开启NWR模式，默认为多数派模型，用户手动设置读写Factor因子后，则视为开启了NWR模式。
NodeImpl#init方法进行逻辑处理，通过判断是否开启了NWR模式，构造对应的Quorum选票实例，例如MajorityQuorum与NWRQuorum。
在构建好选票实例过后，调用对应的方法可以进行选票的初始化（init）、投票（grant）等操作。

NWR涉及模块

Raft协议的Leader选举和日志复制等部分使用到多数派确认模型的地方，我们都需要对应为其添加NWR模型选择。所以在如下的模块中，需要新增NWR模型的逻辑：

Leader选举模块： 一个节点想要成为leader，会经过以下几个阶段：预投票、正式投票、当选leader。所以对于preVote、electSelf、becomeLeader等等与多数派模型相关的方法都会涉及代码的变更。
日志复制模块： 当leader收到客户端的事务请求或者follower与leader数据存在差距时，会调用 Replicator#sendEntries 去复制日志，日志复制消息属于事务消息；而心跳消息和探测消息，则是由 Replicator#sendEmptyEntries 发送的。在日志复制中，有哪些过程会涉及到多数派确认呢？一个是 NodeImpl#executeApplyingTasks ，一个是 NodeImpl#unsafeApplyConfiguration 。在执行这些方法的时候，都会使用 BallotBox#appendPendingTask 方法来构造一个待投票的Ballot（现在叫MajorityQuorum/NWRQuorum）并放置到投票箱中。
一致性读模块： 对于一致性读模块，在raft共识算法中，读取R个节点其实体现在R个节点的心跳响应。通过R个节点的心跳，能保证这个节点一定是leader，一定拥有最新的数据，我们并不是真正需要从R个节点里面读取数据。对应的修改部分，像 NodeImpl#ReadIndexHeartbeatResponseClosure 这样的方法，我们可以看到执行了心跳消息的多数派确认模型的逻辑，ReadIndexHeartbeatResponseClosure构造器里面传入了quorum的值，这里我们需要对应修改为NWR模型的逻辑。
成员变更模块： 对于JRaft成员变更来讲，核心逻辑是采用单成员变更的方式，即使需要同时变更多个成员时，也是会先整理出新add与新remove的成员，再逐个进行单成员变更。其核心方法 addPeer、removePeer、changePeers、resetPeers 等等都会涉及NWR模型的适配。

shihuili1218 commented 1 year ago

@1294566108 辛苦啦，听起来很不错，来尝试完成它吧！

另外可以把最新的文档，补充下，或者维护在rfc里面 https://github.com/sofastack/sofa-jraft/tree/master/rfcs

1294566108 commented 1 year ago

@1294566108 辛苦啦，听起来很不错，来尝试完成它吧！

另外可以把最新的文档，补充下，或者维护在rfc里面 https://github.com/sofastack/sofa-jraft/tree/master/rfcs

sofastack / sofa-jraft