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

素颜马尾好姑娘i 2022-07-16 00:16 178阅读 0赞

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

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

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

两阶段提交协议，简称2PC，是比较常用的解决分布式事务问题的方式，要么所有参与进程都提交事务，要么都取消事务，即实现ACID中的原子性(A)的常用手段。  
两阶段提交将提交过程划分为连续的两个阶段：表决阶段(Voting)和提交阶段(Commit)。假设在没有故障发生的情形下，两阶段提交协议由下列操作序列构成，如下图所示：  
[![2PC1][]][2PC1]

协调者的有限状态机如下图：  
[![xietiaoFSM][]][xietiaoFSM]

如上图所示：协调者初始处于INIT状态，当接收到系统发出的Commit消息后，向参与者多播Vote-request消息后转入WAIT状态，在此进入阻塞状态，因为要等待所有参与者发送返回的消息，当收到所有参与者的返回消息后，如果其中包含Vote-Abort消息，则多播Global-abort消息后转入ABORT状态，否则多播Global-commit消息后转入COMMIT状态。  
参与者的有限状态机如下图：  
[![canyuFSM][]][canyuFSM]  
如上图所示：参与者初始处于INIT状态，当接收到Vote-Request消息时，发出Vote-commit会转入READY状态，告诉协调者已经准备做好提交准备，否则就返回一个VOTE-ABORT消息。等待协调者行为，如果收到Global-Abort消息，就会进入Abort状态，如果收到Global-commit消息，就会转入COMMIT状态。  
从两者的有限状态机可以看出，在所有可能状态中，存在三个阻塞状态：协调者的WAIT状态，参与者的INIT状态和READY状态。

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

3PC就是在2PC基础上将2PC的提交阶段细分位两个阶段：预提交阶段和提交阶段。  
3PC中协调者的有限状态机如下图：  
[![xietiaozhe3pc][]][xietiaozhe3pc]  
3PC中参与者的有限状态机如下图：  
[![canyuzhe3pc][]][canyuzhe3pc]

### 三. 向量时钟 ###

通过向量空间祖先继承的关系比较, 使数据保持最终一致性,这就是向量时钟的基本定义。  
下面给出一个场景来说明向量时钟的作用：  
[![QQ20150613\_3][QQ20150613_3]][QQ20150613_3]

Vector Clock就是为了解决这种问题而设计的，简单来说，就是为每个商议结果加上一个时间戳，当结果改变时，更新时间戳。所以加上时间戳之后，我们再一次描述上面的场景，如下：  
[![QQ20150613\_4][QQ20150613_4]][QQ20150613_4]  
以上这个决策用到了向量时钟，有个图还比较清晰了说明整个过程：  
[![QQ20150613\_5][QQ20150613_5]][QQ20150613_5]

### 四. 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，这种情况对于客户端就是强一致性的。  
[![NWR][]][NWR]  
在上图中，如果R+W>N,则读取操作和写入操作成功的数据一定会有交集（如图中的B），这样就可以保证一定能够读取到最新版本的更新数据，数据的强一致性得到了保证。在满足数据一致性协议的前提下，R或者W设置的越大，则系统延迟越大，因为这取决于最慢的那份备份数据的响应时间。而如果R+W<=N，则无法保证数据的强一致性，因为成功写和成功读集合可能不存在交集，这样读操作无法读取到最新的更新数值，也就无法保证数据的强一致性。  
在具体实现系统时，仅仅依靠NWR协议还不能完成一致性保证，因为在上述过程中，当读取到多个备份数据时，需要判断哪些数据是最新的，如何判断数据的新旧？这需要向量时钟来配合，所以对于Dynamo来说，是通过NWR协议结合向量时钟来共同完成一致性保证的。

### 五. paxos协议 ###

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

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

2.  微信自研生产级Paxos类库Phxpaxos实现原理介绍：[http://mp.weixin.qq.com/s?\_\_biz=MzI4NDMyNTU2Mw==&mid=2247483695&idx=1&sn=91ea422913fc62579e020e941d1d059e\#rd  ][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][http_blog.csdn.net_yinwenjie_article_details_60584554]

### 六. Raft协议 ###

1.  Raft协议的动画： [http://thesecretlivesofdata.com/raft/][http_thesecretlivesofdata.com_raft]

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

### 参考资料： ###

1.  Vector Clock. [http://en.wikipedia.org/wiki/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][http_www.cnblogs.com_yanghuahui_p_3767365.html]
6.  other resources

[2PC1]: /images/20220716/8367e40a0c054f3f818d0fc08eaca896.png
[xietiaoFSM]: /images/20220716/a4285496d73c4d60b8a854bdfb9df81e.png
[canyuFSM]: /images/20220716/e8386c8b07c840c49ec0da12b466360d.png
[xietiaozhe3pc]: /images/20220716/7c43c82702164c84818b516f3c222dbf.png
[canyuzhe3pc]: /images/20220716/20c98e4bca25476b852784f604c17277.png
[QQ20150613_3]: /images/20220716/6c18a6b73d4d47e6b92224501afa9df2.png
[QQ20150613_4]: /images/20220716/a6861e51624944c7851e23775e264fc2.png
[QQ20150613_5]: /images/20220716/a5d4908dcef5435981bf044615f53c5c.png
[NWR]: /images/20220716/4d793a3f83714df88546748c85da5cc0.png
[http_chuansong.me_n_2189245]: http://chuansong.me/n/2189245
[http_mp.weixin.qq.com_s_biz_MzI4NDMyNTU2Mw_mid_2247483695_idx_1_sn_91ea422913fc62579e020e941d1d059e_rd]: http://mp.weixin.qq.com/s?__biz=MzI4NDMyNTU2Mw==&mid=2247483695&idx=1&sn=91ea422913fc62579e020e941d1d059e#rd
[http_blog.csdn.net_yinwenjie_article_details_60584554]: http://blog.csdn.net/yinwenjie/article/details/60584554
[http_thesecretlivesofdata.com_raft]: http://thesecretlivesofdata.com/raft/
[http_en.wikipedia.org_wiki_Vector_clock]: http://en.wikipedia.org/wiki/Vector_clock
[http_www.cnblogs.com_yanghuahui_p_3767365.html]: http://www.cnblogs.com/yanghuahui/p/3767365.html