一致性协议（2PC，3PC，Paxos，Raft， ZAB）

2024-02-16 17:24:58

文章目录

#一致性协议

2PC

阶段一
- “事务询问”
- 执行事务（未提交）
- 参与者反馈“事务询问”的响应
阶段二
两种操作
- 执行事务提交
  - 发送提交请求
  - 参与者执行事务提交
  - 反馈事务提交响应
  - 协调者接受提交响应后，完成事务
- 中断事务
  - 发送回滚请求
  - 执行回滚操作
  - 反馈回滚结果
  - 中断事务

2PC问题：

同步阻塞
协调者单点故障
数据不一致问题，二阶段由于网络问题，commit消息未全部发送成功，或者部分参与者未接收到

3PC

同2PC差异

引入超时机制
在第一阶段和第二阶段中插入一个准备阶段
3PC把2PC的准备阶段再次一分为二，这样三阶段提交就有CanCommit、PreCommit、DoCommit三个阶段

避免了参与者在长时间无法与协调者节点通讯（协调者挂掉了）的情况下，无法释放资源的问题

因为参与者自身拥有超时机制会在超时后，自动进行本地commit从而进行释放资源。

1.CanCommit

事务询问（未执行）
响应反馈

2.PreCommit

两种情况

(1) CanCommit 全部YES

发送PreCommitt请求
事务预提交 执行事务操作，记录undo，redo
响应反馈

(2) CanCommit 其中一个NO响应

发送中断请求 发送abort 请求
中断事务 参与者接收到abort 请求，或者超时

3.DoCommit

该阶段进行真正的事务提交，分两种情况

（1）执行提交

发送提交请求
执行事务提交
响应反馈
完成事务

（2）中断事务

发送中断请求
事务回滚
反馈结果
中断事务

在doCommit阶段，如果参与者无法及时接收到来自协调者的doCommit或者abort请求时，会在等待超时之后，会继续进行事务的提交
当进入第三阶段，参与者都收到了PreCommit请求，说明CanCommit响应都是YES，由于网络超时等原因，虽然参与者没有收到commit或者abort响应，但是他有理由相信：成功提交的几率很大。

强一致性协议

主从复制类

多数派类

Paxos 类（并发环境，需要多数派，还需要关注顺序）

Paxos算法

Paxos 算法需要解决的问题就是如何在一个可能发生机器宕机或者网络异常的分布式环境中，快速且正确的在集群内部对某个数据的值达成一致，并且保证不论发生任何异常，都不会破坏整个系统的一致性

一、算法陈述（Basic Paxos）

在该算法中有三种角色：Proposer，Acceptor，Learner

Proposer：接受client 请求，向集群提出提议（propose）。并在冲突发生时，起到冲突调节的作用。像*替民众提出议案
Acceptor：提议投票和接受者，只有在形成法定人数（Quorum，一般即为majority多数派）时，提议才会最终被接受。像国会
Learner：提议的接受者，backup，备份，对集群一致性没什么影响，像记录员

阶段一
1. Proposer 选择一个提案编号M_n,然后想Acceptor的某个超过半数的子集成员发送编号为M_n的Prepare请求。
2. 如果一个Acceptor接受到一个编号为M_n的Prepare请求，且编号M_n大于该Acceptor已经响应的所有Prepare请求的编号，那么它就会将已经批准过的最大编号的提案作为响应反馈给Proposer，同时该Acceptor会承诺不再批准任何编号小于M_n的提案。
> 举例假定一个Acceptor 已经响应过的所有Prepare请求对应的提案编号分别为1,2，。。。5和7，那么该Acceptor在接收到编号为8的Prepare 请求后，会将编号为7的提案作为响应反馈给Proposer。
阶段二

