Raft 引入 no-op 的作用

今天在看 tikv 社区的文章：TiKV 源码解析系列 - Lease Read 的时候，看到一句话：

也就是 leader 刚通过选举成为 leader 的时候，这时候的 commit index 并不能够保证是当前整个系统最新的 commit index，所以 Raft 要求当 leader 选举成功之后，首先提交一个 no-op 的 entry，保证 leader 的 commit index 成为最新的。

当时有点晕，所以现在来总结一下这个no-op 。

先来看一下 raft 论文中相关部分：

leader之所以不能提交过往任期的日志，本质原因是不能保证过往任期的日志的这个任期在这个index上是最大的，只要任意节点在大于等于这个index上有一个更大任期的日志，就有可能在后面选举中这个节点就有可能胜出，之后覆盖这条日志。

当前term的leader不能“直接”提交之前term的entries 必须要等到当前term有entry过半了，才顺便一起将之前term的entries进行提交 。所以raft靠着这2个约束来进一步保证一致性问题。

再来仔细分析这个案例，其问题就是出在：上述leader选举上，s1如果在c场景下将index为2、term为2的entry提交了，此时s5也就不包含所有的commitLog了，但是s5按照log最新的比较方法还是能当选leader，那就是说log最新的比较方法并不能保证3.1中的选举约束即被选举出来的leader必须要包含所有已经比提交的entries
所以可以理解为：正是由于上述选举约束实现上的缺陷才导致又加了这么一个不能直接提交之前term的entries的约束。

也就是 leader 刚通过选举成为 leader 的时候，这时候的 commit index 并不能够保证是当前整个系统最新的 commit index，所以 Raft 要求当 leader 选举成功之后，首先提交一个 no-op 的 entry，保证 leader 的 commit index 成为最新的。

在这个场景中，虽然logEntry被写入多数节点上，但是这条日志并没有被commit。在这种情况下，写入多数节点并没有推进raft集群的commitIndex。

这里代表了raft的一个隐含保证：前一轮Term未Commit的LogEntry的Commit依赖于高轮Term LogEntry的才能Commit。raft这个隐含的特点，不过不认真对待，会导致违背线性一致性。因此，我们需要引入no-op。

引入no-op之后

no-op是和普通的heartbeat不一样，no-op是一个log entry，是一条需要落盘的log，只不过其只有term、index，没有额外的value信息。

在leader刚选举成功的时候，leader首先发送一个no-op log entry。从而保证之前term的log entry提交成功。并且通过no-op，新当选的leader可快速确认自己的CommitIndex，来保证系统迅速进入可读状态。

具体是怎么做的呢？我们看下图：

(a)：S1是Term2的leader，选为主后，将no-op LogEntry复制到S1和S2之后crash。
(b)：S5被S3、S4和S5选为Term3的leader，并只写入一条no-op LogEntry到本地后crash。
(c)：S1被S1、S2和S3选为Term4的leader。
后面有两种可能:
(c1)：S1作为leader，继续做了以下几件事：
写一条no-op LogEntry
在写no-op的过程中间接提交Term2的no-op，对S5而言，会覆盖Term3的no-op日志。
提交新的日志4
最终整个系统达成状态(c2)，所有的节点对日志达成一致
(d2)：S1写入一条no-op LogEntry之后就crash了。S5被S3、S4和S5选为Term5的leader。
写一条no-op LogEntry
在no-op提交的过程中间接提交Term3提交的no-op，对S1、S2和S3而言，会覆盖不一致的日志。
提交新的日志3
最终整个系统达成状态(d2)，所有节点对日志达成一致。

可见，我们通过引入no-op，修复了之前可能存在的问题，提高了系统的可用性。

那么是否引入no-op之后，之前的违反一致性的情况就不会发生了呢？我们看下面的对比图。

引入no-op之前，如博士论文所述，包含value信息的LogEntry有可能被覆盖掉。
引入no-op之后，如果当前leader已经开始提交含有value信息的LogEntry，那么它一定将之前的LogEntry全部提交了，就算它crash了：
系统也会选拥有最新最全日志的candidate为leader，比如上图，S5就不可能像之前一样成为leader
就算有日志覆盖，覆盖的也是no-op，或者没有复制到多数节点的LogEntry。不会是已经复制到多数节点的包含value的LogEntry。

