从raft看failure的处理

之前潦潦地看过raft的论文并记录过，只能说有个基本的了解。突然叫我说个一二三，肯定回答不上来。分布式领域想深入，一致性协议肯定是避不开的，所以这次又重新看了一遍raft。

开发分布式系统跟开发单机最大的差别在于什么？failure的处理！如果没有failure，那就完全没什么难点了。但是在分布式环境下，错误是常态。某个操作的执行结果是有三种状态的：成功/失败/超时。超时不能确认执行到底是成功了，还是失败了。接下来，就用raft来讨论一下各种failure场景。

假设我们有一个master多个slave。写master后，master将操作发到各个slave，所有slave写成功后，master才返回客户端，这样是可以保证强一致的。如果某个slave挂了怎么办？停止对外服务，让系统就挂掉。显然这么做可用性是有问题的，也就是CAP中一致性和可用性的冲突。为了写入的高可用，我们放松一点限制：写操作写入W份副本就算成功，总副本数量为N。那么读需要读取R份副本，并且R+W>N，这样读到的副本中一定包含了最新的副本，由客户端去选择版本。

假设master是先返回client写成功，再异步去同步给slave的。那么我们看读操作，如果读只允许从master读，那么slave只是一个容灾措施，这种方式是强一致性的。那如果放松一点限制，同一个用户，只会从固定的某一个副本上读取。这样子能够保证单调一致性，即用户不会读到比上次旧的版本。如果再放松一点限制，用户在某一个session上，只能读固定的某个副本，那么这是会话一致性。如果继续放松限制，可以随意读取某个副本，比如这次读的master，下次读slave。这样做可能读到比之前更旧的数据。比如A的值从5更新到6，master已经执行，但是还没有异步到slave。客户端读取master得到6。后来，客户端下一次读，选择了一个slave节点，读出来5。这个级别是最终一致性。

写后读：如果一个系统保证，写数据的那个client立即去读，一定读到自己写入的最新数据，而其它的client则不一定能读到最新数据，这也是一种级别的一致性。写写冲突：如果允许多个master，就可能出现写写冲突，处理起来是比较麻烦的。这里只讨论强一致性，raft保证的。

raft中有leader和follower角色，读写都只能通过leader进行。这样大大地简化了协议。第一步会选举leader，然后进入到日志同步阶段。选择leader的时候，需要获得超过半数的投票。

有节点挂了怎么办？raft并不需要写成功全部副本，只需要超过半数。leader只有在记录了日志，提交了，执行状态机后，才会回复client。整个流程是，leader把日志发给所有follower，如果收到大多数响应就提交，提交之后返回client。我们看一下一些failure。

得到大多数的响应，但是还没有commit，这时leader挂掉了。那么follower里面都是脏数据。然后follower被选为leader了，这里面的数据该怎么处理？

脏数据分几种情况看：少了、多了、错了。先看少了：follower中有缺失的log，假设让它成为leader了，那就相当于之前提交过的数据丢失，这是不能容忍的。

为了避免这个问题，raft在选举的时候加入了一条限制：必须要比大部分其它候选者的log新，才有机会成为leader。这个条件其实是“只有拥有所有commit日志，才有可能被选为leader”的一个充分非必要条件。即，选出来的leader一定是包含完整的commit日志的。这样就保证提交了的数据绝对不会丢。

实现这条限制的方式是，在收到AppendEntries消息时，如果follower发现自身的log比发送者的更完整，就不会投票。于是成为leader的候选者，它既然能收到大多数投票，它的log肯定是比大多数结点更完整的，或者说，它的log比大多数节点要新。所以它一定是包含所有的commit日志的。

对于未成为leader的结点的处理，删除脏的日志，补充缺的日志。leader需要为每个follower维护一个nextIndex。如果一致检查失败了，则nextIndex减1了再测试。

得到大多数的响应，leader于是commit，并且回复client了。但是leader没有给follower发送commit成功的信息，然后就挂掉了。这次commit是成功的么？

commit是成功的。但是是通过一条间接规则实现的：如果一条记录提交了，那么在它之前的记录一定都是提交了的。

根据之前的选举原则，新选举出来的leader一定是包含完整commit log的。然后新选出来的leader，term号一定大于上一轮的term。那么当新的日志提交以后，之前的commit就被间接地提交了。

为什么会设定成这个样子？我们必须要理解下面的问题。即"commit了的log"，跟"在大多数机器中存在"，两者有什么关系？commit了的log，必然在大多数机器中存在。因为只有leader成功同步给大多数的follower了，才会commit。那么，一条记录在大多数机器中存在，是否能说明这条记录是提交了呢？不能！有可能是leader同步给了大多数follwer，但是并没有执行commit，就挂掉了。

这里就要思考一个问题：继任者成为leader以后，是否要把在超过半数的机器中存在的log进行提交？这样做是否安全。其实是不安全的。所以raft在这里有一个限制：新的leader并不会手动提交老的term里面的记录。

然后我们看为什么不安全。因为领导人无法通过老的日志的任期号来判断其提交状态。看看这个时序：

