MIT6.824 -> Raft

在MIT6.824的课程中，Raft算法在Lab中是一个举足轻重的存在，除了MapReduce，其余三个Lab都基于Raft模块的实现。本文将主要介绍Raft算法。

MIT6.824课程先从Google三驾马车MapReduce、GFS、Bigtable中的两个开始，分别引入分布式场景下的计算与存储问题。对于分布式计算，这是一个无状态的过程，从MapReduce到Spark对其进行各种改进（如一个节点可以同时执行多种Map任务）；对于分布式存储，这个话题更加复杂，状态的维护与对外的展现是一个极其棘手的问题，GFS为了追求性能并不能保证多副本的数据一致性，若Secondary chunk server出现错误则已经写入的节点是无法被Primary chunk server纠正的（当然也主要因为业务需求是Web搜索，精确性要求没那么高），而本文的主角Raft则是一个能够维护多副本间一致的一个共识算法，并能够轻易对外界服务提供线性一致性的一致性模型保证。

Raft 的由来与宗旨

众所周知，Paxos 是一个非常划时代的共识算法。在 Raft 出现之前的 10 年里，Paxos 几乎统治着共识算法这一领域：因为绝大多数共识算法的实现都是基于 Paxos 或者受其影响，同时 Paxos 也成为了教学领域里讲解共识问题时的示例。

但是不幸的是，尽管有很多工作都在尝试降低 Paxos 的复杂性，但是它依然十分难以理解。并且，Paxos 自身的算法结构需要进行大幅的修改才能够应用到实际的系统中。这些都导致了工业界和学术界都对 Paxos 算法感到十分头疼。比如 Google Chubby 的论文就提到，因为 Paxos 的描述和现实差距太大，所以最终人们总会实现一套未经证实的类 Paxos 协议。

基于以上背景，Diego Ongaro 在就读博士期间，深入研究 Paxos 协议后提出了 Raft 协议，旨在提供更为易于理解的共识算法。Raft 的宗旨在于可实践性和可理解性，并且相比 Paxos 几乎没有牺牲多少性能。

Raft简介

共识算法的目标就是保证集群上所有节点的状态一致。那么关于这样的副本一致问题主要有两种思路：

①状态转移即完全拷贝节点状态（一般在新节点刚加入集群上时采用此方案）

②复制状态机即仅将来自客户端的操作或其他外部事件从Primary节点传输到其他节点（这也是大多数情况采用的方案）

对于节点一般有两种操作即读操作与写操作。写操作会改变节点状态，便立刻要复制状态机到其他节点上（将写指令同步给其他所有节点）。理想状态下我们希望这种同步可以立即作用于其他节点之上，但由于不可靠的网络将出现分区、冗余、丢失、乱序等问题。如何保证指令能够在所有节点上都以相同的顺序执行呢？这便是Raft所要解决的问题。

一个简易的可行方案

1. 首先在多个副本中选出一个Leader节点负责发送同步日志到其他节点，并确定日志顺序。

2. 所有需要写日志的请求（在未做ReadIndex等优化时默认读请求也要写日志）均需发送给Leader节点。

3. Leader先将日志写入自己的磁盘，日志需要通过某个参数（Index）定义顺序，并发送给其他节点，超过半数的节点同意了此操作Leader节点便会回复服务调用者真正apply该操作。

4. 当Leader节点崩溃时，其他跟随者节点应通过HeartBeat机制重新选举出新的Leader保证集群的正常运行。

5. 当集群新加入节点或有节点退出时时，需要将配置信息同步到集群内所有节点。

Raft的详细实现

根据上文提供的一个简易的可行方案，可以将共识算法这个很难解决的问题分为多个子问题：

• 1：Leader election 选举领导节点统筹全局。

• 2 - 3：Log Replication日志同步 Leader负责从客户端接收请求，并且在集群中扩散同步。

• 4：Safety 各节点间状态机的一致性保证。

• … …

这里简单提一下为什么到此说的所有操作都是以日志形式来记录。Log的作用非常非常大，主要有以下几点：

