raft引入no-op解决了什么问题

　　raft论文In Search of an Understandable Consensus Algorithm中的描述了如下场景，可能会违反raft协议的一致性保证。

　　raft_figure8

　　:S1是Term2的Leader，将LogEntry部分复制到S1和S2的2号位置，然后Crash。:S5被S3、S4和S5选为Term3的Leader，并只写入一条LogEntry到本地，然后Crash。S1被S1、S2和S3选为Term4的Leader，并将2号位置的数据修复到S3，达到多数；并在本地写入一条Log Entry，然后Crash。这个时候2号位置的Log Entry虽然已经被复制到多数节点上，但是并不是Committed。 :S5被S3、S4和S5选为Term5的Leader，将本地2号位置Term3写入的数据复制到其他节点，覆盖S1、S2、S3上Term2写入的数据，这里引用何登成老师的原话：这违背consensus协议原则:S1被S1、S2和S3选为Term5的Leader，将3号位置Term4写入的数据复制到S2、S3，使得2号位置Term2写入的数据变为Committed 在这个场景中，虽然logEntry被写入多数节点上，但是这条日志并没有被commit。在这种情况下，写入多数节点并没有推进raft集群的commitIndex。

　　这里代表了raft的一个隐含保证：前一轮Term未Commit的LogEntry的Commit依赖于高轮Term LogEntry的才能Commit。raft这个隐含的特点，不过不认真对待，会导致违背线性一致性。因此，我们需要引入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可快速确认自己的，来保证系统迅速进入可读状态。(raft协议的线性一致性读和写也有很多讲究，可以另写一遍文章)

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

　　introducing_no-op

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

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

　　no-op_advantages

　　引入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状态机过滤掉。

　　本人对raft的理解也仅限于6.824（这个不用no-op也可以过，更不要提各种工程上的优化了）、博士论文和各种文章的解读，并没有工程上大规模的实践。有理解不对之处欢迎探讨。

　　一文看尽 Raft 一致性协议的关键点raft在处理用户请求超时的时候，如何避免重试的请求被多次应用？braft文档 RAFT介绍线性一致性：什么是线性一致性？关于Paxos "幽灵复现"问题看法