如果Proposer收到来至半数以上Acceptor对于其发出的编号为M_n的Prepare请求的响应，那么它会发送一个针对【M_n，V_n】提案的Accept请求给Acceptor。注意：V_n 的值就是收到的响应中编号最大的提案的值，如果响应中不包含任何提案，那么它就是任意值。
如果Acceptor收到这个针对【M_n，V_n】提案的Accept请求，只要该Acceptor尚未对编号大于M_n的Prepare请求做出响应，它就可以通过这个提案

最后 Learn阶段。Proposer在收到多数Acceptors的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。

二、提案的获取

方案一
一旦 Acceptor批准一个提案，就将该提案发送给所有Learner
优点：尽快获取提案
缺点：每一个Acceptor同所有Learner通信，通信次数是二者个数的乘积，多
方案二
让所有Acceptor批准的提案统一发送给一个主Learner ,主learner通知其他learner
优点：通信次数为二者个数的和，少
缺点：主Learner可能出现故障
方案三
对方案二进行改进，将主Learner范围扩大，Acceptor可以将提案发送给一个特定的Learner集合，这个集合中的Learner 都可以在一个提案被选中后通知所有其他的Learner。

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

为避免Proposer 依次提出一系列编号递增的议案，但是最终无法被选定，必选选择一个主Proposer ,并规定只能有这个Proposer才能提出议案；这样只要主Proposer和过半的Acceptor能够正常进行通信，那么但凡主Proposer提出一个编号更高的提案，该提案将会被批准。

四、算法的优化

小优化尽可能忽略Prepare请求：
假设Acceptor接收到一个编号为M_n的Prepare请求，但是此时该Acceptor已经对对编号大于M_n的Prepare请求做出响应，因此他肯定不会再批准任何新的编号为M_n的提案，那么显然Acceptor就没有必要对这个Prepare 请求做出响应，于是Acceptor可以选择忽略这样的Prepare请求。同时，Acceptor也可以忽略掉那些已经批准过的提案的Prepare请求。

Acceptor忽略编号小于已经响应过的最大编号的Prepare请求
Acceptor也可以忽略那些已经批准过的提案的Prepare请求。

五 Multi-Paxos

首先需要选举Leader，选举Leader 需要一次Basic Paxos 的Prepare请求，选出Leader之后只能由Leader Proposer提交议案

参考
Paxos、Raft分布式一致性最佳实践

Raft 算法

动画讲解
 算法讲解
 算法中文论文
概述：Raft 将一致性分解为多个子问题：Leader Eelection，Log replication，Safety，Log compaction，Membership change
角色
角色重新定义：
Leader：接受客户端请求，并项Follower同步请求日志，当日志同步到大多数节点后告诉Follower提交日志
Follower：接受并持久化Leader同步的日志，在Leader告知日志可以提交之后，提交日志
Candidate：Leader选举过程中的临时角色
下图为服务器角色转换过程:
Raft算法将时间分为一个个的任期（term）,term 一开始都是Learder选举。在Learder选举成功后，Learder会在整个term周期内管理集群

1、Leader选举

Raft 使用心跳（heartbeat）触发Leader选举。当服务器启动时，初始化为Follower。
Leader向所有Followers周期性发送heartbeat。
如果Follower在选举超时时间内没有收到Leader的heartbeat，就会等待一段随机的时间后发起一次Leader选举。

Follower 将当前term值+1 转换为Candidate。它首先给自己投票并且给集群中的其他服务器发送RequestVote RPC ,三种可能结果

赢得多数选票，成功选举为Leader
收到了Leader的消息，表示有其他服务器已经抢先选了Leader
没有服务器赢得多数选票，Leader选举失败，等待选举时间超时后发起下一次选举

选举出Leader后，Leader通过定期向所有Follower发送心跳信息维持其统治。若Follower一段时间未收到Leader心跳则认为Leader可能已经挂了，再次发起Leader选举过程

2、日志同步

Raft日志同步保证如下两点:

如果不同日志中的两个条目有着相同的索引和任期号，则它们存储的条目是相同的
如果不同日志中的两个条目有着相同的所有和任期号，则他们之前的所有条目都是完全一样的

