虽然去年已经看了一遍了，但是因为疫情问题换工作换城市，lab的bug也没修完，现在再看lab的代码一些概念已经陌生了，复习一下。

raft的目标（或者说共识算法的目标）

保证log完全相同地复制到多台服务器上。只要每台服务器得日志相同，那么，在不同服务器上得状态机以相同顺序从日志中执行相同得命令，将会产生相同的结果。共识算法的工作就是管理这些日志。

系统模型

需要考的率的问题：服务器会宕机，会假死（即暂时无法服务等会儿再恢复），网络会中断，会延迟，消息会丢失，会乱序。

leader正常运行，leader故障选出新的leader。leader发生变化的时候会使系统处于不一致的状态，因此下一任leader需要清理。

Leader 选举；
正常运行：日志复制（最简单的部分）；
Leader 变更时的安全性和一致性（最棘手、最关键的部分）；
处理旧 Leader：旧的 Leader 并没有真的下线怎么办？
客户端交互：实现线性化语义(linearizable semantics)；
配置变更：如何在集群中增加或删除节点；

服务的三种状态：leader，candidate，follower。

任期（term）

时间被划分成一个个的term。每个任期都由数字来表示，递增且不重复。一个任期如果没有选出leader，则term递增进入下一个任期。每个节点需要维护自己的currentTerm,需要持久化，以便在服务器宕机后重启恢复。

两个rpc

RequestVote：用于选举
AppendEntries:用于复制log，发送心跳。

选举

启动的时候所有的节点都是follower.
follower被动的接受leader和candidate的rpc.
leader需要不断的给集群中的其他节点发送心跳.
选举超时,开始新一轮的选举.

选举的安全性和选举的活性.

安全:
1.一个任期内只会有一个leader被选出:
每个节点在同一任期(term)内只能投票一次,它将投票给第一个满足投票条件的请求,然后拒绝其他candidate的请求.所以这需要持久化存储投票信息voteFor,以便宕机后重启.
防止重启后投给其他节点.
半数节点的选票才能成为leader，raft的节点书为2n+1，也就是说，两个不同的candidate无法在同一任期内都获取半数的票。
活性：
确保最终能选出一个leader。为了防止选举无限timeout，可以随机节点的超时时间。防止同时开始同时超时的情况。t>>broadcast time(远远大于广播时间)。

日志复制

每个节点存储自己的日志副本（log[]）
每条日志包含：
索引：该记录在日志中的位置
term
command
日志必须持久化。一个节点必须先将记录安全写到磁盘，才能向其他节点返回响应。如果一条日志被存储在过半数的节点上，我们认为该记录commit。

正常运行:
client向leader发送命令,希望该命令被所有的状态机执行.,leader先将该命令追加到自己的日志中做持久化,然后并行的向其他节点发送append entries rpc.等待相应,收到过半节点的响应,则认为新的日志记录是被提交的.当leader确定日志commit之后,会将该命令应用到自己的状态机,然后向客户端返回相应,一旦leader确定commit之后就会在后续append entries rpc通知已经提交的follower,follower将命令应用到自己的状态机.
leader 持久->半数 follower持久->leader 应用到状态机->leader响应客户端->follower应用到状态机.

日志的一致性:
raft使用index和term标识唯一的一条日志.

AppendEntries 一致性检查
对于每个 AppendEntries RPC 包含新日志记录之前那条记录的索引(prevLogIndex)和任期(prevLogTerm),follower检查自己的index和term是否与prevLogIndex,prevLogTerm匹配则接收该记录,这里的机制就类似一个链表的前置节点的检查,确保了数据的顺序.

leader更替

新的leader上任后,日志可能不干净,因为前一任领导可能在完成日志复制之前就宕机了.

新的leader不会立即进行清理操作,他会在正常运行期间进行清理.

