分布式一致性算法：二段提交和三段提交，常用于分布式系统的事务操作。

概念定义

协调者：coordinator,事务管理器，每个节点（参与者）都知道自己的事务状态，但无法知道自己之外的事务状态。协调者的作用是管理所有参与者的事务状态。决定整个事务的commit/rollback。
参与者：participant,资源管理器，真正控制锁定事务资源的节点。可以理解为提供RPC服务的节点。

前提

节点可恢复：宕机后节点必须是能恢复提供正常服务的。
日志持久化：节点写入的undo log和redo log是被认为持久化且不可改变的。
单点问题：单点问题属于HA问题，不在讨论范围内。

二段提交2PC(Two-phase commit)

过程

准备阶段(Voting phase)：协调者询问参与者开启事务，参与者写入undo log和redo log，并告知协调者已就绪
事务提交阶段(Commit phase)：协调者收到所有参与者的就绪确认，则向参与者发送提交事务请求。参与者commit事务并释放资源。并告知协调者事务已提交。

异常分析

参与者宕机：协调者会告知所有参与者回滚事务，执行rollback。参与者如果恢复，对于未提交的事务也采取rollback操作。
协调者宕机：协调者在提交阶段宕机，如果此前没有任何参与者收到协调者的commit or abort命令，则整个事务的状态不可知。只能等待协调者恢复后，重新发送命令告诉参与者。（如果引入协调者响应超时机制，超时后去询问其他参与者，参与者都未提交事务，则事务回滚；若有一个参与者提交了事务，则所有参与者提交事务。）
协调者和参与者同时宕机：而参与者执行了rollback/commit操作，却来不及返回给协调者。此时即使选举了新的协调者，也不知道宕掉的参与者的事务状态。新的协调者也就无法告知其他参与者执行commit还是rollback了。

缺点

最终一致性：参与者宕机，等待恢复期间数据节点间的数据不一致。实现的是最终一致性。
资源阻塞问题：准备阶段事务已经start，各个参与者锁定所有的相关资源，等待事务结束后才释放资源。通过Lease机制，超时后自动释放事务资源，缓解阻塞问题。特别是协调者在提交阶段没有发送commit/abort命令时宕机，所有参与者都不知道事务状态，只能一直阻塞等待协调者恢复服务。

伪代码

来自《Distributed Systems: Principles and Paradigms》一书。

//协调者的代码实现
write("START_2PC tolocal log");
multicast("VOTE_REQUESTto all participants"); //协调者广播消息给参与者并写入WAL
while(not all votes have been collected) //协调者等待所有参与者返回ack消息
{
  waitfor("any incoming vote");//有一个参与者响应了
  if(timeout)//参与者响应超时
  {
    write("GLOBAL_ABORT to local host"); //协调者放弃事务
    multicast("GLOBAL_ABORT to all participants"); //广播所有参与者放弃事务
    exit();
  }
  record(vote);//记录参与者的响应消息
}
if(all participants send VOTE_COMMIT and coordinatorvotes COMMIT)//所有参与者同意提交事务，并且协调者确定应提交事务
{
  write("GLOBAL_COMMIT to local log"); //协调者提交本地WAL
  multicast("GLOBAL_COMMIT to all participants"); //广播所有参与者提交WAL
}
else //如果投票是放弃事务
{
  write("GLOBAL_ABORT to local log");
  multicast("GLOBAL_ABORT to all participants");
}
//参与者的代码实现
write("INIT to locallog");
waitfor("VOTE_REQUEST from coordinator");//等待协调者的开启事务请求
if(timeout) //如果超时，放弃事务
{
  write("VOTE_ABORT to local log");
  exit();
}
if("participantvotes COMMIT") //如果当前参与者同意commit
{
  write("VOTE_COMMIT to local log"); //写入WAL
  send("VOTE_COMMIT to coordinator"); //告诉协调者已经就绪
  waitfor("DESCISION from coordinator"); //等待协调者收集所有参与者的投票，确认是abort or commit
  if(timeout) //如果协调者响应超时
  {
    multicast("DECISION_REQUEST to other participants"); //询问其他参与者的事务状态
    waituntil("DECISION is received"); /// remain blocked 等待确认：是abort or commit
    write("DECISION to local log"); //写本地日志记录
  }
  if(DECISION == "GLOBAL_COMMIT") //如果确定提交事务
  {
    write("GLOBAL_COMMIT to local log");
  }
  else if(DECISION== "GLOBAL_ABORT") //如果确定放弃事务
  {
    write("GLOBAL_ABORT to local log");
  }
}
else //如果参与者不同意事务，告诉协调者
{
    write("GLOBAL_ABORT to local log");
    send("GLOBAL_ABORT to coordinator");
}

三段提交3PC(Three-phase commit)

过程

canCommit：协调者询问参与者是否可以开启事务？（此时事务没有打开，资源没有被锁定阻塞）
preCommit：参与者确认可以提交，协调者请求参与者开启事务，写入redo log和undo log。
doCommit：协调者收到参与者preCommit的确认后，发送请求让参与者提交事务。

异常分析

略。大致类似于2PC，区别在于3PC解决的问题和代价。见下文。

解决了2PC的问题和代价

3PC将2PC的第一阶段拆分为canCommit和preCommit两个阶段。

资源阻塞问题：canCommit阶段不开启事务，只是询问状态。降低阻塞的可能性。代价：多了一次RPC请求，存在数据不一致的情况。
PS：但是之后的preCommit和doCommit不正是2PC吗？2PC会出现的问题理论上也会出现在3PC才对。其解决方法便是增加canCommit阶段，canCommit通过后，参与者宕机是默认commit的，通过这个来减少阻塞。canCommit用来投票，但是preCommit如果反馈的结果是abort事务，不是数据直接不一致了？

缺点

如上，解决2PC的代价便是缺点。只是减少了阻塞，带来更大的数据不一致可能。
不得不联想到CAP啊，三者不能共存。

其他分布式事务解决方案

TCC(Try-Confirm-Cancel)模型(2PC的变种)，手动事务补偿
事务性消息队列
普通消息队列+定时补偿机制

引用

分布式系统的一致性探讨
 深入理解分布式系统的2PC和3PC
关于分布式事务、两阶段提交协议、三阶提交协议
 两阶段提交协议的异常处理
 分布式事务－二阶段提交与三阶段提交
 Introduction to 3PC 三阶段提交协议简介