1. 方便定义顺序（Index）
2. Follower通过Log临时存取操作从而能够等待Commit消息
3. Leader也需要存储Log来对Follower进行重传保证消息不丢失
4. Log可以在节点重启时帮助恢复状态（Follower需要等待Leader的指示）
5. 通过Log携带后续将介绍的任期号Term，可以确定日志新旧 / 是否可以被提交等问题（解决了GFS已写入的错误日志无法被纠正的问题）

总之使用日志机制能够帮助解决非常多的问题，文件系统、数据库也都利用了日志帮助解决可靠的持久化（崩溃后的一致性）、原子性等问题。

Log = Index + Term + cmd

节点的状态机

既然Raft节点有Leader状态，自然也有其他Follower状态，节点间状态的变化较为重要。Raft将节点分为Leader、Candidate、Follower三种状态。现在看可能有些不明白，可以等第二遍看就清晰多了。简单来说就是集群内会有一个Leader负责发起心跳，响应客户端，创建日志，同步日志。其余节点都是Follower，但每个节点内部都会有个超时计时器用于检测自己是否还能和Leader互联（当接受到Leader心跳或同步日志请求便会重置该计时器），如果超时Follower便会将自己转变为候选者Candidate向所有节点索要投票（Term任期号也加一），一旦超过半数的节点同意便会成为当选Leader（后续会什么条件下节点会同意投票），否则可能会再次等待超时器超时重新参选或被其他Leader的消息（含有更新的任期号）打回Follower。

Term任期号保证了安全性，一个任期每个节点只有一张票即能保证半数以上票真的是半数以上的节点投出的，这样便能保证对于一个给定任期号最多只有一个领导者。

Term 在 Raft 算法中充当逻辑时钟。可以作为感受节点状态是否过期的标志。

在博士论文和实际生产系统中，其实又增加了两种身份：

• Learner：不具有选举权，参与日志复制过程但不计数的节点。可以作为新节点加入集群时的过渡状态以提升可用性，也可以作为一种类似于 binlog 的对 Leader 日志流进行订阅的角色，比如可以参考 PingCAP 公司 tikv 和 tiflash 的架构。
• Pre candidate：刚刚发起竞选，还在等待 Pre-Vote 结果的临时状态， 取决于 Pre-Vote 的结果，可能进化为 candidate，可能退化为 follower。

节点状态的数据结构

每一个节点都应该有的持久化状态：

• currentTerm：当前任期，保证重启后任期不丢失。
• votedFor：在当前 term，给哪个节点投了票，值为 null 或 candidate id。即使节点重启，Raft 算法也能保证每个任期最多只有一个 leader。
• log[]：已经 committed 的日志，保证状态机可恢复。

每一个节点都应该有的非持久化状态：

• commitIndex：已提交的最大 index。leader 节点重启后可以通过 appendEntries RPC 逐渐得到不同节点的 matchIndex，从而确认 commitIndex，follower 只需等待 leader 传递过来的 commitIndex 即可。
• lastApplied：已被状态机应用的最大 index。raft 算法假设了状态机本身是易失的，所以重启后状态机的状态可以通过 log[] （部分 log 可以压缩为 snapshot) 来恢复。（不持久化即从0开始apply到恢复的commitIndex）

对于为什么这两个状态在Raft论文中被定义为非持久化的：

CommitIndex 能够很快的被传播、恢复，这不是一个问题。

ApplyIndex 和状态机有关，你的状态机如果是持久化的，你也需要持久化 ApplyIndex 来保存这个状态。

当然，实际工程中对 StateMachine 的假定一般都是 Non-Volatile 的，比如 RocksDB 什么的。这样的设计下状态机不仅能够自恢复，而且自恢复往往更高效（往往只需要重放少数 WAL 即可），此时便可以考虑持久化 commitIndex 和 applyIndex 了。其实持久化 commitIndex 还好，但持久化 applyIndex 会比较麻烦，因为要想保证 safety 就需要保证状态机的更新和 applyIndex 的更新能够做到原子性，否则重启时可能会出现日志多 apply 或者少 apply 的现象。在 TiKV 的实现中，状态机的更新和 applyIndex 的更新是打包成了一条事务去做处理的，这样才算是比较优雅的解决了这个问题。

