从raft看failure的处理

2015-11-28

之前潦潦地看过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提供读服务,就会出问题:也许数据已经更新了,但它并不知道,使得客户端读到错误的数据。

raft