参考 MIT 6.824 2020 课程 LAB2 实现的 C++ 版本，节点通过 RPC 通信，目前已完成：

• leader election
• log replicated
• kv store without snapshot

CAP 定理指的是：

• Consistency - 一致性
• Availability - 可用性
• Partition-tolerance - 分区容错性

在一个分布式系统中，不能同时满足3种属性，一般同时满足 CP 或 AP。

如出现网络分区时，要保证可用性，分区 A 的请求无法同步到 分区 B，此时不满足一致性。而要满足一致性，则要保证分区 A 和分区 B 同步，由于出现网络分区，此时请求会阻塞，不满足可用性。

• 弱一致性：强调最终一致性，可以分别向两个节点请求，且不立刻同步，但经过一段时间后两个节点状态相同。一个典型例子是 DNS 域名系统。
• 强一致性：对节点 A 的请求能立刻在节点 B 看到，也就是直到节点 A 和节点 B 同步，这个请求才完成。

共识算法集群对某个值的数据达成共识，比如 Paxos 能保证对于某个指定序列的位置，在多个 proposer 的情况下只有一个值会被接收

常见的有 Paxos、ZAB、Raft。后两者其实都算是 multi-Paxos 的变种。即集群选择出一个 leader 来向其他节点提交。

考虑一个服务器集群，每台服务器都可对外服务，那么如何确保同步问题？目前一般的解决方法是主从模型，所有请求都通过 leader 处理，follower 只进行数据备份。相比 Paxos 多提议者和两段式提交简化了设计。

但如果 leader 宕机，需要从 follower 中选出新的 leader。理论上所有从节点都应该和主节点的数据一致，但由于网络原因（网络分区，数据无序到达）可能导致每个从节点都有不同的数据。为了解决这个问题提出了：

1. 日志状态机模型：使用日志写入，而不是直接对 server 上的数据进行修改，保证到从节点的同步请求有序且能够重新计算出当前状态。

2. Quorum机制：只有过半节点写入才算请求成功。

比如一个 KV 服务器，对其的每个请求都以日志的形式追加并持久化。这样当某台机器宕机，只要按照持久化日志的请求按需执行就能恢复到之前的状态。

当客户端请求到来，主节点先将请求转化为 log entry，然后向所有节点同步，只有过半接收并持久化时才能返回。

Raft 节点有三种角色：Leader、Follower、Candidate。当集群正常工作时，只有1个主节点和多个从节点，主节点通过心跳与从节点保持联系。

选举流程：

1. 无重复投票。在一个任期内，每一个节点只能投一票，避免了两个候选人都接到过半票数。当收到选举请求时，先比较任期，如果任期比节点当前任期小，直接拒绝。如果任期比当前节点大，则当前节点变成 follower。但如果有两个节点同时发起选举，这时它们的任期一样，那么当前节点先投票然后拒绝后面的请求，直到出现更大的任期。
2. 日志比较。当主节点宕机，优先选择日志最新的节点。当收到选举请求，发现任期更大，则当前节点提升任期。随后比较日志索引，如果索引更小则拒绝投票。由于 Raft 集群的请求会保证被过半节点同步，所以那些因为网络分区等原因失去联系然后由发起选举的节点由于日志不是最新无法得不到投票。

选举中可能发生的问题：

分割选举：在同一任期内两个候选人同时发起选举，得到相同票数无法选出主节点，然后超时发起下一轮选举。造成这种现象的原因有：1.集群节点为偶数，导致两个候选人各出现相同票数。2.超时时间相同，两个节点同时选举，在同一时间段抢夺票数。 解决方法：

1. 集群节点数设置为奇数，避免同一任期两个候选人获得相同票数导致选举失败。

2. 选举超时时间随机，如果主节点挂掉，尽量只让第一个超时的节点发起选举。

Raft 采取日志状态机模型，每一次操作都会被当作一条 log entry，通过同步集群中的日志来获得强一致性。

节点中的日志也分为两三状态：

• uncommitted。未提交，即主节点还没得到过半节点确认。
• committed。已提交。即主节点已经确认有过半节点收到该条 log。此时可以完成日志的持久化并将结果返回给客户端。
• applyed。已交付。已经持久化。

同步过程：

1. 主节点发送心跳消息，附带最新的 log
2. 从节点收到心跳，比较 log 与自身 log。如果不同步，回应主节点从哪里开始不同步；如果同步，回应主节点已同步的 logIndex
3. 主节点收到回应。如果发现从节点日志不同步，选择需要同步的日志发送给从节点。如果发现从节点已成功接收 log，则更新 matchIndex。如果有过半的从节点的 matchIndex > N，则将 commitIndex 更新到 N。

1. 新的主节点选举成功后，怎么知道别的节点有哪些日志？

主节点用 nextIndex 和 matchIndex 数组来分别记录每个节点需要的下一条日志和已经确认的日志。前者用于在发心跳时选择日志发送给对应的节点，后者用于更新集群的 commitIndex。

当一个新的 leader 被选出来，首先会初始化这两个数组，Raft 采用的是一种乐观的策略，即认为目前所有节点的日志都与它一样，于是 nextIndex 就是 leader 的 lastLogIndex + 1。而由于主节点还不知道所有节点的日志同步情况，matchIndex 初始化为 0。