Leader 的非持久化状态：

• nextIndex[]：保存对于每个Follower应该发送的下一份 entry index；初始化为本地 lastIndex + 1，如果发送给Follower对应不上会进行相应的回退。

• matchIndex[]保存对于每个Follower已确认的Log Index，即已经同步到每一个 follower 的 entry index。初始化为 0，根据复制状态不断递增。

  每次选举后，Leader 的此两个数组都应该立刻重新初始化并开始构建。

节点选举

在节点的状态机部分已经基本介绍了什么时候会开始进行选举。这里主要介绍这个子问题中什么情况可以投赞成票选举节点成为Leader。

① 安全选举限制（不能只比CandidateTerm哟）

Leader必须得确保拥有所有已commit的日志。当 Candidate 发送 RequestVoteRPC 时，会带上最后一个 log entry 的信息。 所有的节点收到该请求后，都会比对自己的日志，如果发现自己的日志更新一些，则会拒绝投票给该 Candidate。（Pre-Vote 同理，如果 follower 认为 Pre-Candidate 没有资格的话，会拒绝 PreVote）

针对分区后部分节点会因为永远当不上Leader疯狂递增Term任期号，如果网络恢复后进入集群会更新整个集群的Term，并强行让Leader让出位置。Raft通过Pre-vote机制避免此问题，一个成员可以给所有人发探测包，如果能收到至少多数派的回复，就可以确认自己是否被网络分区，如果自己与多数派连通，那么可以发起选举。即一个 Candidate 必须在获得了多数赞同的情形下， 才会增加自己的 term，当然了Pre-Vote并不会改变其他节点的状态（Term、votefor等）。

判断日志新旧的方式：获取请求的 entry 后，比对自己日志中的最后一个 entry。 首先比对 term，如果自己的 term 更大，则拒绝请求。 如果 term 一样，则比对 index，如果自己的 index 更大（说明自己的日志更长），则拒绝请求。

但是光有这个限制并不能解决下面这个问题。

此问题代表要限定的另一个规则 ② Leader不能提交之前任期的日志，只能通过提交自己任期的日志，从而间接提交之前任期的日志。

先看图中错误的例子：

(a). S1 是任期 2 的 Leader，日志已经复制到了 S2。

(b). S1 宕机，S5 获得 S3、S4 和 S5 的选票成为 Leader，然后写了一条日志 <index=2 , term=3>。

(c). S5 刚写完就宕机了，S1 重新当选 Leader，currentTerm = 4，此刻还没有新的请求进来，S1 将 <index=2 , term = 2>的日志复制到了 S3，多数派达成，S1 提交了这个日志（注意，term=2 不是当前任期的日志，我们在讨论错误的情况）。然后请求进来，刚写了本地 <index=3 , term=4> 的日志，S1 就故障了。

(d1). 这时候 S5 可以通过来自 S2、S3、S4 和自己的投票，重新成为 Leader(currentTerm>=5)，并将 index=2 && term=3 的日志复制到其他所有节点并提交，此时 index=2 的日志提交了两次！一次 term=2，一次term=3，这是绝对不允许发生的，已经提交的日志不能够被覆盖！

(d2). 这里的情况是，S1 在宕机之前将自己 term=4 的日志复制到了大多数机器上，这样 S5 就不可能选举成功。这是 S1 不发生故障，正确复制的情况。

所以，我们要增加提交的约束，不让 (d1) 这种情况发生。这个约束就是，Leader 只能提交自己任期的日志，不然则会出现已提交日志被覆盖的情况。

虽然加了这个约束不会重复提交了，但如果一直没新的请求进来，<index=2 , term=3> 岂不是就一直不能提交？那这里不就阻塞了吗？如果这里是 kv 数据库，问题就很明显了。假设 (c) 或 (d) 中 index=2 那条日志里的 Command 是 Set("k", "1")，S5 当选 Leader 后，客户端来查询 Get("k")（已经优化到读请求不写Log了），Leader 查到日志有记录但又不能回复 1 给客户端（因为按照约束这条日志未提交），线性一致性要求不能返回陈旧的数据，Leader 迫切地需要知道这条日志到底能不能提交。

