Zookeeper分布式一致性原理（二）：一致性协议

心已赠人 2022-04-22 15:16 351阅读 0赞

为了解决分布式一致性问题，在长期的研究过程中，提出了一大批经典的一致性协议和算法，其中最著名的就是2PC和3PC以及Paxos算法了。

# 1. 2PC和3PC #

在分布式系统中，每个节点都明确知道自己事务操作的成功或失败，但无法获取其他分布式节点的操作结果。因此当一个事务需要跨节点进行事务操作时，需要引入协调者（Coordinator）组件来统一调度所有分布式节点的执行逻辑，这些被调度的节点称为参与者（Participant）。

协调者负责调度参与者的行为，最终决定这些参与者是否提交事务。基于这个思想衍生出二阶段提交和三阶段提交两种协议。

## 1.1 2PC ##

### 前提 ###

二阶段提交算法的成立基于以下假设：

>  *  1/ 该分布式系统中，存在一个节点作为协调者(Coordinator)，其他节点作为参与者(Cohorts)。且节点之间可以进行网络通信。
>  *  2/ 所有节点都采用预写式日志，且日志被写入后即被保持在可靠的存储设备上，即使节点损坏不会导致日志数据的消失。
>  *  3/ 所有节点不会永久性损坏，即使损坏后仍然可以恢复。

二阶段提交协议主要分为来个阶段：准备阶段和提交阶段。

**第一阶段(提交请求阶段)**

*  协调者节点向所有参与者节点询问是否可以执行提交操作，并开始等待各参与者节点的响应。
 *  参与者节点执行询问发起为止的所有事务操作，并将Undo信息和Redo信息写入日志。
 *  各参与者节点响应协调者节点发起的询问。如果参与者节点的事务操作实际执行成功，则它返回一个"同意"消息；如果参与者节点的事务操作实际执行失败，则它返回一个"中止"消息。

有时候，第一阶段也被称作投票阶段，即各参与者投票是否要继续接下来的提交操作。

**第二阶段(提交执行阶段)**

**成功**

当协调者节点从所有参与者节点获得的相应消息都为"同意"时：

*  1.协调者节点向所有参与者节点发出"正式提交"的请求。
 *  2.参与者节点正式完成操作，并释放在整个事务期间内占用的资源。
 *  3.参与者节点向协调者节点发送"ACK"消息。
 *  4.协调者节点收到所有参与者节点反馈的"ACK"消息后，完成事务。

**失败**

如果任一参与者节点在第一阶段返回的响应消息为"Abort"，或者 协调者节点在第一阶段的询问超时之前无法获取所有参与者节点的响应消息时：

*  1.协调者节点向所有参与者节点发出"RollBack"的请求。
 *  2.参与者节点利用之前写入的Undo信息执行回滚，并释放在整个事务期间内占用的资源。
 *  3.参与者节点向协调者节点发送"回滚完成"消息。
 *  4.协调者节点收到所有参与者节点反馈的"回滚完成"消息后，取消事务。

有时候，第二阶段也被称作完成阶段，因为无论结果怎样，协调者都必须在此阶段结束当前事务。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70]

**优缺点**

优点：原理简单，实现方便。

### 缺点 ###

1.  同步阻塞问题。执行过程中，所有参与节点都是事务阻塞型的。当参与者占有公共资源时，其他第三方节点访问公共资源不得不处于阻塞状态。
2.  单点故障。由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。（如果是协调者挂掉，可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题）
3.  数据不一致。在二阶段提交的阶段二中，当协调者向参与者发送commit请求之后，发生了局部网络异常或者在发送commit请求过程中协调者发生了故障，这回导致只有一部分参与者接受到了commit请求。而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据部一致性的现象。
4.  二阶段无法解决的问题：协调者再发出commit消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。

## 1.2 3PC ##

3PC，Three-Phase Commit，三阶段提交协议，由CanCommit、PreCommit、Do Commit三阶段组成。

### 阶段一：Can Commit ###

1.  事务询问。协调者向参与者发送一个包含事务内容的canCommit请求，询问是否可以执行事务提交操作，并开始等待参与者相应。
2.  参与者向协调者反馈事务询问的相应。

Can Commit阶段和2PC的提交请求阶段一样。

### 阶段二：PreCommit ###

**执行事务PreCommit**

假如协调者获取的所有相应都是YES则执行事务预提交。

1.  发送预提交请求。
2.  事务预提交，执行事务操作，并将Undo和Redo信息记录到事务日志中
3.  各参与中向协调者反馈事务执行结果的相应。

**中断事务**

假如协调者获取的相应存在NO，或者等待超时，则中断事务。

1.  发送中断请求
2.  中断事务

### 阶段三：doCommit ###

真正的事务提交，存在两种结果：

**执行提交**

1.  发送提交请求 协调者由预提交转换到提交状态，向所有参与者发送doCommit请求
2.  事务提交 参与者收到doCommit请求后，执行事务提交
3.  反馈事务提交结果 参与者完成事务提交后，向协调者发送ACK消息
4.  完成事务 协调者接收到所有参与者反馈的ACK消息后，完成事务

**中断事务**

1.  发送中断请求
2.  事务回滚
3.  反馈事务回滚结果
4.  中断事务

