Zookeeper与Paxos

初识Zookeeper

zookeeper为分布式应用提供了高效且可靠的分布式协调服务，提供了诸如统一命名服务、配置管理和分布式锁等分布式的基础服务。
在解决分布式数据一致性方面，zk没有直接采用Paxos算法，而是采用了一种被称为ZAB(Zookeeper Atomic Broadcast)的一致性协议。
zk可以保证如下分布式一致性特性：
- 顺序一致性：从同一个client发起的事务请求，最终会被严格按照发起顺序被应用到zk中。 --> through为每个请求分配一个全局唯一的递增编号。
- 原子性：所有事务请求的处理结果在整个集群中所有机器上的应用情况一致。
- 单一视图：无论client连接哪个zk server，其看到的服务端数据模型都是一致的。
- 可靠性：一旦server端成功应用了一个事务，并成功对client响应，那么该事务所引起的服务端状态变更会被一直保存，知道另一个事务变更。
- 实时性：zk仅保证在一定时间段内，client最终一定能从server上读取到最新的数据状态。

zk设计目标

简单的数据模型：zk使得分布式程序能够通过一个共享的、树形结构的名字空间来进行相互协调。
可以构建集群：集群中只要有超过一半的机器能正常工作，集群就能对外提供服务。client会和集群中任意一台机器建立TCP连接，断开后，client会自动连接到另一台机器。 --> 可用性up
顺序访问：对于client的每个更新请求，zk都会分配一个全局唯一的递增编号，该编号反应了所有事务操作的先后顺序，app可以用zk的这个特性来实现更高层次的同步原语。
高性能：zk将全量数据存储在内存中，并直接服务client的所有非事务请求，因此尤其适用于以读操作为主的应用场景。

zk的基本概念

集群角色

集群角色：最典型的集群模式是Master/Slave模式。能够处理写操作的称为master，所以通过异步复制方式获取最新数据并提供读服务的为slave。
而zk中没有沿用传统的主从模式，而是引入了Leader、Follower和Observer三种角色。
zk中所有机器通过一个leader选举过程来选定一台被称为leader的机器，leader server为client提供读写服务。
follower和observer都能提供读服务，唯一区别在于observer不参与leader选举过程，也不参与写操作的“过半写成功”策略。因此，observer在不影响写性能的情况下提升集群的读性能。

会话(Session)

在zk中，一个客户端连接是指client和server之间的一个TCP长连接。
通过这个连接，client可以通过心跳检测与服务器保持有效的会话，也能够向zk server发送请求并接受响应。
Session的 sessionTimeout值用来设置一个客户端会话的超时时间。当服务器压力太大、网络故障或是客户端主动断开连接等各种原因导致client连接断开时，只要在sessionTimeout 时间内能够重新连接上集群中任意一台服务器，那么之前创建的会话仍然有效。

数据节点(Znode)

zk中的节点，一类是构建集群的机器，称为机器节点；另一类则是数据模型中的数据单元，称为数据节点ZNode。
zk将所有数据存储在内存中，数据模型是一棵树(ZNode Tree)。
每个znode上会保存自己的数据内容，同时还会保存一系列属性信息。
zk还允许每个节点添加一个特殊的属性：SEQUENTIAL。该属性是一个整形数字，是一个由父节点维护的自增数字。

版本

对于每个znode，zk都会为其维护一个叫做Stat的数据结构，Stat记录了该Znode的三个数据版本，分别是version（当前znode的版本）、cversion（当前znode子节点的版本）和aversion（当前znode的ACL版本）。

Watcher

Watcher（事件监听器）是zk中一个很重要的特性。zk允许用户在指定节点上注册一些watcher，并在一些特定事件触发时通知感兴趣的client。

ACL

zk采用ACL(Access Control Lists)策略来进行权限控制。

ZK的ZAB协议

ZAB协议

