分布式一致性协议

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

1.1 概念

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

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

1.2 2pc执行流程

成功执行事务流程
阶段一：
- 事务询问
- 协调者向所有的参与者发送事务内容，询问是否可以执行事务提交操作，并开始等待各参与者的响应。
- 执行事务 (写本地的Undo/Redo日志)
- 各参与者向协调者反馈事务询问的响应
阶段二：
- 发送提交请求：
- 协调者向所有参与者发出 commit 请求。
- 事务提交：参与者收到 commit 请求后，会正式执行事务提交操作，并在完成提交之后释放整个事务执行期间占用的事务资源。
- 反馈事务提交结果：参与者在完成事务提交之后，向协调者发送 Ack 信息。
- 完成事务：协调者接收到所有参与者反馈的 Ack 信息后，完成事务。
中断事务流程

假如任何一个参与者向协调者反馈了No响应，或者在等待超时之后，协调者尚无法接收到所有参与者的反馈响应，那么就会中断事务
阶段一:
- 事务询问协调者向所有的参与者发送事务内容，询问是否可以执行事务提交操作，并开始等待各参与者的响应。
- 执行事务 (写本地的Undo/Redo日志)
- 各参与者向协调者反馈事务询问的响应
阶段二:
- 发送回滚请求：协调者向所有参与者发出 Rollback 请求。
- 事务回滚：参与者接收到 Rollback 请求后，会利用其在阶段一中记录的 Undo 信息来执行事务回滚操作，并在完成回滚之后释放在整个事务执行期间占用的资源。
- 反馈事务回滚结果：参与者在完成事务回滚之后，向协调者发送 Ack 信息。
- 中断事务：协调者接收到所有参与者反馈的 Ack 信息后，完成事务中断。

1.3 2pc优点缺点

优点

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

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

三阶段提交协议出现背景：一致性协议中设计出了二阶段

2.1 概念

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

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

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

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

2.2 三阶段详解

第一阶段（CanCommit 阶段）

类似于2PC的准备（第一）阶段。协调者向参与者发送commit请求，参与者如果可以提交就返回Yes响应，否则返回No响应。
- 事务询问：协调者向参与者发送CanCommit请求。询问是否可以执行事务提交操作。然后开始等待参与者的响应。
- 响应反馈：参与者接到CanCommit请求之后，正常情况下，如果其自身认为可以顺利执行事务，则返回Yes响应，并进入预备状态。否则反馈No
第二阶段（PreCommit 阶段)

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

该阶段进行真正的事务提交，也可以分为执行提交和中断事务两种情况
执行成功
- 发送提交请求: 协调者接收到参与者发送的ACK响应，那么它将从预提交状态进入到提交状态。并向所有参与者发送doCommit请求。
- 事务提交: 参与者接收到doCommit请求之后，执行正式的事务提交。并在完成事务提交之后释放所有事务资源。
- 响应反馈: 事务提交完之后，向协调者发送ACK响应。
- 完成事务: 协调者接收到所有参与者的ACK响应之后，完成事务。
中断事务
- 发送中断请求: 协调者向所有参与者发送abort请求
- 事务回滚: 参与者接收到abort请求之后，利用其在阶段二记录的undo信息来执行事务的回滚操作，并在完成回滚之后释放所有的事务资源。
- 反馈结果: 参与者完成事务回滚之后，向协调者发送ACK消息
- 中断事务: 协调者接收到所有参与者反馈的ACK消息之后，执行事务的中断
注意：一旦进入阶段三，可能会出现 2 种故障：
- 协调者出现问题
- 协调者和参与者之间的网络故障
如果出现了任一一种情况，最终都会导致参与者无法收到 doCommit 请求或者 abort 请求，针对这种情况，参与者都会在等待超时之后，继续进行事务提交

2.3 2pc对比3pc

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

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

3.NWR协议

3.1 概念

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

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

3.2 原理

NWR值的不同组合会产生不同的一致性效果，当W+R>N的时候，整个系统对于客户端来讲能保证强一致性

以常见的N=3、W=2、R=2为例:

