raft思考推导杂记

基础结论与疑问：

1. Leader不会删除任何自己的日志，只会将自己的日志复制到Follower中
2. Follower的日志可能被覆盖，常见场景：该Follower在某个term中是Leader，但是数据未复制到大多数节点，别的没有复制到数据的节点成为了Leader，所以该数据没有被整个集群提交，这是可能的，因为大部分节点没有复制到数据，是可以给另一个没有该数据的节点投票的
3. Question 未提交的log不可能无限多，Leader能有多少未提交的log？这是否和自己的业务实现有关？比如某个key被update的，那么其余的key的update依旧可以写入log，但是同key的update会被阻塞？
4. Leader的日志，最终还是要被复制到所有的节点上的，没有被写入超过一半副本的日志，是不保证可靠性的，因为没有日志的几个几点在成为candidate的情况下，是可以成为新的Leader的，所以要保证数据的可靠性，写入一半的副本以上，是必须条件
5. Question A/B/C/D/E五节点，假设A为Leader，接受了一个客户端请求，生成了一个新的log，并复制到了B/C节点，并向客户端回应成功。此时A/B节点挂了，由于还有3个节点可用，则集群是可用的。在这种情况下，万一D或者E成为candidate，貌似还可以成为Leader，那么这个写入超过半数的log是丢了，是否有限制使得D/E无法成为Leader？ Answer 这里傻了，整个集群的机器数其实还是5，而不是活着的3。数量是要按照集群所有节点总数来计算，而不是活着的节点数来计算。那么超过一半的节点数就是3，也就是D/E其中一个成为candidate后，由于它的日志比B旧，所以不会得到B的投票，那么赞成票就是2票，无法达到三票。而假设B成为了candidate，由于它的日志比较新，则会得到所有节点的票数，所以只有B节点能成为新的Leader，该被提交的日志最终还是会被复制到D/E中达成一致
6. 当前的Leader肯定会包含最新的log，而该log是否会复制到Follower是不确定的。只有当数据复制到大部分的Follower，那么数据肯定是被提交的。假设该log没有成功复制到大多数，那么该Leader挂了之后，没有被复制到log的Follower可能会成为新的Leader，那么此数据会被删除；假设大多数Follower复制到了该log，那么只有有了最新log的Follower会成为新的Leader，该数据肯定最终还是会复制到集群中所有的节点
7. 关于比较log的新旧，RequestVote中包含了当前最新日志的生成term以及log index，先比较term，再比较log index
8. 关于term的单调递增。集群在所有节点启动的时候，初始化为0。当集群中有节点退出加入的时候，在收到AppendEntries请求的时候，会更新自己的term，所以只要集群中有一个节点在运行，那么term将一直单调递增

---

各个角色的状态(在回RPC请求的时候需要持久化)：

• currentTerm

当前最新的term编号，第一次启动的时候初始化为0，之后单调递增

• votedFor

当前任期内收到的候选者的ID，假设未收到，设置为null

• log[]

日志记录

各个角色的状态(可变状态):

• commitIndex

最新的已提交日志的索引，初始化为0，单调递增

• lastApplied

最新的已应用至状态机的日志索引，初始化为0，单调递增

Leader的可变状态(在下一次选举的时候需要重新初始化)：

• nextIndex[]

数组，分别对应各个Follower的下一次需要复制log的索引

• matchIndex[]

数组，分别对应各个Follower已知的已复制的log索引

---

RPC请求：

• AppendEntries

Leader用来复制日志，也用于心跳包

参数

• term

  Leader的任期号

• leaderId

  Leader的节点ID，Follower将其用于重定向客户端请求

• prevLogIndex

  当前append日志紧跟的之前的一条日志的log索引

• prevLogTerm

  prevLogIndex的任期号

• entries[]

  要复制的日志，心跳包的话是空的

• leaderCommit

  Leader已提交日志的索引号

回应：

• term

  当前的任期号

• success

  是否成功，假设成功了，则代表Follower包含prevLogIndex和prevLogTerm

Follower实现细节：

• 假设term小于自身的term，则返回false
• 假设prevLogIndex与prevLogTerm均不符，返回false
• 假设某一条日志冲突（同索引，不同任期），删除此条日志以及之后的日志
• 假设日志不存在，则追加入自身的log

• 假设leaderCommit大于commitIndex，则更新commitIndex为自身最新的log号和leaderCommit中最小堆那个索引值

• RequestVote

候选人用于获取选票

参数：

• term

  候选人的任期号

• candidateId

  候选人的节点ID

• lastLogIndex

  候选人最新的log索引

• lastLogTerm

  候选人最新的log任期号

回应：

• term

  任期号，用于候选人更新自己的任期号

• voteGranted

  假设为true，则候选人收到了赞成票

