线性一致性、客户端协议与BUG修复

[leakey0626]

非常感谢莫那·鲁道给我们提供了如此优秀的raft开源项目！

我是raft的初学者大东，在学习您的项目的过程中，我发现了该项目存在一定的优化空间，于是我对代码进行了一些增改，希望能达到锦上添花的效果。下面是我对优化点的说明：

日志提交

问题描述

在原项目中，跟随者接收到 append entry 请求后，会立即将日志内容应用到状态机，个人认为这种做法有风险。

假设日志还未分发到多数节点时，【领导者A】宕机，并且下一任【领导者B】恰好不含该日志，那么该日志将会在【领导者B】发出它的 append entry 请求时被清除。但原先持有该日志的节点已经将其应用到状态机了，并且无法撤销 apply。所以，该机制会导致状态机数据与日志数据的不一致。

这种不一致一方面会导致我们无法通过日志准确地恢复出状态机的数据，不利于备份和分析；另一方面，若后期对项目进行扩展，让跟随者承担一部分“读操作”的职责时，会产生严重的数据不一致问题。

优化

领导者提交日志的逻辑修改为：

1. 写本地日志
2. 发送 append entry 请求
3. 大多数跟随者同意后，修改 commit index 并将日志应用至状态机

跟随者提交日志的逻辑修改为：

1. 收到 append entry 请求
2. 若不是心跳请求，则写入本地日志
3. 与领导者同步 commit index，将 index ≤ commit index 的日志应用至状态机
4. 同意 append entry 请求

补充：

1. commit index 会持久化到节点的本地存储空间，可以确保节点重启能后恢复到发生故障之前的状态
2. 对 preLog 匹配逻辑进行了细微的完善：日志索引从0开始；没有日志时，getLastIndex返回-1，getPreLog返回{-1，-1}

no-op 空日志

问题描述

1. 结论①：新领导者上任后不可直接提交旧领导者未提交的日志，即使其已被复制到多数节点；只能在提交自己任期的日志时间接提交旧日志
2. 论证①（反证法）：上图描述了一种可能会破坏数据持久性的情况。任期为2的领导者S1将日志复制到S2后宕机。紧接着任期为3的领导者S5上台，在本地写入了若干日志，然而还没来得及将日志复制到其它节点就宕机了。S1重新上线并恰好当选任期为4的领导者。在没有结论①约束的情况下，S1可以将任期为2的日志复制到S3并提交。如果此时S1宕机，那么S5必然会当选任期为5的领导者，因为它的日志任期是最大的。S5在将它的第3至第5条日志复制到S1~S3时，这些节点里任期为2的日志会被覆盖——这不符合已提交的日志不能被修改的要求。因此需要引入结论①来避免这种情况，该结论在部分raft资料里被称为“延迟提交”
3. 补充①：引入结论①看似很安全，但如果任期为4的领导者S1在上任后没有收到任何客户端的写请求，那么它将没有机会提交任期为2的日志，发出该写请求的客户端会因此而阻塞——这不符合raft的可用性要求

优化

引入 no-op 空日志来解决补充①里提到的可用性问题：

1. 新领导者上任后，立即向 raft 集群写入一条 command 为 null 的日志并提交
2. 这条日志只有索引和任期信息，不会改变状态机的数据
3. 空日志属于领导者任期的日志，其提交之后，可以确保在此之前的日志都被正确提交。既能满足结论①的约束，又可以解决上述的可用性问题

客户端协议

优化

1. 完善了客户端请求类 RaftClientRPC：若 RPC 调用超时，会将请求发送至另一个节点，不断循环直至获取到服务端响应

2. 引入了幂等性机制：在客户端请求体中加入由 ip 和序号组成的 request id。当请求被 raft 集群响应后，request id 会存储至各节点的状态机中。这样可以保证即使领导者在执行命令之后、返回客户端响应之前宕机，客户端去寻找下一任领导者处理请求时，同一命令不会在状态机上执行两次

3. 实现了基于命令行交互的客户端：解析用户输入并返回处理结果

   

线性一致性