Leader崩溃可能会导致日志不一致：旧的Leader可能没有完全复制完日志中的所有条目。
Leader 通过强制Follower 复制它的日志来处理日志的不一致，Follower上的不一致日志会被Leader的日志覆盖

日志同步动画

3、安全性

Raft增加了如下两条限制以保证安全性：

(1) 拥有最新的已提交的log entry的Follower才有资格成为Leader
(2) Leader只能推进commit index来提交当前term的已经复制到大多数服务器上的日志，旧term日志的提交要等到提交当前term的日志来间接提交（log index 小于 commit index的日志被间接提交）。

第二点的意思是，Leader仅提交自己生成的日志，且同步日志时，才会将旧term的日志一并复制提交，来避免旧term的日志被覆盖的问题。

4、日志压缩

Raft采用对整个系统进行snapshot来解决，snapshot之前的日志都可以丢弃。
每个副本独立的对自己的系统状态进行snapshot，并且只能对已经提交的日志记录进行snapshot
Snapshot 包含：

日志元数据最后一条已提交的 log entry的 log index和term
系统当前状态（状态机的状态）

作用：

剔除陈旧的日志信息，提高可用性
Leader 可以将snapshot 发送给运行非常缓慢的Follower 或者新加入集群的机器，快速恢复。

5、成员变更

成员变更是在集群运行过程中副本发生变化，如增加/减少副本数、节点替换等。
成员变更过程的某一时刻，可能出现在Cold和Cnew中同时存在两个不相交的多数派，进而可能选出两个Leader，形成不同的决议，破坏安全性。

两阶段成员变更

Leader收到成员变更请求从Cold切成Cnew；
Leader在本地生成一个新的log entry，其内容是Cold∪Cnew，代表当前时刻新旧成员配置共存，写入本地日志，同时将该log entry复制至Cold∪Cnew中的所有副本。在此之后新的日志同步需要保证得到Cold和Cnew两个多数派的确认；
Follower收到Cold∪Cnew的log entry后更新本地日志，并且此时就以该配置作为自己的成员配置；
如果Cold和Cnew中的两个多数派确认了Cold U Cnew这条日志，Leader就提交这条log entry；
接下来Leader生成一条新的log entry，其内容是新成员配置Cnew，同样将该log entry写入本地日志，同时复制到Follower上；
Follower收到新成员配置Cnew后，将其写入日志，并且从此刻起，就以该配置作为自己的成员配置，并且如果发现自己不在Cnew这个成员配置中会自动退出；
Leader收到Cnew的多数派确认后，表示成员变更成功，后续的日志只要得到Cnew多数派确认即可。Leader给客户端回复成员变更执行成功。

一阶段成员变更

可从数学上严格证明，只要每次只允许增加或删除一个成员，Cold与Cnew不可能形成两个不相交的多数派。

成员变更限制每次只能增加或删除一个成员（如果要变更多个成员，连续变更多次）。
成员变更由Leader发起，Cnew得到多数派确认后，返回客户端成员变更成功。
一次成员变更成功前不允许开始下一次成员变更，因此新任Leader在开始提供服务前要将自己本地保存的最新成员配置重新投票形成多数派确认。
Leader只要开始同步新成员配置，即可开始使用新的成员配置进行日志同步。

Raft与Multi-Paxos的异同

相似：

不同：

ZAB 算法

ZAB协议并不像Paxos算法一样，是一种通用的分布式一致性算法，它是一种特别为Zookeeper设计的奔溃可恢复的原子消息广播算法。

在Zookeeper中，主要依赖ZAB协议实现分布式数据一致性，基于该协议，Zookeeper实现了一种主备模式的系统架构来保持集群中各副本之间数据的一致性。

Zookeeper采用ZAB协议，将服务器数据的状态变更以事务Proposal的形式广播到所有的副本进程上去。