Follower实现细节：

• 假设候选人的term小于currentTerm，则投反对票
• 假设没有给任何候选人投过票，或者给对应的候选人投过票，并且候选人的log至少和自己一样新或者更新，那么投赞成票

---

节点的规则

所有的节点

• 假设commitIndex>lastApplied，则将log[lastApplied]应用至自身的状态机，然后增加lastApplied
• 假设RPC请求或者回应中，term比自身的currentTerm大，则将自身的currentTerm更新为term，并且切换为Follower

Follower节点

• 对Leader或者Candidate的RPC请求回包
• 假设没有收到任何的AppendEntries和RequestVote请求后一段时间内投票定时超时了，则转为候选人

Candidates节点

• 转换为Candidate节点后，开始选举流程：
  • 增加自身的currentTerm值
  • 给自己投票
  • 重置选举定时器
  • 给其它节点发送RequestVote RPC请求
• 假设获得了及群众大部分节点的投票，则称为Leader节点
• 假设收到了新Leader的AppendEntries请求，则转换为Follower
• 假设选举定时器超时，则开启新一轮选举

Leader节点

• 当成为Leader后，发送心跳包给其余节点，同时定时的发送心跳避免新的一次选举
• 假设收到了客户端的请求，则将日志存入本地的log，待log被应用至自己的状态机后，返回给客户
• 假设最新的log日志>=Follower的nextIndex，发送从nextIndex开始的AppendEntries
  • 假设成功，则更新对应Follower的nextIndex和matchIndex
  • 假设失败，这是由于数据不一致导致的，需要将nextIndex减小并且重试
• 假设存在一个日志索引值N，N>commitIndex，并且大部分的Follower都复制了该日志(matchIndex[i]>=N)，并且该日志的任期是当前任期，则可以认为该数据被集群应用了，可以更新commitIndex为该N值

---

节点变更

节点变更最主要的风险点在于可能由于新老配置的交叉，产生两个Leader，举例：

1. 有(A/B/C)三节点集群，加入DE节点
2. DE节点有最新的五节点配置，A/B/C有三节点老配置
3. DE节点会产生选举超时，进行选举，但是无论如何都只有2票，无法当选为Leader（RequestVote会发往A/B/C节点，但是由于A/B/C节点是老配置，DE并不在集群列表中，该请求无效？等待确认）
4. 当C收到了节点变更消息的时候，CDE均为五节点配置，AB为三节点配置，我们就可以看到，CDE中可以有一个节点成为Leader，AB也有一个节点可以成为Leader，导致了两个集群中，存在了2个Leader

添加一个节点

有(A/B/C)三节点集群，加入D节点（一次加一个）

1. ABC为三节点配置，D为四节点配置
2. D无法成为Leader
3. C变更配置
4. AB依旧可以产生Leader，CD无法产生Leader（最多获得） ？？？

---

读请求

线性一致性读

1. 所有的读请求，由Leader节点来处理
2. 处理读请求的时候，记录下当前的commitIndex作为readIndex

---

• 当数据被应用至大部分节点 (N/2)+1，则该数据不会丢弃

推导：

1. 假设有A/B/C/D/E五个节点，当前term为5，A为Leader
2. 写入一条记录，log index为10，复制至B/C节点成功
3. A节点崩溃
4. Election timeout，重新一次选主，此时term单调递增为6
5. 出现数据丢失的场景，可能性主要是由于未成功复制数据的D/E节点成为了Leader，假设当前D先成为了Candidate，此时的Vote应该当上当前的Term=6以及当前D节点的最新数据的Term和Index，分别为5和9(log index肯定比10小，因为还在term=5中，写肯定A的log index大于等于其余节点)
6. 由于term=5，log index=10的日志已经被复制到大多数的节点上，按照对比自身节点的数据来决定是否赞成的规则，至少有大多数节点>=2投反对票
7. 所以D/E不会成为Leader，已提交的数据不会由于数据版本较旧的Follower成为Leader的情况下出现提交丢失

• 当Follower含有未提交的数据的时候，该部分数据会被Leader重写 （Question Leader上未提交的数据也被复制到别的Follower上？ Answer Leader上的数据都是待提交的，最终Follower的数据会和Leader一致）

流程：

1. Leader维护一个所有Follower的next index值，表示下次将从此处将自身的log发送往Follower
2. 初始化的时候，该值被设置为Leader的最大的log index
3. Follower在接收到Leader的AppendEntries请求后，会拒绝该请求
4. Leader将对应的next index递减，直到Follower接受请求
5. 从接收请求的next index处开始复制日志
6. 未提交的日志被删除(数据需要回滚？)，并且复制了Leader中没有的日志

想想为什么会拒绝日志以及commit带上之前log信息的用途：