进入阶段三也存在两种故障：

> 1.  协调者出现问题
> 2.  协调者和参与者网络出现问题。

无论出现那种情况，最终都会导参与者无法及时接收到来自接收到协调者的doCommit请求或者是abort请求，针对这样的异常，参与者都会在等待超时之后，继续进行事务提交。

### 算法示意 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 1]

### 优缺点 ###

优点：降低参与者阻塞范围，并能够在出现单点故障后继续达成一致

缺点：引入preCommit阶段，在这个阶段如果出现网络分区，协调者无法与参与者正常通信，参与者依然会进行事务提交，造成数据不一致。

> 3PC解决了参与者的阻塞范围，并且解决了协调者单点故障的问题。但是3PC还是存在问题：3PC无法解决当存在网络分区的时候，参与者无法通信的问题，在这种情况下，参与者只有一部分参与者能够执行提交请求，造成参与者数据不一致。

**论是二阶段提交还是三阶段提交都无法彻底解决分布式的一致性问题。**

# 2. Paxos算法（解决了单点故障问题） #

## 2.1 Paxos原理 ##

Paxos算法是Lesile Lamport提出的一种基于消息传递且具有高度容错特性的一致性算法。分布式系统中的节点通信存在两种模型: 共享内存和消息传递。基于消息传递通信模型的分布式系统，不可避免会发生进程变慢被杀死，消息延迟、丢失、重复等问题，Paxos算法就是在存在以上异常的情况下仍能保持一致性的协议。

Paxos算法使用一个希腊故事来描述，在Paxos中，存在三种角色，分别为Propose(提议者，用来发出提案proposal), Acceptor（接受者，可以接受或拒绝提案), Learner(学习者，学习被选定的提案，当提案被超过半数的Acceptor接受后为被批准)。下面更精确的定义Paxos要解决的问题：

*  1.  决议(value)只有在被proposer提出后才能被批准
 *  1.  在一次Paxos算法的执行实例中，只批准(chose)一个value
 *  1.  learner只能获得被批准(chosen)的value。

一般的Paxos说明都会采用不断加强条件的方式来最终达成一致性条件，这样的方式看上去不太容易理解，容易让人以为是一步一步推出来的，实际上更像一致性的一种充分不必要条件。

## 2.2 Paxos算法过程 ##

首先有一个递增的编号生成器，可以保证生成的需要递增，用来为Proposer生成提议的编号。

### 第一阶段 准备阶段（Prepare请求） ###

1.  Proposer生成编号n并使用v作为value的提案(n, v)发送prepare请求给Acceptor中的大多数。
2.  Acceptor收到prepare请求后，如果提案的编号大于它已经回复的所有prepare消息，则Acceptor将上次接收的提案和已接收的value回复给Proposer，并承若不再回复编号小于n的提案。如果Acceptor没有接收过prepare请求或收到的prepare请求的编号都比n小则回复该prepare请求。

### 第二阶段 批准阶段（Accept请求） ###

1.  当一个Proposer收到了来自半数以上的Acceptor对prepare的回复后，就进入批准阶段。那么Proposer就会发生一个针对\[Mn,Vn\]提案的Accpet请求给所有的Acceptor。注意Vn的值就收到的响应中编号最大的提案的值。
2.  在不违背自己向其他Proposer的承诺的前提下，Acceptor收到accept请求后接收这个请求。只要该Acceptor尚未对编号大于Mn的Prepare请求做出响应，它就可以通过这个提案。

基于消息传递且具有高度容错性的一致性算法。Paxos算法要解决的问题就是如何在可能发生几起宕机或网络异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

### 第三阶段 提案的获取 ###

Learner获取提案分为以下几个方案：

*  Learner获取一个已经被选定的提案的前提是，该提案已经被半数以上的Acceptor批准，因此，最简单的做法就是一旦Acceptor批准了一个提案，就将该提案发送给所有的Learner。 优点：快速选定提案 缺点：内个Acceptor与所有的Learner逐个通信，通信次数过多。
 *  所有的Acceptor将他们对提案的批准都统一发给特定的主Learner，不考虑拜占庭将军问题前提下，当一个议案被选中后，主Learner负责通知其他Learner。优点：通信次数较少。缺点：主Learner可能会故障。
 *  结合方案二，我们将主Learner作为一个集合来处理，则解决上述两个问题。

### 通过选取主Proposer保证算法的活性 ###

Proposer P1提出了M1提案，完成了阶段一，P2同时提出M2提案完成阶段一，于是Acceptor不再批准M2的提案。当P1进入第二阶段时，会被忽略，于是p1再次进入第一阶段，获取M3 , M3大于M2，由导致P2在第二阶段忽略，由此进入死循环。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 2]

为了解决以上问题，选取一个主Proposer，并规定，只有主Proposer才能提出议案。这样子，只要主Proposer和过半的Acceptor正常通信，凡是主Proposer提出一个编号更改的提案，该提案会被批准，当发现有更大的提案时，则丢弃当前的较小提案。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70]: /images/20220327/c469e8dac4be4d9ca59b6afc246f1fa9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 1]: /images/20220327/3120ba1eb9c74be7a02d1f1aead747de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 2]: /images/20220327/a82727d9513f485184c8c8222d8a18a7.png