预计阅读时长：30分钟
关键字：两阶段，三阶段，分布式
举个小栗子
最近在总结近一段时间的工作，虽然之前不断有接触两阶段提交、Paxos、Raft等一些分布式的名词，但一直是一知半解的状态，并不能很清楚说出来它们各自的特点和应用场景，本文主要就针对两阶段、三阶段提交做下总结。
首先我们先讲一个故事：有三个小孩经常被一个练过武术的大个子欺负，但是由于每个小孩子都身单力薄，谁都打不过大个子，至少三个人才有可能制服他，于是他们决定集体反抗，但是由于他们最近成绩都不好，被家人关了禁闭，出去的时间有限，最好的方式是通过电话来商量几点一起去找大个子的麻烦（假设大个子平时都是一个人呆在一个固定的地方，并且三个小孩都只能直接去找大个子，并不能提前汇合的。别问为啥有这么多限制，就是有这么多限制），他们怎么通过电话达成共识呢？
我们暂时给这三个小孩分别取个名字：A/B/C，首先他们最好不要每个人都向其余的人询问，因为每个人空闲的时间可能都不一样，假如他们各自都给其余的两个人打电话询问，就会显得很混乱。比如A对BC说咱们2点去干大个子，同时C又对AB说咱们3点去干大个子，因为C 2点没有时间，C对A回复2点不行3点可以，但是B对AC说不行，B只有4点才有时间，三个人各自很难达成一个统一的决策。假如有一个核心的决策人的话，效率明显会高一些。
无论是动物还是人，都会选取一个首领，目前看来通过首领来决策应该是现在已知的最优解。
比如A的年龄最大，大家都听他的，A首先询问BC：3点进攻可以吗？C回复可以，但是B回复不行，A收到他俩的消息后，因为有一个人不同意，所以会再次通知BC放弃2点进攻的计划。然后再询问BC：那4点可以吗？BC收到4点进攻的消息后，都觉得可以，便对A回复：ok。A收到BC都确认ok的消息后，然后分别通知BC：大家都认为4点没问题。这时候他们三个就愉快的达成了一致。
从上面可以看出：
1.首先有一个决策人能大大提交决策的效率，并且逻辑很清晰
2.达成一致最起码需要2次通信：询问+确定，因为A最开始通知的时间BC并不一定能接受，所以需要先询问一下，等待响应，并且响应的结果都为ok时，A才能继续向BC通知：达成一致，4点进攻。
这也是最经典的两阶段提交的逻辑，这个故事里有很多限制条件：为啥三个人不能提前汇合坐在一块商量，因为每台机器都是独立的个体，如果能汇合的话，那就变成一台机器内部通信，也就不存在所谓的分布式一致性问题了，再比如为啥只能通过电话沟通，因为机器互相之间只能通过网络通信。
两阶段提交
两阶段提交将节点分为两种角色：协调者+参与者。故事中A其实既扮演了协调者又扮演了参与者，因为他既是决策的发起者，同时也是决策的参与者。BC在里面扮演的是参与者的角色。
硬件或者网络故障是避免不了的，所以如果节点发生故障时，两阶段提交该如何处理才能保证决策能够正确的执行下去呢？下面我们讨论两阶段的容灾处理以及存在的问题。
首先我们把上面的故事改一下，刚才提到了A既是决策者又是参与者，这对A来说压力太大了，假如还有一个小孩D，他也饱受大个子的压迫，他的腿脚不太方便，但脑子很灵活，大家都听他指挥，他充当了A之前协调者的角色，但是不参与一起进攻大个子（只需要3个及以上的人数进攻就可以）。
问题1：假如D正准备咨询ABC其中某一个人时，对方的电话线被挖掘机挖断了，oh my blue shit，这时候怎么办？可以采用这种做法：D由于长时间打不通他的电话，会向之前已经咨询过的人说：取消进攻。这样的话最起码不会造成无谓的人员伤亡，这种处理方式是可以接受的，而且所有人的决策是统一的：取消进攻。
问题2：假如D向ABC咨询4点进攻是否ok，并且都收到了ok的回复，这时候只有D知道大家已经达成了一致意见，但是就在D准备通知“大家都认为4点进攻没问题”时，D的电话线被挖掘机挖断了（不要问为什么会断，支付宝都能断，凭啥我们不能断）。此时ABC都在电话旁边焦急的等待D的回复，不知道下一步该咋办，只能干等着，但是可能一整天都不会有消息了，修电话线应该还挺耗时间的。
那有没有办法解决这个问题呢？有，就是ABC在过了挺久的时间没有收到D的回复的情况下，三个人再选举出来一个决策人，可以是A，可以是B，也可以是C，当然如果有小E的话，选小E也是ok的（看个人爱好，ABCDFEG你更喜欢哪一个？^ ^，另外如何选举，采用什么方式选举不是本文关心的内容），假如就选了E作为决策者指导下一步工作。
问题3：选举出来E后，E根据当前的ABC的状态判断出目前还没有达成一致，E会再次向ABC询问4点进攻如何，而且E收到了ABC的回复，并且A说自己4点没时间，根据A的反馈此时E会做出取消4点进攻的决定，并把取消4点进攻的消息通知了A，A收到消息后就去睡觉了，但是E还没有来得及通知BC，E和A小区的电话线就被挖断了（不要问为什么这么巧，他俩一个小区的）。此时BC由于收不到E的消息，只能干等着。注意：此时也不能再去选举一个F来重新充当决策者，因为A也失联了，就算选出来一个F，由于F联系不上E和A，F并不确定E之前发送给A的消息是什么。因为假如F仅仅询问BC，并且他俩都同意4点进攻，并做出了4点进攻的决策，但是此时A其实认为4点计划取消了，最后只有BC两个人去了，结果可想而知（移动的600块）……
那如果发生了上述情况怎么办？只有一种选择，那就是干等着（阻塞），等待A的电话线修好（不用等待E的原因是：就算E的电话修不好，ABC也可以选举另外一个F来继续协调，因为A已经可以通信了）。
问题4：假如E已经通知所有人4点进攻，并且已经收到所有人回复的ok，根据上面我们描述的，此时E需要将达成一致的这个好消息再发送给所有人，表示刚才的提议木得问题。这里有一个点很微妙：E向所有人发送（已达成一致）这个消息，能不能用短信的方式通知？很明显不能，因为如果只是通过短信简简单单的发送出去就不管了，无法保证消息是否真正的传递到了所有节点，因为有可能在信息发送的途中，短信基站被炸了。所以必须采用打电话的方式确认。
我不确定同步通信是不是两阶段提交的潜在要求，但是本文我们默认全部节点都是同步通信，异步的情况不考虑。比如打电话就是同步操作，必须得到反馈之后才能进行下一步，发短息就是异步操作，发出去了谁tm知道他到底收到没有。FLP论文证明：异步通信模型中，不存在完全保证数据一致性的算法，有兴趣的自己研究，反正我没兴趣……
继续上面说的，采用打电话的方式，假如通知AC成功后，再去通知B的时候B联系不上了怎么办？此时E还能取消计划吗？不能！就像刚才说的，AC收到确认的消息时候可能就去睡觉了，而且是叫不醒的那种。所以这里还有一个一直没有提到的隐性约束：一旦参与者收到了协调者发送的确认信息，并做了确认操作，那么参与者不可以回滚（其实可以理解为单机的数据库事务，我都已经commit了，还怎么去rollback，所有事务只能在commit之前rollback）。这个时候咋办？木得办法，干等……等B恢复。
这也是为什么众多文章中都会提到：两阶段提交是一个 blocking protocol 阻塞的协议。
笔者认为两阶段里面只有参与者挂掉的时候才会引起阻塞，因为只要参与者没挂，总能选举出一个新的协调者，通过询问所有参与者来判断出当前事务的进度，从而进行下一步的处理。
三阶段提交
下面我们看看三阶段提交，三阶段提交主要是引入了超时机制来避免阻塞。三阶段将整个过程分为了三个阶段：canCommit，preCommit，doCommit。有一点需要注意：参与者和协调者并不是总处于同一个阶段。有可能参与者已经是preCommit阶段了，而协调者还处于canCommit阶段。协调者在超时没有收到参与者的信息时，总是执行abort，而参与者在进入doCommit阶段超时没有收到协调者的信息的话，会默认执行commit。
首先我们还是让E当协调者，小E向ABC询问：4点ok不？ABC收到E的咨询后，如果确认没问题，那么ABC会进入preCommi阶段，并向E返回ok，注意此时E如果没有收到全部的节点回复的OK的话，E仍然处于canCommit阶段。
1.假如此时E失联了，ABC执行abort
2.假如ABC有人失联了，E执行abort
解释第1条，为什么E失联了ABC需要abort，因为即使ABC各自处于preCommit阶段，但是他们并不知道大家是否都统一了4点进攻（比如A并不知道BC是否同意4点进攻，需要等待E再次通知确认），因为有可能E下一步想要发送的就是abort信息，所以保险起见此状态下ABC执行abort。
解释第2条，无论何时，只要E发现ABC有人失联了，他都会发起abort指令。
假如ABC全部回复ok，这时E才进入第二阶段preCommit，然后E向ABC发送：那咱们就4点出发（preCommit信息）。ABC收到信息后向E返回ok，并进入doCommit阶段，该祭祖的祭祖，该找女朋友的找女朋友，无牵无挂的那就去吃顿好的。对，有一个要求：就是不能去睡觉，不能去睡觉，不能去睡觉（重要的事情说三遍，上面的例子是ABC收到信息，并向E回复确认之后就睡觉去了，区别就在于不睡觉的话此时依然可以接电话执行回滚rollback）。
1.假如此时E失联了，ABC执行commit
2.假如此时ABC有人失联了，E执行abort
解释一下第1条：假如ABC已经进入doCommit阶段，此时E挂了咋办？三阶段规定处于doCommit阶段的参与者超时未收到协调者的信息后会默认执行commit操作。因为能进入doCommit阶段，说明在此之前已经确认大家是可以达成共识的。但是这一阶段如果协调者和某个参与者都失联的话，三阶段提交就处理不了了，跟上面两阶段里面描述的很类似。网络分区其实就是这种情况中的一种，下面的斜体字会详细解释。
解释一下第2条，我们首先看下问题4，问题4描述的是：E给ABC发送“确认4点进攻”的消息时，假如A收到了，但是B的电话线挖断了并没有收到确认信息，那么所有人都得等B电话线修好，要不然没办法达成一致意见（因为A睡觉去了，不能rollback）。而这次我们对之前的逻辑做了修改，就是A收到确认消息进入doCommit阶段后，不能睡，还得在电话旁边等着（也就是说此时A还不能commit）。而且E的耐心有限，在规定的时间里面他如果联系不上B的话，那么他就会给AC说，B掉链子了，计划取消，跟两阶段不同的是这个阶段E可以做出取消计划的决定了。
不过三阶段并不能解决网络分区的问题，网络分区的情况下也会有数据不一致的现象，这个跟问题3很类似，比如E和A在第三阶段同时和BC失联了，E和A还能联系，并且因为某种原因，第二阶段E收到所有节点的回复后，判断4点不能进攻，进入第三阶段E向A发送的是取消计划的决定，但是BC因为已经进入第二阶段了，按照默认策略超时没有接收到E的消息的话，会默认执行之前通知的4点进攻的策略，结果所有人并没有达成共识。
小结
上面所描述的两阶段和三阶段提交并没有将所有的边界情况全部考虑进去，两阶段和三阶段提交本身只是一个理论模型，真正的工程实现各有各的不同，各有各的优化，可能某种实现规避的A类问题，但是导致了B类问题，同样另一种工程实现可能完全反过来，再加上笔者能力有限，并不能cover所有的细节点，只希望上面的描述对大家理解两阶段三阶段提交有所帮助。
另外从上面也可以看出，所谓的三阶段不存在两阶段提交的阻塞问题，其实也是有很多限制条件，或者牺牲了一致性来换取的，并不是很完美的解决方案。而且三阶段提交在网络分区时也不能保证数据一定就是一致的，除了比两阶段提交延时更高一点外，还真想不出它还有别的什么突出的特色。工程实现时采用哪种方案还是根据场景来分析，目前来看两阶段使用的更加广泛一些（三阶段不理解也没关系，看个热闹就好）。
比如google的论文Percolator就采用的就是两阶段提交，而且巧妙的规避了两阶段提交的一些问题，简单解释：Percolator采用了一个primary锁和多个slave锁来将一个事务涉及的所有行都进行关联，确保事务失败后，新的协调者能够获取本次事务的完整信息；另外根据primary锁（单条记录）来判断事务是否提交，避免了commit不一致的问题；最后数据统一采用bigtable存储，避免了单点故障导致数据不可访问造成的阻塞问题。笔者之前总结过一次Percolator翻译，有兴趣的同学可以了解一下。
参考资料：
某大学一致性算法课件
思考
思考一下：为什么两/三阶段提交往往应用在分布式事务中？分布式事务有个特点：一个事务中每个参与者所存储的数据是不一样的，比如X节点存储了A账号的资金，Y节点存储了B账号的资金，A向B转了10块钱，需要从X节点上的A账户中扣10块钱，然后还要保证Y节点上的B账号增加10块钱。也就是说所有节点的数据加起来共同组成了一个数据一致的系统，但凡它们中的任何一个节点挂了，系统就处于未知的状态，必须等待节点恢复才可以正常运行。也就是说分布式事务本身就有数据节点宕机阻塞的特点，这点跟两阶段提交完美的契合，两阶段提交在参与者节点不出问题时是可以保证数据一致性的，而且拥有不错的性能。分布式事务中相对于系统健壮性，我们更看重数据一致性（理解这点很重要）。
而另一种分布式一致性算法，代表的即为：Raft和Paxos，它们主要解决的是什么问题呢？Raft和Paxos往往是应用在对某个结果达成一致的场景中，就好比上面的例子中我们提到协调者挂的时候需要选举一个节点作为协调者，Raft和Paxos算法解决的是多个节点如何共同维护一个唯一的值（比如状态机，公共配置等），而且Raft和Paxso拥有更好的健壮性，允许部分节点宕机也不会阻塞，但是性能会差一点。
有兴趣的读者可以继续参阅另一篇Raft论文阅读笔记
