对Raft协议的一点理解
最近终于给silly实现了etcd driver。
下一步就要基于etcd来实现我去年提到的分布式框架了。
但在此之前，我需要知道etcd的边界在哪里，他是如何保证一致的，是否有幻读等问题。
由于etcd采用了raft共识算法，所以我需要了解raft的一些基本概念。
最近懒得阅读英文文章，因此在学习raft之前，我先查了一大堆中文资源，最后我都不太满意。
最终只能去啃CONSENSUS: BRIDGING THEORY AND PRACTICE, 于是就有本文。
CONSENSUS: BRIDGING THEORY AND PRACTICE中几乎介绍了需要实现raft中的方方面面，但我并没有看完，因为我只是想了解raft算法的边界。
因此本文只是按我的理解，从leader选举、日志复制和安全性三个方面来描述一下raft算法，其中我会着重描述安全性。
因为我查到的所有中文资料中，对安全性的描述，我最不满意。
raft使用心跳机来触发leader选举，选举机制如下：
进程状态分为follower、candidate和leader三种。
所有服务器启动时都默认是follower状态。
当follower接收到leader或candidate进程的有效RPC请求时，会保持在follower状态。
leader会定时向所有follower发送心跳包(没有日志条目数据的AppendEntries RPCs即为心跳包)来保持他的权威性。
如果follower在election timeout时间内没有收到心跳包，那么follower就会发起一次选举，来选择新的leader。
整个选举流程如下：
- 一个
folllower增加它的当前term(任期)并转换为candidate状态。 candidate给自己投票，并向所有其他服务器发送RequestVote RPCs。candidate一直会保持在candidate状态，直到以下三种情况之一发生：
- 得到了
超过一半的服务器的投票，此时candidate会转换为leader状态。 - 另一个
candidate赢得了选举，此时candidate会转换为follower状态。 - 选举超时，此时
candidate会增加term并重新发起选举。
每个服务器在给定的term(任期)内按照先到先得(安全性部分会增加一些额外的限制)的原则, 只能投出一票。
超过一半原则会保证在一个特定的term内，只有一个candidate会胜出成为leader。
一旦一个candidate胜出选举，他就会成为leader，并向所有服务器发送心跳包，来宣布他的权威性，并阻止新的选择。
在等待投票的过程中，一个candidate可能会收到其他服务器S发送AppendEntries RPC消息来声明服务器S(自己)成为leader， candidate就会检查服务器S发送的term是大于等于自己的term。如果是，那么candidate就会转换为follower状态，否则就拒绝这个RPC请求，然后继续保持在candidate状态。
可以看到整个选举过程，本质上就是使用paxos算法就term的值达成一致的过程，这里其实隐含了一个条件，由于candidate对声明成为leader的RPC请求有拒绝的权限，那就代表一个candidate收到超过半数的选取成功之后，必须等所有服务器都接受了声明自己成为leader的RPC请求之后，才能接受客户端请求。
正如paxos一样，raft的选举过程也会产生活锁, 即永远都无法选出leader。
raft为了解决这一问题，引入了随机化选举超时时间，这样就最大话限度的避免活锁。
再来看看日志复制是怎么进行的，自此raft就和paxos没有任何关系了。
raft的日志复制是基于quorum来保证可靠性的。
一旦一个leader被选出，他就会开始接受客户端的请求。
每个客户端请求包含了一个由复制状态机执行的command。
leader先将这个command作为一条新的日志(log entry)追加(append)到自己的日志中。然后对其他服务器并行发出AppendEntries RPCs，要求他们也将这条日志追加到自己的日志中。
当有超过半数的服务器都成功的将这条日志追加到自己的日志中，那么leader就会将这个日志条目应用到自己的状态机中（这就是大名鼎鼎的quorum）。
此时这条日志就处于committed状态, leader已经可以将状态机中的结果返回给客户端了。
在将结果返回给客户端之后，leader会不停的使用AppendEntries RPCs来重试直到所有followers最终都保存了所有的日志。
需要强调的是，这个committed状态是针对leader来说的，当一条日志处于commited状态，就意味着这条日志产生的结果可能已经被返回给客户端了，因此不能丢失。这一点对于后面理解安全性部分很重要。
raft保证所有处于commited的日志都会持久化，并被所有可用的状态机被执行。
整个log的组织方式如下图所示，每条日志(log entry)都会有一个惟一id, 这个id由term和log index组成。
当一条日志处于commited状态时，leader会将这条日志之前的所有日志都commit, 包括前任leader所产生的日志。
这条规则还隐含了另外一个规则，每个leader只能主动提交自己所产生的日志，前任的日志只能在提交自己term内的日志时被动提交。
这条规则对于保证一致性非常关键，会在下面详细说明。
leader会始终记录当前已经处于committed中日志最大log index(max_log_index)，这个索引会通过下一次AppendEntries RPCs(包括心跳)发送给followers。
当一个follower知道一条日志处于committed状态时，他就会顺序的将这条日志之前的所有日志都应用到本地状态机。
这条规则对于一致性没有任何帮助，只是为了防止当leader宕机时，follower成为leader后，follower能够快速的将自己的状态机和leader的状态机保持一致。
raft的日志机制会使得不同服务器间的日志保持了高度一致，这不仅会简化系统行为，而且会使结果更加可预测，也是确保安全性的重要组成部分。
raft日志有如下属性：
- 如果在两个服务器中的日志有相同的
log index和term，那么这两个日志包含相同的command。 - 如果在两个服务器中的日志有相同的
log index和term, 那么这两个服务器中的这两条日志之前的所有日志都是相同的。
第一个属性来源于这样的一个事实：leader在一个term内，对于给定的log index最多只能产生一条日志。
第二个属性则被AppendEntries中执行的一致性检查来保证。当发送一个AppendEntries RPCs时，leader会将紧接着本次新增日志(可能有多条)的上一条日志的log index和term，发送给所有follower，如果follower发现自己不存在同样的日志，则他会拒绝这条新增日志。
举个例子，当leader发送了一个(last_term=2, last_log_index=1, ((term=2, log_index=2, command="x=1"),(term=2, log_index=3, command="x=2")])的AppendEntries RPCs时，follower会检查自己的日志列表，如果发现自己的日志列表中不存在(term=2, log_index=1)的日志时，follower就会拒绝这个RPC请求。
这就保证了当AppendEntries RPCs成功返回时，leader和follower的日志列表是一致的。
正常情况下，raft的leader和follower之间的日志列表是一致的，但是当leader和follower之间产生一系列的crash之后，日志列表可能就会变得不一致。
下图展示了一些leader和follower之间的日志列表不一致的情况， 一个follower可能会丢失已经存在于leader日志列表中的日志，也可能会拥有不存在于leader日志列表中的日志。
在raft中，leader会通过强制所有follower来复制自己的日志列表来保证一致性。
当leader向follower中的AppendEntries被拒绝时，leader会不停的向历史日志回退，直到找到第一个和follower相同的日志(term=T,log_index=L)，然后使follower删除日志(term=T,log_index=L)之后的所有日志，并复制从leader中日志(term=T,log_index=L)之后的所有日志。
leader会通过找到和被复制的follower中最新一条相同的日志，然他开始往后复制，直到复制完leader中所有的日志，至此leader和follower的日志列表就保持了一致。
上面的日志机制只保证了可以leader和follower之间的日志列表保持一致，但是并不能保证已经处于committed的日志不会丢失。
下面来看看安全性是怎么做到这一点的。
raft规定，如果一个caididate没有包含所有已经处于committed的日志，那它就不可能在选举中胜出。
一个candidate为了被选举成功，必须要联系超过半数的服务器，这意味着，所有已经处于committed的日志至少会存在于被联系的一台服务器之中(同样基于quorum)。
这里需要重申一下，这个处于committed的日志仅仅指，他被前任leader已经应用到状态机并将结果返回给了客户端的日志。
并不是leader通过AppendEntries RPCs同步过的，已经处于committed中日志最大log index(max_log_index)。
这一点需要思考一下才能得出结论，也是所有中文资料最模糊的地方，也是很关键的地方。
假如所有的follower都维护了一个committed index, 这个committed index来源于每次leader发送的AppendEntries RPCs中的最大的已提交日志的log index。
整个集群中日志内容如下， S1为leader, 他已经将(term=1, log_index=2)复制到了大多数服务器中，因此S1已经将(term=1, log_index=2)标记为committed，并且为客户端返回了结果。
S1 (term=1, log_index=1, command="x=1"),(term=1, log_index=2, command="x=2")
S2 (term=1, log_index=1, command="x=1"),(term=1, log_index=2, command="x=2")
S3 (term=1, log_index=1, command="x=1"),(term=1, log_index=2, command="x=2")
S4 (term=1, log_index=1, command="x=1"),
S5 (term=1, log_index=1, command="x=1"),根据规则，本次提交的log_index将会通过下次AppendEntries RPCs同步给所有follower。
因此S2,S3,S4,S5服务中，此时leader已提交的最大的id为(term=1,log_index=1)。
如果此时S1 crash, S5当前持续的最大日志id为(term=1,log_index=1)，是大于等于S2,S3,S4的最大日志id的，因此S5有资格成为leader。
这种情况下已经处于committed状态下的日志(term=1, log_index=2, command="x=2")就会丢失。
因此，如果一个caididate没有包含所有已经处于committed的日志，那它就不可能在选举中胜出只是一个必要条件，并不是用来实现的充分条件。
事实上，当一个candidate发出一个RequestVote RPC时，他会带上自己日志列表中最新日志的(term,log_index), 而集群中别的服务器收到RequestVote RPC时，会拿这个(term,log_index)和自己的最新日志(term,log_index)进行比较，如果发现自己的日志比candidate的日志新(通过比较(term,log_index)二元组来确定），那么就会拒绝这个RequestVote RPC。
由于RequestVote RPC会发给半数以上的服务器，因此当candidate胜出时，他必然会已经包含了所有已经处于committed的日志，不然他就收不到超过半数的投票。
之所以上面说是一个必要条件，是因为candidate也有可能包含超过已经处理committed的之外的日志，这些日志是否需要恢复会产生一个更微妙的问题。
这和上面说到的leader只能主动提交自己当期的日志，前任的日志只能被动提交是有密切关系的。
下图展示了为何leader只能主动提交自己当期的日志。
假如在图(c)中，S1过度到term=4，并且继续提交(term=2,log_index=2)，此时(term=2,log_index=2)在整个集群中的复制数量已经超过半数，因此S1可以将这条日志标记为committed。
然后S1生成了一条新的日志(term=4,log_index=3), 在还没有来得及复制给follower之前crash掉了，此时S5以term=3的情况成为leader, 由于他本地最新的日志为(term=3,log_index=2), 因此他可以胜出获得超过半数的投票。
此时他会强制所有follower来与自己保持一致，会覆盖掉已经处理committed状态下的日志(term=2,log_index=2), 这违反了raft的保证。
这里其实还隐含了一些更微妙的问题。在刚开始阅读原文时我没有注意到。
从图(c)之后，假设S1接受了(term=4, log_index=3)的请求并开始复制，他会先复制(term=2, log_index=2)，然后再复制(term=4, log_index=3)。如果在集群中机器超过半数都已经复制到了(term=4, log_index=2)， 但是在复制(term=4, log_index=3)时，S1再次crash了，虽然(term=2, log_index=2)在集群中的复制数量已经超过了半数，但是由于(term=4, log_index=3)还没有处理committed，因此(term=2, log_index=2)还不能被标记为committed, 因此(term=2, log_index=2)是可以被别的leader覆盖掉的。
至此，raft的leader选举、日志复制和安全性三个部分算法总算描述完了。