所以 raft 论文提到了引入 no-op 日志来解决这个问题。这个在 etcd 中有实现。

no-op 日志即只有 index 和 term 信息，command 信息为空。也是要写到磁盘存储的。

具体流程是在 Leader 刚选举成功的时候，立即追加一条 no-op 日志，并立即复制到其它节点，no-op 日志一经提交，Leader 前面那些未提交的日志全部间接提交，问题就解决了。像上面的 kv 数据库，有了 no-op 日志之后，Leader 就能快速响应客户端查询了。

本质上，no-op 日志使 Leader 隐式地快速提交之前任期未提交的日志，确认当前 commitIndex，这样系统才会快速对外正常工作。

同时no-op还可以解决配置变更带来的可能的数据丢失问题 详见此文章

最后对于节点的选举再说明一点，为了防止在同一时间有太多的 Follower 转变为 Candidate 导致无法选出绝对多数， Raft 采用了随机选举超时（randomized election timeouts）的机制， 即每个节点设定超市计时器的超时时间有一定添加一定随机值，可以有效避免同时选举的活锁问题。

日志同步

Leader 被选举后，则负责所有的客户端请求。每一个客户端请求都包含一个命令，该命令可以被作用到状态机上。

Leader 收到客户端请求后，会生成一个log entry，包含 <Index, Term, cmd>，再将这个log entry 添加到自己的日志末尾后，向所有的节点广播该log entry。

Follower 如果同意接受该 log entry，则在将 log entry 添加到自己的日志后，返回同意。

如果 Leader 收到了多数的成功答复，则将该 log entry 应用到自己的状态机上， 之后可以称该log entry 是 committed 的。该 committed 信息会随着随后的 AppendEntries 或 Heartbeat RPC 被传达到其他节点。

不一致的Follower节点会一步步与Leader节点变为一致，在这里Raft有两点保证：

• 如果在两个日志（节点）里，有两个 entry 拥有相同的 index 和 term，那么它们一定有相同的 cmd；
• 如果在两个日志（节点）里，有两个 entry 拥有相同的 index 和 term，那么它们前面的 entry 也一定相同。

通过“仅有 Leader 可以生成 entry”来确保第一个性质， 第二个性质则通过一致性检查（consistency check）来保证，该检查包含几个步骤：

Leader在同步日志的RPC中还得包含真正需要发送的日志的上一条entry，Follower会进行对比自己的日志，如果发现不符则会拒绝这次AppendEntries RPC，Leader普通做法是对于该Follower的nextIndex进行减一再进行重试，对其的优化的nextIndex快速回退方法是Follower会多返回两个参数ConflictIndex & ConflictTerm：

ConflictTerm = log[prevLogIndex].Term，并且查找其log中term等于 conflictTerm的第一个log的下标设置为ConflictIndex。

Leader接收到回复分为三种情况：

1. 若Leader中无这个ConflictTerm，此情形，Follower的整个ConflictTerm均得删除。所以，我们可以设置nextIndex为此Follower的ConflictTerm的第一个index即ConflictIndex。

2. 若Leader中有这个冲突Term，此情形，Follower的这个ConflictTerm中不一定所有的index都冲突
   所以，我们可以设置nextIndex为Leader log中ConfictTerm最后出现的位置的后一个Index。（Index + Term可以唯一确定cmd！！）

3. 这是Follower都没有prevLogIndex的场景，这里ConflictTerm会返回-1， Leader应该回退到Follower最后一条Log条目的下一条。

⚠️Safety安全性

对于Raft算法的安全性（各状态机状态一致性保证）有五条公理：

1. 选举安全特性：对于一个给定任期号，最多只有一个Leader（因为一个任期每个节点只有一张票，且过半数票才能当选Leader）。

2. 领导人只附加原则：领导人绝不会删除或覆盖自己的日志，只会增加。

