@Author : Spinach | GHB
@Link : http://blog.csdn.net/bocai8058
文章目录
0 前言
为了高可用和数据安全起见，zk集群一般都是由几个节点构成(由n/2+1，投票机制决定，肯定是奇数个节点)。多节点证明它们之间肯定会有数据的通信，同时，为了能够使zk集群对外是透明的，一个整体对外提供服务，那么客户端访问zk服务器的数据肯定是要数据同步，也即数据一致性。
zk集群是Leader/Follower模式来保证数据同步的。整个集群同一时刻只能有一个Leader，其他都是Follower或Observer。Leader是通过选举选出来的，这里涉及到ZAB协议(原子消息广播协议)。
1 ZK数据一致性
- ① 顺序一致性（CAP理论的C）
来自任意特定客户端的更新都会按其发送顺序被提交。也就是说，如果一个客户端将Znode z的值更新为a，在之后的操作中，它又将z的值更新为b，则没有客户端能够在看到z的值是b之后再看到值a（如果没有其他对z的更新）。
- ② 原子性（CAP理论的A）
每个更新要么成功，要么失败。这意味着如果一个更新失败，则不会有客户端会看到这个更新的结果。
- ③ 单一系统映像
一个客户端无论连接到哪一台服务器，它看到的都是同样的系统视图。这意味着，如果一个客户端在同一个会话中连接到一台新的服务器，它所看到的系统状态不会比 在之前服务器上所看到的更老。当一台服务器出现故障，导致它的一个客户端需要尝试连接集合体中其他的服务器时，所有滞后于故障服务器的服务器都不会接受该 连接请求，除非这些服务器赶上故障服务器。
- ④ 持久性
一个更新一旦成功，其结果就会持久存在并且不会被撤销。这表明更新不会受到服务器故障的影响。
1.1 ZK选举
- 何时触发选举
选举Leader不是随时选举的，毕竟选举有产生大量的通信，造成网络IO的消耗。因此下面情况才会出现选举：
集群启动
服务器处于寻找Leader状态
当服务器处于LOOKING状态时，表示当前没有Leader，需要进入选举流程
崩溃恢复
Leader宕机
网络原因导致过半节点与Leader心跳中断
- 如何成为Leader
数据新旧程度
只有拥有最新数据的节点才能有机会成为Leader
通过zxid的大小来表示数据的新，zxid越大代表数据越新
myid
集群启动时，会在data目录下配置myid文件，里面的数字代表当前zk服务器节点的编号
当zk服务器节点数据一样新时， myid中数字越大的就会被选举成ОLeader
当集群中已经有Leader时，新加入的节点不会影响原来的集群
投票数量
只有得到集群中多半的投票，才能成为Leader
多半即：n/2+1,其中n为集群中的节点数量
- 重要的zxid
zxid由两部分构成：主进程周期epoch和事务单调递增的计数器。zxid是一个64位的数，高32位代表主进程周期epoch，低32位代表事务单调递增的计数器。
主进程周期epoch也叫epoch，是选举的轮次，每选举一次就递增1。事务单调递增的计数器在每次选举完成之后就会从0开始。
如果是比较数据新旧的话，直接比较就可以了。因为如果是主进程周期越大，即高32位越大，那么低32位就不用再看了。如果主进程周期一致，低32位越大，整个zxid就越大。所以直接比较整个64位就可以了，不必高32位于高32位对比，低32位与低32位比较。
示例如下：
在选举的时候是投票方式进行的，除主进程周期外，投票格式为(myid,zxid)。
第一种情况，比较容易理解，下面以3台机器为例子。
三个zk节点A，B，C，三者开始都没有数据，即Zxid一致，对应的myid为1，2，3。
A启动myid为1的节点，zxid为0，此时只有一台服务器无法选举出Leader
B启动myid为2的节点，zxid为0，B的zxid与A一样，比较myid，B的myid为2比A为1大，B成Leader
C启动myid为3的节点，因为已经有Leader节点，则C直接加入集群，承认B是leader
第二种情况，已5台机器为例子。
五个节点A，B，C，D，E，B是Leader，其他是Follower，myid分别为1，2，3，4，5，zxid分别为3，4，5，6，6。运行到某个时刻时A，B掉线或宕机，此时剩下C D E。在同一轮选举中，C，D，E分别投自己和交叉投票。
第一次投票，都是投自己。
投票情况为：C:(3,5) D:(4,6) E:(5,6)。
同时也会收到其他机器的投票。
投票情况为：C:(3,5)(4,6)(5,6)，D:(4,6)(3,5)(5,6)，E:(5,6)(4,6)(3,5)
机器内部会根据选主原则对比投票，变更投票，投票情况为：C:(3,5)(4,6)(5,6)【不变更】。 D:(4,6)(4,6)(5,6)【变更】。E:(5,6)(5,6)(5,6)【变更】
统计票数，C-1票，D-3票，E-5票。因此E成为Leader。
接下来就是对新Leader节点的检查，数据同步，广播，对外提供服务。
注：具体选举过程请参考 40_ZooKeeper选举制度.md
1.2 ZK原子广播机制(ZAB协议)
graph LR
A[Zab]-->B[恢复模式]
A-->C[广播模式]
- 恢复模式
当服务启动或者在领导者崩溃后，Zab就进入了恢复模式，当领导者被选举出来，且大多数server完成了和leader的状态同步以后，恢复模式就结束了。状态同步保证了leader和server具有相同的系统状态。
- 广播模式
一旦Leader已经和多数的Follower进行了状态同步后，他就可以开始广播消息了，即进入广播状态。这时候当一个Server加入ZooKeeper服务中，它会在恢复模式下启动，发现Leader，并和Leader进行状态同步。待到同步结束，它也参与消息广播。ZooKeeper服务一直维持在Broadcast状态，直到Leader崩溃了或者Leader失去了大部分的Followers支持。
1.2.1 广播模式
广播模式类似一个简单的两阶段提交：接收读写请求，广播发送后待收到ack后，提交事务。
graph TB
A[leader]-->|1.proposal| B[follower]
A[leader]-->|1.proposal| C[follower]
B-->|2.ack|A
C-->|2.ack|A
A-->|3.commit|B
A-->|3.commit|C
广播协议在所有的通讯过程中使用TCP的FIFO信道，通过使用该信道，使保持有序性变得非常的容易。通过FIFO信道，消息被有序的deliver。只要收到的消息一被处理，其顺序就会被保存下来。
Leader会广播已经被deliver的Proposal消息。在发出一个Proposal消息前，Leader会分配给Proposal一个单调递增的唯一id，称之为zxid。因为Zab保证了因果有序， 所以递交的消息也会按照zxid进行排序。广播是把Proposal封装到消息当中，并添加到指向Follower的输出队列中，通过FIFO信道发送到 Follower。当Follower收到一个Proposal时，会将其写入到磁盘，可以的话进行批量写入。一旦被写入到磁盘媒介当 中，Follower就会发送一个ACK给Leader。 当Leader收到了指定数量的ACK时，Leader将广播commit消息并在本地deliver该消息。当收到Leader发来commit消息时，Follower也会递交该消息。过程如下：
- 集群选举完成，并且完成数据同步后，开始对外服务，接收读写请求
- 当leader接收到客户端新的事务请求后，会生成对新的事务proposal，并根据zxid的顺序向所有的follower分发事务proposal
- 当follower收到leader的proposal时，根据接收的先后顺序处理proposal
- 当Leader收到follower针对某个proposal过半的ack后，则发起事务提交，重新发起一个commit的proposal
- Follower收到commit的proposal后，记录事务提交，并把数据更新到内存数据库
# 补充说明
由于只有过半的机器给出反馈，则可能存在某时刻某些节点数据不是最新的
如果需要确定读取到的数据是最新的，则可以在读取之前，调用sync方法进行数据同步
需要注意的是，该简化的两阶段提交自身并不能解决Leader故障，所以添加恢复模式来解决Leader故障。
1.2.2 恢复模式
正常工作时，Zab协议会一直处于广播模式，直到Leader故障或失去了指定数量的Followers。 为了保证进度，恢复过程中必须选举出一个新Leader，并且最终让所有的Server拥有一个正确的状态。对于Leader选举，需要一个能够成功高几率的保证存活的算法。Leader选举协议，不仅能够让一个Leader得知它是leader，并且有指定数量的Follower同意该决定。如果Leader选举阶段发生错误，那么Servers将不会取得进展。最终会发生超时，重新进行Leader选举。在我们的实现中，Leader选举有两种不同的实现方式。如果有指定数量的Server正常运行，快速选举的完成只需要几百毫秒。
该恢复过程的复杂部分是在一个给定的时间内，提议冲突的绝对数量。最大数量冲突提议是一个可配置的选项，但是默认是1000。为了使该协议能够即使在Leader故障的情况下也能正常运作。我们需要做出两条具体的保证：
① 我们绝不能遗忘已经被deliver的消息，若一条消息在一台机器上被deliver，那么该消息必须将在每台机器上deliver。
② 我们必须丢弃已经被skip的消息。
如果Leader选举协议保证了新Leader在Quorum Server中具有最高的提议编号，即Zxid最高。那么新选举出来的leader将具有所有已deliver的消息。新选举出来的Leader，在提出一个新消息之前，首先要保证事务日志中的所有消息都由Quorum Follower已Propose并deliver。需要注意的是，我们可以让新Leader成为一个用最高zxid来处理事务的server，来作为一个优化。这样，作为新被选举出来的Leader，就不必去从一组Followers中找出包含最高zxid的Followers和获取丢失的事务。
- ① 第一条
所有的正确启动的Servers，将会成为Leader或者跟随一个Leader。Leader能够确保它的Followers看到所有的提议，并deliver所有已经deliver的消息。通过将新连接上的Follower所没有见过的所有PROPOSAL进行排队，并之后对该Proposals的COMMIT消息进行排队，直到最后一个COMMIT消息。在所有这样的消息已经排好队之后，Leader将会把Follower加入到广播列表，以便今后的提议和确认。这一条是为了保证一致性，因为如果一条消息P已经在旧Leader-Server1中deliver了，即使它刚刚将消息P deliver之后就挂了，但是当旧Leader-Server1重启恢复之后，我们的Client就可以从该Server中看到该消息P deliver的事务，所以为了保证每一个client都能看到一个一致性的视图，我们需要将该消息在每个Server上deliver。
- ② 第二条
skip已经Propose，但不能deliver的消息，处理起来也比较简单。在我们的实现中，Zxid是由64位数字组成的，低32位用作简单计数器。高32位是一个epoch。每当新Leader接管它时，将获取日志中Zxid最大的epoch，新Leader Zxid的epoch位设置为epoch+1，counter位设置0。用epoch来标记领导关系的改变,并要求Quorum Servers 通过epoch来识别该leader，避免了多个Leader用同一个Zxid发布不同的提议。
这个方案的一个优点就是，可以skip一个失败的领导者的实例，从而加速并简化了恢复过程。如果一台宕机的Server重启，并带有未发布的 Proposal，那么先前的未发布的所有提议将永不会被deliver。并且它不能够成为一个新leader，因为任何一种可能的Quorum Servers，都会有一个Server其Proposal 来自于一个新epoch，因此它具有一个较高的zxid。
1.2.3 Paxos与Zab一致性对比
Paxos的一致性不能达到ZooKeeper的要 求，我们可以下面一个例子。我们假设ZK集群由三台机器组成，Server1、Server2、Server3。Server1为Leader，他生成了 三条Proposal，P1、P2、P3。但是在发送完P1之后，Server1就挂了。
Server1挂掉之后，Server3被选举成为Leader，因为在Server3里只有一条Proposal—P1。所以，Server3在P1的基础之上又发出了一条新Proposal—P2＇，P2＇的Zxid为02。
Server2发送完P2＇之后，它也挂了。此时Server1已经重启恢复，并再次成为了Leader。那么，Server1将发送还没有被deliver的Proposal—P2和P3。由于Follower-Server2中P2＇的Zxid为02和Leader-Server1中P2的Zxid相等，所以P2会被拒绝。而P3，将会被Server2接受。
我们分析一下Follower-Server2中的Proposal，由于P2’将P2的内容覆盖了。所以导致，Server2中的Proposal-P3无法生效，因为他的父节点并不存在。
首先来分析一下，上面的示例中为什么不满足ZooKeeper需求。ZooKeeper是一个树形结构，很多操作都要先检查才能确定能不能执行，比如，在图3.8中Server2有三条Proposal。P1的事务是创建节点"/zk"，P2’是创建节点"/c"，而P3是创建节点 “/a/b”,由于"/a"还没建，创建"a/b"就搞不定了。那么，我们就能从此看出Paxos的一致性达不到ZooKeeper一致性的要求。
为了达到ZooKeeper所需要的一致性，ZooKeeper采用了Zab协议。Zab做了如下几条保证，来达到ZooKeeper要求的一致性。
- Zab要保证同一个leader的发起的事务要按顺序被apply，同时还要保证只有先前的leader的所有事务都被apply之后，新选的leader才能在发起事务。
- 一些已经Skip的消息，需要仍然被Skip。
我想对于第一条保证大家都能理解，它主要是为了保证每 个Server的数据视图的一致性。我重点解释一下第二条，它是如何实现。为了能够实现，Skip已经被skip的消息。我们在Zxid中引入了 epoch，如下图所示。每当Leader发生变换时，epoch位就加1，counter位置0。
我们继续使用上面的例子，看一下他是如何实现Zab的 第二条保证的。我们假设ZK集群由三台机器组成，Server1、Server2、Server3。Server1为Leader，他生成了三条 Proposal，P1、P2、P3。但是在发送完P1之后，Server1就挂了。
Server1挂掉之后，Server3被选举成为 Leader，因为在Server3里只有一条Proposal—P1。所以，Server3在P1的基础之上又发出了一条新Proposal—P2＇， 由于Leader发生了变换，epoch要加1，所以epoch由原来的0变成了1，而counter要置0。那么，P2＇的Zxid为10。
Server2发送完P2＇之后，它也挂了。此时Server1已经重启恢复，并再次成为了Leader。那么，Server1将发送还没有被deliver的Proposal—P2和P3。由于Server2中P2＇的Zxid为10，而Leader-Server1中P2和P3的Zxid分别为02和03，P2＇的epoch位高于P2和P3。所以此时Leader-Server1的P2和P3都会被拒绝,那么我们Zab的第二条保证也就实现了。
1.3 ZK数据同步机制
1.3.1 同步准备
完成选举之后，为了数据一致性，需要进行数据同步流程。
Leader准备
Leader告诉其它follower当前最新数据是什么即zxid
Leader构建一个NEWLEADER的包，包括当前最大的zxid，发送给所有的follower或者Observer
Leader给每个follower创建一个线程LearnerHandler来负责处理每个follower的数据同步请求，同时主线程开始阻塞，等到超过一半的follwer同步完成，同步过程才完成，leader才真正成为leaderFollower准备
选举完成后，尝试与leader建立同步连接，如果一段时间没有连接上就报连接超时，重新回到选举状态FOLLOWING
向leader发送FOLLOWERINFO包，带上follower自己最大的zxid
1.3.2 同步初始化
同步初始化涉及到三个东西：minCommittedLog、maxCommittedLog、zxid
– minCommittedLog:最小的事务日志id，即zxid没有被快照存储的日志文件的第一条，每次快照存储
完，会重新生成一个事务日志文件
– maxCommittedLog:事务日志中最大的事务，即zxid
1.3.3 数据同步场景
直接差异化同步(DIFF同步)
仅回滚同步TRUNCͨ，即删除多余的事务日志，比如原来的Leader宕机后又重新加入，可能存在它自己写
入提交但是别的节点还没来得及提交
先回滚再差异化同步(TRUNC+DIFF同步)
全量同步(SNAP同步)
不同的数据同步算法适用不同的场景。
ZK读写机制
- client向zk中的server发送写请求，如果该server不是leader，则会将该写请求转发给leader server，leader将请求事务以proposal形式分发给follower；
- 当follower收到收到leader的proposal时，根据接收的先后顺序处理proposal；
- 当Leader收到follower针对某个proposal过半的ack后，则发起事务提交，重新发起一个commit的proposal
- Follower收到commit的proposal后，记录事务提交，并把数据更新到内存数据库；
- 当写成功后，反馈给client。
- client可以对zk中的任意一个server(因为zk数据是一致性的)发出读请求，然后server反馈给client读出的数据结果。
引用：https://www.jianshu.com/p/57fecbe70540
| http://www.cnblogs.com/wuxl360/p/5817646.html | 部分内容参考了一篇论文“A simple totally ordered broadcast protocol”