分布式理论与设计 三、分布式一致性协议

1.两阶段提交协议（2PC）

1）两阶段提交协议

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

分布式事务：事务提供一种操作本地数据库的不可分割的一系列操作“要么什么都不做，要么做全套（All or Nothing）”的机制，而分布式事务就是为了操作不同数据库的不可分割的一些列操作“要么什么都不做，要么做全套（All or Nothing）”的机制

2）2PC执行流程

(1)成功执行事务事务提交流程

阶段一：

• 事务询问
  • 协调者向所有的参与者发送事务内容，询问是否可以执行事务提交操作，并开始等待各参与者的响应
• 执行事务（写本地的Undo/Redo日志）
• 各参与者向协调者反馈事务询问的响应

阶段二：

• 发送提交请求
  • 协调者向所有参与者发出commit请求
• 事务提交
  • 参与者收到commit请求后，会正式执行事务提交操作，并在完成提交之后释放整个事务执行期间占用的事务资源
• 反馈事务提交结果
  • 参与者在完成事务提交之后，向协调者发送Ack信息
• 完成事务
  • 协调者接受到所有参与者反馈的Ack信息后，完成事务

(2)中断事务流程

假如任何一个参与者向协调者反馈了No响应，或者在等待超时之后，协调者尚无法接收到所有参与者的反馈响应，那么就会中断事务

第一阶段：

• 事务询问
  • 协调者向所有的参与者发送事务内容，询问是否可以执行事务提交操作，并开始等待各参与者的响应
• 执行事务（写本地的Undo/Redo日志）
• 各参与者向协调者反馈事务询问的响应

第二阶段：

• 发送回滚请求
  • 协调者向所有参与者发出Rollback请求
• 事务回滚
  • 参与者接收到Rollback请求后，会利用其在阶段一中记录的Undo信息来执行事务回滚操作，并在完成回滚之后释放在整个事务执行期间占用的资源
• 反馈事务回滚结果
  • 参与者在完成事务回滚之后，向协调者发送Ack信息
• 中断事务
  • 协调者接收到所有参与者反馈的Ack信息后，完成事务中断

3）2PC优点和缺点

优点：原理简单

缺点：

• 同步阻塞
  • 在二阶段提交的执行过程中，所有参与该事务操作的逻辑都处于阻塞状态，即当参与者占有公共资源时，其他节点访问公共资源会处于阻塞状态
• 单点问题
  • 若协调器出现问题，那么整个二阶段提交流程将无法运转，若协调者是在阶段二中出现问题时，那么其他参与者将会一直处于锁定事务资源的状态中，而无法继续完成事务操作
• 数据不一致
  • 在阶段二中，执行事务提交的时候，当协调者向所有的参与者发送Commit请求之后，发生了局部网络异常或者是协调者在尚未发送完Commit请求之前发生了崩溃，导致最总只有部分参与者收到了Commit请求，于是会出现数据不一致的现象
• 太过保守
  • 在进行事务提交询问的过程中，参与者出现故障而导致协调者始终无法获取到所有参与者的响应信息的话，此时协调者只能依靠自身的超时机制来判断是否需要中断事务，这样的策略过于保守，即没有完善的容错机制，任意一个节点的失败都会导致整个事务的失败

2.三阶段提交协议（3PC）

三阶段提交协议出现背景：一致性协议中设计出了二阶段提交协议（2PC），但是2PC设计中还存在缺陷，于是就有了三阶段提交协议，这便是3PC的诞生背景。

1）三阶段提交协议

3PC，全称“three phase commit”，是2PC的改进版，将2PC的“提交事务请求“过程一分为二，共形成了由CanCommit、PreCommit和doCommit三个阶段组成的事务处理协议

三阶段提交升级点（基于二阶段）：

• 三阶段提交协议引入了超时机制
• 在第一阶段和第二阶段中，引入了一个准备阶段。保证了在最后提交阶段之前参与节点的状态是一致的

简单讲：就是除了引入超时机制之外，3PC把2PC的准备阶段再次一分为二，这样三阶段提交就有CanCommit、PreCommit、DoCommit三个阶段

2）三个阶段详解

(1)第一阶段（CanCommit阶段）

类似于2PC的准备（第一）阶段。协调者向参与者发送commit请求，参与者如果可以提交就返回Yes响应，否则返回No响应。