问题描述

系统发生网络分区时，可能存在两个领导者。旧领导者仍在工作，但集群的另一部分已经选举出一个新的领导者，并提交了新的日志条目。如果此时客户端连接的恰好是旧领导者，那么它将返回旧的数据给客户端，这不满足线性一致性——读操作必须返回最近一次提交的写操作的结果。

优化

结合心跳机制实现线性一致性：

1. 领导者接收到客户端的读请求后，需要先确认它是当前集群的真正领导者——向跟随者发送心跳请求，并统计响应结果
2. 如果收到多数派的响应，那么可以认为在发出心跳的那一刻，集群中不存在任期更新的领导者，当前领导者节点存储的就是最新的数据。此时可以继续执行读请求，返回数据给客户端

运行说明

1. 在 VM 参数中配置节点端口号，如 -Dserver.port=8775
2. 在不同端口下运行 RaftNodeBootStrap
3. 启动客户端 RaftClient 进行调试和验证

---

参考：《深入理解分布式系统》，唐伟志

[stateIs0]

感谢pr，我先看看细节😁

[leakey0626]

哈喽，请问review过程还需要我提供什么帮助吗（本机上测试ok）

[stateIs0]

哈喽，请问review过程还需要我提供什么帮助吗（本机上测试ok）

我正在看代码。改的地方比较多，比如这个 心跳间隔基数 为什么改成 300？

[stateIs0]

哈喽，请问review过程还需要我提供什么帮助吗（本机上测试ok）

还有一些重入锁，为什么把超时锁变成无超时的？我理解后者相较而言不容易排查问题。

[leakey0626]

嗯嗯，小改动确实比较多，辛苦您review了~ 我为了提高测试效率（raft整体运行效率），把心跳时间间隔、选举超时时间等参数调小了。我应该改回去或者说明一下的，后面给忘记了，不好意思。。

[leakey0626]

哈喽，请问review过程还需要我提供什么帮助吗（本机上测试ok）

还有一些重入锁，为什么把超时锁变成无超时的？我理解后者相较而言不容易排查问题。

您指的是不是DefaultLogModule里面的lock？原项目这部分的代码在tryLock超时之后仍会继续执行，这样难以保证写日志过程的线程安全。我参考了另外一些开源项目的设计，如 sofa-jraft 、wenweihu86的raft-java，它们也是采用无超时锁，所以我认为不存在死锁条件时可以使用无超时锁。如果有说得不对的地方烦请指出~

[stateIs0]

使用超时锁 是一种好的开发习惯

[leakey0626]

受教了~ 如果此处改为 if (!lock.tryLock(3000, MILLISECONDS)) return; 会不会更合适一些呢

[leakey0626]

抱歉，感觉代码还有很多不完善的地方，我再改进一下~

[stateIs0]

@leakey0626 刚刚我还在 review 呢，回过头就 close 了 😂

[leakey0626]

@leakey0626 刚刚我还在 review 呢，回过头就 close 了 😂

这两天回看代码的时候发现我优化的部分有不少问题，为了不耽误您的时间，我就想着先 close，改完之后再提交。 可能有点缺乏 git 使用经验，擅自关闭 pr 是不是不太友好。。

[stateIs0]

@leakey0626 刚刚我还在 review 呢，回过头就 close 了 😂

这两天回看代码的时候发现我优化的部分有不少问题，为了不耽误您的时间，我就想着先 close，改完之后再提交。 可能有点缺乏 git 使用经验，擅自关闭 pr 是不是不太友好。。

没关系，你再看看呗，我也研究你提的几个问题。期待你的新提pr。

[leakey0626]

@leakey0626 刚刚我还在 review 呢，回过头就 close 了 😂

这两天回看代码的时候发现我优化的部分有不少问题，为了不耽误您的时间，我就想着先 close，改完之后再提交。 可能有点缺乏 git 使用经验，擅自关闭 pr 是不是不太友好。。

没关系，你再看看呗，我也研究你提的几个问题。期待你的新提pr。

跟您的交流过程中学到了很多东西，非常感谢