谈谈谈zookeeper

    ZK采用树形结构，这棵树由节点组成，每个节点称为ZNode。ZNode引用方式是路径引用，比如/app1/p1，这样的层级结构让每个ZNode都有唯一的路径。每个ZNode兼具文件和目录的特点，既像文件一样维护着数据、元信息、ACL等数据结构，又像目录一样可以作为路径标识的一部分。每个ZNode节点由4部分组成：

• data：存储数据信息。
• stat：  ZNode的元数据，比如事务ID，时间戳，版本号，大小等。
• ACL：记录ZNode的访问权限，那些可以访问该节点。
• child：当前节点子节点的引用。

    ZK在内存中存储的数据形式为如上类似文件系统的数据结构，而持久化在磁盘中的数据为：快照+事务日志。

读锁/共享锁：

• 上读锁的前提：之前的锁没有写锁
• 创建临时顺序节点，(节点的数据可以是read，表示是读锁；)获取当前zk中序号比自己小的所有节点；判断最小节点是否是读锁，如果是则上锁成功；否则上锁失败，为最小节点设置监听，阻塞等待，通过watch机制当最小节点变化时通知当前节点，当前节点重新进行判断。

写锁：

• 上写锁的前提：之前没有锁
• 创建临时顺序节点，(节点的数据可以是write，表示是写锁；)获取子节点，判断自己是否是最小的节点；如果是则上锁成功；否则上锁失败，监听最小节点，最小节点变化后，重新进行判断。
• 羊/惊群效应：有一个锁存在的情况下，多个并发同时监听最小节点，尝试上写锁；当最小节点变化时，会触发多个监听事件，给ZK带来压力，可以调整为链式监听(监听前一个节点)。

1. 发出投票：每个服务器发出一个投票。由于是初始情况，Server1和Server2都会将自己作为Leader服务器来进行投票，每次投票会包含所推举的服务器的myid和ZXID，使用(myid, ZXID)来表示。此时Server1的投票为(1, 0)，Server2的投票为(2, 0)，它们各自将这个投票发给集群中其他机器；
2. 接收投票：接受来自各个服务器的投票。集群的每个服务器收到投票后，首先判断该投票的有效性，如检查是否是本轮投票、是否来自LOOKING状态的服务器；
3. 处理投票：针对每一个投票，服务器都将别人的投票和自己的投票进行PK，比较顺序：ZXID > myid(SID)。然后更新选票并重新投出；
4. 统计投票：每次投票后，服务器都会统计投票信息，判断是否已经有过半机器接受到相同的投票信息(一台机器收到超过半数的投票)。此时统计得出集群中的Server1、Server2这两台机器接受了(2, 0)的投票信息，便认为已经选出了Leader；
5. 变更状态：一旦确定了Leader，每个服务器就会更新自己的状态(LOOKING)，如果是Follower，那么就变更为FOLLOWING，如果是Leader，就变更为LEADING。

集群中存在Leader：

        某台机器加入/重新加入/启动较晚，其启动前集群已经在正常工作；此时，该机器只需和Leader建立连接并同步状态即可(试图选举Leader，被告知当前Leader信息)。

集群中不存在Leader:

   （Leader本身故障或集群中半数服务器无法与Leader通信）

1. 变更状态：Leader宕机后，余下的非Observer服务器会讲将自己的服务器状态变更为LOOKING，然后进入Leader选举过程；
2. 发出投票：在运行期间，每个服务器上的ZXID可能不同；
3. 接收投票：
4. 处理投票：先判断Epoch(小则丢弃，大则更新自己的投票)，一致则比较顺序：ZXID > myid
5. 统计投票：
6. 变更状态：

1. Client向ZK的Server1发送一个写请求；
2. 如果Server1不是Leader，则将接收到的写请求转发给Leader；然后Leader将数据写到本节点，并将写请求转发给每个Server；
3. 其他Server写入数据成功后，通知Leader；
4. 当Leader收到半数以上节点(包含自己)的写成功消息后，返回写成功消息给Follower。
5. 接受访问的Server1通知Client数据写成功。

相比数据写入流程，读取流程简单得多；因为每台server中数据一致性一样，所以随便访问任意server读数据都可以；没有写入流程中请求转发、数据同步、成功通知这些步骤。

       Zookeeper Atomic Broadcast是ZK的分布式一致性协议，其包含两种基本模式，分别是崩溃恢复和消息广播。

消息广播：

• [广播事务] 同一时刻只有一个主进程(Leader)以事务Proposal的形式将服务器数据状态广播到所有的副本进程(Follower)中；[广播提交] Leader接收到半数以上Follower的ACK后，会再次向所有Follower分发Commit消息(自身也会Commit)，要求将Proposal提交。
• Leader广播事务Proposal之前，会为该Proposal分配一个全局单调递增的ZXID(保证顺序一致性)
• Leader为每一个Follower分配了一个单独的队列，然后将需要广播的事务Proposal依次放入这些队列中，根据FIFO策略进行消息的发送。Follower收到Proposal后，会首先将其以事务日志的形式写入本地磁盘，写入成功后即向Leader返回ACK。

崩溃恢复：

• 消息广播可能因为Leader宕机导致数据不一致：

1. Leader提出一个Proposal后宕机，未向Follower分发完Proposal或未收到Follower的ACK；
2. Leader提交一个Proposal后宕机，未向Follower分发完Commit消息。

• 崩溃恢复需要满足要求：

1. 确保Leader提出，但未提交的Proposal被丢弃；
2. 确保Leader提交的Proposal，最终被所有Follower提交。

• 基于以上要求，Zab需要确保选举出来的Leader满足：

1. 不包含未提交的Proposal；
2. 含有最大的ZXID(避免Leader检查Proposal的提交和丢弃)。

• 崩溃恢复除Leader选举外，还包括数据恢复：新的Leader在开始正式工作前（接收事务请求，提出新的Proposal），会确认：

1. 事务日志中的所有Proposal是否已经被集群中过半的服务器Commit；
2. 所有的Follower都能接收到每一条事务的Proposal，并能将所有已提交的Proposal应用到内存数据中(等到Follower将所有未同步的事务Proposal从服务器上同步过并应用到内存数据后，Leader才认为该Follower可用)。

ZAB协议中的角色：

        Leader / Follower / Observer（不参与Proposal的投票和Leader的选举，在不影响集群事务处理能力的前提下，提升集群的非事务处理能力）

Paxos简介：

• Paxos解决如何在一个分布式系统中快速正确地对某个数据值达成一致，并且保证不论发生任何异常，都不会破坏该系统的一致性。

• 在Paxos中节点的角色有Proposer(提案者)、Acceptor(投票者)和Learner(提案接受者)，每个节点可身兼数职，其算法流程为：

1. [Prepare阶段] Proposer向多个Acceptor发出Proposal，请求Promise（此次Proposal中仅是一个全局唯一且递增的Proposal ID，不会携带Value)；
2. [Prepare阶段] Acceptor针对收到的Proposal请求，进行Promise；
3. [Accept阶段] Proposer收到多数Acceptor承诺的Promise后，向Accepter发出Propose请求（此次将Value放入Proposal中)；
4. [Accept阶段] Acceptor针对收到的Propose请求进行Accept处理；
5. [Learn阶段] Proposer将形成的决议发送给所有Learners。

• ZK保证的是CP，如leader选举时集群不可用。
• 一致性模型：前一致性 / 弱一致性(最终一致性是弱一致性的一种)。
• 分布式系统实现fault tolerance的一般解决方式是state machine replication。