• 事务询问：
  • 协调者向参与者发送CanCommit请求。询问是否可以执行事务提交操作。然后开始等待参与者的响应
• 响应反馈：
  • 参与者接到CanCommit请求之后，正常情况下，如果其自身认为可以顺序执行事务，则返回Yes响应，并进入预备状态。否则，反馈No

(2)第二阶段（PreCommit阶段）

协调者根据参与者的反映情况来决定是否可以执行事务的PreCommit操作。根据响应情况，有以下两种可能：

1. Yes
   1. 发送预提交请求：协调者向参与者发送PreCommit请求，并进入Prepared阶段
   2. 事务预提交：参与者接收到PreCommit请求后，会执行事务操作，并将undo和redo信息记录到事务日志中
   3. 响应反馈：如果参与者成功的执行了事务操作，则返回ACK响应，同时开始等待最终指令
2. No
   1. 假如有任何一个参与者向协调者发送了No响应，或者等待超时之后，协调者都没有接收到参与者的响应，那么就执行事务的中断。则有：
      1. 发送中断请求：协调者向所有参与者发送abort请求
      2. 中断事务：参与者收到来自协调者的abort请求之后（或超时之后，仍未收到协调者的请求），执行事务的中断

(3)第三阶段（doCommit阶段）

该阶段进行真正的事务提交，也可以分为执行提交和中断事务两种情况。

• 执行成功
  • 发送提交请求：协调者接收到参与者发送的ACK响应，那么它将从预提交状态进入到提交状态。并向所有参与者发送doCommit请求
  • 事务提交：参与者接收到doCommit请求之后，执行正式的事务提交。并在完成事务提交之后释放所有事务资源
  • 响应反馈：事务提交完之后，向协调者发送ACK响应
  • 完成事务：协调者接收到所有参与者的ACK响应之后，完成事务
• 中断事务
  • 发送中断请求：协调者向所有参与者发送abort请求
  • 事务回滚：参与者接收到abort请求之后，利用其在阶段二记录的undo信息来执行事务的回滚操作，并在完成回滚之后释放所有的事务资源
  • 反馈结果：参与者完成事务回滚之后，向协调者发送ACK消息
  • 中断事务：协调者接收到所有参与者反馈的ACK消息之后，执行事务的中断

(4)注意：一旦进入阶段三，可能出现两种故障

• 协调者出现问题
• 协调者和参与者之间的网络故障

如果出现任意一种情况，最终都会导致参与者无法收到doCommit请求或者abort请求，针对这种情况，参与者都会在等待超时之后，继续进行事务提交

3）2PC对比3PC

1. 首先对于协调者和参与者都设置了超时机制（在2PC中，只有协调者拥有超时机制，即如果在一定时间内没有收到参与者的消息则默认失败），主要是避免了参与者在长时间无法与协调者节点通讯（协调者挂到了）的情况下，无法释放资源的问题，因为参与者自身拥有超时机制在超时后，自动进行本地commit从而进行释放资源。而这种机制也侧面降低了整个事务的阻塞时间和范围
2. 通过CanCommit、PreCommit、DoCommit三个阶段的设计，相较于2PC而言，多设置了一个缓冲阶段保证了在最后提交之前个参与节点的状态是一致的
3. PreCommit是一个缓冲，保证了在最后提交阶段之前个参与节点的状态是一致的

问题：3PC协议并没有完全解决数据一致问题

3.NWR协议

1）什么是NWR协议

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

• N：在分布式存储系统中，有多少份备份数据
• W：代表一次成功的更新操作要求至少有W份数据写入成功
• R：代表一次成功的读数据操作要求至少有R份数据成功读取

2）原理

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

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

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

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

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

2. 当R+W<=N，无法保证数据的强一致性

因为成功写和成功读集合可能不存在交集，这样读操作无法读取到最新的更新数值，也就无法保证数据的强一致性

4.Gossip协议

1）什么是Gossip协议

