一.分布式简介

分布式：分布在不同的网络计算机上的软硬件组件通过消息传递进行通信和协调系统。有以下几个特点：

1. 分布性。空间上随意分布。
2. 对等性。无主从之分。节点之间是对等的。分为数据副本(数据冗余，解决分布式系统数据丢失问题)和服务副本(提供同样的服务，节点均有能力处理外部请求)。
3. 并发性。准确并高效地协调分布式并发操作称为最大挑战之一。
4. 缺乏全局时钟。分布式系统的时间和事件顺序。
5. 故障总会发生。黄金法则：任何在设计阶段考虑到的异常情况，一定在系统实际运行中发生。

在分布式环境中，存在以下几个问题：

1. 通信异常。消息丢失和消息延迟。单机延时: 10ns. 网络延迟: 0.1~1ms。
2. 网络分区。又称为脑裂。部分节点独立完成原本需要整个分布式系统才能完成的功能，由于网络延迟，可能会出现数据不一致的情况。
3. 三态。单机的事务要么响应成功，要么失败。而分布式的每一次请求与响应，存在特有的”三态”：成功、失败与超时。
4. 节点故障，每个节点都可能会出现故障，宕机。

分布式中唯一的一个问题：对某事达成一致。

在单机中，很容易实现ACID，但是在分布式系统中，如果想要严格满足ACID，就会牺牲系统的可用性，这在高访问，高并发的网站中是不可接受的。为了权衡可用性和一致性，产生了一系列的算法，在这里，主要介绍下2PC，3PC。

二.分布式一致性协议：2PC和3PC

2PC，3PC协议用于保证属于多个数据分片上的操作的原子性。这些数据分片可能分布在不同的服务器上，2PC和3PC协议保证多台服务器上的操作要么全部成功，要么全部失败。

一.2PC（两阶段提交）

在分布式系统中，每个节点虽然可以知晓自己的操作时成功或者失败，却无法知道其他节点的操作的结果。所以需要引入一个作为协调者，统一掌控所有节点(称作参与者)的操作结果，并决定最终结果。因此，二阶段提交的算法思路可以概括为：参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。

第一阶段，提交事务请求：

协调者会问所有的参与者结点，是否可以执行提交操作。 各个参与者开始事务执行的准备工作：如：为资源上锁，预留资源，写undo/redo log，进行事务的实际操作。 参与者响应协调者，如果事务的准备工作成功，则回应“可以提交”，否则回应“拒绝提交”。

第二阶段，执行事务提交：

如果所有的参与者都回应“可以提交”，那么，协调者向所有的参与者发送“正式提交”的命令。参与者完成正式提交，并释放所有资源，然后回应“完成”，协调者收集各结点的“完成”回应后结束这个事务。 如果有一个参与者回应“拒绝提交”，那么，协调者向所有的参与者发送“回滚操作”，并释放所有资源，然后回应“回滚完成”，协调者收集各结点的“回滚”回应后，取消这个事务。

主要缺点：

1. 同步阻塞问题。执行过程中，所有参与节点都是事务阻塞型的。当参与者占有公共资源时，其他第三方节点访问公共资源不得不处于阻塞状态。
2. 单点故障。由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。
3. 数据不一致。在二阶段提交的阶段二中，当协调者向参与者发送commit请求过程中，网络异常或者协调者发生了故障，导致只有一部分参与者接受到了commit请求。于是整个分布式系统便出现了数据不一致的现象。
4. 参与者故障时，协调者只能靠超时操作中断事务，容错性差，一个节点失败，整个事务就失败了。

   二.3PC（三阶段提交）

   3PC相比较2PC有两个改动点。

5. 把二段提交的第一个段分成了两段：询问，然后再锁资源，在询问的时候并不锁定资源，除非所有人都同意了，才开始锁资源。
6. 在参与者中也引入超时机制。

第一阶段，CanCommit：

协调者向参与者发送cancommit请求，参与者如果可以提交就返回Yes响应，否则返回No响应。

第二阶段，PreCommit：

假如协调者从所有的参与者获得的反馈都是Yes响应，那么就会执行事务的预执行。 假如有任何一个参与者向协调者发送了No响应，或者等待超时之后，协调者都没有接到参与者的响应，那么就执行事务的中断。

第三阶段，DoCommit：

进行真正的事务提交。

优点:

相对于2PC，3PC主要解决的单点故障问题，并减少阻塞，因为一旦参与者无法及时收到来自协调者的信息之后，他会默认执行commit(因为理论上来说，如果第一阶段所有的结点返回成功，那么有理由相信成功提交的概率很大)。而不会一直持有事务资源并处于阻塞状态。

缺点：

但是这种机制也会导致数据一致性问题，因为，由于网络原因，协调者发送的中断响应没有及时被参与者接收到，那么参与者在等待超时之后执行了commit操作。这样就和其他接到abort命令并执行回滚的参与者之间存在数据不一致的情况。

