原文同步至https://waylau.com/distributed-system-transaction/
为保障系统的可用性、可靠性以及性能，在分布式系统中，往往会设置数据冗余，即对数据进行复制。举例来说，当一个数据库的副本被破环以后，那么系统只需要转换到其他数据副本就能继续运行下去。另外一个例子，当访问单一服务器管理的数据的进程数不断增加时，系统就需要对服务器的数量进行扩充，此时，对服务器进行复制，随后让它们分担工作负荷，就可以提高性能。但同时，如何保障多个数据节点之间数据的一致以及如何处理分布式事务，将成为为一个复杂的话题。本文将介绍常用的事务处理机制。
CAP 定理
CAP 定理（也称为 Brewer 定理），是由计算机科学家 Eric Brewer 提出的，即在分布式计算机系统不可能同时提供以下全部三个保证：
- 一致性（Consistency）：所有节点同一时间看到是相同的数据；
- 可用性（Availability）：不管是否成功，确保每一个请求都能接收到响应；
- 分区容错性（Partition tolerance）：系统任意分区后，在网络故障时，仍能操作
显然，为了保障性能和可靠性，我们将数据复制多份，分布到多个节点上，同时也带来了一个难点，那就是如何保持各个副本数据的一致性。换句话说，我们选择了 AP ，则必须要牺牲掉 C 了。
但是，在实际的应用场景中，数据的一致性往往也是需要保证的。那么这是否违背了 CAP 定理呢？
一致性模型
其实，数据的一致性也分几种情况，大致可以分为：
- Weak 弱一致性：当你写入一个新值后，读操作在数据副本上可能读出来，也可能读不出来。比如：某些存储系统，搜索引擎，实时游戏，语音聊天等，这些数据本文对完整性要求不高，数据是否一致关系也不大。
- Eventually 最终一致性：当你写入一个新值后，并不一定能马上读出来，但在某个时间窗口之后保证最终能读出来。比如：DNS，电子邮件，消息中间件等系统，大部分分布式系统技术都采用这类模式。
- Strong 强一致性：新的数据一旦写入，在任意副本任意时刻都能读到新值。比如：文件系统，RDBMS都是强一致性的。
也就是说，在设计分布式系统时，我们并不一定要求是强一致性的，根据应用场景可以选择弱一致性或者是最终一致性。
事务的作用
事务有如下作用：
- 保证执行结果的正确性
- 保证数据的一致性
- ACID
常见的事务处理机制
Master-Slave 复制
Slave 一般是 Master 的备份。在这样的系统中，一般是如下设计的：
- 读写请求都由 Master 负责。
- 写请求写到 Master 上后，由 Master 同步到 Slave 上。
这种机制的特点是：
- 数据同步通常是异步的
- 有良好的吞吐量，低延迟
* 在大多数 RDBMS 中支持，比如 MySQL二进制日志 - 弱/最终一致性
这种机制的缺点是，如果 Master 挂了，Slave 只能提供读服务，而没有写服务。
Master-Master 多主复制
指一个系统存在两个或多个Master，每个Master都提供读写服务。这个机制是Master-Slave的加强版，数据间同步一般是通过Master间的异步完成，所以是最终一致性。 Master-Master的好处是，一台Master挂了，别的Master可以正常做读写服务，他和Master-Slave一样，当数据没有被复制到别的Master上时，数据会丢失。很多数据库都支持Master-Master的Replication的机制。
这种机制的特点是：
- 异步
- 最终的一致性
- 多个节点间需要序列化协议
两阶段提交
两阶段提交协议 （Two-phase commit protocol，2PC）的过程涉及到协调者和参与者。协调者可以看做成事务的发起者，同时也是事务的一个参与者。对于一个分布式事务来说，一个事务是涉及到多个参与者的。具体的两阶段提交的过程如下：
第一阶段（准备阶段）
- 协调者节点向所有参与者节点询问是否可以执行提交操作(vote)，并开始等待各参与者节点的响应。
- 参与者节点执行询问发起为止的所有事务操作，并将 Undo 信息和 Redo 信息写入日志。（注意：若成功这里其实每个参与者已经执行了事务操作）
- 各参与者节点响应协调者节点发起的询问。如果参与者节点的事务操作实际执行成功，则它返回一个“同意”消息；如果参与者节点的事务操作实际执行失败，则它返回一个“中止”消息。
第二阶段（提交阶段）
如果协调者收到了参与者的失败消息或者超时，直接给每个参与者发送回滚(Rollback)消息；否则，发送提交(Commit)消息；参与者根据协调者的指令执行提交或者回滚操作，释放所有事务处理过程中使用的锁资源。(注意:必须在最后阶段释放锁资源)
- 当协调者节点从所有参与者节点获得的相应消息都为“同意”时:
- 协调者节点向所有参与者节点发出“正式提交(commit)”的请求。
- 参与者节点正式完成操作，并释放在整个事务期间内占用的资源。
- 参与者节点向协调者节点发送“完成”消息。
- 如果任一参与者节点在第一阶段返回的响应消息为”中止”，或者 协调者节点在第一阶段的询问超时之前无法获取所有参与者节点的响应消息时：
- 协调者节点向所有参与者节点发出”回滚操作(rollback)”的请求。
- 参与者节点利用之前写入的Undo信息执行回滚，并释放在整个事务期间内占用的资源。
- 参与者节点向协调者节点发送”回滚完成”消息。
- 协调者节点受到所有参与者节点反馈的”回滚完成”消息后，取消事务。
- 协调者节点受到所有参与者节点反馈的”完成”消息后，完成事务
不管最后结果如何，第二阶段都会结束当前事务。
二段式提交协议的优缺点：
优点：原理简单，实现方便；
缺点：
- 同步阻塞问题。执行过程中，所有参与节点都是事务阻塞型的。
- 单点故障。由于协调者的重要性，一旦协调者发生故障，参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。
- 数据不一致。在阶段二中，当协调者向参与者发送 commit 请求之后，发生了局部网络异常或者在发送 commit 请求过程中协调者发生了故障，这回导致只有一部分参与者接受到了 commit 请求。而在这部分参与者接到 commit 请求之后就会执行 commit 操作。但是其他部分未接到 commit 请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据部一致性的现象。
- 二阶段无法解决的问题：协调者再发出 commit 消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。
为了解决两阶段提交协议的种种问题，研究者们在二阶段提交的基础上做了改进，提出了三阶段提交。
三阶段提交
三阶段提交协议（Three-phase commit protocol，3PC），是二阶段提交（2PC）的改进版本。与两阶段提交不同的是，三阶段提交有两个改动点：
- 引入超时机制。同时在协调者和参与者中都引入超时机制。
- 在第一阶段和第二阶段中插入一个准备阶段。保证了在最后提交阶段之前各参与节点的状态是一致的。
即 3PC 把 2PC 的准备阶段再次一分为二，这样三阶段提交就有 CanCommit、PreCommit、DoCommit 三个阶段。
CanCommit 阶段
CanCommit 阶段其实和 2PC 的准备阶段很像。协调者向参与者发送 commit 请求，参与者如果可以提交就返回 Yes 响应，否则返回 No 响应。
- 事务询问：协调者向参与者发送 CanCommit 请求。询问是否可以执行事务提交操作。然后开始等待参与者的响应。
- 响应反馈：参与者接到 CanCommit 请求之后，正常情况下，如果其自身认为可以顺利执行事务，则返回 Yes 响应，并进入预备状态。否则反馈 No
PreCommit 阶段
协调者根据参与者的反应情况来决定是否可以记性事务的 PreCommit 操作。根据响应情况，有以下两种可能。
- 假如协调者从所有的参与者获得的反馈都是 Yes 响应，那么就会执行事务的预执行。
- 发送预提交请求：协调者向参与者发送 PreCommit 请求，并进入Prepared 阶段。
- 事务预提交：参与者接收到 PreCommit 请求后，会执行事务操作，并将undo 和 redo 信息记录到事务日志中。
- 响应反馈：如果参与者成功的执行了事务操作，则返回 ACK 响应，同时开始等待最终指令。
- 假如有任何一个参与者向协调者发送了 No 响应，或者等待超时之后，协调者都没有接到参与者的响应，那么就执行事务的中断。
- 发送中断请求：协调者向所有参与者发送 abort 请求。
- 中断事务：参与者收到来自协调者的 abort 请求之后（或超时之后，仍未收到协调者的请求），执行事务的中断。
doCommit 阶段
该阶段进行真正的事务提交，也可以分为以下两种情况。
- 执行提交
- 发送提交请求：协调接收到参与者发送的 ACK 响应，那么他将从预提交状态进入到提交状态。并向所有参与者发送 doCommit 请求。
- 事务提交：参与者接收到 doCommit 请求之后，执行正式的事务提交。并在完成事务提交之后释放所有事务资源。
- 响应反馈：事务提交完之后，向协调者发送 ACK 响应。
- 完成事务：协调者接收到所有参与者的 ACK 响应之后，完成事务。
- 中断事务：协调者没有接收到参与者发送的 ACK 响应（可能是接受者发送的不是 ACK 响应，也可能响应超时），那么就会执行中断事务。
- 发送中断请求：协调者向所有参与者发送 abort 请求
- 事务回滚：参与者接收到 abort 请求之后，利用其在阶段二记录的undo 信息来执行事务的回滚操作，并在完成回滚之后释放所有的事务资源。
- 反馈结果：参与者完成事务回滚之后，向协调者发送 ACK 消息
- 中断事务：协调者接收到参与者反馈的 ACK 消息之后，执行事务的中断。
在 doCommit 阶段，如果参与者无法及时接收到来自协调者的 doCommit 或者 rebort 请求时，会在等待超时之后，会继续进行事务的提交。即当进入第三阶段时，由于网络超时等原因，虽然参与者没有收 到 commit 或者 abort 响应，事务仍然会提交。
三阶段提交不会一直持有事务资源并处于阻塞状态。但是这种机制也会导致数据一致性问题，因为，由于网络原因，协调者发送的 abort 响应没有及时被参与者接收到，那么参与者在等待超时之后执行了 commit 操作，这样就和其他接到 abort 命令并执行回滚的参与者之间存在数据不一致的情况。
Paxos 算法
Paxos 算法是 Leslie Lamport 于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。Paxos 算法目前在 Google 的 Chubby、MegaStore、Spanner 等系统中得到了应用，Hadoop 中的 ZooKeeper 也使用了 Paxos 算法。
在 Paxos 算法中，分为4种角色：
- Proposer ：提议者
- Acceptor：决策者
- Client：产生议题者
- Learner：最终决策学习者
算法可以分为两个阶段来执行：
阶段1
- Proposer 选择一个议案编号 n，向 acceptor 的多数派发送编号也为 n 的 prepare 请求。
- Acceptor：如果接收到的 prepare 请求的编号 n 大于它已经回应的任何prepare 请求，它就回应已经批准的编号最高的议案（如果有的话），并承诺不再回应任何编号小于 n 的议案；
阶段2
- Proposer：如果收到了多数 acceptor 对 prepare 请求（编号为 n）的回应，它就向这些 acceptor 发送议案{n, v}的 accept 请求，其中 v 是所有回应中编号最高的议案的决议，或者是 proposer 选择的值，如果回应说还没有议案。
- Acceptor：如果收到了议案{n, v}的 accept 请求，它就批准该议案，除非它已经回应了一个编号大于 n 的议案。
- Proposer 可以提出多个议案，只要它遵循上面的算法。它可以在任何时刻放弃一个议案。（这不会破坏正确性，即使在议案被放弃后，议案的请求或者回应消息才到达目标）如果其它的 proposer 已经开始提出更高编号的议案，那么最好能放弃当前的议案。因此，如果 acceptor 忽略一个 prepare 或者 accept 请求（因为已经收到了更高编号的 prepare 请求），它应该告知 proposer 放弃议案。这是一个性能优化，而不影响正确性。
参考文献
- http://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-paxos.pdf
- https://www.oschina.net/question/2720166_2235329
- 《分布式系统常用技术及案例分析》:https://github.com/waylau/distributed-systems-technologies-and-cases-analysis