raft

实现单个运行慢的 follower不会影响整体的性能，即防止尾部延迟影响性能；

复制状态机

Replicated state machine

状态机：一个确定的输入只会到达一个确定的状态；

即：相同的初始状态 + 相同的输入 = 相同的结束状态

在 Raft 中，leader 将客户端请求封装到多个 log entry 中(start)，再将这些日志条目复制到所有 follower 节点，节点按照相同的顺序执行日志条目中的 command，最终得到各个节点的状态必定一致；

分布式场景下的节点之间，通过 -> 共识算法保持命令序列的一致性 -> 保持节点状态一致 -> 实现高可用；

状态简化

在任何时刻，每个服务器节点都处于 leader，follower 或 candidate 这三个状态之一；

状态机转换

Raft 把时间分割成任意长度的任期（term），用连续的自增整数所表示；

每一段任期都是从选举开始；如果在选举中没有选出 leader，则该任期将以无 leader 的状态结束，并很快会开始新的一段任期；（Raft保证在任意一个任期内，最多只有一个 leader，防脑裂）

没有选出leader的原因：

网络分区：如果集群中的节点被分割成两个或更多的部分，每个部分都无法与其他部分通信，那么每个部分都可能进行选举，但由于没有节点可以获得大多数的投票（因为一部分节点是不可达的），所以选举会失败；

网络延迟：如果网络延迟导致一些节点的投票没有及时到达候选者，此时候选者的任期已经自增了；

选票分裂：如果多个候选者同时开始选举，选票可能会被分裂，导致没有候选者能达成 majority，则选举会失败，超时后会开始新一轮的选举；（通过随机化选举超时时间来减少选票分裂的可能性）

raft 集群的节点之间通过 RPC 进行通信，主要有两种核心 RPC：

RequestVote RPC（请求投票）：由 candidate 在选举期间发起；
AppendEntries RPC（追加条目）：由 leader 发起，用于复制日志和心跳机制；

服务器之间通信的时候会交换当前任期号；如果节点上的当前任期号小于其他节点，则节点会将自己的任期号更新为较大的值；

如果 candidate 或者 leader 检测到自己的任期号已经过期了，会立刻转换为 follower 状态；

如果节点接收到一个包含过期的任期号的请求 RPC，它会直接拒绝这个请求；

领导者选举

Raft 有一种心跳机制，如果存在 leader，那么它就会周期性向所有 follower 发送心跳，以此维持自己的地位；如果 follower 一段时间没有收到心跳，那么它会认为系统中无可用的 leader，然后开始选举流程；

开启一个选举流程后，follower 先自增自己的目前的任期号，并转换到 candidate 状态；然后投票给自己，并且并行、多次向集群中的其他服务器节点发送RequestVote RPC；

需满足：up-to-date，即自己有最新日志，这个判断由 follower 执行；

选举最终有三种结果：

candidate 获得超过半数的选票(majority)，转换为 leader ，并开始发送心跳；
其他节点赢得了选举，则该 candidate 收到新 leader 的心跳后，如果新 leader 的任期号大于自己当前的任期号，那么 candidate 将会转换为 follower 状态；
一段时间后没有节点赢得选举，则 candidate 在自己的随机选举超时时间后，增加任期号再开启新一轮的选举；

论文原文（In Search of an Understandable Consensus Algorithm）给出的随机选举超时时间范围为 150~300ms；

请求投票（arguments，results）

type RequestVoteArgs struct {
	Term         int // 候选人的任期号
	CandidateID  int // 请求选票的候选人ID
	LastLogIndex int // 候选人的最后日志条目的索引值
	LastLogTerm  int // 候选人最后日志条目任期号
}
type RequestVoteReply struct {
	Term        int  // 当前任期号，候选人会更新自己的任期号
	VoteGranted bool // true表示候选人获得了选票
}

对于没有成为 candidate 的 follower 节点，对于同一任期，会按照先来先得的原则投出自己的选票（一次选举中最多投一票，但实际上由于 follwer 只会接收大于自己任期的投票请求，然后会更新自己的任期，所以实际代码中这里不需要特殊处理）；

特殊情况：