3. 日志匹配原则：如果两个节点日志在相同index上term相同，则0～index的日志完全相同。

由1和2可以推出3。因为集群在任一时刻只有一个Leader，所以一个任期内只会在同一个index上写入一次日志。又因为Leader不会覆盖和删除自己的日志，日志一旦写入就不允许更改，所以只要term和index相同，那么在任何节点上的日志也都相同。因为跟随者每次都会根据Leader发来的PreLogIndex和PrevLogTerm寻找日志共识点，所以根据递归性质0～index的所有日志都匹配。

4. 领导人完全特性：如果某个日志条目在某个任期号中已经被提交，那么之后的新Leader必然拥有此日志（具体实现见节点选取章节的两个限制，必须对领导人选举做出基本的安全选举限制 + 不能单独提交旧Term的日志 + 成为leader后要立刻加入no-op携带Term信息去提交以往的日志这些约束才能实现领导人完全特性）

5. 状态机安全特性：如果一个Leader已经将给定index的日志条目apply到了状态机上，那么其他任何一个节点不会在这个index apply一个不同的日志。

定义A为上个任期最后一条已提交日志

根据4，A必然同步到了集群中半数以上的节点并且Leader必然拥有A

根据3，如果A被Leader包含则比A旧的日志一定被Leader包含。

因为lastApplied <= commitIndex 且已提交的日志在所有集群节点上顺序一致。所以apply日志必然在所有节点上顺序一致，因为状态机只能按序应用日志。所以状态机在整个集群所有节点上必然最终一致。

配置变更

Raft 的配置变更一般分为两种方式：一次变更一个和一次变更多个。

一次变更一台

因为在 Raft 算法中，集群中每一个节点都存有整个集群的信息，而集群的成员有可能会发生变更（节点增删、替换节点等）。 Raft 限制一次性只能增／删一个节点，在一次变更结束后，才能继续进行下一次变更。

如果一次性只变更一个节点，不需要做什么限制，即使发生网络分区，有新的候选者想当 leader 时，因为新旧这两个集合中的多数派中必然会出现交集，这样就可以保证不会因为配置不一致而导致脑裂。【单节点也有坑，需要Leader 当选立刻提交一个no_op，这条日志可以保证跟上一人Leader未提交的成员变更日志至少有一个节点交集，这样可以发现上一任Leader的日志是旧的，从而阻止上一任Leader重新选为Leader】

当 Leader 收到集群变更的请求后，就会生成一个特殊的 entry 项用来保存配置， 在将配置项添加到 log 后，该配置立刻生效（也就是说任何节点在收到新配置后，就立刻启用新配置）。 然后 Leader 将该 entry 扩散至多数节点，成功后则提交该 entry。 一旦一个新配置项被 committed，则视为该次变更已结束，可以继续处理下一次变更了。

为了保证可用性，需要新增一项规则，节点在响应 RPC 时，不考虑来源节点是否在自己的配置文件之中。 也就是说，即使收到了一个并不在自己配置文件之中的节点发来的 RPC， 也需要正常处理和响应，包括 AppendEntriesRPC 和 RequestVoteRPC。

一次变更多台

一次变更多台则需要要求“在新／旧集群中，都必须取得多数（N/2+1）”，也就是一开始会同步C_new和C_old的并集的配置给各个节点，最后再同步为C_new。

好像都按照 C_new + C_old 同步反而更加规范，一次变更一台也可以使用此方法。

日志压缩——快照

Raft 的日志在正常运行期间会增长以合并更多的客户请求，但是在实际的系统中，Raft 的日志无法不受限制地增长。随着日志的增长，日志会占用更多空间，并且需要花费更多时间进行重放。如果没有某种机制可以丢弃日志中累积的过时信息，这最终将导致可用性问题。因此需要定时去做 snapshot。

snapshot 会包括：

• 状态机当前的状态。
• 状态机最后一条应用的 entry 对应的 index 和 term。
• 集群最新配置信息。
• 为了保证 exactly-once 线性化语义的去重表