通过no-op，我们解决了raft在实践中遇到的违反consensus的问题。另外可以保证新当选的leader迅速获取系统的CommitIndex，方便提供读服务。

当然，引入no-op会让系统复杂化，产生额外的落盘开销。但是，工程上可以通过Leader Stickiness，增加pre-vote等方式避免leader频繁切换。另外raft本身的幂等性保证也决定了，LogEntry可能会被raft系统commit多次，这些重复的log也可以被认为是no-op，可以被RSM状态机过滤掉。

---

转载一个知乎er @无名的回答：

先说结论，这个no-op是raft对paxos的phase2a的一个非常巧妙的优化，能显著降低实现复杂度，减少phase2a的通信量。当然这个优化需要和raft的其他特性结合在一起才能发挥其威力：选主条件、日志连续以及顺序commit。

下文中提到的proposal id在各种paxos变种中，名称有可能不同，multi-paxos里叫proposal id，zab里叫zxid，raft里叫term。这里为了简化讨论，我们统统叫 proposal id。

在对paxos有更多的了解后，我现在理解paxos的两阶段有各自非常明确的目标：

Phase1： 找到系统所有可能committed的条目；

Phase2：努力促成一阶段找到的条目得以最终committed。

在具体的工程实践中，paxos的各种变种协议的实现方式有所不同：

1. 以multi-paxos为代表：成为主后，有个专门的流程用于获取这些条目，然后以新的proposal id对这些条目发起accept请求。
2. 以viewstamped（比paxos还早一年发布）为代表：在选主流程中获取这些条目，然后以新的proposal id对这些条目发起accept请求。
3. 以raft为代表：不需要获取，选出的新主，天然就有一阶段所需要的条目，然后以新的proposal id发起no-op，可能促成条目以旧的proposal id得以comitted。

可以看出，前两者需要对一阶段获取的条目，以新的proposal id发起新的accept请求，影响的条目数和复制状态机的log数组长度成正比。假设log数组的长度为n，复杂度是O(n)级别。

而raft只需要一条no-op请求，因为日志连续，顺序commit的特性，no-op最多只会促成一个条目得以committed，影响的条目数和复制状态机的log数组长度无关，复杂度是O(1)级别。

从对比可以看出，raft和前两者相比，phase2a的通信量由O(n)降低成O(1)，优化是十分明显的。至于前两者为什么需要以新的proposal Id对一阶段获取的条目发起新的accept请求，和no-op的额外作用是一致的，避免已经committed的条目被覆盖。

总结

raft选主后的no-op操作不仅实现简单，而且对paxos的phase2a的性能提升明显，因此我认为是一个比较巧妙的设计。可是这是建立在raft选主条件，日志连续以及顺序commit以及的前提下才能达成：选主条件保证了新主一定有最全的log，不需要再额外拉取可能committed的条目；日志连续以及顺序commit保证了no-op最多只会促成一个条目得以committed，通信数量是O(1)级别。