三.Paxos

Google Chubby的作者说过这个世界上只有一种一致性算法，那就是Paxos，其它的算法都是残次品。 Paxos协议用于保证同一个数据分片的多个副本之间的数据一致性，要解决的问题就是如何在可能发生几起宕机或网络异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

Paxos中存在三种角色Proposer（提议者）、Acceptor（决策者）、Learner（议案学习者）。 Paxos 协议需要依赖一个基本假设，主备之间有多数派机器（N / 2 + 1）存活并且他们之间的网络通信正常，如果不满足这个条件，则无法启动服务，数据也无法写入和读取。 协议规则：

P1: Acceptor必须接受他接收到的第一个提案。

　　有这约束就会出现一个新问题：当多个议案被多个Proposer同时提出，这时每个Acceptor都接收到了他收到的第一个议案，此时没法选择最终议案。所以就又存在一个新的约束P2；

P2: 一个提案被选中需要过半数的Acceptor接受。

　　假设A为整个Acceptor集合，B为一个超过A一半的Acceptor集合，B为A的子集，C也是一个超过A一半的Acceptor集合，C也是A的子集，有此可知任意两个过半集合中必定有一个共同的成员Acceptor； 　　此说明了一个Acceptor可以接受不止一个提案，此时需要一个编号来标识每一个提案，提案的格式为：[编号，Value]，编号为不可重复全序的，因为存在着一个一个Paxos过程只能批准一个value这时又推出了一个约束P3；

P3：当编号K0、Value为V0的提案(即[K0,V0])被过半的Acceptor接受后，今后（同一个Paxos或称一个Round中）所有比K0更高编号且被Acceptor接受的提案，其Value值必须为V0。

　　因为每个Proposer都可提出多个议案，每个议案最初都有一个不同的Value所以要满足P3就又要推出一个新的约束P4； P4：只有Acceptor没有接受过提案Proposer才能采用自己的Value，否者Proposer的Value提案为Acceptor中编号最大的Proposer Value；

通过一个决议分为两个阶段：

phase1（准备阶段）

　　1. Proposer向超过半数（n/2+1）Acceptor发起prepare消息(发送提案号，这个数不断递增，而且是唯一的，也就是说不可能有相同的提案号)。 　　2. acceptor收到prepare消息后，如果提案的编号大于它已经回复的所有prepare消息，则acceptor将自己上次接受的提案回复给proposer，并承诺不再回复小于n的提案；

phase2（决议阶段或投票阶段）

　　1. 如果超过半数Acceptor回复promise，Proposer向Acceptor发送accept消息，包括编号n和根据P2决定的value（如果根据P2没有已经接受的value，那么它可以自由决定value）。 　　2. Acceptor检查accept消息是否符合规则，消息符合则批准accept请求。 　　 下图可以看做一个选主Server的流程

　P1编号2，P2编号1，P3编号3，分别发送消息。

Phase1（准备阶段）

1. P1编号2，P2编号1，P3编号3，分别发送消息。
2. 这时P1发送的消息先到达A1和A2，这两个都没有接收过请求所以接受了请求返回[2,null]给P1，并承诺不接受编号小于2的请求；
3. 此时P2发送的消息到达A2和A3，A3没有接收过请求返回[1,null]给P2，并承诺不接受编号小于1的请求，但这时A2已经接受过P1的请求并承诺不接受编号小于的2的请求了，所以A2拒绝P2的请求；
4. 最后P3发送的消息到达A2和A3，A2接受过提议，但此时编号为3大于A2的承诺2与A3的承诺1，所以接受提议返回[3,null];
5. P2没收到过半的回复所以重新取得编号4，并发送给A2和A3，然后A2和A3都收到消息，此时编号4大于A2与A3的承诺3，所以接受提议返回[4,null]；

   Phase2（决议阶段）

6. Proposer3收到过半的返回，并且返回的Value为null，所以Proposer3提交了[3,server3]的议案；
7. Proposer1收到过半返回，返回的Value为null，所以Proposer1提交了[2,server1]的议案；
8. Proposer2收到过半返回，返回的Value为null，所以Proposer2提交了[4,server2]的议案；
9. Acceptor1、Acceptor2接收到Proposer1的提案[2,server1]请求，A承诺编号大于4所以拒绝了通过；
10. Proposer2的提案[4,server2]发送到了Acceptor2、Acceptor3，提案编号为4所以Acceptor2、Acceptor3都通过了提案请求；
11. Acceptor2、Acceptor3接收到Proposer3的提案[3,server3]请求，A2、A3承诺编号大于4所以拒绝了提案；
12. 此时过半的A都接受了Proposer2的提案[4,server2],L感知到了提案的通过，L学习提案. 一个Paxos过程只会产生一个议案,至此这个流程结束,value为P2。