事实上，zk并没有完全采用Paxos算法，而是使用了Zookeeper Atomic Broadcast即zk原子消息广播协议作为其数据一致性的核心算法。
ZAB是为zk专门设计的支持崩溃恢复的原子广播协议。
zk主要依赖ZAB协议来实现分布式数据的一致性。基于该协议，zk实现了一种主备模式的系统架构来保持集群中各副本之间数据的一致性。
- 具体的，zk使用一个单一的主进程来接收并处理client的所有事务请求，并采用ZAB的原子广播协议，将server数据的状态变更以事务Proposal的形式广播到所有的副本进程上。
- 由于顺序执行的状态变更前后会存在一定的依赖关系，ZAB协议需要保证若一个状态变更被处理时，所有其依赖的状态变更都应该已经被处理了。 --> 顺序性
- 考虑到主进程可能崩溃，ZAB协议还需要在主进程崩溃时保持正常工作。 --> 高可用性

协议介绍

ZAB协议包括两种基本的模式，分别是崩溃恢复和消息广播。
当整个服务框架在启动过程中，或是当leader服务器出现网络中断、崩溃退出与重启等异常情况时，ZAB协议就会进入恢复模式并选举产生新的Leader服务器。当选举产生了新的Leader服务器，同时集群中已有过半的机器(follower)与Leader完成状态同步(即数据同步，用以保证集群中存在过半的机器与leader的数据状态保持一致)后，退出恢复模式。
过半机器同步完成后，整个服务框架就可以进入消息广播模式了。启动后新加入的机器会自觉进入数据恢复模式(即找到leader并进行数据同步)。
leader server是唯一允许处理事务请求的机器，若其他机器接收到client的事务请求，会将该请求转发给leader。接着，leader会生成相应的事务提案并发起一轮广播协议。

消息广播

ZAB协议的消息广播过程使用的是一个原子广播协议，类似于一个二阶段提交过程。
当过半的follower反馈Ack之后就可以提交事务Proposal了。
但是该模型无法处理leader崩溃退出而带来的数据不一致问题。因此，在ZAB协议中添加了另一模式，即采用崩溃恢复模式来解决这个问题。
另外，整个消息广播协议是基于具有FIFO特性的TCP协议来进行网络通信的，因此能够很容易地保证消息广播过程中消息接收与发送的顺序性。(zk采用单一主线程来处理client请求)
在整个消息广播过程中，leader服务器会为每个事物请求生成对应的Proposal来进行广播，并且在广播事务Proposal之前，为proposal分配一个全局单调递增的唯一ID，即事务ID(ZXID)。
具体而言，在消息广播过程中，leader server会为每个follower分配一个单独的队列，然后将需要广播的事务proposal依次放入这些队列中，并且根据FIFO策略发送消息。每个follower接收到proposal后，会首先将其以事务日志形式写入本地磁盘，并且在成功写入后反馈给leader。当leader收到超过半数的ack后，会广播一个commit消息给所有的follower以通知其进行事务提交，同时leader自身也会完成对事务的提交，而follower也会在接收到commit消息后，完成对事务的提交。

Phase1: leader发送事务proposal --> follower将proposal以事务形式写入本地磁盘，并且反馈ack给leader。
Phase2: leader在收到半数ack后，会广播一个commit消息给所有follower --> leader完成事务提交 --> follower完成事务的提交。

过半follower写入成功，可以提高系统可用性，即在leader崩溃之后可以选择数据一致的follower替换当前leader。而只需要过半写入成功，也可以提高整个过程的效率，缩短阻塞时间。(zk在整个过程中并没有阻塞，是通过为每个follower维护一个proposal queue，并且用TCP来保证FIFO。)
这个过程中，为了保证事务的顺序性，为每个事务proposal分配了全局唯一的ZXID，发送端以FIFO的方式发送proposal，并且使用一个单一的主线程以TCP协议发送事务，从这两个方面保证了事务发送&接收的顺序性。
除了上述两个方面，zk还需要解决2PC带来的单点故障和数据不一致的问题，这就引入了下面一小节要介绍的“崩溃恢复”啦。

崩溃恢复

