一文详细讲解一致性常见算法Paxos、Raft、Zab

一、一致性模型

现阶段工业上有两种一致性模型：弱一致性和强一致性。弱一致性中最主要的是最终一致性，对于最终一致性最好的体现是DNS和Gossip通信协议。强一致性主要有：同步（主从同步）、Paxos、Raft、Zab、多数派机制。

二、Paxos

Paxos共识机制有多个版本，常见的有Basic、Multi、Fast。

（1）Basic Paxos

系统角色如下：

• Client：系统外部角色，请求的发起者，类似于议会选举中的民众。
• Propser：用于接收Client请求，向集群提出议案Propose，并在冲突的时候起到调节作用。
• Accpetor：提议投票和接受者，只有形成法定的人数（Quorum一般是marjority多数派），议案才会被接受，类似于国会。
• Learner：提议接受者，主要是进行集群备份。类似于记录员。

该算法有两个阶段，每个阶段有两个分支阶段：

• Prepare：提出一个提案，编号为N，此N大于这个Propser之前提出的提案编号，请求Accpetor的Quorum接受。
• Promise：接受这个发来的请求，前提是该请求编号N大于之前任何提案的编号。
• Accept：如果达到了多数派，Propser会发出Accept请求，此请求包含提案编号N和提案内容。
• Accpeted：如果此Acccetor在此期间没有收到任何编号大于N的提案，则接受刚刚的提案，否则忽略。

在议案还诶有被接受的情况下，如果再出现新编号，那么就会不断出现讨论新提案而不是接受一个提案，这就是Basic Paxos的活锁问题。解决方案就是提供一个random timeout的方案，其他提案等待一段随机时间，再讨论。

Basic Paxos其他问题还有难实现，需要2轮RPC效率低。

（2）Multi Paxos

在该算法中提出了Leader新概念，唯一的Propser，所有的请求都需要经过此Leader。由于需要产生Leader作为唯一的Propser，因此初次需要竞选出Leader。竞选Leader的方式和讨论提案类似。以后所有的提案都由Leader指定讨论。

三、Raft

与Paxos一样，也是解决状态机复制问题，可以将Raft理解为简化版的Paxos。Raft将分布式问题划分成三个小问题：

• Leader Election
• Log Replication
• Safety

并重新定义了角色状态，Leader选举执行流程如下：

• Leader，整个集群只有一个Leader
• Follower，只能在Leader接收数据
• Candidate，在发现集群没有Leader后参与竞选的状态

日志复制执行流程如下:

• 客户端请求Leader写入数据
• Leader将数据分发到Follower中，然后数据被写入Follower的内存
• Follower向Leader发送确认消息，Leader首先提交自己的数据，然后向Follower发送提交数据请求
• Follower提交数据

Raft保证数据安全的执行流程如下：

• 每个Follower自己维持一个timeout，如果在timeout时间段内没有收到Leader的心跳，那么就认为是整个集群中没有Leader
• 当集群没有Leader，那么其中没有发现Leader的Follower中会维持两个值：Term和Vote Count。
  • Term：表示任期
  • Vote Count：表示投票数量，当某个Follower自己参加选举时，首先投自己一票

• 相当Leader的阶段向其他节点发送投票请求，由于在timeout时间段内接受到了投票请求，所以其他Follower不会再次发送Leader投票请求。

• 每次Leader发送心跳，Follower都会更新自己的timeout周期
• 如果同时两个节点同时参加选举并且票数相同，那么就会在timeout时间内开启下一次竞选

由于集群中的节点是奇数，所以当网络分区的时候，总会出现新数据和旧数据，那么Raft不会产生脑裂。

四、Zab

Zab与Raft基本相同，Zab将任期term换成了epoch，Raft保证日志连续性的时候心跳是由Follower发送至Leader。

五、Zookeeper

ZooKeeper是一个分布式的，开放源码的分布式应用程序协调服务，它包含一个简单的原语集，分布式应用程序可以基于它实现同步服务，配置维护和命名服务等。Zookeeper是hadoop的一个子项目，其发展历程无需赘述。在分布式应用中，由于工程师不能很好地使用锁机制，以及基于消息的协调机制不适合在某些应用中使用，因此需要有一种可靠的、可扩展的、分布式的、可配置的协调机制来统一系统的状态。Zookeeper的目的就在于此。

（1）Zookeeper中的角色

• Leader，负责进行投票的发起和决议，更新系统状态。
• Follower，接受客户端请求，响应客户端结果，参与投票。
• Observer，可以接受客户端请求，将其转发给Leader，但是不参与投票过程，只是同步Leader状态。Observer是为了扩展系统，提高读取速度。

（2）Zookeeper的特性