1、因为网络等原因，一个或多个节点与集群失去联系，正常情况下，失联的节点因为收不到心跳包，会转换为 candidate 并尝试发起选举，并自增任期号，并且在无法胜选的情况下不断自增任期号；此时如果该节点重连回集群，因为节点的 term id 大于其他所有节点，那么它会干扰集群的正常工作；

注意此时它并不会竞选成功，因为成为 leader 不仅需要获得大多数投票，还需要有最新的日志条目，即是由最后一个日志条目的索引和任期号共同决定是否为最新的日志条目，故该 candidate 在原 leader 控制下转换为 follower；

问题出现：如果原集群没有 commit 日志，失联节点重连后会发起不必要的一轮有效选举；

故可引入预投票机制（preVote）（基于2PC），简单来说预投票的过程和真实选举大差不差，但是预投票并不会改变任何状态，即只要预投票后，当前可转变为 candidate 的 follower 确认可以当选（prepare 阶段成功），才会转换为 candidate 并发起真实选举流程（commit 阶段）；

2、非对称网络分区

假设有 A, B, C, D, E 五台机，A 是 leader，某个时刻 A, B 出现了分区，但是 A, C, D, E 以及 B, C, D, E 都可以互相通信。B 在超时没有收到心跳后，把 term+1，发起选举，如果这段时间 C, D, E 没有写入更新的日志，由于 B 的 term 更大，就会被选为 leader，A 在后面的 RPC 中因为自己的 term 较小也会被降为 follower；

问题出现：A成为 follower 之后又会按照上面 B 的方式发起选举成为 leader，同理 B 也会再次发起选举，导致 leader 不停轮换；这样周而复始会造成很大的网络开销，降低系统性能，徒增term；可能的解决方法：

在 follower 响应 pre-vote 的过程中，添加判断当前 leader 是否还在线，如果在线，则否定 pre-vote；
类似 Peer-to-Peer 系统，如果A和B出现分区，但同时 A 和 B 之间可以通过 C/D/E 通讯，比如 A->C->B，这样就可以从根上避免问题的发生，但明显这种方法会使延迟变大且带宽和CPU有所浪费；

日志复制

当 leader 收到客户端的指令后，会把指令作为一个新的条目追加到日志中去；

日志包含：

状态机指令

leader 的任期号

日志号（日志索引）

生成日志后，leader 并行发送 AppendEntries RPC 给follower，让它们复制该条目；当该条目被超过半数（majority）的 follower 复制后，leader 就可以应用该指令并把提交结果返回客户端；

本地执行指令 = leader 应用日志于状态机 = 提交到上层 server；

在日志复制的过程中，leader 或 follower 随时都有可能崩溃或缓慢的可能性，raft 须在存在节点宕机的情况下继续支持日志复制，并且需要保证每个副本日志顺序的一致（以确保复制状态机的实现）；存在三种可能：

1、follower 没有给 leader 返回响应，leader 会不断地重发追加条目请求，即使 leader 已经响应客户端的请求；

2、follower 崩溃后恢复工作，此时 raft 追加条目的一致性检测生效，保证 follower 能按顺序恢复崩溃后的缺失的日志（或者通常都是先应用快照，在恢复增量数据）；

一致性检测：leader 在每一个发往 follower 的追加条目 RPC 中，会放入前一个日志条目的索引位置和任期号，如果 follower 在它的日志中找不到前一个日志，那么它就会拒绝此日志；leader 收到 follower 的拒绝后，会将本地维护的 follower 的期望日志列表对应回退，从而逐渐向前定位到 follower 第一个缺失的日志；

优化：follower 拒绝第一个追加条目的请求后，可以返回包含冲突条目的任期号和自己存储的那个任期的第一个index（实践中，失败不经常发生，论文中认为没有必要优化，但 lab 有要求）；

3、 leader 发生崩溃，崩溃前 leader 可能已经复制了日志到部分 follower，但是还没有提交，而被选出的新 leader 可能也不具备这部分的日志，此时部分 follower 中的日志和新 leader 的日志不相同，此时 leader 会强制 follower 复制它的日志，此时 follower 与 leader 冲突的日志条目的部分会被新 leader 的日志条目所覆盖（被覆盖的日志条目还没有提交，所以不违背外部一致性）；

注意：