N=3，表示，任何一个对象都必须有三个副本

W=2表示，对数据的修改操作只需要在3个副本中的2个上面完成就返回

R=2表示，从三个对象中要读取到2个数据对象，才能返回

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

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

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

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

4.Gossip协议

4.1 概念

Gossip 协议也叫 Epidemic 协议（流行病协议）。原本用于分布式数据库中节点同步数据使用，后被广泛用于数据库复制、信息扩散、集群成员身份确认、故障探测等。

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

4.2 原理

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

反熵传播

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

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

4.3 通信方式

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

push

节点 A 将数据 (key,value,version) 及对应的版本号推送给 B 节点，B 节点更新 A 中比自己新的数据
pull

A 仅将数据 key, version 推送给 B，B 将本地比 A 新的数据（Key, value, version）推送给 A，A 更新本地
Pull/push

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

4.4 优缺点

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

优点

扩展性：允许节点的任意增加和减少，新增节点的状态最终会与其他节点一致

容错：任意节点的宕机和重启都不会影响 Gossip 消息的传播，具有天然的分布式系统容错特性

去中心化：无需中心节点，所有节点都是对等的，任意节点无需知道整个网络状况，只要网络连通，任意节点可把消息散播到全网

最终一致性：Gossip 协议实现信息指数级的快速传播，因此在有新信息需要传播时，消息可以快速地发送到全局节点，在有限的时间内能够做到所有节点都拥有最新的数据。

缺点

消息延迟:节点随机向少数几个节点发送消息，消息最终是通过多个轮次的散播而到达全网；不可避免的造成消息延迟。

消息冗余:节点定期随机选择周围节点发送消息，而收到消息的节点也会重复该步骤；不可避免的引起同一节点消息多次接收，增加消息处理压力

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

5.Paxos协议

5.1概念

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

Paxos由莱斯利·兰伯特(Leslie Lamport)于1998年在《The Part-Time Parliament》论文中首次公开，最初的描述使用希腊的一个小岛Paxos，描述了Paxos小岛中通过决议的流程，并以此命名这个算法，但是这个描述理解起来比较有挑战性。后来在2001年，莱斯利·兰伯特重新发表了朴实的算法描述版本《Paxos Made Simple》

自Paxos问世以来就持续垄断了分布式一致性算法，Paxos这个名词几乎等同于分布式一致性。 Google的很多大型分布式系统都采用了Paxos算法来解决分布式一致性问题，如Chubby、Megastore以及Spanner等。开源的ZooKeeper，以及MySQL 5.7推出的用来取代传统的主从复制的MySQL Group Replication等纷纷采用Paxos算法解决分布式一致性问题。然而，Paxos的最大特点就是难，不仅难以理解，更难以实现。

Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法，那就是Paxos，其它的算法都是残次品。

5.2 解决了什么问题

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

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

在之前讲解2PC 和 3PC的时候在一定程度上是可以解决数据一致性问题的. 但是并没有完全解决就是协调者宕机的情况.

如何解决2PC和3PC的存在的问题呢?

引入多个协调者,但以哪个为主?
引入主协调者,以他的命令为基准

其实在引入多个协调者之后又引入主协调者.那么这个就是最简单的一种Paxos 算法.

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

5.3 basic paxos

角色介绍
- Client:客户端客户端向分布式系统发出请求，并等待响应。例如，对分布式文件服务器中文件的写请求。
- Proposer：提案发起者提案者提倡客户端请求，试图说服Acceptor对此达成一致，并在发生冲突时充当协调者以推动协议向前发展
- Acceptor: 决策者，可以批准提案 Acceptor可以接受（accept）提案；并进行投票, 投票结果是否通过以多数派为准, 以如果某个提案被选定，那么该提案里的value就被选定了
- Learner: 最终决策的学习者学习者充当该协议的复制因素(不参与投票)
决策模型
basic paxos流程
- Prepare Proposer提出一个提案,编号为N, 此N大于这个Proposer之前提出所有提出的编号, 请求Accpetor的多数人接受这个提案
- Promise 如果编号N大于此Accpetor之前接收的任提案编号则接收, 否则拒绝
- Accept 如果达到多数派, Proposer会发出accept请求, 此请求包含提案编号和对应的内容
- Accepted 如果此Accpetor在此期间没有接受到任何大于N的提案,则接收此提案内容, 否则忽略