zk中一旦leader崩溃(或者可能是由于网络原因导致leader失去了与过半follower的联系)，那么就会进入崩溃恢复模式。
在ZAB协议中，为保证程序的正确运行，整个恢复过程结束后需要选举出一个新的leader server。因此，ZAB协议需要一个高效且可靠的leader选举算法。leader选举算法需要保证leader以及集群中其他机器都知道谁是leader。
由上一小节了解到，zk本质上类似于一个2PC的过程，而崩溃恢复就是为了应对2PC存在的“单点故障”和“数据不一致问题”的。
- 其中，“单点故障”是通过leader selection来处理的，也就是说在leader崩溃(失去与过半follower联系)时会进入崩溃恢复模式。
- 而对于数据不一致问题，我们首先考虑可能产生数据不一致的情况：
  在zk处理事务的流程中(具体见上一小节)，考虑所有leader可能崩溃的时间点，可以发现：
  - leader发生proposal后崩溃：则leader有proposal，而follower中没有(本地磁盘)。
  - leader在发送commit消息前崩溃：则leader提交了proposal，而follower未提交。

基本特性

在崩溃过程中，可能会出现的两个数据不一致的隐患及针对这些情况ZAB协议所需要保证的特性。
ZAB协议需要保证那些已经在leader server上提交的事务最终被所有server都提交。
- 假设一个事务已经得到过半follower的ack，并且已经在leader上被提交了，但是在它将commit消息发送给所有follower之前，leader挂了。
  比如，leader先后广播了P1、P2、C1、P3和C2，其中，当leader将C2(Commit of Proposal2)发出后就立即崩溃退出了，针对这种情况，ZAB协议需要确保proposal2最终能够在所有的服务器上都被提交成功，否则将出现不一致。
ZAB协议需要确保丢弃那些只在leader server上被提出的事务。
- 相反，如果崩溃恢复过程中出现一个需要被丢弃的提案，那么崩溃恢复结束后需要跳过该事务proposal。
  比如，leader在提出了proposal3之后就崩溃退出了，从而导致集群中其他服务器都没有收到这个事务proposal。于是当server1恢复过来再次加入到集群中时，ZAB协议需要确保丢弃proposal3这个事务。
结合上述两个需求，ZAB协议必须设计一个这样的leader选举算法：能够确保提交已经被leader提交的事务proposal，同时丢弃已经被跳过的事务proposal。因为
- 已经被leader提交的proposal，必定已经被超过半数的follower执行，只是可能还未提交。既然已经被leader提交，为了保证一致性，需要保证所有follower也提交。
- 还未被leader提交的proposal，意味着还没有超过半数的follower执行。既然leader还未提交，那么必定没有follower提交，那么可以直接丢弃该proposal。
Solution：如果leader选举算法能够保证新选举出来的leader服务器拥有集群中所有机器最高编号(即ZXID最大)的事务proposal，那么就可以保证这个新选举出来的lader一定具有所有已提交的提案。更为重要的是，如果让具有最高编号事务proposal的机器成为leader，就可以省去leader server检查proposal的提交和丢弃工作这一操作了。

数据同步

完成leader选举之后，在正式开始工作(即接收客户端的事务请求，然后提出新的提案)之前，leader server会首先确认事务日志中的所有proposal是否都已经被集群中过半的机器提交了，即是否完成数据同步。
下面来看ZAB协议的数据同步过程：
- 首先，leader需要确保所有的follower能够接收到每一条proposal，并且能正确地将所有已提交的proposal应用到内存数据库中去。具体的：
  - leader为每个follower准备一个队列，并将那么未被各follower同步的事务以proposal消息的形式逐个发送给follower，并在每个proposal后紧接着一个commit消息，表明该事务已提交
  - 等到follower将其所有尚未同步的事务proposal都从leader上同步过来并成功应用到本地数据库中后，leader会将follower加入到真正的可用follower列表中。
还需要考虑如何处理那些需要被丢弃的事务proposal(即上面一条处理的需要被所有follower提交的事务)：