• 最终一致性：client不论连接到哪个Server，展示给它都是同一个视图，这是zookeeper最重要的性能。
• 可靠性：具有简单、健壮、良好的性能，如果消息m被到一台服务器接受，那么它将被所有的服务器接受。一旦一个更新操作被应用，那么在客户端再次更新它之前，它的值将不会改变。这个保证将会产生下面两种结果
• 可用性：Zookeeper保证了可用性，数据总是可用的，没有锁.并且有一大半的节点所拥有的数据是最新的，实时的. 如果想保证取得
• 实时性：Zookeeper保证客户端将在一个时间间隔范围内获得服务器的更新信息，或者服务器失效的信息。Zookeeper提供的一致性是弱一致性，首先数据的复制有如下规则:zookeeper确保对znode树的每一个修改都会被复制到集合体中超过半数的机器上，那么就有可能有节点的数据不是最新的而被客户端访问到，并且会有一个时间点，在集群中是不一致的，同时由于网络延时等原因，Zookeeper不能保证两个客户端能同时得到刚更新的数据。因此Zookeeper只保证最终一致性，但是实时的一致性可以由客户端调用自己来保证，通过调用sync()方法，在十几秒可以Sync到各个节点。
• 等待无关（wait-free）：慢的或者失效的client不得干预快速的client的请求，使得每个client都能有效的等待。
• 原子性：更新只能成功或者失败，没有中间状态。
• 顺序性：包括全局有序和偏序两种：全局有序是指如果在一台服务器上消息a在消息b前发布，则在所有Server上消息a都将在消息b前被发布；偏序是指如果一个消息b在消息a后被同一个发送者发布，a必将排在b前面。
• 节点多了会导致写数据延时非常大，因为需要多个节点同步，节点多了Leader选举非常耗时， 就会放大网络的问题. 可以通过引入observer节点缓解这个问题
• 单系统镜像：无论客户端连接到哪一个服务器，客户端将看到相同的 ZooKeeper 视图。

（3）Zookeeper工作原理

Zookeeper的核心是原子广播，这个机制保证了各个Server之间的同步。实现这个机制的协议叫做Zab（Zookeeper Atomic Broadcast）协议。Zab协议有两种模式，它们分别是恢复模式（选主）和广播模式（同步）。当服务启动或者在领导者崩溃后，Zab就进入了恢复模式，当领导者被选举出来，且大多数Server完成了和leader的状态同步以后，恢复模式就结束了。状态同步保证了leader和Server具有相同的系统状态。

为了保证事务的顺序一致性，zookeeper采用了递增的事务id号（zxid）来标识事务。所有的提议（proposal）都在被提出的时候加上了zxid。实现中zxid是一个64位的数字，它高32位是epoch用来标识leader关系是否改变，每次一个leader被选出来，它都会有一个新的epoch，标识当前属于那个leader的统治时期。低32位用于递增计数。

每个Server在工作过程中有三种状态：

• LOOKING：当前Server不知道leader是谁，正在搜寻
• LEADING：当前Server即为选举出来的leader
• FOLLOWING：leader已经选举出来，当前Server与之同步

（4）选主流程

当leader崩溃或者leader失去大多数的follower，这时候zk进入恢复模式，恢复模式需要重新选举出一个新的leader，让所有的Server都恢复到一个正确的状态。Zk的选举算法有两种：一种是基于basic paxos实现的，另外一种是基于fast paxos算法实现的。系统默认的选举算法为fast paxos。

（5）同步流程

选完leader以后，zk就进入状态同步过程。

1. leader等待server连接；

2. Follower连接leader，将最大的zxid发送给leader；
3. Leader根据follower的zxid确定同步点；
4. 完成同步后通知follower 已经成为uptodate状态；
5. Follower收到uptodate消息后，又可以重新接受client的请求进行服务了。

（6）Leader工作流程

• 恢复数据

• 维持与Learner的心跳，接收Learner请求并判断Learner的请求消息类型

• Learner的消息类型主要有PING消息、REQUEST消息、ACK消息、REVALIDATE消息，根据不同的消息类型，进行不同的处理。

  PING消息是指Learner的心跳信息；REQUEST消息是Follower发送的提议信息，包括写请求及同步请求；ACK消息是Follower的对提议的回复，超过半数的Follower通过，则commit该提议；REVALIDATE消息是用来延长SESSION有效时间。

Leader的工作流程启动了三个线程来实现功能。

（7）Follower工作流程

• 向Leader发送请求（PING消息、REQUEST消息、ACK消息、REVALIDATE消息）

• 接收Leader消息并进行处理

• 接收Client的请求，如果为写请求，发送给Leader进行投票

• 返回Client结果

  Follower的消息循环处理如下几种来自Leader的消息：

• PING消息： 心跳消息；

• PROPOSAL消息：Leader发起的提案，要求Follower投票；

• COMMIT消息：服务器端最新一次提案的信息；

• UPTODATE消息：表明同步完成；

• REVALIDATE消息：根据Leader的REVALIDATE结果，关闭待revalidate的session还是允许其接受消息；

