之前的一篇文章感觉分析得不太完整,所以再记录点东西。
故障组合情况
对于多个节点且每个节点有多个可能状态参与的分布式系统来说,假设在有限的某个时间点上发生故障的概率为0,对于coordinator(proposer/master/leader等),在发送接收的一轮交互中,可能在发送消息前(t < t1),发送部分消息(t1 < t < t2),发送所有消息后并且接收消息前(t2 < t < t3),接收到部分消息(t3 < t < t4),接收到所有消息后发生故障(t > t4);对于每个participant(acceptor/follower/slave)来说,在接收发送的一轮交互中,可能在接收消息前(t’ < t1’),接收到消息且未发送应答(t1’ < t’ < t2’),发送应答后(t’ > t2’)发生故障。
coordinator和participants在不同的时间段发生故障的组合会有不同的能够保持全局事务状态一致的故障发生时行为以及恢复策略,而且可能不存在能保持全局事务状态一致的相应行为以及恢复策略。对于发生故障时的行为,在程序实现上我们必须用上面提到的时间段来分析,而且假定coordinator广播消息这个动作的过程中不会出现故障(这其实是比较合理的,因为即使只发送了部分消息也可以看做是有一部分participants没有收到消息,这两种情况对于最终的系统全局状态是一样的),这样程序实现上相应能简化不少。而对于故障恢复的策略以及正确性,我们可以从有节点发生故障后最终整个系统可能处于的全局状态来详细分析论证,虽然对于n个参与节点来说,其状态组合指数级增长,但是其中大多数状态可以用全称量词和存在量词描述,因为很多状态对于恢复策略是一样的。下面以2PC和3PC为例来分析,从中可以比较容易地看出2PC存在的问题,以及3PC为什么能够解决这个问题。2PC和3PC的正常流程可以参考相应的资料,这里不赘述。


故障模型
首先我们这里只考虑fail-recover的故障模型
我们只考虑在有coordinator以及participant挂掉的情况,而且coordinator本身不具有participant的身份。对于没有participant挂掉但是coordinator挂掉的情况,只需要选择新的coordinator并向所有存活的participant发送最后一条日志记录的请求就可以确定发生故障时全局事务的状态,从而恢复,所以比较简单。对于有paticipant挂掉以及coordinator没有挂掉的情况,由于coordinator知道所有participants的响应消息,所以可以决定此次事务的最终状态,可能会阻塞等待participant的恢复,但不会造成不一致。
举一个coordinator没有故障但是paticipant故障的例子:对于2PC的阶段一(即有部分participant还未收到coordinator的proposal消息),如果coordinator未发生故障,但是有participant发生故障,这种情况下,只需要取消此次proposal即可,等到故障的participant恢复后询问coordinator要相应的日志记录,不会造成最终全局事务状态的不一致。(这里关于整个系统能不能progress可能有不同说法,如果我们将故障的participant移除coordinator活跃列表那么接下来的事务(如果这里的事务只是单纯的replication)可以正常进行,但是如果分布式事务本身必须要故障的participant参与,那么整个系统必须阻塞直到participant恢复,但总之不会造成恢复后系统全局状态的不一致)。
2PC故障恢复分析
下面考虑coordinator和participant故障的情况:
3PC故障恢复分析
总结
本文对于每种恢复情况都做了一定考虑,对于只有一个coordinator和participant的情况,我们可以画出系统的全局状态图,从而判断不同故障组合是否会导致状态转换的不确定结果,即最终的全局状态既有commit又有abort,上述的分析本质上也是将一些状态分了类。但是对于多节点的组合,感觉始终没有太严格地形式证明,在思考代码实现的时候也是总感觉不具有百分之百的说服力…状态组合爆炸也是并发与分布式的一个比较难的问题吧。