分布式系统中的一致性协议总结

分布式系统中的一致性协议总结

本文详细介绍目前分布式系统中常见的一些一致性协议：两阶段提交协议，三阶段提交协议，向量时钟，RWN协议，paxos协议，Raft协议。下面就一个个详细讲解下。

一. 两阶段提交协议(2PC)

两阶段提交协议，简称2PC，是比较常用的解决分布式事务问题的方式，要么所有参与进程都提交事务，要么都取消事务，即实现ACID中的原子性(A)的常用手段。

两阶段提交将提交过程划分为连续的两个阶段：表决阶段(Voting)和提交阶段(Commit)。假设在没有故障发生的情形下，两阶段提交协议由下列操作序列构成，如下图所示：

协调者的有限状态机如下图：

如上图所示：协调者初始处于INIT状态，当接收到系统发出的Commit消息后，向参与者多播Vote-request消息后转入WAIT状态，在此进入阻塞状态，因为要等待所有参与者发送返回的消息，当收到所有参与者的返回消息后，如果其中包含Vote-Abort消息，则多播Global-abort消息后转入ABORT状态，否则多播Global-commit消息后转入COMMIT状态。

参与者的有限状态机如下图：

如上图所示：参与者初始处于INIT状态，当接收到Vote-Request消息时，发出Vote-commit会转入READY状态，告诉协调者已经准备做好提交准备，否则就返回一个VOTE-ABORT消息。等待协调者行为，如果收到Global-Abort消息，就会进入Abort状态，如果收到Global-commit消息，就会转入COMMIT状态。

从两者的有限状态机可以看出，在所有可能状态中，存在三个阻塞状态：协调者的WAIT状态，参与者的INIT状态和READY状态。

二. 三阶段提交协议(3PC)

3PC就是在2PC基础上将2PC的提交阶段细分位两个阶段：预提交阶段和提交阶段。

3PC中协调者的有限状态机如下图：

3PC中参与者的有限状态机如下图：

三. 向量时钟

通过向量空间祖先继承的关系比较, 使数据保持最终一致性,这就是向量时钟的基本定义。

下面给出一个场景来说明向量时钟的作用：

Vector Clock就是为了解决这种问题而设计的，简单来说，就是为每个商议结果加上一个时间戳，当结果改变时，更新时间戳。所以加上时间戳之后，我们再一次描述上面的场景，如下：

以上这个决策用到了向量时钟，有个图还比较清晰了说明整个过程：

四. NWR协议

NWR是一种在分布式存储系统中用于控制一致性级别的一种策略。在Amazon的Dynamo云存储系统中，就应用NWR来控制一致性。

让我们先来看看这三个字母的含义：

N：在分布式存储系统中，有多少份备份数据

W：代表一次成功的更新操作要求至少有w份数据写入成功

R： 代表一次成功的读数据操作要求至少有R份数据成功读取

NWR值的不同组合会产生不同的一致性效果，当W+R>N的时候，整个系统对于客户端来讲能保证强一致性。当W+R 以常见的N=3、W=2、R=2为例：

N=3，表示，任何一个对象都必须有三个副本（Replica），W=2表示，对数据的修改操作（Write）只需要在3个Replica中的2个上面完成就返回，R=2表示，从三个对象中要读取到2个数据对象，才能返回。

在分布式系统中，数据的单点是不允许存在的。即线上正常存在的Replica数量是1的情况是非常危险的，因为一旦这个Replica再次错误，就 可能发生数据的永久性错误。假如我们把N设置成为2，那么，只要有一个存储节点发生损坏，就会有单点的存在。所以N必须大于2。N约高，系统的维护和整体 成本就越高。工业界通常把N设置为3。

当W是2、R是2的时候，W+R>N，这种情况对于客户端就是强一致性的。

在上图中，如果R+W>N,则读取操作和写入操作成功的数据一定会有交集（如图中的B），这样就可以保证一定能够读取到最新版本的更新数据，数据的强一致性得到了保证。在满足数据一致性协议的前提下，R或者W设置的越大，则系统延迟越大，因为这取决于最慢的那份备份数据的响应时间。而如果R+W<=N，则无法保证数据的强一致性，因为成功写和成功读集合可能不存在交集，这样读操作无法读取到最新的更新数值，也就无法保证数据的强一致性。

在具体实现系统时，仅仅依靠NWR协议还不能完成一致性保证，因为在上述过程中，当读取到多个备份数据时，需要判断哪些数据是最新的，如何判断数据的新旧？这需要向量时钟来配合，所以对于Dynamo来说，是通过NWR协议结合向量时钟来共同完成一致性保证的。

五. paxos协议

Paxos协议的基础比较难以理解，这里就不枯燥无味的介绍paxos协议的理论基础，这方面的资料也是非常多的。估计大家也不希望看到很多理论，公式很多。这里给出几个参考资料供阅读：

1.  架构师需要了解的Paxos原理，历程及实践：http://chuansong.me/n/2189245

2.  微信自研生产级Paxos类库Phxpaxos实现原理介绍：http://mp.weixin.qq.com/s?__biz=MzI4NDMyNTU2Mw==&mid=2247483695&idx=1&sn=91ea422913fc62579e020e941d1d059e#rd  

3.  数据一致性与Paxos算法(上，中，下三篇文章): http://blog.csdn.net/yinwenjie/article/details/60584554

六. Raft协议

1.  Raft协议的动画： http://thesecretlivesofdata.com/raft/

2.  https://raft.github.io/

参考资料：

1. Vector Clock. http://en.wikipedia.org/wiki/Vector_clock
2. Leslie Lamport. Paxos Made Simple. ACM SIGACT News
3. The chubby lock service for loosely-coupled distributed systems.pdf
4. Diego Ongaro and John Ousterhout. In Search of an Understandable Consensus Algorithm
5. http://www.cnblogs.com/yanghuahui/p/3767365.html
6. other resources