5.4 basic paxos流程图

无故障basic paxos
Acceptor失败时的basic Paxos

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

Proposer失败时的basic Paxos

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

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

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

5.5 Multi-Paxos流程图

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

第一次流程-确定Leader
第二次流程-直接由Leader确认

5.5 Multi-Paxos角色重叠流程图

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

6.Raft协议

6.1 概念

Paxos 是论证了一致性协议的可行性，但是论证的过程据说晦涩难懂，缺少必要的实现细节，而且工程实现难度比较高, 广为人知实现只有 zk 的实现 zab 协议。

Paxos协议的出现为分布式强一致性提供了很好的理论基础，但是Paxos协议理解起来较为困难，实现比较复杂。

然后斯坦福大学RamCloud项目中提出了易实现，易理解的分布式一致性复制协议 Raft。Java， C++，Go 等都有其对应的实现之后出现的Raft相对要简洁很多。引入主节点，通过竞选确定主节点。节点类型：Follower、Candidate 和 Leader

Leader 会周期性的发送心跳包给 Follower。每个 Follower 都设置了一个随机的竞选超时时间，一般为 150ms~300ms，如果在这个时间内没有收到 Leader 的心跳包，就会变成 Candidate，进入竞选阶段, 通过竞选阶段的投票多的人成为Leader

6.2 相关概念

节点状态
- Leader（主节点）：接受 client 更新请求，写入本地后，然后同步到其他副本中
- Follower（从节点）：从 Leader 中接受更新请求，然后写入本地日志文件。对客户端提供读请求
- Candidate（候选节点）：如果 follower 在一段时间内未收到 leader 心跳。则判断 leader 可能故障，发起选主提议。节点状态从 Follower 变为 Candidate 状态，直到选主结束
termId

任期号，时间被划分成一个个任期，每次选举后都会产生一个新的 termId，一个任期内只有一个 leader。
RequestVote

请求投票，candidate 在选举过程中发起，收到多数派响应后，成为 leader。

6.3 竞选阶段流程

这个是Raft完整版http://thesecretlivesofdata.com/raft/动画演示

单节点是不存在数据不一致问题的. 一个节点就很容易就该值达成一致性。

如果是多个节点如何达成一致性.Raft是用于实施分布式数据一致性协议的。

大致流程，具体动画可参考网站动画：

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

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

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

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

6.4 Leader节点宕机

参考网站动画

剩余节点会相互选举

6.5 多个 Candidate 竞选

个 Follower 成为 Candidate，并且所获得票数相同，那么就需要重新开始投票

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

6.6 日志复制、网络分区、网络分区情况日志复制

参考网站动画讲解

7.Lease机制

7.1 概念

Lease机制，翻译过来即是租约机制，是一种在分布式系统常用的协议，是维护分布式系统数据一致性的一种常用工具。

特点：

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

以租车为例

7.2 解决什么问题

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

在分布式中最直观的处理方法是在每个副本与主副本维护一个心跳，期望通过心跳是否存在而判断对方是否依旧存活。

心跳方法其实根本无法解决分布式下节点是否正常的这个的这个问题。考虑如下场景：

在某个时刻Node1主节点突然出现网络抖动或者网络中断情况(注意:不是宕机),导致从节点无法接受到心跳.

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

主要解决思路：

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

7.3 lease原理

引入中心节点负责下发Lease
出现网络问题

在01:05期间如果出现网络抖动导致其他节点申请Lease会申请失败, 因为中心节点在01:10之前都会承认有主节点,不允许其他节点在申请Lease
如果网络恢复
如果到01:10时间,主节点会进行续约操作,然后在下发新的Lease
如果主节点宕机,其他节点申请Lease也会失败,承认主节点存在
副节点申请Lease,申请成功. 因为Lease过期

7.4 lease的容错

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

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

7.5 应用

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