1. 2PC
在分布式系统中，每个节点虽然可以知晓自己的操作时成功或者失败，却无法知道其他节点的操作的成功或失败。当一个事务跨越多个节点时，为了保持事务的ACID特性，需要引入一个作为协调者的组件来统一掌控所有节点(称作参与者)的操作结果并最终指示这些节点是否要把操作结果进行真正的提交(比如将更新后的数据写入磁盘等等)。 两阶段提交的算法如下：
第一阶段 投票阶段（voting phase）
- 事务协调者(事务管理器)给每个参与者(资源管理器)发送Prepare消息,询问是否可以执行提交操作
- 每个参与者开始事务执行的准备工作，如：为资源上锁，预留资源，写本地undo/redo日志等等，但是不提交
- 参与者响应协调者，如果事务的准备工作成功，则回应“可以提交”，否则回应“拒绝提交”。
第二阶段 提交阶段（commit phase）
如果协调者收到了参与者的失败消息或者超时，直接给每个参与者发送回滚(Rollback)消息；否则，发送提交(Commit)消息；参与者根据协调者的指令执行提交或者回滚操作，释放所有事务处理过程中使用的锁资源。(注意:必须在最后阶段释放锁资源)
接下来分两种情况分别讨论提交阶段的过程。
当协调者节点从所有参与者节点获得的相应消息都为”可以提交”时:
+-----+ prepare +-----+
| |----------> | c |
| | yes | o |
| |<---------- | h |
+-----+ prepare | c | commit | o |
| c |<---------- | o |----------> | r |
| o | yes | o | ack | t |
| h |----------> | r |<---------- | s |
| o | commit | d | +-----+
| r |<---------- | i |
| t | ack | n | prepare +-----+
| s |----------> | a |----------> | c |
+-----+ | t | yes | o |
| o |<---------- | h |
| r | commit | o |
| |----------> | r |
| | ack | t |
| |<---------- | s |
| | +-----+
+-----+
- 协调者节点向所有参与者节点发出”正式提交(commit)”的请求
- 参与者节点正式完成操作，并释放在整个事务期间内占用的资源
- 参与者节点向协调者节点发送”完成”消息
- 协调者节点受到所有参与者节点反馈的”完成”消息后，完成事务
如果任一参与者节点在第一阶段返回的响应消息为”中止”，或者 协调者节点在第一阶段的询问超时之前无法获取所有参与者节点的响应消息时：
+-----+ prepare +-----+
| |----------> | c |
| | no | o |
| |<---------- | h |
+-----+ prepare | c | rollback | o |
| c |<---------- | o |----------> | r |
| o | yes | o | ack | t |
| h |----------> | r |<---------- | s |
| o | rollback | d | +-----+
| r |<---------- | i |
| t | ack | n | prepare +-----+
| s |----------> | a |----------> | c |
+-----+ | t | yes | o |
| o |<---------- | h |
| r | rollback | o |
| |----------> | r |
| | ack | t |
| |<---------- | s |
| | +-----+
+-----+
- 协调者节点向所有参与者节点发出”回滚操作(rollback)”的请求
- 参与者节点利用之前写入的Undo信息执行回滚，并释放在整个事务期间内占用的资源
- 参与者节点向协调者节点发送”回滚完成”消息
- 协调者节点受到所有参与者节点反馈的”回滚完成”消息后，取消事务
不管最后结果如何，第二阶段都会结束当前事务
缺陷
二阶段提交看起来确实能够提供原子性的操作，但是不幸的事，二阶段提交还是有几个缺点的：
- 同步阻塞问题。执行过程中，所有参与节点都是事务阻塞型的。当参与者占有公共资源时，其他第三方节点访问公共资源不得不处于阻塞状态。
- 单点故障。由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。（如果是协调者挂掉，可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题）
- 数据不一致。在二阶段提交的阶段二中，当协调者向参与者发送commit请求之后，发生了局部网络异常或者在发送commit请求过程中协调者发生了故障，这回导致只有一部分参与者接受到了commit请求。而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据部一致性的现象。
- 二阶段无法解决的问题：协调者再发出commit消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。
2. 3PC
三阶段提交（Three-phase commit），也叫三阶段提交协议（Three-phase commit protocol），是二阶段提交（2PC）的改进版本
+------------------+ +---------------+
| Coordinator | | Cohorts |
+--------+---------+ +--------+------+
| |
| canCommit? |
| ------------------------> |
| yes |
| <----------------------- |
| |
| preCommit |
| ------------------------> |
| ack |
| <----------------------- |
| |
| doCommit |
| ------------------------> |
| haveCommitted |
| <----------------------- |
| |
与两阶段提交不同的是，三阶段提交有两个改动点。
- 引入超时机制。同时在协调者和参与者中都引入超时机制
- 在第一阶段和第二阶段中插入一个准备阶段。保证了在最后提交阶段之前各参与节点的状态是一致的
也就是说，除了引入超时机制之外，3PC把2PC的准备阶段再次一分为二，这样三阶段提交就有CanCommit、PreCommit、DoCommit三个阶段。
CanCommit阶段
该阶段协调者会去询问各个参与者是否能够正常执行事务，参与者根据自身情况回复一个预估值，相对于真正的执行事务，这个过程是轻量的。
- 事务询问 协调者向参与者发送CanCommit请求。询问是否可以执行事务提交操作。然后开始等待参与者的响应。
- 响应反馈 参与者接到CanCommit请求之后，正常情况下，如果其自身认为可以顺利执行事务，则返回Yes响应，并进入预备状态。否则反馈No
PreCommit阶段
协调者根据参与者的反应情况来决定是否可以进行事务的PreCommit操作。根据响应情况，有以下两种可能。
假如协调者从所有的参与者获得的反馈都是Yes响应，那么就会执行事务的预执行。
- 发送预提交请求 协调者向参与者发送PreCommit请求，并进入Prepared阶段。
- n事务预提交 参与者接收到PreCommit请求后，会执行事务操作，并将undo和redo信息记录到事务日志中。
- 响应反馈 如果参与者成功的执行了事务操作，则返回ACK响应，同时开始等待最终指令。
假如有任何一个参与者向协调者发送了No响应，或者等待超时之后，协调者都没有接到参与者的响应，那么就执行事务的中断。
- 发送中断请求 协调者向所有参与者发送abort请求。
- 中断事务 参与者收到来自协调者的abort请求之后（或超时之后，仍未收到协调者的请求），执行事务的中断。
doCommit阶段
该阶段进行真正的事务提交，也可以分为以下两种情况。
执行提交
- 发送提交请求 协调接收到参与者发送的ACK响应，那么他将从预提交状态进入到提交状态。并向所有参与者发送doCommit请求。
- 事务提交 参与者接收到doCommit请求之后，执行正式的事务提交。并在完成事务提交之后释放所有事务资源。
- 响应反馈 事务提交完之后，向协调者发送Ack响应。
- 完成事务 协调者接收到所有参与者的ack响应之后，完成事务。
中断事务 协调者没有接收到参与者发送的ACK响应（可能是接受者发送的不是ACK响应，也可能响应超时），那么就会执行中断事务。
- 发送中断请求 协调者向所有参与者发送abort请求
- 事务回滚 参与者接收到abort请求之后，利用其在阶段二记录的undo信息来执行事务的回滚操作，并在完成回滚之后释放所有的事务资源。
- 反馈结果 参与者完成事务回滚之后，向协调者发送ACK消息
- 中断事务 协调者接收到参与者反馈的ACK消息之后，执行事务的中断
在doCommit阶段，如果参与者无法及时接收到来自协调者的doCommit或者rebort请求时，会在等待超时之后，会继续进行事务的提交。（其实这个应该是基于概率来决定的，当进入第三阶段时，说明参与者在第二阶段已经收到了PreCommit请求，那么协调者产生PreCommit请求的前提条件是他在第二阶段开始之前，收到所有参与者的CanCommit响应都是Yes。（一旦参与者收到了PreCommit，意味他知道大家其实都同意修改了）所以，一句话概括就是，当进入第三阶段时，由于网络超时等原因，虽然参与者没有收到commit或者abort响应，但是他有理由相信：成功提交的几率很大。 ）
三段提交的核心理念是：在询问的时候并不锁定资源，除非所有人都同意了，才开始锁资源。
理论上来说，如果第一阶段所有的结点返回成功，那么有理由相信成功提交的概率很大。这样一来，可以降低参与者Cohorts的状态未知的概率。也就是说，一旦参与者收到了PreCommit，意味他知道大家其实都同意修改了
3. 2PC与3PC的区别
相对于2PC，3PC主要解决的单点故障问题，并减少阻塞，因为一旦参与者无法及时收到来自协调者的信息之后，他会默认执行commit。而不会一直持有事务资源并处于阻塞状态。但是这种机制也会导致数据一致性问题，因为，由于网络原因，协调者发送的abort响应没有及时被参与者接收到，那么参与者在等待超时之后执行了commit操作。这样就和其他接到abort命令并执行回滚的参与者之间存在数据不一致的情况。
了解了2PC和3PC之后，我们可以发现，无论是二阶段提交还是三阶段提交都无法彻底解决分布式的一致性问题。你会发现Timeout是个非常难处理的事情，因为网络上的Timeout在很多时候让你无所事从，你也不知道对方是做了还是没有做。于是你好好的一个状态机就因为Timeout成了个摆设。
一个网络服务会有三种状态：1）Success，2）Failure，3）Timeout，第三个绝对是恶梦，尤其在你需要维护状态的时候。
4. 两将军问题
两将军问题是这么一个思维性实验问题：
有两支军队，它们分别有一位将军领导，现在准备攻击一座修筑了防御工事的城市。这两支军队都驻扎在那座城市的附近，分占一座山头。一道山谷把两座山分隔开来，并且两位将军唯一的通信方式就是派各自的信使来往于山谷两边。不幸的是，这个山谷已经被那座城市的保卫者占领，并且存在一种可能，那就是任何被派出的信使通过山谷是会被捕。 请注意，虽然两位将军已经就攻击那座城市达成共识，但在他们各自占领山头阵地之前，并没有就进攻时间达成共识。两位将军必须让自己的军队同时进攻城市才能取得成功。因此，他们必须互相沟通，以确定一个时间来攻击，并同意就在那时攻击。如果只有一个将军进行攻击，那么这将是一个灾难性的失败。 这个思维实验就包括考虑他们如何去做这件事情。下面是我们的思考：
- 第一位将军先发送一段消息“让我们在上午9点开始进攻”。然而，一旦信使被派遣，他是否通过了山谷，第一位将军就不得而知了。任何一点的不确定性都会使得第一位将军攻击犹豫，因为如果第二位将军不能在同一时刻发动攻击，那座城市的驻军就会击退他的军队的进攻，导致他的军队被摧毁。
- 知道了这一点，第二位将军就需要发送一个确认回条：“我收到您的邮件，并会在9点的攻击。”但是，如果带着确认消息的信使被抓怎么办？所以第二位将军会犹豫自己的确认消息是否能到达。
- 于是，似乎我们还要让第一位将军再发送一条确认消息——“我收到了你的确认”。然而，如果这位信使被抓怎么办呢？
- 这样一来，是不是我们还要第二位将军发送一个“确认收到你的确认”的信息。
这事情很快就发展成为不管发送多少个确认消息，都没有办法来保证两位将军有足够的自信自己的信使没有被敌军捕获。
这个实验意在阐明：试图通过建立在一个不可靠的连接上的交流来协调一项行动的隐患和设计上的巨大挑战。
从工程上来说，一个解决两个将军问题的实际方法是使用一个能够承受通信信道不可靠性的方案，并不试图去消除这个不可靠性，但要将不可靠性削减到一个可以接受的程度。比如，第一位将军排出了100位信使并预计他们都被捕的可能性很小。在这种情况下，不管第二位将军是否会攻击或者受到任何消息，第一位将军都会进行攻击。另外，第一位将军可以发送一个消息流，而第二位将军可以对其中的每一条消息发送一个确认消息，这样如果每条消息都被接收到，两位将军会感觉更好。然而我们可以从证明中看出，他们俩都不能肯定这个攻击是可以协调的。他们没有算法可用（比如，收到4条以上的消息就攻击）能够确保防止仅有一方攻击。再者，第一位将军还可以为每条消息编号，说这是1号，2号……直到n号。这种方法能让第二位将军知道通信信道到底有多可靠，并且返回合适的数量的消息来确保最后一条消息被接收到。如果信道是可靠的话，只要一条消息就行了，其余的就帮不上什么忙了。最后一条和第一条消息丢失的概率是相等的。
两将军问题可以扩展成更变态的拜占庭将军问题 (Byzantine Generals Problem)
5. 拜占庭将军问题
Leslie Lamport 在三十多年前发表的论文《拜占庭将军问题》。
拜占庭位于如今的土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了防御目的，因此每个军队都分隔很远，将军与将军之间只能靠信差传消息。在战争的时候，拜占庭军队内所有将军必需达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定又扰乱整体军队的秩序，在进行共识时，结果并不代表大多数人的意见。这时候，在已知有成员不可靠的情况下，其余忠诚的将军在不受叛徒或间谍的影响下如何达成一致的协议，拜占庭问题就此形成。拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或断开以及遭到恶意攻击，计算机和网络可能出现不可预料的行为。
Lamport 一直研究这类问题，发表了一系列论文。但综合总结一下就是回答下面三个问题：
- 类似拜占庭将军这样的分布式一致性问题是否有解？
- 如果有解的话需要满足什么样的条件？
- 在特定前提条件的基础上，提出一种解法。
区块链解决了拜占庭将军问题，很复杂，可以参考这篇文章
Paxos算法
Raft算法
Gossip算法
6. 参考资料
http://coolshell.cn/articles/10910.html
http://mp.weixin.qq.com/s?__biz=MjM5ODYxMDA5OQ==&mid=201414704&idx=1&sn=1d2ee4273bc9c6615b84827e9abac12c&mpshare=1&scene=23&srcid=101352qbTdFqo4Ad2izjNmcl#rd
http://blog.jobbole.com/95632/
