分布式一致性算法有哪些

paxos

是由Leslie Lamport（就是大名鼎鼎的LaTeX中的“La”）提出的一种基于消息传递的协商共识算法。现在，Paxos 算法已经成了分布式系统最重要的理论基础，几乎就是“共识”这两字的代名词了。

Paxos 算法的工作流程

Paxos 算法将分布式系统中的节点分为提案节点、决策节点和记录节点三类。

分为提案节点，决策节点，记录节点

• 提案节点：提出对某个值进行设置操作的节点，设置值这个行为就是提案（Proposal）。值一旦设置成功，就是不会丢失也不可变的
• 决策节点：应答提案的节点 过半数被接受就被批准
• 记录节点：不参与提案，也不参与决策，只是单纯地从提案、决策节点中学习已经达成共识的提案。比如，少数派节点从网络分区中恢复时，将会进入这种状态。

在使用 Paxos 算法的分布式系统里，所有的节点都是平等的，它们都可以承担以上某一种或者多种角色。

Paxos 算法是怎么解决并发操作带来的竞争的

• 准备阶段

提案节点发起一个提案ID n，向所有的决策节点广播一个提案，决策节点返回2个承诺和一个应答，2个承诺指的是不再接受小于等于编号n的prepare请求；不再接受小于等于编号n的accept请求；

一个应答是指：在不违背以前作出的承诺的前提下，回复已经批准过的提案中 ID 最大的那个提案所设定的值和提案 ID，如果该值从来没有被任何提案设定过，则返回空值。如果违反此前做出的承诺，也就是说收到的提案 ID 并不是决策节点收到过的最大的，那就可以直接不理会这个 Prepare 请求

• 批准阶段 收到过半数进入批准阶段

        提案节点收到的应答多数是空 说明之前没有过 （id，value）组成二元组再次广播给决策节点；

        提案节点发现响应的决策节点中，已经有至少一个节点的应答中包含有值了，那它就不能够随意取值了，必须无条件地从应答中找出提案 ID 最大的那个值并接受，构成一个二元组 (id, maxAcceptValue)，然后再次广播给全部的决策节点（称为 Accept 请求）。

        假设一个分布式系统有五个节点，分别是 S1、S2、S3、S4 和 S5；全部节点都同时扮演着提案节点和决策节点的角色。此时，有两个并发的请求希望将同一个值分别设定为 X（由 S1 作为提案节点提出）和 Y（由 S5 作为提案节点提出）；我们用 P 代表准备阶段、用 A 代表批准阶段，这时候可能发生下面四种情况。

情况一：比如，S1 选定的提案 ID 是 3.1（全局唯一 ID 加上节点编号），先取得了多数派决策节点的 Promise 和 Accepted 应答；此时 S5 选定的提案 ID 是 4.5，发起 Prepare 请求，收到的多数派应答中至少会包含 1 个此前应答过 S1 的决策节点，假设是 S3。那么，S3 提供的 Promise 中，必将包含 S1 已设定好的值 X，S5 就必须无条件地用 X 代替 Y 作为自己提案的值。由此，整个系统对“取值为 X”这个事实达成了一致。如下图所示：

情况二：事实上，对于情况一，X 被选定为最终值是必然结果。但从图中可以看出，X 被选定为最终值并不是一定要多数派的共同批准，而只取决于 S5 提案时 Promise 应答中是否已经包含了批准过 X 的决策节点。比如下图所示，S5 发起提案的 Prepare 请求时，X 并未获得多数派批准，但由于 S3 已经批准的关系，最终共识的结果仍然是 X。

情况三：当然，另外一种可能的结果是，S5 提案时 Promise 应答中并未包含批准过 X 的决策节点。比如，应答 S5 提案时，节点 S1 已经批准了 X，节点 S2、S3 未批准但返回了 Promise 应答，此时 S5 以更大的提案 ID 获得了 S3、S4 和 S5 的 Promise。这三个节点均未批准过任何值，那么 S3 将不会再接受来自 S1 的 Accept 请求，因为它的提案 ID 已经不是最大的了。所以，这三个节点将批准 Y 的取值，整个系统最终会对“取值为 Y”达成一致。

情况四：从情况三可以推导出另一种极端的情况，如果两个提案节点交替使用更大的提案 ID 使得准备阶段成功，但是批准阶段失败的话，这个过程理论上可以无限持续下去，形成活锁（Live Lock）。在算法实现中，会引入随机超时时间来避免活锁的产生。

一共有5个节点，提案节点向决策节点发送prepare请求，当发生网络分区，三个提案节点发出prepare请求

发送提案，发送成功了三个，批准回复数不过半，继续广播，继续批准；

mullti paxos

Multi PaxosMulti Paxos 对 Basic Paxos 的核心改进是，增加了“选主”的过程：提案节点会 通过定时轮询（心跳），确定当前网络中的所有节点里是否存在一个主提案节点；

一旦没有发现主节点存在，节点就会在心跳超时后使用 Basic Paxos 中定义的准备、批准的两轮网络交互过程，向所有其他节点广播自己希望竞选主节点的请求，希望整个分布式系统对“由我作为主节点”这件事情协商达成一致共识；