• SYNC消息：返回SYNC结果到客户端，这个消息最初由客户端发起，用来强制得到最新的更新。

在实际实现中，Follower是通过5个线程来实现功能的。

（8）主要应用场景

• 集群的配置管理
• 集群管理

（9）监视

Zookeeper 所有的读操作——getData()、 getChildren() 和 exists() 都 可以设置监视(watch)，监视事件可以理解为一次性的触发器。

当设置监视的数据发生改变时，该监视事件会被发送到客户端，例如，如果客户端调用了 getData("/znode1"， true) 并且稍后 /znode1 节点上的数据发生了改变或者被删除了，客户端将会获取到 /znode1 发生变化的监视事件，而如果 /znode1 再一次发生了变化，除非客户端再次对 /znode1 设置监视，否则客户端不会收到事件通知。

Zookeeper 客户端和服务端是通过 socket 进行通信的，由于网络存在故障，所以监视事件很有可能不会成功地到达客户端，监视事件是异步发送至监视者的，Zookeeper 本身提供了保序性：即客户端只有首先看到了监视事件后，才会感知到它所设置监视的 znode 发生了变化

Zookeeper 中的监视是轻量级的，因此容易设置、维护和分发。当客户端与 Zookeeper 服务器端失去联系时，客户端并不会收到监视事件的通知，只有当客户端重新连接后，若在必要的情况下，以前注册的监视会重新被注册并触发，对于开发人员来说 这通常是透明的。只有一种情况会导致监视事件的丢失，即：通过 exists() 设置了某个 znode 节点的监视，但是如果某个客户端在此 znode 节点被创建和删除的时间间隔内与 zookeeper 服务器失去了联系，该客户端即使稍后重新连接 zookeeper服务器后也得不到事件通知。

（10）文件系统

每个子目录项如 NameService 都被称作为znode，和文件系统一样，我们能够自由的增加、删除znode，在一个znode下增加、删除子znode，唯一的不同在于znode是可以存储数据的。

有四种类型的znode：

• PERSISTENT-持久化目录节点 ，客户端与zookeeper断开连接后，该节点依旧存在
• PERSISTENT_SEQUENTIAL-持久化顺序编号目录节点 ，客户端与zookeeper断开连接后，该节点依旧存在，只是Zookeeper给该节点名称进行顺序编号
• EPHEMERAL-临时目录节点，客户端与zookeeper断开连接后，该节点被删除
• EPHEMERAL_SEQUENTIAL-临时顺序编号目录节点，客户端与zookeeper断开连接后，该节点被删除，只是Zookeeper给该节点名称进行顺序编号

客户端注册监听它关心的目录节点，当目录节点发生变化（数据改变、被删除、子目录节点增加删除）时，zookeeper会通知客户端。

（11）Zk分布式锁

锁服务可以分为两类，一个是保持独占，另一个是控制时序。

• 对于第一类，我们将zookeeper上的一个znode看作是一把锁，通过createznode的方式来实现。所有客户端都去创建 /distribute_lock 节点，最终成功创建的那个客户端也即拥有了这把锁。用完删除掉自己创建的distribute_lock 节点就释放出锁。

• 对于第二类， /distribute_lock 已经预先存在，所有客户端在它下面创建临时顺序编号目录节点，和选master一样，编号最小的获得锁，用完删除，依次方便。

（12）Zookeeper队列管理

• 同步队列，当一个队列的成员都聚齐时，这个队列才可用，否则一直等待所有成员到达。 在约定目录下创建临时目录节点，监听节点数目是否是我们要求的数目。
• 队列按照 FIFO 方式进行入队和出队操作。 和分布式锁服务中的控制时序场景基本原理一致，入列有编号，出列按编号。

（13）分布式与数据复制

Zookeeper作为一个集群提供一致的数据服务，自然，它要在所有机器间做数据复制。数据复制的好处：

• 容错：一个节点出错，不致于让整个系统停止工作，别的节点可以接管它的工作
• 提高系统的扩展能力 ：把负载分布到多个节点上，或者增加节点来提高系统的负载能力
• 提高性能：让客户端本地访问就近的节点，提高用户访问速度

从客户端读写访问的透明度来看，数据复制集群系统分下面两种：

• 写主(WriteMaster) ：对数据的修改提交给指定的节点。读无此限制，可以读取任何一个节点。这种情况下客户端需要对读与写进行区别，俗称读写分离
• 写任意(Write Any)：对数据的修改可提交给任意的节点，跟读一样。这种情况下，客户端对集群节点的角色与变化透明

对zookeeper来说，它采用的方式是写任意。通过增加机器，它的读吞吐能力和响应能力扩展性非常好，而写，随着机器的增多吞吐能力肯定下降（这也是它建立observer的原因），而响应能力则取决于具体实现方式，是延迟复制保持最终一致性，还是立即复制快速响应。