ZAB的事务编号ZXID被设计为一个64位的数字，其中低32位可以看作一个简单的单调递增的计数器，leader在产生一个新的proposal的时候，都会加一；而高32位则代表了leader周期epoch的编号，每当产生一个新的leader，就会从这个leader上取出起本地日志的最大事务proposal的ZXID，并从该ZXID中解析出对应的epoch值，然后加1作为新的epoch，并将低32位置0来开始生成新的ZXID。从而，ZAB协议可以通过epoch编号来区分leader周期变化的策略，有效避免不同的leader错误地使用相同的ZXID编号提出不一样的proposal的异常情况。
基于这样的策略，当一个包含了上一个leader周期中尚未提交的proposal的server启动时肯定无法成为leader，因为其不可能拥有最高ZXID的proposal。那么该server会成为follower，当其连接上leader后，会被leader要求进行回退操作，即回退到一个确实已经被集群中过半机器提交的最新的proposal。

深入理解ZAB协议

前面的内容介绍了ZAB协议的大体内容以及在实际运行过程中消息广播和崩溃恢复这两个基本模式，下面将从系统模型、问题描述、算法描述和运行分析四方面来深入理解ZAB协议。

系统模型

ZAB协议需要构建的分布式系统模型：
- 在一个由一组进程 {P1, P2, ..., Pn}组成的分布式系统中，其每个进程都有各自的存储设备，进程间通过相互通信来实现消息的传递。
- 每个进程随时有可能崩溃退出(进入DOWN状态)，在退出后还有可能再次加入(重新进入UP状态)。
- 集群中存在过半的处于UP状态的进程组成一个进程子集(Quorum)之后就可以进行正常的消息广播了。

问题描述

zk是一个高可用的分布式协调服务，在yahoo的很多大型系统上得到应用。这类应用有个共同的特点，即通常都存在大量的客户端进程，并且都依赖zk来完成一系列诸如可靠的配置存储和运行时状态记录等分布式协调工作。
因而，zk必须具有高吞吐和低延迟的特性，并且能够很好地在高并发情况下完成分布式数据的一致性处理，同时能够优雅地处理运行时故障，并具备快速故障恢复的能力。
ZAB协议时整个zk框架的核心所在，其规定来任何时候都需要保证只有一个主进程负责进行消息广播，并且在主进程崩溃的时候进行leader选举。

事务

假设各个进程都存在一个类似transaction(v, z)这样的函数调用，来实现主进程对状态变更的广播。主进程每个对transaction(v, z)的调用都包含了：事务内容v和事务标识z，而每个事务标识z又由z = <e, c>两部分组成，前者是主进程周期e，后者是当前主进程周期内的事务计数c。
针对一个新事务，主进程首先递增事务计数c。

算法描述

下面将从算数描述角度来深入理解ZAB协议的内部原理。
整个ZAB协议主要包括消息广播和崩溃恢复两个过程。进一步可以细分为发现(discovery)、同步(synchronization)和广播(broadcast)三个阶段。组成ZAB协议的每一个分布式进程，会循环地执行这三个阶段，这样的一个循环称为一个主进程周期。
首先，给出ZAB协议中一些专有术语的定义

阶段一：发现