各个节点自行择机完成自己的 snapshot 即可，如果 leader 发现需要发给某一个 follower 的 nextIndex 已经被做成了 snapshot，则需要将 snapshot 发送给该 follower。注意 follower 拿到非过期的 snapshot 之后直接覆盖本地所有状态即可，不需要留有部分 entry，也不会出现 snapshot 之后还存在有效的 entry。因此 follower 只需要判断 InstallSnapshot RPC 是否过期即可。过期则直接丢弃，否则直接替换全部状态即可。

snapshot 可能会带来两个问题：

1. 做 snapshot 的策略？
   一般为定时或者定大小，达到阈值即做 snapshot，做完后对状态机和 raft log 进行原子性替换即可。
2. 做 snapshot 时是否还可继续提供写请求？
   一般情况下，做 snapshot 期间需要保证状态机不发生变化，也就是需要保证 snapshot 期间状态机不处理写请求。当然 raft 层依然可以去同步，只是状态机不能变化，即不能 apply 新提交的日志到状态机中而已。要想做的更好，可以对状态机采用 copy-on-write 的复制来不阻塞写请求。

Raft优化

先回顾一下简单的Raft流程

1. Leader 收到 client 发送的 request。
2. Leader 将 request append 到自己的 log。
3. Leader 将对应的 log entry 发送给其他的 follower。
4. Leader 等待 follower 的结果，如果大多数节点提交了这个 log，则 apply。
5. Leader 将结果返回给 client。
6. Leader 继续处理下一次 request。

可以看到，上面的流程是一个典型的顺序操作，如果真的按照这样的方式来写，那性能是完全不行的。

读写分离——读优化

Raft对外保证线性一致性。上述简单步骤所有读写请求都通过Leader来进行，并且读请求也会按照Log进行处理。因为 Raft 本来就是一个为了实现分布式环境下线性一致性的算法，所以通过 Raft 非常方便的实现线性 Read，也就是将任何的读请求走一次 Raft Log，等此 Log 提交之后在 apply 的时候从状态机里面读取值，一定能够保证这个读取到的值是满足线性要求的。

当然，因为每次 Read 都需要走 Raft 流程，Raft Log 存储、复制带来刷盘开销、存储开销、网络开销，走 Raft Log不仅仅有日志落盘的开销，还有日志复制的网络开销，另外还有一堆的 Raft “读日志” 造成的磁盘占用开销，导致 Read 操作性能是非常低效的，所以在读操作很多的场景下对性能影响很大，在读比重很大的系统中是无法被接受的，通常都不会使用。

所以可以考虑Read不按Log处理，因为读Leader其实可以完全确保读到最新的写入数据，所以只需要确保Leader处理读请求时还是Leader即可。

ReadIndex

当 Leader 需要处理 Read 请求时，Leader 与过半机器交换心跳信息确定自己仍然是 Leader 后可提供线性一致读：

1. Leader 将自己当前 Log 的 commitIndex 记录到一个 Local 变量 ReadIndex 里面；
2. 接着向 Followers 节点发起一轮 Heartbeat，如果半数以上节点返回对应的 Heartbeat Response，那么 Leader就能够确定现在自己仍然是 Leader；
3. Leader 等待自己的 StateMachine 状态机执行，至少应用到 ReadIndex 记录的 Log，直到 applyIndex 超过 ReadIndex，这样就能够安全提供 Linearizable Read，也不必管读的时刻是否 Leader 已飘走；
4. Leader 执行 Read 请求，将结果返回给 Client。

使用 ReadIndex Read 提供 Follower Read 的功能，很容易在 Followers 节点上面提供线性一致读，Follower 收到 Read 请求之后：

1. Follower 节点向 Leader 请求最新的 ReadIndex；
2. Leader 仍然走一遍之前的流程，执行上面前 3 步的过程(确定自己真的是 Leader)，并且返回 ReadIndex 给 Follower；
3. Follower 等待当前的状态机的 applyIndex 超过 ReadIndex；
4. Follower 执行 Read 请求，将结果返回给 Client。