Gossip协议也叫Epidemic协议（流行病协议）。原本用于分布式数据库中节点同步数据使用，后被广泛用于数据库复制、信息扩散、集群成员身份确认、故障探测等。
从gossip单词就可以看到，其中文意思是八卦、流言等意思，我们可以想象下绯闻的传播（或者流行病的传播）；gossip协议的工作原理就类似于这个。gossip协议利用一种随机的方式将信息传播到整个网络中，并在一定时间内使得系统内的所有节点数据一致。Gossip其实是一种去中心化思路的分布式协议，解决状态在集群中的传播和状态一致性的保证两个问题。

2）Gossip原理

Gossip协议的消息传播方式有两种：反熵传播和谣言传播

(1)反熵传播

是以固定的概率传播所有的数据。所有参与节点只有两种状态：Suspective(病原)、Infective(感染。过程是种子节点会把所有的数据都跟其他节点共享，以便消除节点之间数据的任何不一致，它可以保证最终、完全的一直。缺点是消息数量非常庞大，且无限制；通常只用于新加入节点的数据初始化。

(2)谣言传播

是以固定的概率仅传播新到达的数据。所有参与节点有三种状态：Suspective(病原)、Infective(感染)、Removed(愈除)。过程是消息只包含最新update，谣言消息在某个时间点之后会被标记为removed，并且不再被传播。缺点是系统有一定的概率会不一致，通常用于节点间数据增量同步。

3）通信方式

Gossip协议最终目的是将数据分发到网络中的每一个节点。根据不同的具体应用场景，网络中两个节点之间存在三种通信方式：推送模式、拉取模式、推/拉模式

1.Push
节点A将数据（key, value, version)及对应的版本号推送给B节点，B节点更新A中币自己新的数据

2.Pull
A仅将数据 key，version 推送给B，B将本地比A新的数据 (key, value, version)推送给A，A更新本地

3.Push/Pull
与Pull类似，只是多了一步，A再将本地比B新的数据推送给B，B则更新本地

4）优缺点

综上所述，我们可以得出Gossip是一种去中心化的分布式协议，数据通过节点像病毒一样逐个传播。因为是指数级传播，整体传播速度非常快。

• 优点
  • 扩展性：允许节点的任意增加和减少，新增节点的状态最终会与其他节点一致
  • 容错：任意节点的宕机和重启都不会影响Gossip消息的传播，具有天然的分布式系统容错特性
  • 去中心化：无需中心节点，所有节点都是对等的，任意节点无需知道整个网络状况，只要网络连通，任意节点可把消息散播到全网
  • 最终一致性：Gossip协议实现信息指数级的快速传播，因此在有新信息需要传播时，消息可以快速地发送到全局节点，在有限的时间内能够做到所有节点都拥有最新的数据
• 缺点
  • 消息延迟：节点随机向少数几个节点发送消息，消息最终是通过多个轮次的散播而到达全网；不可避免的造成消息延迟。
  • 消息冗余：节点定期随机选择周围节点发送消息，而收到消息的节点也会重复步骤；不可避免的引起同一节点消息多次接收，增加消息处理压力

Gossip协议由于以上的优缺点，所以适合于AP场景的数据一致性处理，场景应用有P2P网络通信、Redis Cluster、Consul

5.Paxos协议

1）什么是Paxos

Paxos协议其实说的就是Paxos算法，Paxos算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。

2）Paxos解决了什么问题

在常见的分布式系统中，总会发生注入机器宕机或网络异常（包括消息的延迟、丢失、重复、乱序、还有网络分区）等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

注：这里某个数据的值并不只是狭义上的某个数，它可以是一条日志，也可以是一条命令（command）。根据应用场景不同，某个数据的值有不同的含义。

Paxos的版本有：Basic Paxos，Multi Paxos，Fast-Paxos，具体落地有Raft和zk的ZAB协议

3）Basic Paxos相关概念

(1) 角色介绍

• Client：客户端
  • 客户端向分布式系统发出请求，并等待响应。例如，对分布式文件 服务器中文件的写请求
• Proposer：提案发起者
  • 提案者提倡客户端请求，试图说服Acceptor对此达成一致，并在发生冲突时充当协调者以推动协议向前发展
• Acceptor：决策者，可以批准提案
  • Acceptor可以接受（accept）提案；并进行投票，投票结果是否通过以多数派为准，以如果某个提案被选定，那么该提案里的value就被选定了。
• Learner：最终决策的学习者
  • 学习者充当该协议的复制因素（不参与投票）

(2)决策模型