当选主完成之后，除非主节点失联会发起重新竞选，否则就只有主节点本身才能够提出提案。此时，无论哪个提案节点接收到客户端的操作请求，都会将请求转发给主节点来完成提案，而主节点提案的时候，也就无需再次经过准备过程，因为可以视作是经过选举时的那一次准备之后，后续的提案都是对相同提案 ID 的一连串的批准过程。我们也可以通俗地理解为：选主过后，就不会再有其他节点与它竞争，相当于是处于无并发的环境当中进行的有序操作，所以此时系统中要对某个值达成一致，只需要进行一次批准的交互即可。

如果得到了决策节点中多数派的批准，便宣告竞选成功。

从整体来看，当节点有了选主机制的支持后，就可以进一步简化节点角色，不必区分提案节点、决策节点和记录节点了，可以统称为“节点”，节点只有主（Leader）和从（Follower）的区别。此时的协商共识的时序图如下：

zab协议

Zab协议 的全称是 Zookeeper Atomic Broadcast （Zookeeper原子广播）。

Zookeeper 是通过 Zab 协议来保证分布式事务的最终一致性。

1. Zab协议是为分布式协调服务Zookeeper专门设计的一种 支持崩溃恢复 的 原子广播协议 ，是Zookeeper保证数据一致性的核心算法。Zab借鉴了Paxos算法，但又不像Paxos那样，是一种通用的分布式一致性算法。它是特别为Zookeeper设计的支持崩溃恢复的原子广播协议。
2. 在Zookeeper中主要依赖Zab协议来实现数据一致性，基于该协议，zk实现了一种主备模型（即Leader和Follower模型）的系统架构来保证集群中各个副本之间数据的一致性。

写：这里的主备系统架构模型，就是指只有一台客户端（Leader）负责处理外部的写事务请求，然后Leader客户端将数据同步到其他Follower节点。

读：Zookeeper 客户端会随机的链接到 zookeeper 集群中的一个节点，如果是读请求，就直接从当前节点中读取数据；如果是写请求，那么节点就会向 Leader 提交事务，Leader 接收到事务提交，会广播该事务，只要超过半数节点写入成功，该事务就会被提交。

Zab协议的核心：定义了事务请求的处理方式

所有的事务请求必须由一个全局唯一的服务器来协调处理，这样的服务器被叫做 Leader服务器。其他剩余的服务器则是 Follower服务器。

Leader服务器 负责将一个客户端事务请求，转换成一个 事务Proposal，并将该 Proposal 分发给集群中所有的 Follower 服务器，也就是向所有 Follower 节点发送数据广播请求（或数据复制）

分发之后Leader服务器需要等待所有Follower服务器的反馈（Ack请求），在Zab协议中，只要超过半数的Follower服务器进行了正确的反馈后（也就是收到半数以上的Follower的Ack请求），那么 Leader 就会再次向所有的 Follower服务器发送 Commit 消息，要求其将上一个 事务proposal 进行提交。

ZAB协议主要用于构建一个高可用的分布式数据主备系统，例如ZooKeeper，而Paxos算法则是用于构建一个分布式一致性状态机系统。

zk集群Leader的选举

在讲解选举之前，我们需要先了解一下什么是zxid。在zk的节点数据中，每次发生数据变动都会有一个流水id做递增的记录，这个id我们称之为zxid，不同机器的zxid可能会有所不同，越大代表当前的数据越新。

实际上每个zk节点都有两个用于记录更新的id，分别是czxid和mzxid。通过名称的缩写可以翻译为：

czxid：创建节点时候的xid。

mzxid：修改节点数据时候的xid。

投票整体思路

第一轮投票全部投给自己

第二轮投票给zxid比自己大的相邻节点 如果得票超过半数，选举结束。

假设现在有3台机器参与选举，分别是1，2，3号机器，启动顺序是1，2，3

第一轮投票：

1号机器投票给到1自己

2号机器投票给到2自己

3号机器投票给到3自己

第二轮：

1号机器的id< 2号机器的id <3号机器的id

1号机器投票给到2号机器，此时2号获取选票大于总机器数目的一半，所以2号成为leader

2号投票给到3号机器，由于此时2号机器已经是leader了，所以3号机器依然只能和1号机器一起保持为follower角色。

所以经过一轮选举之后，2号机当选leader

Gossip

Gossip 的过程可以说是十分简单了，可以看作是两个步骤的简单循环：如果有某一项信息需要在整个网络中的所有节点中传播，那从信息源开始，选择一个固定的传播周期（比如 1 秒），随机选择与它相连接的 k 个节点（称为 Fan-Out）来传播消息。如果一个节点收到消息后发现这条消息之前没有收到过，就会在下一个周期内，把这条消息发送给除了给它发消息的那个节点之外的相邻的 k 个节点，直到网络中所有节点都收到了这条消息。尽管这个过程需要一定的时间，但理论上网络的所有节点最终都会拥有相同的消息。

摘自周志明老师的架构专栏笔记，后面再补充