ReadIndex Read 使用 Heartbeat 方式来让 Leader 确认自己是 Leader，省去 Raft Log 流程。相比较于走 Raft Log 方式，ReadIndex Read 省去磁盘的开销，能够大幅度提升吞吐量。虽然仍然会有网络开销，但是 Heartbeat 本来就很小，所以性能还是非常好的。

并且还能成功将读压力分散到了各个Follower上，一举两得。

Lease Read

虽然 ReadIndex Read 比原来的 Raft Log Read 快很多，但毕竟还是存在 Heartbeat 网络开销，所以考虑做更进一步的优化。Raft 论文里面提及一种通过 Clock + Heartbeat 的 Lease Read 优化方法，也就是 Leader 发送 Heartbeat 的时候首先记录一个时间点 Start，当系统大部分节点都回复 Heartbeat Response，由于 Raft 的选举机制，Follower 会在 Election Timeout 的时间之后才重新发生选举，下一个 Leader 选举出来的时间保证大于 Start+Election Timeout/Clock Drift Bound，所以可以认为 Leader 的 Lease 有效期可以到 Start+Election Timeout/Clock Drift Bound 时间点。Lease Read 与 ReadIndex 类似但更进一步优化，不仅节省 Log，而且省掉网络交互，大幅提升读的吞吐量并且能够显著降低延时。

Lease Read 基本思路是 Leader 取一个比 Election Timeout 小的租期（最好小一个数量级），在租约期内不会发生选举，确保 Leader 不会变化，所以跳过 ReadIndex 的第二步也就降低延时。由此可见 Lease Read 的正确性和时间是挂钩的，依赖本地时钟的准确性，因此虽然采用 Lease Read 做法非常高效，但是仍然面临风险问题，也就是存在预设的前提即各个服务器的 CPU Clock 的时间是准的，即使有误差，也会在一个非常小的 Bound 范围里面，时间的实现至关重要，如果时钟漂移严重，各个服务器之间 Clock 走的频率不一样，这套 Lease 机制可能出问题。

Lease Read 实现方式包括：

1. 定时 Heartbeat 获得多数派响应，确认 Leader 的有效性；
2. 在租约有效时间内，可以认为当前 Leader 是 Raft Group 内的唯一有效 Leader，可忽略 ReadIndex 中的 Heartbeat 确认步骤(2)；
3. Leader 等待自己的状态机执行，直到 applyIndex 超过 ReadIndex，这样就能够安全的提供 Linearizable Read。

这个方法主要优化Leader提供的读服务。

Batch & Pipeline

使用Batch通常情况下能提升性能，写入不会只写入一个值，而是用一个Batch 缓存一批修改，然后再整个写入。 对于 Raft 来说，Leader 可以一次收集多个 requests，然后一批发送给 Follower。当然，我们也需要有一个最大发送容量来限制每次最多可以发送多少数据。

但只有Batch依旧要等待Follower返回才能继续后面的流程。其实这里可以做一个假定，通常Leader和Follower建立连接后就可以认为网络是互通的。Leader根据NextIndex变量指示发送给Follower的下一个发送Log的位置，所以当 Leader 给 Follower 发送了一批Log 之后，可以像Pipeline一样直接更新 NextIndex，并且立刻发送后面的 Log，不需要等待 Follower 的返回。如果网络出现了错误，或者 Follower 返回一些错误，Leader 就需要重新调整 NextIndex，然后重新发送 Log 了。

并行添加日志

Leader 可以先并行的将 log 发送给 Followers，然后再本地log append。为什么可以这么做，主要是因为在 Raft 里面，如果一个 log 被大多数的节点append（并回复Leader），我们就可以认为这个 log 是被 committed 了，所以即使 Leader 再给 Follower 发送 log 之后，自己 append log 失败 panic 了，只要 N / 2 + 1个 Follower 能接收到这个 log 并成功 append，我们仍然可以认为这个 log 是被 committed 了，被 committed 的 log 后续就一定能被成功 apply。

那为什么我们要这么做呢？主要是因为 append log 会涉及到落盘，有开销，所以我们完全可以在 Leader 落盘的同时让 Follower 也尽快的收到 log 并 append。