从节点收到新主节点的心跳包时，如果日志不同步，会发现主节点发来的日志不匹配，然后找到冲突的 logIndex 和 logterm 发送给主节点。主节点收到后根据这两个信息更新节点的 nextIndex，下一次心跳时再发送节点需要的日志。

主节点收到从节点的回复后，开始更新 matchIndex 与commitIndex。当 commitIndex 更新，主节点也会在心跳包中加上这一信息告诉从节点可持久化的日志。

如果集群状态稳定，每个节点的 matchIndex 会和 leader 的 commitIndex 保持一致，实现了一致性。如果某个节点故障，恢复时也能通过 nextIndex 的回滚迅速与主节点同步日志，而如果主节点故障，拥有最新日志的从节点会选举成功并如上面的流程般同步。

2. commitIndex 推进时机？

只有 leader 确认过半节点收到 log 时（通过 macthIndex）才能更新 commitIndex，随后才能被持久化并对客户端可见。如果主节点未经确认就更新 commitIndex。如果出现网络分区，少数集群的 leader 更新 commitIndex 并持久化，而多数集群的 leader 也更新 commitIndex，就会导致访问两个 leader 出现不同的结果。

而采用过半更新的策略，即使少数集群的 leader 收到大量的 log，但这些 log 并不能被 commit。但网络分区恢复时，少数集群 leader 继续发送心跳会知道自己不是最新的任期了，降级为跟随者，随后在于新 leader 的同步中丢弃这些未同步日志，恢复数据的一致。

除了过半更新，commitIndex 还需满足另一个条件：leader 不能 commit term 不是 currentTerm 的 log。这一点在 Raft 作者的论文中有提及：

假设在 c 阶段 S1 为 leader，term 为 4，其发现 term 2 的 log 已被多数节点同步（S1、S2、S3），如果 commit log 2，那么这时可能出现 d1 和 d2 两种情况。d1 是 此时 S1 挂掉，由于 S5 有最新的 term log，成为 leader，这时它会发现从节点提交的 log 2 与其冲突，直接覆盖掉导致状态机的不一致。 d2 是 S1 没挂，继续同步 log 4，此时 S5 不可能成为 leader，不会出现问题。

而如果对 commitIndex 的更新加限制：不能 commit term 不是 currentTerm 的 log。那么在 c 阶段 S1 发现过半节点都有 log 2，但由于 log 2 的 term 是 2，而当前 term 是 4，不能更新。知道多数节点都得到了 log 4，此时同步 log 4 之前的所有节点，这时就算 S1 挂掉， S5 发起选举也不会成为 leader。

3. 从节点如何找到冲突的日志告知主节点？

如果有5个节点，假设出现分区，旧的主节点和一个从节点一个分区（分区1），此时其他三个节点选举出 leader（分区2）；现在有两个客户端往2个分区各追加50条日志，分区1由于不足节点数一半，虽然会追加到节点的 log 中，但commitIndex 不会更新，而分区2正常更新 commitIndex。

现在让分区1和分区2的一个从节点在一个新的分区内，此时分区2的从节点有更高的任期和日志，会成为新的主节点，此时主节点和两个从节点的 log 各有50条记录，但从节点的 log 是旧的，应该与新的主节点同步：

• 从节点收到主节点心跳包，发现虽然它们的 log 数量一样，但最后一条 log 的 term 不同（从节点的 term 是旧的），说明从节点的 log 是无效的，就找到这个无效 term 的第一条 log，从这个 log 开始所有属于这个无效 term的 log 都应该丢弃

4. 单个节点出现网络分区

测试时遇到的情况，一个节点与集群断开连接，此时发起超时选举一直失败，然后不断递增 term。当网络分区恢复时，继续发起选举，其他节点会发现这个节点的 term 更大从而降级为跟随者。虽然因为日志的限制这个节点不能成为 leader，但这仍然导致正常工作的 leader 被降级为 follower，导致新的一轮没必要的选举。查阅资料后发现可以通过 preVote 解决。即节点发起 election 的时候，先进行一轮预选举，同样是发起 RequestVote，但先不递增自己的 term，而是在 RequestArg 中先增加 term。如果收到过半的回复，说明该节点可以成为 leader，此时递增 term，再发起一轮 RequestVote。

单机测试多个 Raft 节点的选举与日志同步过程：

1. 3个节点能否选举成功
2. 主节点掉线能否成功选主；旧主节点重连后能否降级为从节点；集群有一半以上节点掉线能否选举成功
3. 正常连接下往 leader 发三个请求并检查所有 Raft 是否同步
4. 少数节点掉线后往 leader 发送请求剩余节点能否同步；节点重连能否同步
5. 多数节点掉线时 leader 能否 commit；网络恢复后发送命令所有节点能否同步
6. 主节点出现网络分区后分别往旧主节点和新主节点发送请求能否 commit；旧主节点恢复分区后能否日志同步
7. 出现掉线和网络分区时能否正常选主和 commit；最终日志能否一致