分布式事务，两阶段提交协议，三阶段提交协议
1. 分布式中的CAP怎么理解
1.1 CAP
C（Consistency）一致性 每一次读取都会让你得到最新的写入结果
A （Availability）可用性 每个节点(如果没有失败)，总能执行查询(读取和写入)操作
P （Partition Tolerance）分区容忍性 即使节点之间的连接关闭，其他两个属性也会得到保证
CAP理论认为，任何联网的共享数据系统智能实现三个属性中的两个，但是可以通过明确处理分区，优化一致性和可用性，从而实现三者之间的某种权衡
1.2 ZooKeeper提供的一致性服务
很多文章和博客里提到，zookeeper是一种提供强一致性的服务，在分区容错性和可用性上做了一定折中，这和CAP理论是吻合的。但实际上zookeeper提供的只是单调一致性。
原因：
- 假设有2n+1个server，在同步流程中，leader向follower同步数据，当同步完成的follower数量大于 n+1时同步流程结束，系统可接受client的连接请求。如果client连接的并非同步完成的follower，那么得到的并非最新数据，但可以保证单调性。
- follower接收写请求后，转发给leader处理；leader完成两阶段提交的机制。向所有server发起提案，当提案获得超过半数（n+1）的server认同后，将对整个集群进行同步，超过半数（n+1）的server同步完成后，该写请求完成。如果client连接的并非同步完成follower，那么得到的并非最新数据，但可以保证单调性。
用分布式系统的CAP原则来分析Zookeeper：
C: Zookeeper保证了最终一致性,在十几秒可以Sync到各个节点.
A: Zookeeper保证了可用性,数据总是可用的,没有锁.并且有一大半的节点所拥有的数据是最新的,实时的. 如果想保证取得是数据一定是最新的,需要手工调用Sync()
P: 有2点需要分析的.
- 节点多了会导致写数据延时非常大,因为需要多个节点同步.
- 节点多了Leader选举非常耗时, 就会放大网络的问题. 可以通过引入 observer节点缓解这个问题.
2. 分布式一致性
2.1 引言
在分布式系统中，为了保证数据的高可用,通常我们会将数据保留多个副本(replica), 这些副本会放置在不同的物理机器上。为了对用户提供正确的curd等语意，我们需要保证这些放置在不同无力机器上的副本是一致的
为了解决这种分布式一致性问题，提出了很多典型的协议和算法，比较著名的是二阶段提交协议，三阶段提交协议和paxos算法。
2.2 分布式事务
在分布式系统中，各个节点之间在物理上相互独立，通过网络进行沟通和协调。由于存在事务机制，可以保证每个独立节点上的数据操作可以满足ACID。但是，相互独立的节点之间无法准确地知道其他节点的事务执行情况。所以从理论上来讲，两台机器无法达到一致的状态。如果想让分布式部署的多台机器中的数据保持一致性，那么就要保证在所有节点数据的写操作，要么全部都执行，要么全部都不执行。但是，一台机器在执行本地事务的时候无法知道其他机器中的本地事务的执行结果，所以它也就不知道本次事务到底应该commit还是rollback。所以，常规的解决办法就是引入一个"协调者"的组件来统一调度所有分布式节点的执行。
3. 2PC（Two-phaseCommit）
二阶段提交的算法思路可以概括为: 参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。
二阶段是指: 第一阶段 - 请求阶段(表决阶段) 第二阶段 - 提交阶段(执行阶段)
3.1 请求阶段（表决）
事务协调者通知每个参与者准备提交或取消事务，然后进入表决过程，参与者要么在本地执行事务，写本地的redo和undo日志，但不提交，到达一种"万事俱备，只欠东风"的状态。请求阶段，参与者将告知协调者自己的决策: 同意(事务参与者本地作业执行成功)或取消（本地作业执行故障）
3.2 提交阶段（执行）
在该阶段，写调整将基于第一个阶段的投票结果进行决策：提交或取消
当且仅当所有的参与者同意提交事务，协调者才通知所有的参与者提交事务，否则协调者将通知所有的参与者取消事务
参与者在接收到协调者发来的消息后将执行响应的操作
3.3 两阶段提交的缺点
- 同步阻塞问题。执行过程中，所有参与节点都是事务阻塞型的。当参与者占有公共资源时，其他第三方节点访问公共资源不得不处于阻塞状态。
- 单点故障。由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。（如果是协调者挂掉，可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题）
- 数据不一致。在二阶段提交的阶段二中，当协调者向参与者发送commit请求之后，发生了局部网络异常或者在发送commit请求过程中协调者发生了故障，这回导致只有一部分参与者接受到了commit请求。而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据不一致性的现象。
3.4 两阶段提交无法解决的问题
当协调者出错，同时参与者也出错时，两阶段无法保证事务执行的完整性。
考虑协调者在发出commit消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。
那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。
4. 3PC（Three-phaseCommit）
三阶段提交协议在协调者和参与者中都引入超时机制，并且把两阶段提交协议的第一个阶段分成了两步: 询问，然后再锁资源，最后真正提交。
4.1 三阶段的执行
(1) canCommit阶段
3PC的canCommit阶段其实和2PC的准备阶段很像。协调者向参与者发送commit请求，参与者如果可以提交就返回yes响应，否则返回no响应
(2) preCommit阶段
协调者根据参与者canCommit阶段的响应来决定是否可以继续事务的preCommit操作。根据响应情况，有下面两种可能:
- 协调者从所有参与者得到的反馈都是yes，那么进行事务的预执行，协调者向所有参与者发送preCommit请求，并进入prepared阶段。参与泽和接收到preCommit请求后会执行事务操作，并将undo和redo信息记录到事务日志中。如果一个参与者成功地执行了事务操作，则返回ACK响应，同时开始等待最终指令
- 协调者从所有参与者得到的反馈有一个是No或是等待超时之后协调者都没收到响应，那么就要中断事务，协调者向所有的参与者发送abort请求。参与者在收到来自协调者的abort请求，或超时后仍未收到协调者请求，执行事务中断。
(3) doCommit阶段
协调者根据参与者preCommit阶段的响应来决定是否可以继续事务的doCommit操作。根据响应情况，有下面两种可能:
- 协调者从参与者得到了ACK的反馈: 协调者接收到参与者发送的ACK响应，那么它将从预提交状态进入到提交状态，并向所有参与者发送doCommit请求。参与者接收到doCommit请求后，执行正式的事务提交，并在完成事务提交之后释放所有事务资源，并向协调者发送haveCommitted的ACK响应。那么协调者收到这个ACK响应之后，完成任务。
- 协调者从参与者没有得到ACK的反馈, 也可能是接收者发送的不是ACK响应，也可能是响应超时: 执行事务中断。
5. 2PC vs 3PC
5.1 2PC和3PC
对于协调者(Coordinator)和参与者(Cohort)都设置了超时机制（在2PC中，只有协调者拥有超时机制，即如果在一定时间内没有收到cohort的消息则默认失败）。
在2PC的准备阶段和提交阶段之间，插入预提交阶段，使3PC拥有CanCommit、PreCommit、DoCommit三个阶段。
PreCommit是一个缓冲，保证了在最后提交阶段之前各参与节点的状态是一致的。
*：
三阶段提交是“非阻塞”协议。
三阶段提交在两阶段提交的第一阶段与第二阶段之间插入了一个准备阶段，
使得原先在两阶段提交中，参与者在投票之后，由于协调者发生崩溃或错误，
而导致参与者处于无法知晓是否提交或者中止的“不确定状态”所产生的可能相当长的延时的问题得以解决。 举例来说，假设有一个决策小组由一个主持人负责与多位组员以电话联络方式协调是否通过一个提案，以两阶段提交来说，主持人收到一个提案请求，打电话跟每个组员询问是否通过并统计回复，然后将最后决定打电话通知各组员。
要是主持人在跟第一位组员通完电话后失忆，而第一位组员在得知结果并执行后老人痴呆，那么即使重新选出主持人，也没人知道最后的提案决定是什么，也许是通过，也许是驳回，不管大家选择哪一种决定，都有可能与第一位组员已执行过的真实决定不一致，老板就会不开心认为决策小组沟通有问题而解雇。
三阶段提交即是引入了另一个步骤，主持人打电话跟组员通知请准备通过提案，以避免没人知道真实决定而造成决定不一致的失业危机。
为什么能够解决二阶段提交的问题呢？
回到刚刚提到的状况，在主持人通知完第一位组员请准备通过后两人意外失忆，即使没人知道全体在第一阶段的决定为何，全体决策组员仍可以重新协调过程或直接否决，不会有不一致决定而失业。
那么当主持人通知完全体组员请准备通过并得到大家的再次确定后进入第三阶段，
当主持人通知第一位组员请通过提案后两人意外失忆，这时候其他组员再重新选出主持人后，
仍可以知道目前至少是处于准备通过提案阶段，表示第一阶段大家都已经决定要通过了，此时便可以直接通过。
5.2 三阶段提交协议的缺点
如果进入PreCommit后，Coordinator发出的是abort请求，假设只有一个Cohort收到并进行了abort操作，而其他对于系统状态未知的Cohort会根据3PC选择继续Commit，此时系统状态发生不一致性。
5.3 替代
目前还有一种重要的算法就是Paxos算法，Zookeeper采用的就是Paxos算法的改进。