(3)Basic paxos 流程

basic paxos流程一共分为4个步骤：

• Prepare
  • Proposer提出一个提案，编号为N，此N大于这个Proposer之前提出的所有提出的编号，请求Acceptor的多数人接受这个提案
• Promise
  • 如果编号N大于此Acceptor之前接收的提案编号则接收，否则拒绝
• Accept
  • 如果达到多数派，Proposer会发出accept请求，此请求包含提案编号和对应的内容
• Accepted
  • 如果此Acceptor在此期间没有接受到任何大于N的提案，则接收此提案内容，否则忽略

4）Basic Paxos流程图

(1)无故障的Basic Paxos

(2)Acceptor失败时的basic Paxos

在下图中，多数派中的一个Acceptor发生故障，因此多数派大小变为2。在这种情况下，Basic Paxos协议仍然成功。

(3)Proposer失败时的basic Paxos

Proposer在提出提案之后但在达成协议之前失败。具体来说，传递到Acceptor的时候失败了，这个时候需要选出新的Proposer（提案人），那么Basic Paxos协议仍然成功。

(4)当多个提议者发生冲突时的basic Paxos

最复杂的情况是多个Proposer都进行提案，导致Paxos的活锁问题

针对活锁问题解决起来非常简单：只需要在每个Proposer在去提案的时候随机加上一个等待时间即可

5）Multi-Paxos流程图

针对basic Paxos是存在一定的问题，首先就是流程复杂，实现及其困难，其次效率低（达成一致性需要2轮RPC调用），针对basic Paxos流程进行拆分为选举和复制的过程。

(1)第一次流程-确定Leader

(2)第二次流程-直接由Leader确认

6）Multi-Paxos角色重叠流程图

Multi-Paxos在实施的时候会将Proposer，Acceptor和Learner的角色合并统称为“服务器”。因此，最后只有“客户端”和“服务器”

6.Raft协议

1）什么是Raft协议

Paxos是论证了一致性协议的可行性，但是论证的过程晦涩难懂，缺少必要的实现细节，而且工程实现难度比较高，广为人知实现只有zk的实现zab协议。
Paxos协议的出现为分布式强一致性提供了很好的理论基础，但是Paxos协议理解起来较为困难，实现比较复杂

此时出现了一个易理解的分布式一致性复制协议Raft。Java，C++，Go等都有其对应的实现，之后出现的Raft相对要简洁很多。引入主节点，通过竞选确定主节点。节点类型：Follower、Candidate和Leader。
Leader会周期性的发送心跳包给Follower。每个Follower都设置了一个随机的竞选超时时间，一般为150ms~300ms，如果在这个时间内没有收到Leader的心跳包，就会编程Candidate，进入竞选阶段，通过精选阶段的投票多的人成为Leader。

2）Raft相关概念

1. 节点状态
   1. Leader（主节点）：接受client更新请求，写入本地后，然后同步到其他副本中
   2. Follower（从节点）：从Leader中接受更新请求，然后写入本地日志文件。对客户端提供读请求
   3. Candidate（候选节点）：如果Follower在一段时间内未收到Leader心跳。则判断Leader可能故障，发起选主提议。节点状态从Follower变为Candidate状态，直到选主结束。
2. termId：任期号，时间被划分成一个个任期，每次选举都会产生一个新的termId，一个任期内只有一个leader
3. RequestVote：请求投票，candidate在选举过程中发起，收到多数派响应后，成为leader

3）竞选阶段流程

这个是Raft完整版http://thesecretlivesofdata.com/raft/动画演示
github也提供一个https://raft.github.io/动画演示地址 . 原理都是一样的.

单节点是不存在数据不一致问题的，一个节点就很容易就该值达成一致性
如果是多个节点如何达成一致性.Raft是用于实施分布式数据一致性协议的。

我们使用了3个不同的圆圈表示三种不同的状态

接下来开始完成整个竞选阶段流程：
1）下图表示一个分布式系统的最初阶段，此时只有Follower，没有Leader。Follower A等待一个随机的竞选超时时间之后，没收到Leader发来的心跳包，因此进入竞选阶段。

2）此时A发送投票请求给其它所有节点

3）其他节点会对请求进行恢复，如果超过一半的节点回复了，那么该Candidate就会变成Leader