leader 从来不会覆盖或者删除自己的日志条目（Append-Only）；
只要过半的服务器节点可以正常运行，raft 集群就可以正常对外提供服务；
单个运行慢的 follower 不会影响整体的性能；

追加日志

type AppendEntriesArgs struct {
	Term         int          // leader当前任期
	LeaderID     int          // 使follower可以找到leader，为clients重定向
	PrevLogIndex int          // 紧接着新日志之前的日志条目的索引
	PrevLogTerm  int          // 紧接着新日志之前的日志条目的任期
	Entries      []LogEntries // 需要被保存的日志条目（心跳包的内容为空，运行一次发送多个）
	LeaderCommit int          // leader已知已提交的最高日志条目的索引
}

type AppendEntriesReply struct {
	Term               int  // 当前任期
	Success            bool // 如果日志条目顺序匹配，则返回true
	ConflictTerm       int  // 冲突的term
	ConflictFirstIndex int  // 该term的第一个日志的index值
}

如果对于 follower 而言，如果自己复制的日志条目的索引小于 leader 发送追加日志RPC内的已提交日志的索引，则更新；

安全性

raft需要考虑的边界问题：

Leader 宕机处理：选举限制；
Leader 宕机处理：新 leader 是否提交之前任期内的日志条目；
Follower 和 Candidate 宕机处理；
时间与可用性限制；

选举限制

前面也提到过：当一个 follower 落后了 leader 若干条日志（没有落后整个任期的日志），由于胜选的限制要求：此时的 candidate 需要包含之前各任期的所有被提交的日志条目，所以不用担心错误覆盖已提交日志；

up-to-date

投票者通过比较自身与 candidate 的日志中最后一条日志条目的索引值和任期号来确定谁的日志更新，

如果两份日志最后条目的任期号不同，那么任期号大的日志更新；
如果两份日志最后条目的任期号相同，那么日志较长的那个更新；

如果投票者发现自己的日志条目比候选者的日志条目更为新，那么他们将会否决该候选者的投票请求；

新 leader 是否提交之前任期内的日志条目 (f8)

任期内的某个日志条目已经存储到过半的服务器节点上，leader 就知道该日志条目可以被提交了；

leader 提交一条日志条目后，先更新自己的 commit index，再向 follower 发送 AppendEntries RPC；

follower 的提交正是依赖于下一个 AppendEntries RPC，如心跳（包含leaderCommit，无日志体）或者新日志条目，接收后，将自己的 commit index 更新，并将所有在这个 index 之前的日志条目应用到状态机中；

一条日志需要 commit 时，说明集群中该日志已经存储到过半的服务器节点，而 commit index 只是一个位置，标记了该位置之前的日志是已经提交了；不存在独立的 commit log entries 和 uncommitted entries，全部都在log[]里面；

如果 leader 在提交某个日志条目之前崩溃了，以后的新 leader 一定包含这个日志条目（由选举机制保证，up-to-date），此时 leader 需要将该日志条目复制到其他 follower 上，此时由于 raft 永远不会通过计算副本数目的方式提交一个之前任期内的日志条目，只有 leader 当前任期的日志条目通过计算副本数目后，可以提交；一旦当前任期的日志条目以这种方式被提交，那么由于日志匹配特性，之前的日志条目也都会被间接的提交。

问题出现：leader 当前任期没有收到写请求（从而无法提交之前的日志）的情况下，收到了依赖于历史这个日志的查询，那么此时将会返回旧数据，违背一致性要求；

解决：raft 引入 no-op 日志（只包含 term 和 index，数据为空）的概念，新 leader 当选后，会立即写入一条 no-op 日志，并复制到其他节点，当 no-op 日志被提交后， leader 前面未提交的日志都会被间接提交；

日志匹配性： If two entries in different logs have the same index and term, then they store the same command. 如果不同日志中的两个条目具有相同的索引和术语，则它们存储相同的命令。

If two entries in different logs have the same index and term, then the logs are identical in all preceding entries. 如果不同日志中的两个条目具有相同的索引和术语，则前面所有条目中的日志都是相同的。

Follower 和 Candidate 宕机处理

当 follower 或者 candidate 宕机了，leader 会无限重试处理失败，即重复向宕机节点发送请求RPC，等到宕机节点恢复正常后，就能正常收到RPC并作出响应；