不过任何工程都是trade off的结果，raft虽然将phase2a的通信量的复杂度减少到O(1)，可是实际上却是将成本分摊到每一次写上了(；′⌒`)，因此，raft的读写性能是要比支持乱序commit的paxos差的，不过好在易于理解和实现。

---

最后，记录一下 tikv 的两种 lease read机制：

ReadIndex Read
第一种就是 ReadIndex，当 leader 要处理一个读请求的时候：

1. 将当前自己的 commit index 记录到一个 local 变量 ReadIndex 里面。
2. 向其他节点发起一次 heartbeat，如果大多数节点返回了对应的 heartbeat response，那么 leader 就能够确定现在自己仍然是 leader。
3. Leader 等待自己的状态机执行，直到 apply index 超过了 ReadIndex，这样就能够安全的提供 linearizable read 了。
4. Leader 执行 read 请求，将结果返回给 client。

可以看到，不同于最开始的通过 Raft log 的 read，ReadIndex read 使用了 heartbeat 的方式来让 leader 确认自己是 leader，省去了 Raft log 那一套流程。虽然仍然会有网络开销，但 heartbeat 本来就很小，所以性能还是非常好的。

但这里，需要注意，实现 ReadIndex 的时候有一个 corner case，在 etcd 和 TiKV 最初实现的时候，我们都没有注意到。也就是 leader 刚通过选举成为 leader 的时候，这时候的 commit index 并不能够保证是当前整个系统最新的 commit index，所以 Raft 要求当 leader 选举成功之后，首先提交一个 no-op 的 entry，保证 leader 的 commit index 成为最新的。

所以，如果在 no-op 的 entry 还没提交成功之前，leader 是不能够处理 ReadIndex 的。但之前 etcd 和 TiKV 的实现都没有注意到这个情况，也就是有 bug。解决的方法也很简单，因为 leader 在选举成功之后，term 一定会增加，在处理 ReadIndex 的时候，如果当前最新的 commit log 的 term 还没到新的 term，就会一直等待跟新的 term 一致，也就是 no-op entry 提交之后，才可以对外处理 ReadIndex。

使用 ReadIndex，我们也可以非常方便的提供 follower read 的功能，follower 收到 read 请求之后，直接给 leader 发送一个获取 ReadIndex 的命令，leader 仍然走一遍之前的流程，然后将 ReadIndex 返回给 follower，follower 等到当前的状态机的 apply index 超过 ReadIndex 之后，就可以 read 然后将结果返回给 client 了。

Lease Read
虽然 ReadIndex 比原来的 Raft log read 快了很多，但毕竟还是有 Heartbeat 的开销，所以我们可以考虑做更进一步的优化。

在 Raft 论文里面，提到了一种通过 clock + heartbeat 的 lease read 优化方法。也就是 leader 发送 heartbeat 的时候，会首先记录一个时间点 start，当系统大部分节点都回复了 heartbeat response，那么我们就可以认为 leader 的 lease 有效期可以到 start + election timeout / clock drift bound 这个时间点。

为什么能够这么认为呢？主要是在于 Raft 的选举机制，因为 follower 会在至少 election timeout 的时间之后，才会重新发生选举，所以下一个 leader 选出来的时间一定可以保证大于 start + election timeout / clock drift bound。

虽然采用 lease 的做法很高效，但仍然会面临风险问题，也就是我们有了一个预设的前提，各个服务器的 CPU clock 的时间是准的，即使有误差，也会在一个非常小的 bound 范围里面，如果各个服务器之间 clock 走的频率不一样，有些太快，有些太慢，这套 lease 机制就可能出问题。

TiKV 使用了 lease read 机制，主要是我们觉得在大多数情况下面 CPU 时钟都是正确的，当然这里会有隐患，所以我们也仍然提供了 ReadIndex 的方案。

• TiKV 的 lease read 实现在原理上面跟 Raft 论文上面的一样，但实现细节上面有些差别，我们并没有通过 heartbeat 来更新 lease，而是通过写操作。对于任何的写入操作，都会走一次 Raft log，所以我们在 propose 这次 write 请求的时候，记录下当前的时间戳 start，然后等到对应的请求 apply 之后，我们就可以续约 leader 的 lease。当然实际实现还有很多细节需要考虑的，譬如：
• 我们使用的 monotonic raw clock，而 不是 monotonic clock，因为 monotonic clock 虽然不会出现 time jump back 的情况，但它的速率仍然会受到 NTP 等的影响。

我们默认的 election timeout 是 10s，而我们会用 9s 的一个固定 max time 值来续约 lease，这样一个是为了处理 clock drift bound 的问题，而另一个则是为了保证在滚动升级 TiKV 的时候，如果用户调整了 election timeout，lease read 仍然是正确的。因为有了 max lease time，用户的 election timeout 只能设置的比这个值大，也就是 election timeout 只能调大，这样的好处在于滚动升级的时候即使出现了 leader 脑裂，我们也一定能够保证下一个 leader 选举出来的时候，老的 leader lease 已经过期了。

参考资料：

1. TiKV 源码解析系列 - Lease Read
2. raft算法中，5.4.2节一疑问？
3. 杰特JET博客