ZooKeeper原理总结
主要参考了Guide哥和Hollis哥的文章以及其他一些技术视频。
1.Paxos算法
Paxos算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一，其解决的问题就是在分布式系统中如何就某个值（决议）达成一致 。
在Paxos中主要有三个角色，分别为Proposer提案者、Acceptor表决者、Learner学习者。Paxos算法和2PC一样，也有两个阶段，分别为prepare和accept阶段。
1.1prepare阶段
Proposer提案者：负责提出proposal，每个提案者在提出提案时都会首先获取到一个具有全局唯一性的、递增的提案编号N，即在整个集群中是唯一的编号N，然后将该编号赋予其要提出的提案，在第一阶段是只将提案编号发送给所有的表决者。Acceptor表决者：每个表决者在accept某提案后，会将该提案编号N记录在本地，这样每个表决者中保存的已经被accept的提案中会存在一个编号最大的提案，其编号假设为maxN。每个表决者仅会accept编号大于自己本地maxN的提案，在批准提案时表决者会将以前接受过的最大编号的提案作为响应反馈给Proposer。
1.2accept阶段
当一个提案被Proposer提出后，如果Proposer收到了超过半数的Acceptor的批准（Proposer本身同意），那么此时Proposer会给所有的Acceptor发送真正的提案（你可以理解为第一阶段为试探），这个时候Proposer就会发送提案的内容和提案编号。
表决者收到提案请求后会再次比较本身已经批准过的最大提案编号和该提案编号，如果该提案编号 大于等于已经批准过的最大提案编号，那么就accept该提案（此时执行提案内容但不提交），随后将情况返回给Proposer。如果不满足则不回应或者返回NO。
当Proposer收到超过半数的accept，那么它这个时候会向所有的acceptor发送提案的提交请求。需要注意的是，因为上述仅仅是超过半数的acceptor批准执行了该提案内容，其他没有批准的并没有执行该提案内容，所以这个时候需要向未批准的acceptor发送提案内容和提案编号并让它无条件执行和提交，而对于前面已经批准过该提案的acceptor来说仅仅需要发送该提案的编号，让acceptor执行提交就行了。
而如果Proposer如果没有收到超过半数的accept那么它将会将递增该Proposal的编号，然后 重新进入Prepare阶段 。
1.3Paxos算法的死循环问题
比如说，此时提案者P1提出一个方案M1，完成了Prepare阶段的工作，这个时候acceptor则批准了M1，但是此时提案者P2同时也提出了一个方案M2，它也完成了Prepare阶段的工作。然后P1的方案已经不能在第二阶段被批准了（因为acceptor已经批准了比M1更大的M2），所以P1自增方案变为M3重新进入Prepare阶段，然后acceptor又批准了新的M3方案，它又不能批准M2了，这个时候M2又自增进入Prepare阶段。。。
就这样无休无止的永远提案下去，这就是Paxos算法的死循环问题。
那么如何解决呢？很简单，人多了容易吵架，我现在 就允许一个能提案 就行了。
2.ZAB协议
2.1ZooKeeper架构
作为一个优秀高效且可靠的分布式协调框架，ZooKeeper在解决分布式数据一致性问题时并没有直接使用Paxos，而是专门定制了一致性协议叫做ZAB(ZooKeeper Atomic Broadcast) 原子广播协议，该协议能够很好地支持 崩溃恢复 。
2.2ZAB中的角色
和介绍Paxos一样，在介绍ZAB协议之前，我们首先来了解一下在ZAB中三个主要的角色，Leader领导者、Follower跟随者、Observer观察者。
Leader：集群中唯一的写请求处理者，能够发起投票（投票也是为了进行写请求）。Follower：能够接收客户端的请求，如果是读请求则可以自己处理，如果是写请求则要转发给Leader。在选举过程中会参与投票，有选举权和被选举权 。Observer：就是没有选举权和被选举权的Follower。
在ZAB协议中对zkServer(即上面我们说的三个角色的总称) 还有两种模式的定义，分别是消息广播和崩溃恢复。
2.3消息广播模式
说白了就是ZAB协议是如何处理写请求的，上面我们不是说只有Leader能处理写请求嘛？那么我们的Follower和Observer是不是也需要同步更新数据呢？总不能数据只在Leader中更新了，其他角色都没有得到更新吧？
不就是 在整个集群中保持数据的一致性 嘛？如果是你，你会怎么做呢？
废话，第一步肯定需要Leader将写请求广播出去呀，让Leader问问Followers是否同意更新(Observer不参与数据一致性更新过程)，如果超过半数以上的同意那么就进行Follower和Observer的更新（和Paxos一样）。当然这么说有点虚，画张图理解一下。
嗯。。。看起来很简单，貌似懂了 🤥🤥🤥。这两个Queue哪冒出来的？答案是**ZAB需要让Follower和Observer保证顺序性** 。何为顺序性，比如我现在有一个写请求A，此时Leader将请求A广播出去，因为只需要半数同意就行，所以可能这个时候有一个FollowerF1因为网络原因没有收到，而Leader又广播了一个请求B，因为网络原因，F1竟然先收到了请求B然后才收到了请求A，这个时候请求处理的顺序不同就会导致数据的不同，从而产生数据不一致问题。
所以在Leader这端，它为每个其他的zkServer准备了一个队列，采用先进先出的方式发送消息。由于协议是**通过TCP**来进行网络通信的，保证了消息的发送顺序性，接受顺序性也得到了保证。
除此之外，在ZAB中还定义了一个**全局单调递增的事务ID ZXID**，它是一个64位long型，其中高32位表示epoch年代，低32位表示事务id。epoch是会根据Leader的变化而变化的，当一个Leader挂了，新的Leader上位的时候，年代（epoch）就变了。而低32位可以简单理解为递增的事务id。
定义这个的原因也是为了顺序性，每个proposal在Leader中生成后需要通过其ZXID来进行排序，才能得到处理。
2.4崩溃恢复模式
说到崩溃恢复我们首先要提到ZAB中的Leader选举算法，当系统出现崩溃影响最大应该是Leader的崩溃，因为我们只有一个Leader，所以当Leader出现问题的时候我们势必需要重新选举Leader 。
Leader选举可以分为两个不同的阶段，第一个是我们提到的Leader宕机需要重新选举，第二则是当Zookeeper启动时需要进行系统的Leader初始化选举。下面我先来介绍一下ZAB是如何进行初始化选举的。
假设我们集群中有 3 台机器，那也就意味着我们需要两台以上同意（超过半数）。比如这个时候我们启动了server1，它会首先投票给自己，投票内容为服务器的myid和ZXID，因为初始化所以ZXID都为0，此时server1发出的投票为(1,0)。但此时server1的投票仅为1，所以不能作为Leader，此时还在选举阶段所以整个集群处于**Looking状态**。
接着server2启动了，它首先也会将投票选给自己(2,0)，并将投票信息广播出去（server1也会，只是它那时没有其他的服务器了），server1在收到server2的投票信息后会将投票信息与自己的作比较。首先它会比较ZXID，ZXID大的优先为Leader，如果相同则比较myid，myid大的优先作为Leader。所以此时server1发现server2更适合做Leader，它就会将自己的投票信息更改为(2,0)然后再广播出去，之后server2收到之后发现和自己的一样无需做更改，并且自己的投票已经超过半数，则**确定server2为Leader**，server1也会将自己服务器设置为Following变为Follower。整个服务器就从Looking变为了正常状态。
当server3启动发现集群没有处于Looking状态时，它会直接以Follower的身份加入集群。
还是前面三个server的例子，如果在整个集群运行的过程中server2挂了，那么整个集群会如何重新选举Leader呢？其实和初始化选举差不多。
首先毫无疑问的是剩下的两个Follower会将自己的状态从Following变为Looking状态，然后每个server会向初始化投票一样首先给自己投票（这不过这里的zxid可能不是0了，这里为了方便随便取个数字）。
假设server1给自己投票为(1,99)，然后广播给其他server，server3首先也会给自己投票(3,95)，然后也广播给其他server。server1和server3此时会收到彼此的投票信息，和一开始选举一样，他们也会比较自己的投票和收到的投票（zxid大的优先，如果相同那么就myid大的优先）。这个时候server1收到了server3的投票发现没自己的合适故不变，server3收到server1的投票结果后发现比自己的合适于是更改投票为(1,99)然后广播出去，最后server1收到了发现自己的投票已经超过半数就把自己设为Leader，server3也随之变为Follower。
那么说完了ZAB中的Leader选举方式之后我们再来了解一下 崩溃恢复 是什么玩意？
其实主要就是 当集群中有机器挂了，我们整个集群如何保证数据一致性？
如果只是Follower挂了，而且挂的没超过半数的时候，因为我们一开始讲了在Leader中会维护队列，所以不用担心后面的数据没接收到导致数据不一致性。
如果Leader挂了那就麻烦了，我们肯定需要先暂停服务变为Looking状态然后进行Leader的重新选举（上面我讲过了），但这个就要分为两种情况了，分别是 确保已经被Leader提交的提案最终能够被所有的Follower提交 和 跳过那些已经被丢弃的提案 。
确保已经被Leader提交的提案最终能够被所有的Follower提交是什么意思呢？
假设Leader (server2)发送commit请求（忘了请看上面的消息广播模式），他发送给了 server3，然后要发给server1的时候突然挂了。这个时候重新选举的时候我们如果把server1作为Leader的话，那么肯定会产生数据不一致性，因为server3肯定会提交刚刚server2发送的commit请求的提案，而server1根本没收到所以会丢弃。
那怎么解决呢？
聪明的同学肯定会质疑，这个时候server1已经不可能成为Leader了，因为server1和server3进行投票选举的时候会比较ZXID，而此时server3的ZXID肯定比server1的大了。(不理解可以看前面的选举算法)
那么跳过那些已经被丢弃的提案又是什么意思呢？
假设Leader (server2)此时同意了提案N1，自身提交了这个事务并且要发送给所有 Follower要commit的请求，却在这个时候挂了，此时肯定要重新进行Leader的选举，比如说此时选server1为Leader（这无所谓）。但是过了一会，这个挂掉的Leader又重新恢复了，此时它肯定会作为Follower的身份进入集群中，需要注意的是刚刚server2已经同意提交了提案N1，但其他server并没有收到它的commit信息，所以其他server不可能再提交这个提案N1了，这样就会出现数据不一致性问题了，所以该提案N1最终需要被抛弃掉。
3.ZooKeeper的Watcher原理
在Zookeeper中，watch机制是一种非常重要的特性，它能够让应用程序监听Zookeeper上节点的变化，从而及时做出响应。Zookeeper的watch机制实现中，涉及到多个概念，首先是客户端和服务端，这个好理解，Zookeeper的集群就是服务端，调用ZK服务的机器就是客户端。
还有两个模块，分别叫做WatchManager和ZkWatcherManager。
- WatchManager是Zookeeper服务端内部的一个模块，用于管理所有watcher的相关操作，包括watcher的注册、注销、触发等。
- ZkWatcherManager是Zookeeper客户端中的一个模块，用于管理客户端中watcher的相关操作，包括创建watcher、注册watcher、处理watcher事件等。
了解了这几个概念之后，再来说一下ZK的watch机制是如何工作的:
- 客户端连接到Zookeeper服务端，客户端创建一个ZkWatcherManager实例，用于管理客户端中所有的watcher。
- 当客户端想要监控某个znode节点时，它可以调用ZkWatcherManager中的方法创建watcher并将其注册到客户端中。客户端将watcher的信息发送到Zookeeper服务端
- Zookeeper服务端接收到客户端发送的watcher信息后，会将该watcher信息交给WatchManager处理。WatchManager会将该watcher注册到相应的znode节点上，并将watcher相关的信息保存在内存中。
- 当znode节点发生变化时，WatchManager会通知Zookeeper Server。
- Zookeeper Server会根据变化类型通知相应的客户端，告知它们发生了哪些变化。
- 当客户端接收到Zookeeper Server的通知后，ZkWatcherManager会根据watcher的类型(data watcher或child watcher）来触发相应的事件处理方法，例如data watcher会触发processDataChanged()方法，child watcher会触发processChildChanged()方法等。