1. AppendEntries中含有当前的log index和之前的一个log index值，必须都要符合。根据数学归纳法，commit之前的log需要被commit，那么肯定有一个初始的情况，也就是空的commit无论如何都会成功
2. 假设一个commit成功了，那么则代表之前所有的commit都肯定成功

• 在当前任期内的log，当被大部分Follower接收的时候，那么可以确定该log被提交了；而当前任期之前的log，无法根据大多数原则来判定log是否被提交。所以只有当前term的log被提交了，那么可以确定当前的以及当前之前的log都被commit了。因为当前term肯定是最新的，不可能有另一个节点有更加新的term导致没有复制到数据的节点成为Leader。

推导（反例）：

1. 假设当前集群有A/B/C三个节点
2. A成为term=1的Leader
3. A接受客户端的1个请求，写入index=1的log，而此时A挂了
4. 下一轮选举的定时器C先超时，C可以当选为Leader（B的票），此时C接受了客户端的请求，在term=2的任期内，在index=1处写入了log，还没复制到其它节点的时候，挂了
5. A此时恢复，A可以成为Leader（B的票），当前term=3，此时A开始将自己的日志log index=1,term=1复制到B节点并复制成功。仔细想一想，该日志在A、B中都有了该日志条目，那该日志是否能认定被提交？结论是不能认为提交成功。原因是之前任期的log可能从来都没有提交成功。当一个新节点成为Leader的时候，它的日志的确是会被复制到Follower节点，以Leader节点的日志为准，但是当某一部分的数据不在大部分的Follower上的时候，其实该数据从来没有被复制成功过，只是属于写了小部分的数据。而跨过这一部分写了小部分的数据之后，任何没有复制到该小部分数据的节点其实都能（注意是能，而不是只有）当选为Leader，那么假设该情况的节点成为了Leader，那么之前写了小部分数据的节点上的数据也会被清空
6. 接着5，假设我们认为之前任期的log index=1,term=1的日志是被提交成功的，那么我们来想一下反例，也就是复制到B上之后，A挂了，C这时候可以成为Leader（A与B都会投赞成票），之前被复制到大部分节点的log index=1,term=1的数据，最终会被log index=1,term=2的数据覆盖，结果就出现了这种情况：日志已经被复制到大部分的节点，却丢失。
7. 这种情况最根本的原因在于，之前任期的log，即使被复制到了大部分的节点，但是可能会有某些节点上存在于任期数大于之前任期的log，这些某些节点，也能成为新的Leader，因为选举的机制是依赖最新log的term和log index来比较的，假设一个节点拥有较新term的log，则必定表示即使它没有一些日志，那么这些日志肯定没有被提交成功，在它成为Leader的term中，假设没有Leader的所有权切换，则其它节点的日志会被删除；假设有切换，则它的log可能会被覆盖。

怎么解决这个问题：

​ 通过在复制之前任期日志的时候，附带一条当前任期的日志

• (etcd raft) 为何commitIndex不用持久化

commitIndex在节点重启后会初始化为0，这个commitIndex需要Leader的commitIndex才能被更新。当Leader第一次启动的时候，commitIndex会被初始化为0，commitIndex是可以通过各个节点的matchIndex来获取的，所以不必持久化保存。

• (etcd raft) 为何ConfState只保存于snapshot，而在没snapshot的时候，不用保存

节点在非第一次启动的时候，节点信息不会再次传入，而是通过Storage的InitialState的函数来获取HardState和ConfState。ConfState主要保存了节点列表信息，是在ready中通过保存snapshot来实现的。而假设没有snapshot，那么ConfState就会返回一个空的，那么不就是没有节点信息了么？实际上，etcd在第一次启动后，会写入一条confChangeAddNode消息，而假设此消息没有被compact，则就还在log中，log中数据会被重新的在重启后commit一次，交由给raft状态机则可以完成新增节点的功能。

在第一次启动的时候，因为节点信息是确定的，所以在启动后，每个节点都会写入和节点条数一致的ConfChangeAddNode消息，同时这些消息会被存入Storage，并标识为已经commit掉了，因为所有节点的集群配置都是一致的，所以每个节点的log也是一致的，这部分是不需要被别的节点做共识的。然后这些被commit的会被ready通知上层应用，上层应用就可以知道该集群的节点信息了。

所以我们再回到问题上来，由于commitIndex和applyIndex都会在重启后初始化为0，commitIndex可以被leader更新掉，于是更新后，从日志的起始点的log其实还是会被应用至状态机的（状态机可以做去重幂等等操作），也就是节点信息还是会被应用至raft协议层。

假设这段日志被snapshot了，那么日志肯定会丢失，然而snapshot的信息里，含有该位置的ConfState，所以集群信息还是被保存到了snapshot中了。