在 (a) 中，S1 是领导者，部分的复制了索引位置 2 的日志条目。在 (b) 中，S1 崩溃了，然后 S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举，然后从客户端接收了一条不一样的日志条目放在了索引 2 处。然后到 (c)，S5 又崩溃了；S1 重新启动，选举成功，开始复制日志。在这时，来自任期 2 的那条日志已经被复制到了集群中的大多数机器上，但是还没有被提交。如果 S1 在 (d) 中又崩溃了，S5 可以重新被选举成功（通过来自 S2，S3 和 S4 的选票），然后覆盖了他们在索引 2 处的日志。但是，在崩溃之前，如果 S1 在自己的任期里复制了日志条目到大多数机器上，如 (e) 中，然后这个条目就会被提交（S5 就不可能选举成功）。 在这个时候，之前的所有日志就会被正常提交处理。

脑裂问题(partition)。会主动放弃leader么？不会。假设leader跟其它所有节点partition了，但是它还以为自己是leader，继续处理请求。由于它得不到大部分的确认，它没法commit，但是会积累脏数据。积累了脏数据的这个家伙，回头被选为leader，会覆盖掉已提交的正确数据？

为了解决这个问题，raft计算commit的条件继续补充：至少需要存储到大多数的节点上了。这个leader负责的term至少有一个新的记录也存到大多数的节点中了(即term号遍布到大多数结点了)。

这个可怜的家伙(partition的老leader)是无法被选为leader的。因为它由于partition的原因，它无法把自己的term遍布到大多数结点上，而当partition恢复的时候，如果期间有新的leader选出来过，term号已经增加了。

网络闪断：leader连不上网，其它节点被选为leader，老的leader想提交记录，但是leader的term是小于其它的，所以会失败，它成为follower。

一个节点先投票给了A，后来又接到一个来自B的term更高的投票请求，该怎么办？投票！更高的term，说明已经是下一轮选举了。上一轮肯定是已经结束的，要么是没有leader被选出来，要么是选出了leader但是这个节点没收到过leader请求。不管哪种情况，这是新的一轮了。

执行了命令，还没有返回client，crash了。客户端超时失败后会重试这个请求。

线性可序列化要求这个请求是不能执行两次的。做法是客户端每个命令带一个id，服务端发现如果是重复id，就是不执行命令，而是直接返回上次执行的结果。

扩容。迁移期间的一致性。在冲突中，一部分处理新配置，一部分处理老配置。大家都觉得自己是majorities。这一部分内容还没有细看。

正确性证明。上面写了很多failure的场景，raft协议都能正确地处理，但是这样子举例子并不能表示没问题。必须从理论上证明，不过raft确实是可以证明正确性的协议。只大致地提一下证明的思路。

一个是证明领导人的完备性。证明领导人的完备性，是指一旦日志被commit之后，后面的无论发生leader选举或者什么情况，日志不会丢，不会重写或覆盖以前的日志。保证这一点之后，复制状态机模型就可以保证在不同机器上执行结果的一致性。

证明的方式是使用反证法，先假设领导人完全性特性是不存在的，然后我们推出矛盾来。假设任期 T 的领导人（领导人 T）在任期内提交了一条日志条目，但是这条日志条目没有被存储到该领导人未来某个任期的日志中。设大于 T 的最小任期 U 的领导人 U 没有这条日志条目。具体的证明过程就略了。

另一个是证明日志匹配原则。日志匹配原则是要证明，如果一条记录提交了，那么在它之前的记录一定都是提交了的。因为在上面证明领导人完备性时，需要使用到这个条件。这个证明使用的是数学归纳法：初始状态是满足条件的，然后证明假设某一个状态满足条件，按我们的操作和约束，下一个状态也是满足条件的。具体过程也略了。

其实理解raft的比较关键的点，已经用的粗体字了。这几条理解了，应该就能理解它是如何容错的。

1. 选择leader的时候，需要获得超过半数的投票
2. 必须要比大部分其它候选者的log新，才有机会成为leader
3. 如果一条记录提交了，那么在它之前的记录一定都是提交了的

2016.4.12更新

节点加入集群的条件。假设有A B C三个节点，C是leader。A挂掉了，A1节点加入，从C同步数据。这时C又挂掉了，B被选为leader。C1加入集群，从B同步数据。当A1和C1数据都还没同步完，此时的leader，B又挂掉。那么不管A1或者C1成为新的leader，都意味着数据丢失！

这个case意味着，之前的理解还有漏洞的地方。还有进一步的约束没有考虑到，这个约束就是：节点加入集群的条件。实际上节点加入集群需要走membership change的逻辑，也就是前面没有讨论到的迁移其它一致性。新加节点的时候，我们首先要保证新增的节点的log要追上leader的，然后才能开始configuration change流程

2016.4.16更新

stale read问题。假设现在出现脑裂了，老的leader跟少量follower维持着小的集群，而majority已经形成并推选出了新的leader。客户端连的还是老的leader。写是没问题的，因为不得到多数投票是不能commit的。但读呢？由于partition，老的leader不知道它已不是leader了，继续为client提供读服务，就会出问题：也许数据已经更新了，但它并不知道，使得客户端读到错误的数据。