服务端的节点是幂等性的，所以如果节点完成一个RPC后，没有返回相应就挂了，等节点恢复后仍会收到相同的RPC请求，输出的结果也不会变；

时间与可用性限制

raft 算法不依赖客观时间，即使后发RPC先到，正常节点因为日志匹配性质也会拒绝该 RPC，所以也不会影响 raft 的正确性； raft 的系统只需要满足（大于一个数量级）：广播时间（0.5ms~20ms） < 选举超时时间（10ms~500ms） < 平均故障时间

集群成员变更

增减、替换节点；

问题出现：可能出现脑裂的情况，即新旧两个配置都分别满足大多数，会选举出两个 leader；

解决：采用两个阶段更新节点，集群先切换到一个过渡的配置：联合一致成员配置（Joint Consensus）；

第一个阶段，leader 发起 C~old,new~，使 C~old~ 和 C~new~ 同步该条 C~old,new~ 日志，在此之后所有的日志（包括请求RPC，即集群是正常工作的）都需要 C~old~ 和 C~new~ 两个大多数的确认（避免脑裂），同样 C~oldm,new~ 日志在得到 C~old~ 和 C~new~ 两个大多数的确认后就会提交；

第二个阶段，leader 再向 C~old~ 和 C~new~ 同步只包含 C~new~ 的日志，在此之后所有日志都需要 C~new~ 大多数的确认，同样 C~new~ 日志在得到 C~new~ 大多数的确认后就会提交，提交后，成员变更操作正式完成；

验证：leader可能在集群成员变更时宕机，分为：

1、 leader 在 C~old,new~ 未提交时宕机；

此时如果一个 C~old,new~ 都没复制到其他节点，则直接变更失败；
如果复制成功了，根据 up-to-date 则有 C~old,new~ 的节点才可能胜选，但是无论此时有 C~old,new~ 的节点属于C~old~ 还是 C~new~ 或者两者皆有，因为需要满足 C~old~ 和 C~new~ 两个大多数的确认才能胜选，所以很明显在联合一致的情况下，不可能选出有 C~old,new~ 的节点为 leader，除非整个 C~old~ 或者 C~new~ 没有同步到C~old,new~ 日志，之中的节点就可以胜选，且至多选出一个 leader；
- 特殊情况：选出的新 leader 具有 C~old,new~ 日志，按照安全性原则，新 leader 无法直接提交 C~old,new~ ，所以需要新 leader 继续发送 C~new~ 进行成员变更，满足 C~new~ 大多数后直接一起提交即可；

2、 leader 在 C~old,new~ 已提交但 C~new~ 未发起时宕机；

此时在 C~old~ 和 C~new~ 内都满足大多数有 C~old,new~ ，故至多选举出一个有 C~old,new~ 日志的节点；

3、 leader 在 C~new~ 已发起时宕机；

此时有无复制到 Cnew 的节点都有可能胜选（注意此处是发起不是提交，故 C~new~ 可能占少数），但结果都一样，即使无复制到 C~new~ 的节点满足两个大多数后胜选，它也会发起 C~new~ 进行同步；

特殊情况：缩减节点时，leader 可能也是被缩减之一，此时它会完成 C~new~ 的提交后自动退位；注意计数 C~new~ 日志时不计算要退出的 leader 本身；

缩减节点时，如果需要下线的节点没有及时下线，新 leader 此时也不会给节点发送心跳，故节点可能会超时并发起选举，即使该节点不可能胜选，但是进入选举阶段也是浪费集群性能；故 raft 在 RequestVote RPC 上补充：一个节点如果在最小超时时间之内收到了 RequestVote RPC，会直接拒绝 RPC；

先同步再加入：

新增节点时，如果是等新增节点完成日志同步再开始集群成员变更，优点在于不会影响服务可用性，缺点在于过程复杂且慢，在同步完新日志前只可读，没有投票权，也不参与日志计数；

先加入再同步：

优点在于简单，但是可能影响服务可用性，可能不满足多数成员存活；

raft

Oct 23, 2024 • accelerator

raft

复制状态机

状态简化

领导者选举

特殊情况：

日志复制

安全性

选举限制

新 leader 是否提交之前任期内的日志条目 (f8)

Follower 和 Candidate 宕机处理

时间与可用性限制

集群成员变更