4）之后Leader会周期性地发送心跳包给Follower，Follower接收到心跳包，会重新开始计时

4）Leader节点宕机

Leader节点B宕机之后，会在剩下的节点中继续去选举新的Leader

5）多个Candidate竞选

1.如果有多个Follower成为Candidate，并且所获得票数相同，那么就需要重新开始投票，例如下图中Candidate B和Candidate D都获得两票，因此需要重新开始投票

2.当重新开始投票时，由于每个节点设置的随机竞选超时时间不同，因此能下一次再次出现多个Candidate并获得同样票数的概率很低

6）日志复制

1.来自客户端的修改都会被传入Leader。注意该修改还未被提交，只是写入日志中

2.Leader会把修改复制到所有Follower

3.Leader会等待大多数的Follower也进行了修改，然后才将修改提交

4.此时，Leader会通知所有的Follower让它们也提交修改，此时所有节点的值达成一致

5.多次日志复制情况

7）网络分区

面对网络分区，Raft甚至可以保持一致
1.最初始正常情况下状态，B节点会对其他4个节点发送心跳

2.当出现网络分区情况，但是出现网络分区的请求后，只能对A发送心跳，同时其他三个节点会再次选出一个Leader节点。

以term大的为准

8）网络分区情况日志复制

网络分区情况日志复制工作也可以完成数据一致性

1. 不同分区写入数据不同

2. 最终E节点TermId最大成为Leader节点，同步节点数据，达成数据一致性

7.Lease机制

1）什么是Lease机制

Lease机制，即租约机制，是一种在分布式系统常用的协议，是维护分布式系统数据一致性的一种常用工具。
Lease机制有以下几个特点：

• Lease是颁发者对一段时间内数据一致性的承诺
• 颁发者发出Lease后，不管是否被接收，只要Lease不过期，颁发者都会按照协议遵守承诺
• Lease的持有者只能在Lease的有效期内使用承诺，一旦Lease超时，持有者需要放弃执行，重新申请Lease

以租车为例：

2）Lease机制解决了什么问题

分布式系统中，如何确认一个节点是否工作正常？如果有5副本1-5,。其中1号为主副本

在分布式中最直观的处理方法是在每个副本与主副本维护一个心跳，期望通过心跳是否存在而判断对方是否依旧存活。
心跳方法其实根本无法解决分布式下节点是否正常的这个问题。考虑如下场景：

1. 在某个时刻Node1主节点突然出现网络抖动或网络中断情况（注意：不是宕机），导致从节点无法接收到心跳

2. 会在剩下的副节点中选取一个当主节点

主要解决思路有四种：

1. 设计能容忍双主的分布式协议
2. Raft协议通过Term版本高的同步低的
3. 用lease机制
4. 涉及去中心化-Gossip协议

3）Lease的原理

1. 引入中心节点负责下发Lease

2. 出现网络问题

在01:05期间如果出现网络抖动导致其他节点申请Lease会申请失败，因为中心节点在01:10之前都会承认有主节点，不允许其他节点再申请Lease

3. 如果网络恢复

4. 如果到01:10时间，主节点会进行续约操作，然后在下发新的Lease

5. 如果主节点宕机，其他节点申请Lease也会失败，承认主节点存在

6. 副节点申请Lease，申请成功，因为Lease过期

4）Lease的容错

• 主节点宕机
  • Lease机制天生即可容忍网络、Lease接收方的出错，时间即Lease剩余过期时长
• 中心节点异常
  • 颁发者宕机可能使得全部节点没有Lease，系统处于不可用状态，解决的方法就是使用一个小集群而不是单一节点作为颁发者
• 时差问题
  • 中心节点与主节点之间的时钟可能也存在误差，只需要中心节点考虑时钟误差即可

Lease时间长短一般取经验值1-10秒即可。太短网络压力太大，太长则收回承诺时间过长影响可用性

5）应用

1. GFS（Google文件系统）中，Master通过Lease机制决定哪个是主副本，Lease在给各节点的心跳响应消息中携带。收不到心跳时，则等待Lease过期，再办法给其它节点
2. chubby中，paxos选主后，从节点会给主办法Lease，再期限内不选其他节点为主。另一方面，主节点给每个client节点发送Lease，用于判断client死活。