这篇文章主要讨论下解决分布式一致性问题的两种算法：两阶段提交(2PC)和三阶段提交(3PC)。之前感觉2PC和3PC的流程挺简单的，但是真正仔细去分析过后，才发现很多的细节。而这些细节对理解Paxos，Raft，Viewstamp Replication，Atomic Broadcast等其他更复杂的一致性算法有很大的作用。所以才在此记录一下这些细节，尤其是从工程实现的角度来思考。
具体的术语，像coordinator,participant具体指代什么，不熟悉的可以参考其他讲2PC和3PC的文章。
1.正常交互流程
这里的正常是指coordinator和participant没有挂掉的。交互流程如下所示，比较容易理解。
2PC
- (1). coordinator ——(proposal)—–> all participants
- (2). all participants —-(accept/refuse)———-> coordinator
- (3.1). if any of participants is refuse, then coordinator ——-(abort)——–> all participants
(3.2). else coordinator ——-(commit)——-> all participants
3PC
- (1). coordinator ——(proposal)—–> all participants
- (2). all participants —-(accept/refuse)———-> coordinator
- (3.1). if any of participants is refuse, then coordinator ——-(cancel)——–> all participants
(3.2). else coordinator ——-(prepare-commit)——-> all participants - (4). all participants ——(prepare-commit-received)——> coordinator
- (5). if coordinator received prepare-commit-received from all participants then coordiantor —(commit)—> all participants
2.有挂掉的情况
2PC和3PC很多细节其实是在这一部分，因为在不同时间点(阶段)，不同类型节点挂掉的情况下，能不能recover以及recover的结果都是不一样的(也就是容错，比如fail-recover，fail-stop，network partition等的程度不同)。我觉得严格来讲，对于coordinator和participants的挂掉的不同组合以及相应的恢复策略，应该用各自接收和发送消息的时间点严格定义，而不是笼统地说阶段1，阶段2等。由于组合情况比较多，而且有些情况的recover方式相同，这里就简单总结分类一下。
2PC和3PC最主要的区别在于coordinator挂掉的情况下，如果存在participant挂掉，那么能不能recover保证liveness(或者整个系统progress)的问题。对于2PC来说是不能的，对于3PC来说是可以的，而prepare-commit阶段起了决定性作用，这一点后面会详细分析。
2PC 有节点挂掉的可能情况(主要以coordinator的视角)
- (1).coordinator在未发送proposal消息给任何participant以及之前挂掉了
- (2).coordinator在给一部分participant发送proposal消息后挂掉
- (3).coordinator在给所有participant发送proposal消息，但是没有发送所有commit/abort消息的情况下挂掉了
- (4).coordinator在发送所有commit/abort后挂掉
上述(1)和(4)是相同的情况，对于(2)recover处理比较简单，对于(3)比较麻烦，因为participants可能存在一种状态，是在有至少一个participant挂掉的情况下，整个事务状态是无法确定的。下面具体分析。
2PC coordinator recovery
这里不讨论所有participant都返回(即没有participant挂掉的情况)，因为只要所有的participant都返回了，判断事务的状态就能确定了
- 新的coordinator向剩余的所有participant发送query请求，获得其最后一条日志记录
- 如果返回至少一个refuse，则新的coordinator abort
- 如果返回至少一个commit，则新的coordinator commit
- 导致可能出现不一致的情况：如果其中有一个participant挂掉没返回，而且其他节点都返回accept，这种情况下，新的coordinator无法决定是abort还是commit，因为挂掉的节点可能处于accept/refuse/commit/abort的任何一个状态，如果coordiantor commit或者abort了，都可能导致次participant恢复后与其余participant不一致。2PC最主要的限制就在这一点
3PC 有节点挂掉的可能情况(主要以coordinator的视角)
- (1).coordinator在未发送proposal消息给任何participant以及之前挂掉了
- (2).coordinator在给一部分participant发送proposal消息后挂掉
- (3).发送全部proposal消息，但是没有发送全部prepare-commit/cancel消息
- (4).发送全部prepare-commit消息，但是没有发送全部commit消息
- (5).发送全部commit消息。
3PC coordinator recovery
这里不讨论所有participant都返回(即没有participant挂掉的情况)，因为只要所有的participant都返回了，判断事务的状态就能确定了
- 新的coordinator向剩余的所有participant发送query请求，获得其最后一条日志记录
- 如果返回至少一个refuse，则新的coordinator abort
- 如果返回至少一个commit，则新的coordinator commit
- 如果返回的所有节点中有一个不是prepare-commit，则可以安全地abort，因为不可能有节点进入commit(其实包含了第一种情况)
- 如果返回的节点全部是prepare-commit，此时可能会有participant挂掉，但是其可能的状态为accept/prepare-commit/commit，这三种情况下此participant恢复的时候都能commit，所以此时新的coordinator可以决定提交，不会造成恢复后的不一致状态。这一点是与2PC最大的区别
3.总结
综上，最核心的还是recovery中2PC和3PC的最后一点，也是加入prepare-commit阶段后造成的本质区别。当然虽然3PC保证了participant挂掉的时候系统能够继续progress(也就是能容错)，但是其也存在问题，比如在网络分区的时候，刚好coordinator所在的一部分能commit，但是另一部分重新选择coordinator后不能commit，这样分区恢复后会导致不一致，这种情况就是Paxos，Raft等算法能解决的，后面会结合这些更复杂一些的算法分析。其实，对于分布式一致性算法来说，了解其历史对了解算法本质是很有帮助的。