原因是当一个新的 Leader 上任时，往往意味着有机器故障了，那些机器可能宕机或网络不通，所以没有办法立即清理他们的日志。在机器恢复运行之前，我们必须保证系统正常运行。大前提是 Raft 假设了 Leader 的日志始终是对的。所以 Leader 要做的是，随着时间推移，让所有 Follower 的日志最终都与其匹配。

安全性
一旦状态机执行了一条日志里的命令，必须确保其它状态机在同样索引的位置不会执行不同的命令。
leader不会覆盖日志中的记录.
只有leader的日志中的记录才能被提交.
在应用到状态机之前,日志必须提交.

所以需要修改一下上面的选举过程:
如果节点的日志中没有正确的内容,需要避免其成为新的leader.
我们需要延迟提交,在某些时候我们需要知道这条记录是安全的,即在后续的leader也会有这条日志.

Candidate 在 Request Vote rpc 中包含日志信息（最后一条记录的 index 和 term，记为 last Index 和 last Term).
收到投票请求的节点将会比谁的日志更完整,即比较last Term>=,当term相同时last Index大的日志更完整.节点会投票给这个定义下Candidate,有因为一个term内只能投一票的规则,不会再投票给其他candidate.

新的leader需要对日志做两种修复
1.删除多余的日志.
2.补齐缺失的日志.

leader为每个follower保存next index:
下一个要发给follower的日志索引
初始化1+leader最后一条日志的索引

Leader 通过 next Index 来修复日志。当 Append Entries RPC 一致性检查失败，递减 next Index 并重试.

处理旧的leader

每个rpc都包含了节点的当前任期,如果接收方判断该任期太老就会拒绝请求,发送方转变到follower并更新任期.由于新的leader的选举会更新超过半数服务器的任期.旧的leader不能提交更新的日志,因为它会联系至少一台多数派集群的节点,然后发现自己任期太老,会转为follower继续工作.

客户端协议

客户端只是将命令发送到leader:
如果客户端不知道leader是谁,它会和任意一台服务器通信
如果通信的节点不是leader,它会告诉客户端leader是谁.

leader记录命令,提交和执行到状态机之前,不会做出响应.

这里的问题是,如果leader宕机请求会超时:
客户端重新发出命令到其他服务器上,最终重定向到新的leader.
用新的leader重试请求,直到命令被执行.

这里留下了一个命令可能被执行两次的风险:leader可能在执行命令之后但响应客户端之前宕机,此时客户端再去寻找下一个leader,同一个命令就会被执行两次.

解决方案,客户端给每个命令都带上唯一id
leader将唯一id写到日志记录中,在leader接受命令之前,先检查日志中是否已经具有该id,如果id在日志中,说明是重复请求.则忽略新命令,返回旧命令的响应.

每个命令只会被执行一次，这就是所谓的线性化的关键要素。

配置变更

随着时间推移,会有机器故障需要我们去替换它,或者修改节点的数量.

系统配置是指:
每台服务器的id和地址.
系统配置信息是非常重要的,它决定了多数派的组成

共同一致(Joint Consensus)
新,旧两种配置上都获得多数派选票.

第一阶段:
leader收到c new的配置之后,先写入一条c old+new的日志,配置变更立即生效,然后将日志通过Append Entries RPC复制的follower,收到该c old+new的节点立即应用该配置作为当前节点的配置.
c old+new日志复制到多数节点上时,c old+new的日志commit.

c old+new日志commit保证了后续任何leader一定有c old+new日志,leader选举过程必须获取旧配置中的多数派和新配置中的多数派同时投票.

第二阶段:
c old+new日志commit,立即写入一条 c new日志,并将该日志通过Append Entries RPC 复制到 Follower 中，收到 C new 的节点立即应用该配置作为当前节点的配置

C new 日志复制到多数派节点上时，C new 的日志已提交；在 C new 日志提交以后，后续的配置都基于 C new 了；

Joint Consensus 还有一些细节：

变更过程中，来自新旧配置的节点都有可能成为 Leader；
如果当前 Leader 不在 C new 配置里面，一旦 C new 提交，它必须下台(step down)。