这里我们还需要注意，虽然 Leader 能在 append log 之前给 Follower 发 log，但是 Follower 却不能在 append log 之前告诉 Leader 已经成功 append 这个 log。如果 Follower 提前告诉 Leader 说已经成功 append，但实际后面 append log 的时候失败了，Leader 仍然会认为这个 log 是被 committed 了，这样系统就有丢失数据的风险了。

异步Apply

当一个log被大部分节点append并回复Leader收到commitIndex的更新后，我们就可以认为这个log被committed了，被 committed 的 log 在什么时候被 apply 都不会再影响数据的一致性。所以当一个 log 被 committed 之后，我们可以用另一个线程去异步的 apply 这个 log。

所以整个 Raft 流程就可以变成：

1. Leader 接受一个 client 发送的 request。
2. Leader 将对应的 log 发送给其他 follower 并本地 append。
3. Leader 继续接受其他 client 的 requests，持续进行步骤 2。
4. Leader 发现 log 已经被 committed，在另一个线程 apply。
5. Leader 异步 apply log 之后，返回结果给对应的 client。

使用 asychronous apply 的好处在于我们现在可以完全的并行处理 append log 和 apply log，虽然对于一个 client 来说，它的一次 request 仍然要走完完整的 Raft 流程，但对于多个 clients 来说，整体的并发和吞吐量是上去了。

… …

Raft与客户端的交互

虽然说 raft 算法只是一个 RSM，其只需要保证不同节点上的日志相同即可，其他的事情它都不需要关心。但是要想保证线性一致性语义，对于基于 raft 的 KV 往往还需要额外做一些事情，比如即使客户端会超时重试，也要保证日志的 exactly-once 执行。这也是Lab3需要解决的问题。

即使写请求的业务语义能够保证幂等，但不进行额外的处理让其重复执行多次也会破坏线性一致性（毕竟会覆盖其他客户端的修改）。当然，读请求由于不改变系统的状态，重复执行多次是没问题的。

对于这个问题，raft 作者介绍了想要实现线性化语义，就需要保证日志仅被执行一次，即它可以被 commit 多次，但一定只能 apply 一次。

基本思路便是：

• 每个 client 都需要一个唯一的标识符，它的每个不同命令需要有一个顺序递增的 commandId，clientId 和这个 commandId，clientId 可以唯一确定一个不同的命令，从而使得各个 raft 节点可以记录保存各命令是否已应用以及应用以后的结果。

为什么要记录应用的结果？因为通过这种方式同一个命令的多次 apply 最终只会实际应用到状态机上一次，之后相同命令 apply 的时候实际上是不应用到状态机上的而是直接返回的，那么这时候应该返回什么呢？直接返回成功吗？不行，如果第一次应用时状态机报了什么例如 key not exist 等业务上的错而没有被记录，之后就很难捕捉到这个执行结果了，所以也需要将应用结果保存下来。

如果默认一个客户端只能串行执行请求的话，服务端这边只需要记录一个 map，其 key 是 clientId，其 value 是该 clientId 执行的最后一条日志的 commandId 和状态机的输出即可。

raft 论文中还考虑了对这个 map 进行一定大小的限制，防止其无线增长。这就带来了两个问题：

• 集群间的不同节点如何就某个 clientId 过期达成共识。
• 不小心驱逐了活跃的 clientId 怎么办，其之后不论是新建一个 clientId 还是复用之前的 clientId 都可能导致命令的重执行。

这些问题在工程实现上都较为麻烦。比如后者如果业务上是事务那直接 abort 就行，但如果不是事务就很难办了。

注：日志压缩部分暂未仔细好好研究 Todo。

其实Raft还有一些容错性问题的细节本文没有提到，那些细小的场景有可能影响Raft的正确性，也应做相应处理，具体可以详见Raft论文。

参考

1. 潭新宇的博客
2. 硬核课堂Raft论文导读
3. 潭新宇知乎回答
4. Raft 的 Figure 8 讲了什么问题？为什么需要 no-op 日志？
5. 线性一致读SOFAJRaft
6. TiKV Raft优化
7. Raft 成员变更