Zookeeper与Paxos

zk是什么

zk是一个典型的分布式数据一致性的解决方案，分布式应用程序可以基于它实现数据分布/订阅、负载均衡、命名服务、分布式协调/通知、集群管理、Master选举、分布式锁和分布式队列等功能。zk可以保证如下分布式一致性性特征：

• 顺序一致性：从同一客户端发起的事务请求，最终将会严格按照其发起的顺序被应用到zk中去。
• 原子性
• 单一视图：集群中各个zk机器的数据模型都是一致的。
• 可靠性
• 实时性：zk仅保证一定的时间段内，客户端最终一定能够从服务端上读取到最新的数据状态。

zk的设计目标

zk致力于提供一个高性能，高可用、且具有严格的顺序访问控制能力的分布式协调服务。以下为四个设计目标：

• 目标一：简单的数据模型：数据全部存储在内存中，通过快照和事务日志保证可用性
• 目标二：可以构建集群
• 目标三：顺序访问：zk会为每个事务分配一个全局唯一的递增编号，这个编号反映了所有事务操作的先后顺序
• 目标四：高性能：更适用于以读未主的应用场景。

ZAB（zookeeper atomic brodcast）协议

所有事务请求必须由一个全局唯一的服务器来协调处理，这样的服务器称为Leader,而其他服务器称为Follower。Leader服务器负责将一个客户端事务请求转换成一个事务Proposal（提议）,并将该Proposal分发给集群中所有的Follower机器。之后Leader服务器需要等待所有Follower服务器的反馈，一旦超过半数的Follower机器进行了正确的反馈后，那么Leader就会再次向所有的Follower服务器分发Commit消息，要求其前一个Proposal进行提交。

协议介绍

重点介绍ZAB协议的消息广播和崩溃恢复过程：

消息广播

ZAB协议的消息广播过程使用的是一个原子广播协议，类似于一个二阶段提交过程。我们可以在过半的Follower服务器反馈ACK之后就开始提交事务Proposal了，而不需要等待集群中所有机器响应。消息是基于TCP协议来进行网络通信的。 具体的，在消息广播过程中，Leader服务器会为每一个Follower服务器都各自分配一个单独的队列，然后将需要广播的事务Proposal依次放入这些队列中去，并且根据FIFO策略进行消息发送。每一个Follower服务器在接收到这个事务Proposal后，都会首先将其以事务日志的形式写入到本地磁盘中去，并且成功后写入反馈给Leader服务器一个ACK响应。当Leader收到过半数的ACK响应后，就会广播一个Commit消息给所有Follower服务器以通知其进行事务提交，同时Leader自身也会完成对事务的提交，而每一个Follower服务器在接收到Commit消息后，也会完成对事务的提交。

崩溃恢复

ZAB协议需要一个高效且可靠的Leader选举算法，从而确保能够快速地选举出新的Leader，同时还要让集群中其他机器感知到新的Leader服务器。

Leader选举算法：能够确保提交已经被Leader提交的事务Proposal，同时丢弃已经被跳过的事务Proposal。只需要保证新leader拥有集群中所有机器最高编号（ZXID）的事务Proposal,同时可以省去Leader服务器检测Proposal的提交和丢弃的这一步操作了。

数据同步：主要ZXID来完成数据同步

深入ZAB协议

整个ZAB协议主要包括消息广播和崩溃恢复两个过程，进一步可以细分为三个阶段，分别是发现（Discovery）、同步（Synchronization）和广播（Broadcast）阶段。组成ZAB协议的每一个分布式进程，会循环地执行这三个阶段，我们将这样一个循环称为一个主进程周期。 下面是描述算法流程的定义标识和术语：

下面从我们就从发现、同步和广播三个阶段来讲解ZAB协议的内容： 阶段一：发现 关于这个epoch值e'，准leader L会从所有接收到的CEPOCH(F.p)消息中选取出最大的epoch值，然后对其进行加1操作，即为e'。 当Leader L接收来自过半Follower的确认消息ACK之后，Leader L就会从这过半的服务器中选取出一个Follower F,并使用其作为初始化事务集合Ie'。

阶段二：同步

阶段三：广播