ZAB协议的主备模型架构保证了同一时刻集群中只能有一个主进程来广播服务器的状态变更；
ZAB协议必须能够保证一个全局的变更序列被顺序应用。

ZAB 两种模式

奔溃恢复模式

基本特性：

ZAB协议需要确保那些已经在Leader服务器上提交的事务最终被所有服务器都提交。
ZAB协议需要确保丢弃那些只在Leader服务器上被提出的事务

数据同步：
完成Leader选举后，在正式开始工作之前，Leader服务器首先确认事务日志中所有Proposal是否都已经被集群中过半的机器提交了。
正常情况过程如下：
Leader服务器会为每一个Follower服务器都准备一个队列，并将那些没有被各Follower服务器同步的事务以Proposal消息的形式逐个发送给Follower服务器，并在每一个Proposal消息后面紧接着再发送一个Commit消息，以表示该事务已经被请提交。等到Follower服务器将所有尚未同步的事务Proposal都从Leader服务器上同步过来并成功应用到本地数据库中后，Leader服务器就会将该Follower服务器加入到真正的可用Follower列表中。
被丢弃的事务Proposal：
ZXID（64位数字）=Leader周期epoch（[ˈiːpɒk]
）的编号（高32位）+低32位
每当选举产生新的Leader服务器，就会将epoch+1,生成新epoch，并将第32位置为0.
基于该策略，当一个包含上一个Leader周期中尚未提交过的事务Proposal的服务器启动时，肯定无法成为Leader，因为当前集群中一定包含一个Quorum 集合包含更高epoch的事务Proposal，因此这台机器的事务Proposal肯定不是最高，也就无法成为Leader。最终会以Follower角色连上Leader，Leader 会比较自身和Follower的Proposal，结果是Leader会要求Follower进行一个回退操作，回退到一个确实被集群过半机器提交的最新的事务Proposal。

消息广播模式

类似于两阶段提交过程，针对客户端的请求，Leader 服务器生成事务Proposal，发送给其他服务器，然后分别收集各自的选票，最后进行事务的提交。
每个广播事务Proposal 都有一个**单调递增的唯一ID**（ZXID），每个事务Proposal都必须按照**ZXID的先后顺序**进行排序和处理

内部原理

阶段一：发现

CEPOCH：Follower进程准备向准Leader 发送自己处理过的最后一个事务Proposal的epoch值
NEWEPOCH：准Leader 进程根据接受的各进程的epoch，来生成新一轮周期的epoch值
ACK-E：Follower进程反馈准Leader进程发来的NEWEPOCH消息。

阶段二：同步

NEWLEADER：准Leader进程确立自己的领导地位，并发送NEWLEADER消息给各进程。
该消息包含新EPOCH值，以及准Leader已经处理过的事务Proposal集合，用于数据同步。
ACK-LD：Follower进程反馈Leader进程发来的NEWLEADER消息
COMMIT-LD：要求Follower进程提交相应的历史实物Proposal。

阶段三：广播

PROPOSE：Leader 进程生成一个针对客户端事务请求的Proposal。
ACK：Follower进程反馈Leader进程发来的Proposal消息
COMMIT：Leader 发送Commit消息，要求所有进程提交事务PROPOSE。

运行分析

每一个进程处于以下三总状态：

LOOKING：Leader选举
FOLLOWER ：Follower服务器和Leader服务器保持同步状态
LEADING：Leader作为主进程领导状态

ZAB 与Paxos 联系和区别

联系：

都存在类似Leader的角色，协调多个Follower进程运行
都会等待过半的Follower 正确反馈，才会将天提交
都存在一个标识新阶段的值，如epoch[ˈiːpɒk] ，Ballot['bælət]

区别： ZAB 有一个同步阶段，本质区别是ZAB协议用于构建一个高可用的分布式数据主备系统，而Paxos用于构建一个分布式的一致性状态机系统

码农公寓