阶段一主要就是leader选举过程，用于在多个分布式进程中选举出主进程，准leader L和follower F的工作流程如下：
- 步骤F.1.1 follower将自己最后接受的事务proposal的epoch值CEPOCH(F.p)发送给准leader L
- 步骤L.1.1 当接收到过半follower的CEPOCH(F.p)消息后，准Leader L会生成NEWEPOCH(e')消息给这些过半的follower
- 步骤 F.1.2 当follower接收到来自准leader L的NEWPOCH(e')后，如果其检测到当前的CEPOCH(F.p)值小于e'，那么就会将CEPOCH(F.p)赋值为e', 同时向准leader L发送ack。这个反馈消息(ACK-E(F.p, hf))中，包含了当前该follower的epoch CEPOCH(F.p)以及该follower的历史proposal集合: hf。
当leader L收到来自过半follower的ack后，L就会从这过半服务器中选举一个follower，使用其作为初始化事务集合Ie'。
- 选取方式：对Quorum中其他任意一个Follower F'，F需要满足以下两个条件之一:
至此，ZAB协议完成阶段一的工作流程。

阶段二：同步

步骤 L.2.1 Leader L会将e' 和 Ie' 以NEWLEADER(e', Ie')消息的形式发送给所有Quorum中的follower。
步骤 F.2.2 当follower接收到来自L的NEWLEADER(e', Ie')消息后，若follower发现CEPOCH(F.p) 不等于 e'，那么直接进入下一轮循环。若想等，则follower会执行事务应用操作。具体的，对于每个事务Proposal：<v, z>属于Ie'，follower会接收<e', <v, z>>。最后反馈给leader，表明自己已经接受并处理了所有Ie'中的事务proposal。
步骤 L2.2 当leader接收到来自过半follower针对NEWLEADER(e', Ie')的ack后，就会向所有follower发commit消息。至此leader完成阶段二。
当follower收到leader的commit消息后，会依次处理并提交所有在Ie''中未处理的事务。至此follower完成阶段二。

阶段三：广播

完成同步之后，ZAB协议就可以正式开始接受客户端的事务请求，并进行消息广播流程。
步骤 L.3.1 Leader L接收到client新的事务请求后，会生成proposal，并根据ZXID的顺序向所有follower发送提案<e', <v, z>>，其中epoch(z) = e'。
步骤 F.3.1 follower根据消息接收的先后次序来处理这些来自leader的事务proposal，并将他们追加到hf中去，之后反馈给leader。
步骤 L.3.1 当leader接收到过半follower的针对proposal <e', <v, z>>的ack后，就会发送commit<e', <v, z>>消息给所有follower。
步骤 F.3.2 当follower F接收到来自leader的commit<e', <v, z>>后，会开始提交proposal<e', <v, z>>。需要注意的是，此时follower F必定已经提交了事务proposal <v', z'>, 其中<v', z'> 属于hf，z' < z。
在正常运行过程中，ZAB协议会一直运行于阶段三来反复地进行消息广播流程。如果出现leader崩溃或其他原因导致leader缺失，ZAB会再次进入阶段一。

运行分析

在ZAB协议的设计中，每个进程都可能处于以下三种状态之一：
- LOOKING: leader选举阶段
- FOLLOWING: follower和leader保持同步状态
- LEADING: leader作为主进程领导状态

ZAB与Paxos算法的联系与区别

ZAB协议并不是Paxos算法的一个典型实现。
两者的联系：
- 两者都存在一个类似于leader进程的角色，由其负责协调多个follower进程的运行；
- leader进程会等待超过半数的follower作出正确的反馈后，才会将一个提案进行提交；
- 在ZAB协议中，每个proposal都包含一个epoch值，用以代表当前的leader周期，在Paxos算法中，同样存在一个这样的标识，只是名字变成了Ballot。
在Paxos算法中，一个新选举的主进程会进行两个阶段的工作，第一阶段被称为读阶段，在这个阶段中，这个新的主进程会通过和所有其他进程进行通信的方式来收集上一个主进程提出的提案，并将它们提交。第二阶段称为写阶段，在这个阶段，当前主进程开始提出自己的提案。
ZAB协议在Paxos基础上，ZAB额外添加了一个同步阶段。在同步阶段之前，ZAB协议也存在一个和Paxos读阶段非常类似的过程，即发现阶段。在同步阶段，新的leader会确保存在过半的follower已经提交了之前leader周期中的所有事务proposal。一旦同步完成之后，ZAB就会执行和Paxos类似的写阶段。
总的来说，ZAB和Paxos算法的本质区别在于，两者的设计目标不太一样。ZAB主要用于构建一个高可用的分布式数据主备系统，例如zk。而Paxos算法则是用于构建一个分布式的一致性状态机系统。