1. 分布式一致性
在分布式系统中，为了保证数据的高可用，通常，我们会将数据保留多个副本(replica)，这些副本会放置在不同的物理的机器上。为了对用户提供正确的增\删\改\差等语义，我们需要保证这些放置在不同物理机器上的副本是一致的。
为了解决这种分布式一致性问题，前人在性能和数据一致性的反反复复权衡过程中总结了许多典型的协议和算法。其中比较著名的有二阶提交协议（Two Phase Commitment Protocol）、三阶提交协议（Three Phase Commitment Protocol）和Paxos算法。
2. 分布式事务
分布式事务是指会涉及到操作多个数据库的事务。其实就是将对同一库事务的概念扩大到了对多个库的事务。目的是为了保证分布式系统中的数据一致性。分布式事务处理的关键是必须有一种方法可以知道事务在任何地方所做的所有动作，提交或回滚事务的决定必须产生统一的结果（全部提交或全部回滚）
在分布式系统中，各个节点之间在物理上相互独立，通过网络进行沟通和协调。由于存在事务机制，可以保证每个独立节点上的数据操作可以满足ACID。但是，相互独立的节点之间无法准确的知道其他节点中的事务执行情况。所以从理论上讲，两台机器理论上无法达到一致的状态。如果想让分布式部署的多台机器中的数据保持一致性，那么就要保证在所有节点的数据写操作，要不全部都执行，要么全部的都不执行。
但是，一台机器在执行本地事务的时候无法知道其他机器中的本地事务的执行结果。所以他也就不知道本次事务到底应该commit还是 roolback。所以，常规的解决办法就是引入一个“协调者”的组件来统一调度所有分布式节点的执行。
3. 两阶段提交协议
两阶段提交（Two-phase Commit）主要保证了分布式事务的原子性：即所有结点要么全做要么全不做。
分布式事务的实现技术如下表所示。（以PostgreSQL作为事务参与方为例）
| 分布式ACID | 实现技术 |
|---|---|
| 原子性（Atomicity） | MVCC + 两阶段提交 |
| 一致性（Consistency） | 约束（主键、外键等） |
| 隔离性 | MVCC |
| 持久性 | WAL |
从上表可以看到，一致性、隔离性和持久性靠的是各分布式事务参与方自己原有的机制，而两阶段提交主要保证了分布式事务的原子性。
二阶段提交的算法思路可以概括为：参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。
所谓的两个阶段是指：第一阶段：准备阶段(投票阶段)和第二阶段：提交阶段（执行阶段）。
3.1. 协调者和参与者
在两阶段提交协议中，系统一般包含两类机器（或节点）：
- 一类为协调者（coordinator），通常一个系统中只有一个；
- 另一类为事务参与者（participants，cohorts或workers），一般包含多个，在数据存储系统中可以理解为数据副本的个数。
- 协议中假设每个节点都会记录写前日志（write-ahead log）并持久性存储，即使节点发生故障日志也不会丢失。协议中同时假设节点不会发生永久性故障而且任意两个节点都可以互相通信。
3.2. 准备阶段
commit-request phase，或称表决阶段，voting phase。在请求阶段，协调者将通知事务参与者准备提交或取消事务，然后进入表决过程。 在表决过程中，参与者将告知协调者自己的决策：同意（事务参与者本地作业执行成功）或取消（本地作业执行故障）。
3.3. 提交阶段
commit phase。在该阶段，协调者将基于第一个阶段的投票结果进行决策：提交或取消。 当且仅当所有的参与者同意提交事务协调者才通知所有的参与者提交事务，否则协调者将通知所有的参与者取消事务。参与者在接收到协调者发来的消息后将执行响应的操作。
3.4. 两阶段提交的问题
1、同步阻塞问题。执行过程中，所有参与节点都是事务阻塞型的。当参与者占有公共资源时，其他第三方节点访问公共资源不得不处于阻塞状态。
2、单点故障。由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。（如果是协调者挂掉，可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题）
3、数据不一致。在二阶段提交的阶段二中，当协调者向参与者发送commit请求之后，发生了局部网络异常或者在发送commit请求过程中协调者发生了故障，这回导致只有一部分参与者接受到了commit请求。而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据部一致性的现象。
4、二阶段无法解决的问题：协调者再发出commit消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。
4. 三阶段提交协议
三阶段提交（Three-phase commit）与两阶段提交不同，有两个改动点。
- 引入超时机制。同时在协调者和参与者中都引入超时机制。
- 在第一阶段和第二阶段中插入一个预提交阶段。使三阶段变成CanCommit，PreCommit，DoCommit阶段。PreCommit是一个缓存，保证在最后提交阶段之前各个节点状态一致的。
4.1. CanCommit阶段
3阶段CanCommit阶段和2阶段准备阶段很像。 协调者向参与者发送Commit请求，参与者如果可以提交就Yes响应，否则No响应。
4.2. PreCommit阶段
根据第一阶段反应情况决定执行PreCommit操作。
如Yes:就进行事务的预执行：
发送预提交请求，进入Prepared阶段。 事务预提交，执行事务操作，将undo和redo信息记录到事务日志中。 响应反馈，如果事务成功执行，等待最终指令。
如果No，或等待超时：中断事务：
发送中断请求。 中断事务。
4.3. DoCommit阶段
该阶段进行真正的事务提交，两种情况：
执行提交：
发送提交请求，将从预提交进入提交状态。 事务提交，上面执行成功执行正式的事务提交。在事务提交之后释放事务资源。 响应反馈，事务提交之后反馈。 完成事务。收到反馈之后，完成事务。
中断事务：
没有收到反馈，中断事务。
5. 2PC VS 3PC
2PC
3PC
总结：
相对于2PC，3PC主要解决的单点故障问题，并减少阻塞，因为一旦参与者无法及时收到来自协调者的信息之后，他会默认执行commit。而不会一直持有事务资源并处于阻塞状态。
但是这种机制也会导致数据一致性问题，因为，由于网络原因，协调者发送的abort响应没有及时被参与者接收到，那么参与者在等待超时之后执行了commit操作。这样就和其他接到abort命令并执行回滚的参与者之间存在数据不一致的情况。
无论是二阶段提交还是三阶段提交都无法彻底解决分布式的一致性问题。世上只有一种一致性算法，那就是Paxos，所有其他一致性算法都是Paxos算法的不完整版。
参考资料：
6. paxos
Paxos算法就是解决这种分布式场景中的一致性问题。对于一般的开发人员来说，只需要知道paxos是一个分布式选举算法即可。多个节点之间存在两种通讯模型：共享内存（Shared memory）、消息传递（Messages passing），Paxos是基于消息传递的通讯模型的。
6.1. 约束条件
P1： Acceptor必须接受他接收到的第一个提案，
注意P1是不完备的。如果恰好一半Acceptor接受的提案具有value A，另一半接受的提案具有value B，那么就无法形成多数派，无法批准任何一个value。
P2：当且仅当Acceptor没有回应过编号大于n的prepare请求时，Acceptor接受（accept）编号为n的提案。
如果一个没有chosen过任何proposer提案的Acceptor在prepare过程中回答了一个proposer针对提案n的问题，但是在开始对n进行投票前，又接受（accept）了编号小于n的另一个提案（例如n-1），如果n-1和n具有不同的value，这个投票就会违背P2c。因此在prepare过程中，Acceptor进行的回答同时也应包含承诺：不会再接受（accept）编号小于n的提案。
P3：只有Acceptor没有接受过提案Proposer才能采用自己的Value，否者Proposer的Value提案为Acceptor中编号最大的Proposer Value；
P4: 一个提案被选中需要过半数的Acceptor接受。
假设A为整个Acceptor集合，B为一个超过A一半的Acceptor集合，B为A的子集，C也是一个超过A一半的Acceptor集合，C也是A的子集，有此可知任意两个过半集合中必定有一个共同的成员Acceptor；此说明了一个Acceptor可以接受不止一个提案，此时需要一个编号来标识每一个提案，提案的格式为：[编号，Value]，编号为不可重复全序的，因为存在着一个一个Paxos过程只能批准一个value这时又推出了一个约束P3；
P5：当编号K0、Value为V0的提案(即[K0,V0])被过半的Acceptor接受后，今后（同一个Paxos或称一个Round中）所有比K0更高编号且被Acceptor接受的提案，其Value值也必须为V0。
该约束还可以表述为：
- 一旦一个具有value v的提案被批准（chosen），那么之后任何Acceptor再次接受（accept）的提案必须具有value v。
- 一旦一个具有value v的提案被批准（chosen），那么以后任何proposer提出的提案必须具有value v。
- 如果一个编号为n的提案具有value v，那么存在一个多数派，要么他们中所有人都没有接受（accept）编号小于n
的任何提案，要么他们已经接受（accept）的所有编号小于n的提案中编号最大的那个提案具有value v。
因为每个Proposer都可提出多个议案，每个议案最初都有一个不同的Value所以要满足P3就又要推出一个新的约束P4；
6.2. 基本概念
- Proposal Value：提议的值；
- Proposal Number：提议编号，要求提议编号不能冲突；
- Proposal：提议 = 提议的值 + 提议编号；
- Proposer：提议发起者；
- Acceptor：提议接受者；
- Learner：提议学习者。
注意，提议跟提议的值是有区别的，后面会具体说明。协议中 Proposer 有两个行为，一个是向 Acceptor 发 Prepare 请求，另一个是向 Acceptor 发 Accept 请求；Acceptor 则根据协议规则，对 Proposer 的请求作出应答；最后 Learner 可以根据 Acceptor 的状态，学习最终被确定的值。
方便讨论，在本文中，记{n，v}为提议编号为 n，提议的值为 v 的提议，记 (m，{n，v}) 为承诺了 Prepare（m）请求，并接受了提议{n，v}。
6.3. 协议过程
第一阶段 A
Proposer 选择一个提议编号 n，向所有的 Acceptor 广播 Prepare（n）请求。
第一阶段 B
Acceptor 接收到 Prepare（n）请求，若提议编号 n 比之前接收的 Prepare 请求都要大，则承诺将不会接收提议编号比 n 小的提议，并且带上之前 Accept 的提议中编号小于 n 的最大的提议，否则不予理会。
第二阶段 A
Proposer 得到了多数 Acceptor 的承诺后，如果没有发现有一个 Acceptor 接受过一个值，那么向所有的 Acceptor 发起自己的值和提议编号 n，否则，从所有接受过的值中选择对应的提议编号最大的，作为提议的值，提议编号仍然为 n。
第二阶段 B
Acceptor 接收到提议后，如果该提议编号不违反自己做过的承诺，则接受该提议。
需要注意的是，Proposer 发出 Prepare（n）请求后，得到多数派的应答，然后可以随便再选择一个多数派广播 Accept 请求，而不一定要将 Accept 请求发给有应答的 Acceptor，这是常见的 Paxos 理解误区。
6.4. 小结
上面的图例中，P1 广播了 Prepare 请求，但是给 A3 的丢失，不过 A1、A2 成功返回了，即该 Prepare 请求得到多数派的应答，然后它可以广播 Accept 请求，但是给 A1 的丢了，不过 A2，A3 成功接受了这个提议。因为这个提议被多数派（A2，A3 形成多数派）接受，我们称被多数派接受的提议对应的值被 Chosen。
三个 Acceptor 之前都没有接受过 Accept 请求，所以不用返回接受过的提议，但是如果接受过提议，则根据第一阶段 B，要带上之前 Accept 的提议中编号小于 n 的最大的提议。
Proposer 广播 Prepare 请求之后，收到了 A1 和 A2 的应答，应答中携带了它们之前接受过的{n1, v1}和{n2, v2}，Proposer 则根据 n1，n2 的大小关系，选择较大的那个提议对应的值，比如 n1 > n2，那么就选择 v1 作为提议的值，最后它向 Acceptor 广播提议{n, v1}。