[大数据]Zookeeper及分布式理论

Zookeeper详解

1、简介

1) 什么是ZooKeeper？

Zookeeper 分布式服务框架是Apache Hadoop的一个子项目，它是一个针对大型分布式系统的高可用、高性能且具有一致性的开源协调服务，它主要是用来解决分布式应用中经常遇到的一些数据管理问题，可以高可靠的维护元数据。提供的功能包括：配置维护、名字服务、分布式同步、组服务等。ZooKeeper的设计目标就是封装好复杂易出错的关键服务，将简单易用的接口和性能高效、功能稳定的系统提供给用户。

ZooKeeper在实现这些服务时，首先它设计了一种新的数据结构——Znode，然后在该数据结构的基础上定义了一些原语，也就是一些关于该数据结构的一些操作。有了这些数据结构和原语还不够，因为ZooKeeper是工作在一个分布式的环境下，服务是通过消息以网络的形式发送给分布式应用程序的，所以还需要一个通知机制——Watcher机制。总结一下，ZooKeeper所提供的服务主要是通过：数据结构+原语+Watcher机制，三个部分来实现的。

2) Znode

理解ZooKeeper的一种方法就是将其看作一个具有高可用性的文件系统。但这个文件系统中没有文件和目录，而是统一使用“节点”(node)的概念，称为Znode。Znode既可以作为保存数据的容器（如同文件），也可以作为保存其他Znode的容器（如同目录）。所有的Znode构成一个层次化的命名空间。一种自然的建立组成员列表的方式就是利用这种层次结构，创建一个以组名为节点名的Znode作为父节点，然后以组成员名为节点名来创建作为子节点的Znode。ZK是将全量的数据存在内存中。

有四种类型的Znode：

1、PERSISTENT——持久化节点

客户端与ZooKeeper断开连接后，该节点依旧存在

2、 PERSISTENT_SEQUENTIAL——持久化顺序编号节点

客户端与ZooKeeper断开连接后，该节点依旧存在，只是Zookeeper给该节点名称进行顺序编号

3、EPHEMERAL——临时节点

客户端与ZooKeeper断开连接后，该节点被删除

4、EPHEMERAL_SEQUENTIAL——临时顺序编号节点

客户端与ZooKeeper断开连接后，该节点被删除，只是Zookeeper给该节点名称进行顺序编号

3)ZK集群模式

单机模式

伪集群模式

集群模式

4)Watcher

ZooKeeper为解决数据的一致性，使用了Watcher的异步回调接口，将服务端Znode的变化以事件的形式通知给客户端，让客户端可以做出及时响应。

5)工作流程

比如，一个Zookeeper集群中有五台机器，在整个集群刚刚启动的时候，会进行Leader选举，当Leader确定之后，其他机器自动成为Follower，并和Leader建立长连接，用于数据同步和请求转发等。若是读请求，则由每台Server直接响应。当有客户端机器的写请求落到Follower机器上的时候，Follower机器会把请求转发给Leader，由Leader处理该请求，在请求处理完之后再把数据同步给所有的Follower，然后在返回给客户端。

6）如何查看一个节点是否是Leader？

./zkServer.sh status 2>/dev/null | grep Mode

7）为什么要奇数个节点？

为了确保ZooKeeper服务的稳定与可靠性，通常是搭建成一个ZK集群来对外提供服务。关于ZooKeeper，需要明确一个很重要的特性：集群中只要有过半的机器是正常工作的，那么整个集群对外就是可用的。基于这个特性，那么如果想搭建一个能够允许F台机器down掉的集群，那么就要部署一个由2*F+1 台机器构成的ZK集群。因此一个由3台机器构成的ZK集群，能够在down掉一台机器后依然正常工作，而5台机器的集群，能够对两台机器down掉的情况容灾。注意，如果是一个6台机器构成的ZK集群，同样只能够down掉两台机器，因为如果down掉3台，剩下的机器就没有过半了。基于这个原因，ZK集群通常设计部署成奇数台机器。

8）ZK server类型

ZK server根据其身份特性分为三种：Leader，Follower，Observer，其中Follower和Observer又统称Learner（学习者）。

Leader：负责进行投票的发起和决议，更新系统状态。可为客户端提供读和写请求

Follower：负责客户端的reader类型请求，参与Leader选举等

Observer：特殊的“Follower”，其可以接受客户端reader请求，但不参与选举。

9）为什么要引入Observer

在ZooKeeper中引入Observer，主要是为了使ZooKeeper具有更好的可伸缩性。这里的可伸缩性是指工作负载可以通过给系统分配更多的资源来分担，一个不可伸缩的系统却无法通过增加资源来提升性能，甚至会在工作负载增加时，性能急剧下降。

在Observer出现以前，ZooKeeper的伸缩性由Follower来实现，可以通过添加Follower节点的数量来保证ZooKeeper服务的读性能。但是随着Follower节点数量的增加，ZooKeeper服务的写性能受到了影响。为什么会出现这种情况呢？就需要先了解一下这个"ZK服务"是如何工作的。

ZooKeeper服务中的每个Server可服务于多个Client，并且Client可连接到ZK服务中的任一台Server来提交请求。若是读请求，则由每台Server直接响应。若是改变Server状态的写请求，需要通过一致性Zab协议来处理。简单来说，Zab协议规定：来自Client的所有写请求，都要转发给ZK服务中唯一的Server——Leader，由Leader根据该请求发起一个Proposal。然后其他的Server对该Proposal进行Vote。之后，Leader对Vote进行收集，当Vote数量过半时Leader会向所有的Server发送一个通知消息。最后，当Client所连接的Server收到该消息时，会把该操作更新到内存中并对Client的写请求做出响应。该工作流程如下图所示。

10）zk的特性

1.顺序一致性。同一个客户端发起的事务请求，严格按照发起顺序应用到zk中去。

2.原子性。所有事务的处理结果在整个集群中所有机器应用情况一致，要么都成功，要么都失败。

3.单一视图。无论客户端连接的是哪个zk服务器，看到的数据模型都一样。

4.可靠性。

5.实时性。保证一定的时间段内，客户端最终一定能读到最新到的数据状态。

11）与chubby对比

• Chubby 是 Google 的，完全实现 Paxos 算法，不开源。

• Zookeeper 是 Chubby 的开源实现，使用 ZAB 协议(Paxos 算法的变种)。

12）应用场景

• 负载均衡

基于ZK的动态DNS方案描述如下：
1.创建一个节点进行配置映射，如/root/app1/server.app1.com
2.在app1这个节点每个应用都可以将自己的域名配置上去
3.域名解析由应用自己负责（读zk并watch）
4.域名变更会告知客户端更新
5.每个服务都启动时将自己的域名注册进去

• 统一命名服务

命名服务是指通过指定的名字来获取资源或服务的地址，利用zk创建一个全局的路径，即时唯一的路径，这个路径就可以作为一个名字，指向集群中机器或者提供服务的地址，又或者一个远程的对象等。

• 配置管理

例如说，Spring Cloud Config Zookeeper ，就实现了基于 Zookeeper 的 Spring Cloud Config 的实现，提供配置中心的服务。基本的流程是服务启动时都会去get配置节点内容，同时注册一个watch事件。这样配置发生变化时都会通知给订阅者。一般来说配置需要具有以下特点：1.数据量不大；2.内容会动态变化；3.需要各个机器一致。
?

• 注册与发现

是否有机器加入或退出
?
所有机器约定在父目录下创建临时目录节点，然后监听父目录节点下的子节点变化。一旦有机器挂掉，该机器与 ZooKeeper 的连接断开，其所创建的临时目录节点也被删除，所有其他机器都收到通知：某个节点被删除了。

• master选举

基于 Zookeeper 实现分布式协调，从而实现主从的选举。这个在 Kafka、Elastic-Job 等等中间件，都有所使用到。
步骤十分容易：
1.每个子系统都向一个路径创建一个临时节点，那么只有一个能够创建成功，成功的那个就是多个子系统的主
2.各个子系统都会watch这个节点，假如发现这个临时节点没有了（挂了），就重新开始选举

• 分布式锁

有了 ZooKeeper 的一致性文件系统，锁的问题变得容易。锁服务可以分成两类，一个是保持独占，另一个是控制时序。
?
1、保持独占，我们把 znode 看作是一把锁，通过 createZnode 的方式来实现。所有客户端都去创建 /distribute_lock 节点，最终成功创建的那个客户端也即拥有了这把锁。用完删除掉自己创建的 /distribute_lock 节点就释放出锁。
2、控制时序，/distribute_lock 已经预先存在，所有客户端在它下面创建临时顺序编号目录节点，和 Master 一样，编号最小的获得锁，用完删除，依次方便。
?
-----
排他锁：
1.获取锁，针对同一路径/root/lock创建临时子节点，最终只有一个客户端创建成功（获得了锁），没有创建成功的客户端要watch这个节点。
2.释放锁，当上述节点被移除之后，客户端得到通知，重新获取锁。
?
共享锁
1.获取锁，比如创建类似/root/lock0000000001这样的临时顺序节点，而且可以加上标志，比如这是一个读请求就是/root/lock_read_0000000001,一个写请求就是/root/lock_write_0000000002，创建完毕都对root节点进行监听，以便获取子节点变更事件。
2.由于共享锁的定义，不同事务可以对一个对象进行读，但是写必须在没有事务读的情况下进行。
3.对于读请求，获取children节点，如果没有比自己序号更小的节点或者比自己序号小的节点都是读节点，那么就可以执行读逻辑了(获取到了读锁)。
4.对于写请求，获取children节点，只要自己不是序号最小的节点，就需要等待。
?
由于伴随大量的watch通知，和获取子节点列表，所以这就称为羊群效应。
改进后的分布式实现：
1.创建类似/root/lock0000000001这样的临时顺序节点，而且可以加上标志，比如这是一个读请求就是/root/lock_read_0000000001,一个写请求就是/root/lock_write_0000000002。
2.客户端获取children节点列表但并不watch
3.如果无法获取到共享锁，那么：
1）读请求向比自己小的最后一个写节点注册watch
2）写请求向比自己序号小的最后一个节点注册watch
?

• 分布式队列管理

两种类型的队列。
?
1、同步队列，当一个队列的成员都聚齐时，这个队列才可用，否则一直等待。在约定的目录下创建临时目录节点，监听节点数目是否是我们要求的数目。
2、队列按照 FIFO 方式进行入队和出队操作。和分布式锁服务中的控制时序的场景基本原理一致，入列有编号，出列按编号。创建 PERSISTENT_SEQUENTIAL 节点，创建成功时 Watcher 通知等待的队列，队列删除序列号最小的节点以消费。此场景下，znode 用于消息存储，znode 存储的数据就是消息队列中的消息内容，SEQUENTIAL 序列号就是消息的编号，按序取出即可。由于创建的节点是持久化的，所以不必担心队列消息丢失的问题。
?

13）常见命令

• ./zkCli.sh #连接本地的zookeeper服务器

• ./zkCli.sh -server ip:port #连接指定的服务器

• create -s /zk-test ’123‘ #创建一个顺序节点

• create -e /zk-temp ’123‘ #创建一个临时节点

• ls /root/ #查看子节点

• create /zk-permanent '123' #任何选项都不带的是持久节点

• get /zk/test #读取节点内容

• get /zk/test watch #读取后watch该节点

• set /zk/test '1111' [version]#更新节点内容 version表示基于哪个版本执行的

• delete /zk/test 删除节点

• rmr 递归删除节点

• stat /zookeeper 获取节点状态信息

2、工作流程

1、请求处理

ZooKeeper服务器会在本地处理只读请求（exists、getData、getChildren），例如一个服务器接收客户端的getData请求，服务器读取该状态信息，并把这些信息返回给客户端。那些会改变ZooKeeper状态的客户端请求（create， delete和setData）将会转发到群首，群首执行对应的请求，并形成状态的更新，称为事务（transaction）， 其中事务要以原子方式执行。同时，一个事务还要具有幂等性，事务的幂等性在我们进行恢复处理时更加简单，后面我们可以看到如何利用幂等性进行数据恢复或者灾备。在群首产生了一个事务，就会为该事务分配一个标识符，称为会话id（zxid），通过Zxid对事务进行标识，就可以按照群首所指定的顺序在各个服务器中按序执行。服务器之间在进行新的群首选举时也会交换zxid信息，这样就可以知道哪个无故障服务器接收了更多的事务，并可以同步他们之间的状态信息。 Zxid为一个long型（64位）整数，分为两部分：时间戳（epoch）部分和计数器（counter）部分。每一部分为32位，在我们讨论zab协议时，我们就会发现时间戳（epoch）和计数器（counter）的具体作用，我们通过zab协议来广播各个服务器的状态变更信息。

2、选举

群首为集群中的服务器选择出来的一个服务器，并会一直被集群所认可。设置群首的目的是为了对客户端所发起的ZooKeeper状态更新请求进行排序，包括create，setData和delete操作。群首将每一个请求转换为一个事务，将这些事务发送给追随者，确保集群按照群首确定的顺序接受并处理这些事务。

每个服务器启动后进入LOOKING状态，开始选举一个新的群首或者查找已经存在的群首。如果群首已经存在，其他服务器就会通知这个新启动的服务器，告知哪个服务器是群首，于此同时，新服务器会与群首建立连接，以确保自己的状态与群首一致。如果群首中的所有的服务器均处于LOOKING状态，这些服务器之间就会进行通信来选举一个群首，通过信息交换对群首选举达成共识的选择。在本次选举过程中胜出的服务器将进入LEADING状态，而集群中其他服务器将会进入FOLLOWING状态。

注意，一个刚刚启动的集群，投票都会投给自己，也就是(mySid,0)。而如果是已经运行一会的集群，leader挂了以后，所有的非observer机器都会进入选举（LOOKING）状态。

具体看，一个服务器进入LOOKING状态，就会发送向集群中每个服务器发送一个通知信息，该消息中包括该服务器的投票（vote）信息，投票中包含服务器标识符（sid）和最近执行事务的zxid信息。<sid,zxid>

当一个服务器收到一个投票信息，该服务器将会根据以下规则修改自己的投票信息：

1. zxid较大的优先作为leader；

2. zxid相同，比较sid，sid较大的作为leader；

从上面的投票过程可以看出，只有最新的服务器将赢得选举，因为其拥有最近一次的zxid。如果多个服务器拥有的最新的zxid值，其中的sid值最大的将会赢得选举，每次投票以后，服务器都会统计，判断是否已经有过半（n/2+1)的机器获得相同的投票信息（也就是说zk保存着其余所有机器的列表，投票后会统计各个机器的得票）。

当一个服务器连接到仲裁数量的服务器发来的投票都一样时，就表示群首选举成功，如果被选举的群首为某个服务器自己，该服务器将会开始行使群首角色，否则就会成为一个追随者并尝试连接被选举的群首服务器。一旦连接成功，追随者和群首之间将会进行状态同步，在同步完成后，追随者才可以进行新的请求。

3、状态更新广播协议

在接收到一个写请求操作后，追随者会将请求转发给群首，群首将会探索性的执行该请求，并将执行结果以事务的方式对状态更新进行广播。如何确认一个事务是否已经提交，ZooKeeper由此引入了zab协议，即Zookeeper原子广播协议（ZooKeeper Atomic Broadeast protocol）。该协议提交一个事务非常简单，类型于一个两阶段提交。

1. 群首向所有追随者发送一个PROPOSAL消息p。

2. 当一个追随者接收到消息p后，会响应群首一个ACK消息，通知群首其已接受该提案（proposal）。

3. 当收到仲裁数量（过半）的服务器发送的确认消息后（该仲裁数包括群首自己），群首就会发送消息通知追随者进行提交（COMMIT）操作。

Zab 保障了以下几个重要的属性：

1. 如果群首按顺序广播了事务T1和事务T2，那么每个服务器在提交T2事务前保证事务T1已经完成提交。

2. 如果某个服务器按照事务T1和事务T2的顺序提交了事务，所有其他服务器也必然会在提交事务T2前提交事务T1。

3. 第一个属性保证事务在服务器之间传送顺序的一致，而第二个竖向保证服务器不会跳过任何事务。

4、observer

观察者与追随者有一些共同的特点，他们提交来自群首的提议，不同于追随者的是，观察者不参与选举过程，他们仅仅学习经由INFORM消息提交的提议。

引入观察者的一个主要原因是提高读请求的可扩展性。通过加入多个观察者，我们可以在不牺牲写操作的吞吐率的前提下服务更多的读操作。但是引入观察者也不是完全没有开销，每一个新加入的观察者将对应于每一个已提交事务点引入的一条额外消息。

采用观察者的另外一个原因是进行跨多个数据中心部署。由于数据中心之间的网络链接延时，将服务器分散于多个数据中心将明显地降低系统的速度。引入观察者后，更新请求能够先以高吞吐量和低延迟的方式在一个数据中心内执行，接下来再传播到异地的其他数据中心得到执行。

5、持久化

zk是一个内存数据库，数据模型像是一棵树，内存中保存了这棵树的所有内容，但是会定期将内存的内容保存在磁盘上。

服务器通过事务日志来持久化事务。在接受一个提案时，一个服务器就会将提议的事务持久化到事务日志中，该事务日志保存在服务器本地磁盘中，而事务将会按照顺序追加其后。写事务日志是写请求操作的关键路径，因此ZooKeeper必须有效处理写日志问题。在持久化事务到磁盘时，还有一个重要说明：现代操作系统通常会缓存脏页（Dirty Page），并将他们异步写入磁盘介质。然而，我们需要在继续之前，要确保事务已经被持久化。因此我们需要冲刷（Flush，CAPI的fsync）事务到磁盘介质。冲刷在这里就是指我们告诉操作系已经把脏页写入到磁盘，并在操作完成后返回。同时为了提高ZooKeeper系统的运行速度，也会使用组提交和补白的。其中组提交是指一次磁盘写入时追加多个事务，可以减少磁盘寻址的开销。补白是指在文件中预分配磁盘存储块。

快照是ZooKeeper数据树的拷贝副本，每一个服务器会经常以序列化整个数据树的方式来提取快照，并将这个提取的快照保存到文件。服务器在进行快照时不需要进行协作，也不需要暂停处理请求。因此服务器在进行快照时还会继续处理请求，所以当快照完成时，数据树可能又发生了变化，称为快照是模糊的，因为它们不能反映出在任意给定的时间点数据树的准确的状态。快照集群中所有机器同一时刻的数据快照，在zk的具体实现中，是采用过半随机的策略（假如配置的snapCount=100000,那么会在50000-100000次事务之后进行一次数据快照），快照的写入是启动一个异步线程完成的，并且最后会序列化。

因此对于一个zk集群的启动，先进行数据初始化工作，这个是从快照加载出来的，策略是获取最新100个快照文件，逐个校验，通过后根据最新zxid的快照文件来生成数据。根据快照同时也初始化了epoch和zxid。

6、会话

会话（session）是ZooKeeper的一个重要的抽象。保证请求有序，临时znode节点，监控点都与会话密切相关。因此会话的跟踪机制对ZooKeeper来说也是非常重要的。其包含四种重要属性：

1）sessionID，每次客户端新建会话，zk都会分配一个全局唯一的。

2）timeout，会话的超时时间。

3）ticktime，下次会话超时的时间点。为了进行分桶策略的管理（分桶策略：将类似的会话放到同一个区块进行管理，首先创建时就估算出一个可能的过期时间currentTime+sessionTimeout，根据此进行分配)。

4）isClosing，标记是否关闭

会话的管理策略是分桶策略，是指类似的会话放在同一区块进行管理。在独立模式下，单个服务器会跟踪所有的会话，而在仲裁模式下则由群首服务器来跟踪和维护。而追随者服务器仅仅是简单地把客户端连接的会话信息转发到群首服务器。

为了保证会话的存活，服务器需要接收会话的心跳信息。心跳的形式可以是一个新的请求或者显式的ping信息。两种情况下，服务器通过更新会话的过期时间来触发会话活跃，在仲裁模式下，群首服务器发送一个PING信息给它的追随者们，追随者们返回自从最新一次PING消息之后的一个session列表。群首服务器每半个tick就会发送一个ping信息给追随者们。

7、监视器-watcher

监视点是由读取操作所设置的一次性触发器，每个监视点有一个特定操作来触发，即通过监视点，客户端可以对指定的znode节点注册一个通知请求，在发生时就会收到一个单次的通知。监视点只会存在内存，而不会持久化到硬盘，当客户端与服务端的连接断开时，它的所有的监视点会从内存中清除。因为客户端也会维护一份监视点的数据，在重连之后，监视点数据会再次同步到服务端。

运行流程为：客户端向服务端注册watcher，同时也会保存在客户端的watcherManager中，当服务端触发watch后，向客户端发送通知，客户端再取出对应的watcher进行回调。

watcher的特点：

• 一次性，一旦触发后，就会将其移除。所以需要反复注册。

• 客户端串行，客户端回调是一个串行同步过程，保证了顺序。

• 轻量，watchedEvent仅仅返回了通知状态、事件类型、节点路径。

8、客户端

在客户端库中有2个主要的类：ZooKeeper和ClientCnxn，写客户端应用程序时通过实例化ZooKeeper类来建立一个会话。一旦建立起一个会话，ZooKeeper就会使用一个会话标识符来关联这个会话。这个会话标识符实际上是有服务端所生产的。

ClientCnxn类管理连接到server的socket连接。该类维护一个可连接的ZooKeeper的服务列表，并当连接断掉的时候无缝地切换到其他服务器，当重连到一个其他的服务器时会使用同一个会话，客户端也会重置所有的监视点到刚连接的服务器上。

对于一个写请求，zookeeper集群是半数以上写成功，则给客户端返回成功。而读请求则是客户端连接的zookeeper直接将其内存数据返回给客户端。那么如下两种场景下，客户端读出数据是否会存在问题呢？

（1）两个客户端连接zookeeper，一个客户端负责写，另一个客户端负责读，会不会读到旧数据呢？答案是肯定的。对于同一个客户端，写入成功后，立即读，肯定是能读到刚刚写入的数据，因为写响应成功(比如clien连接到了z0-z1-z2集群，z0是主其他时从，clent连接的是z1那么写请求发给z1,z1转发给z0，提案-提交之后z1已经更新了数据，才返回，但是z2可能依然是旧数据)，代表客户端连接的zookeeper节点内存数据已经更新成最新数据，那么读当然能读到最新数据。但两个客户端就不一样，如果一个客户端写入数据成功，有两个zookeeper节点内存修改成功，第三个zookeeper节点由于网络时延较高还没写入成功，那么此时负责读的客户端正好连接的是第三个zookeeper节点就有可能读到旧数据。该场景对于数据实时性要求不高的场景可以适用。

（2）如果有一个客户端写入数据成功，有两个zookeeper内存修改成功，第三个zookeeper节点内存数据未修改成功，客户端断开连接快速连接到第三个zookeeper节点，会不会读到旧数据呢？答案是否定的。zookeeper内部对于这种场景做了保护，zookeeper为了保证事务消息处理的时序性，保证先到的事务消息先处理，处理完一个事物消息会取出下一个待处理的事物ZXID。例如，处理完zxid=100的事物，那么下一个等待的zxid就必然是101，如果收到的是102，则说明zxid=101消息丢失了（可能由于网络原因丢失了），就会触发syn流程主动与leader节点进行数据同步。另外，如果客户端进程没重启，则会保留最新的zxid，与zk server建立连接时客户端会把自己缓存的zxid带给zk server；zk server会检查客户端zxid，如果发现客户端zxid比自己大，zk server会告诉zk client你的事物zxid比我的zxid大，拒绝连接，这样也能防止客户端端开后连接到未同步数据的zk server。

对于上述问题，client重先建立连接过程会触发一个session创建或者revalidate的过程，这个过程对于zookeeper集群而言是一个写事务过程，leader节点会向这第三个zookeeper节点同步最新的zxid，该节点发现期待的ZXID与收到的ZXID不一致，主动与leader进行数据同步。

9、序列化

对于网络传输和磁盘保存的序列化消息和事务，ZooKeeper使用了Hadoop中的Jute来做序列化。

10、保证数据一致性

一、zookeeper写流程

客户端会随机连接一个zookeeper服务器，后续客户端读写都是通过该连接进行。如果客户端连接的是follower，则follower会将收到的写请求转发到leader节点来完成写流程；由此可见，zookeeper的写流程是由leader节点统一控制的，再加上leader和follower内部采用了很多先进先出队列，保证了消息处理的时序性。

第一步：客户端发起写操作，请求发送到客户端连接的follower，follower收到请求后，发现是写请求，就会将写请求转发到leader节点；

第二步：leader节点收到写请求后，为该请求构建唯一事物ID，即ZXID；然后向所有的follower发送proposal请求，携带ZXID，同时将该请求写本地log；等待follower的响应；

第三步：follower收到leader发送过来的proposal请求后，将写请求记录本地log；然后给leader响应，表示数据已经接收OK了；

第四步：leader收到包括自己半数以上的proposal ack后，给所有的follower发送commit请求；

第五步：follower收到commit请求后，修改内存数据，setData的数据在内存生效；client连接的zookeeper节点就可以给client回复setData响应了

二、写过程中follower节点异常重启

一个Follower节点重启，不会影响zookeeper集群对外提供服务，客户端无感知，可以继续写入数据；follower节点一旦重启，重启后会主动向leader节点做数据同步，保证在对外提供服务之前与leader节点数据一致；根据上面流程图，针对一次写操作，follower节点可能在记录log之前重启，也可能在记录log之后重启，这两种场景，zookeeper恢复流程是一样的。

zookeeper进程重启后，就自动加载本地snap文件和log文件，获得最大ZXID，即peerLastZxid。follower加载完数据后会通知leader节点自己最大的peerLastZxid；leader内存中会记录一个最小ZXID和最大ZXID，即minCommittedZxid，maxCommittedZxid；

（1）如果follower节点的最大ZXID小于leader节点的最小ZXID，即peerLastZxid<minCommittedZxid，则需要将本地内存数据全部清空，从leader节点全量同步数据信息，这种模式称为SNAP模式；这种场景一般出现在follower节点故障时间比较长，恢复后从leader同步数据；

（2）如果follower节点的最大ZXID在leader的最小ZXID和当前ZXID之间，即minCommittedZxid<=peerLastZxid<=maxCommittedZxid，那么follower节点需要从leader同步增量数据，这种模式称为DIFF模式；这种场景一般出现在follower节点故障时间比较短，恢复后从leader进行同步数据；

从上面分析可以看出，如果follower节点还未写log进程就重启了；重启期间，如果zookeeper集群没有新的数据写入，就通过DIFF模式同步丢失的最一个IO即可；如果重启期间发生了一次重先选主或者有大量新数据写入，则可能需要通过SNAP模式全量同步数据。follower节点在数据同步完成后，会立即对内存数据做一次全量快照，写入到快照snap文件中。

三、写过程中leader节点异常重启

如果写操作过程中，leader重启，则zookeeper集群停止对外提供服务器，客户端连接会断开，业务层可以感知该异常；此时客户端提交的写操作是否成功不可知，这种异常对业务的影响需要业务层来保证。但zookeeper集群重先对外提供服务后，能保证无论客户端连接哪个zookeeper节点，读出的数据都是一样的。

Leader节点进程异常后，zookeeper集群会触发重先选主；zookeeper加载本地数据恢复后的peerLastZxid最大的会当选为leader。

那么，对于一个新的写请求，如果leader节点本地记录了log，其他follower节点尚未记录log，leader节点进程重启，导致zookeeper集群重先选主。就会出现两种情况：

（1）选主期间，原来的leader节点进程参与选主；由于本地log比其他节点多一个事物记录，peerLastZxid就会比其他节点大，那么久理所当然当选为leader，其他节点会从leader将该写事物同步过去；这样，这个写事物对zookeeper集群而言是成功的，客户端可以访问到；

（2）重先选主期间，原来的leader节点由于故障没有参与选主；那么新的leader节点在其他两个节点中产生，其他两个节点中还未记录最后提交的写请求，所以最后的这个写请求对zookeeper集群而言是失败的，客户端不可访问。原来的leader节点进程起来后，与新leader同步数据，会发现本地多了一个事物，就会发起TRUN模式进行数据同步，抹掉这个多余的写记录。

针对这两种情况，业务侧都要能够做相应的保护性处理。

11、ACL

ACL即访问控制列表，ZK中能够使用的是4种权限模式：

• IP模式，根据ip及其网段进行授权

• Digest模式，也就是用户名-密码模式

• World模式，即对所有人开放

• super模式，一种特殊的digest模式

权限，分为五种。

• cretate（C)，创建权限

• delete（D)，删除权限

• read（R)，读取权限

• write（W)，写权限

• admin（A），管理权限，可以进行acl操作

12、脑裂概念

比如原来5个机器，node1-node5,node4、node5与node1，2，3不通了， 但是node4 5还是通的，因此一个集群最后变成了两个集群，有两个leader。

但是zk实际上解决了这个痛点，node4 node5依然需要过半才能选举成功，但是这里只有两台机器，所以，是选不出leader的。整个集群（虽然产生脑裂）但依然只有一个leader。

3、分布式协议

就目前来说比较常用的，广为流传的协议一般是paxos，raft两种算法。下面解释相似点、不同点以及相关概念。

零、分布式理论

CAP定理：

C=Consistency一致性、A=Availability可用性、P=Partition Tolerance分区容错性，CAP三个特性不可同时满足。

• 一致性是指的是多个数据副本是否能保持一致的特性，在一致性的条件下，系统在执行数据更新操作之后能够从一致性状态转移到另一个一致性状态。对系统的一个数据更新成功之后，如果所有用户都能够读取到最新的值，该系统就被认为具有强一致性。

• 可用性指分布式系统在面对各种异常时可以提供正常服务的能力，可以用系统可用时间占总时间的比值来衡量，4 个 9 的可用性表示系统 99.99% 的时间是可用的。在可用性条件下，要求系统提供的服务一直处于可用的状态，对于用户的每一个操作请求总是能够在有限的时间内返回结果。

• 网络分区指分布式系统中的节点被划分为多个区域，每个区域内部可以通信，但是区域之间无法通信。

  在分区容错性条件下，分布式系统在遇到任何网络分区故障的时候，仍然需要能对外提供一致性和可用性的服务，除非是整个网络环境都发生了故障。

可以看出ZK是维护CP性质的。

不能保证每次服务请求的可用性。任何时刻对ZooKeeper的访问请求能得到一致的数据结果，同时系统对网络分割具备容错性；但是它不能保证每次服务请求的可用性（注：也就是在极端环境下，ZooKeeper可能会丢弃一些请求，消费者程序需要重新请求才能获得结果）。所以说，ZooKeeper不能保证服务可用性。

进行leader选举时集群都是不可用。在使用ZooKeeper获取服务列表时，当master节点因为网络故障与其他节点失去联系时，剩余节点会重新进行leader选举。问题在于，选举leader的时间太长，30 ~ 120s, 且选举期间整个zk集群都是不可用的，这就导致在选举期间注册服务瘫痪，虽然服务能够最终恢复，但是漫长的选举时间导致的注册长期不可用是不能容忍的。所以说，ZooKeeper不能保证服务可用性。

BASE定理：

BASE 是基本可用（Basically Available）、软状态（Soft State）和最终一致性（Eventually Consistent）三个短语的缩写。

BASE 理论是对 CAP 中一致性和可用性权衡的结果，它的核心思想是：即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性。

• 基本可用：指分布式系统在出现故障的时候，保证核心可用，允许损失部分可用性。

• 软状态：指允许系统中的数据存在中间状态，并认为该中间状态不会影响系统整体可用性，即允许系统不同节点的数据副本之间进行同步的过程存在时延。

• 最终一致性：最终一致性强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能达到一致的状态。

2PC、3PC和TCC协议

https://blog.csdn.net/bjweimengshu/article/details/86698036

两阶段提交又称2PC（two-phase commit protocol）,2pc是一个非常经典的强一致、中心化的原子提交协议。这里所说的中心化是指协议中有两类节点：一个是中心化协调者节点（coordinator）和N个参与者节点（partcipant）。

三阶段提交又称3PC，其在两阶段提交的基础上增加了CanCommit阶段，并引入了超时机制。一旦事务参与者迟迟没有收到协调者的Commit请求，就会自动进行本地commit，这样相对有效地解决了协调者单点故障的问题。

TCC（Try-Confirm-Cancel）又称补偿事务。其核心思想是："针对每个操作都要注册一个与其对应的确认和补偿（撤销操作）"。它分为三个操作：

• Try阶段：主要是对业务系统做检测及资源预留。

• Confirm阶段：确认执行业务操作。

• Cancel阶段：取消执行业务操作。

TCC事务的处理流程与2PC两阶段提交类似，不过2PC通常都是在跨库的DB层面，而TCC本质上就是一个应用层面的2PC，需要通过业务逻辑来实现。这种分布式事务的实现方式的优势在于，可以让应用自己定义数据库操作的粒度，使得降低锁冲突、提高吞吐量成为可能。

XA分布式事务与2PC、3PC、TCC

XA两阶段提交究竟有哪些不足呢？

1.性能问题

XA协议遵循强一致性。在事务执行过程中，各个节点占用着数据库资源，只有当所有节点准备完毕，事务协调者才会通知提交，参与者提交后释放资源。这样的过程有着非常明显的性能问题。

2.协调者单点故障问题

事务协调者是整个XA模型的核心，一旦事务协调者节点挂掉，参与者收不到提交或是回滚通知，参与者会一直处于中间状态无法完成事务。

3.丢失消息导致的不一致问题。

在XA协议的第二个阶段，如果发生局部网络问题，一部分事务参与者收到了提交消息，另一部分事务参与者没收到提交消息，那么就导致了节点之间数据的不一致。

如果避免XA两阶段提交的种种问题呢？有许多其他的分布式事务方案可供选择：

1.XA三阶段提交

XA三阶段提交在两阶段提交的基础上增加了CanCommit阶段，并且引入了超时机制。一旦事物参与者迟迟没有接到协调者的commit请求，会自动进行本地commit。这样有效解决了协调者单点故障的问题。但是性能问题和不一致的问题仍然没有根本解决。

2.MQ事务

利用消息中间件来异步完成事务的后一半更新，实现系统的最终一致性。这个方式避免了像XA协议那样的性能问题。

3.TCC事务

TCC事务是Try、Commit、Cancel三种指令的缩写，其逻辑模式类似于XA两阶段提交，但是实现方式是在代码层面来人为实现。

一、多副本状态机

为了解决单机服务的问题，比如一个KV系统。按照主从模式两者异步或者同步复制。当主挂了后，从就变成了主（主备切换）。缺点是：1）无法解决脑裂（指一个HA系统中二者直接无法相互访问，心跳断开等原因，都认为是对方出现的故障，之后就会争抢资源、争抢服务）问题。2）数据一致性不好保证。一般为了解决这种问题都使用手动切换或者依赖外部的共享服务，比如zk/etcd来规避。

多副本状态机(State machine replication)也可以用来解决上述服务的单点问题，多副本状态机的核心思想是deterministic的状态机，输入同样的日志序列，状态机最终的状态是一样的，这样多个节点，每个节点保存一个副本的状态机，然后通过paxos或者raft等一致性consensus协议，协商出一个共同的日志序列，应用到每个副本的状态机上，最终状态机的状态也是一致的，这样就实现了一个高可用的服务。多副本状态机可以应对脑裂的问题，多副本状态机只要majority的节点能互相通信就能正常工作。

二、基础paxos

basic paxos用来在分布式环境中协商一个值，值协商确定之后，不会再发生变化。basic paxos协商一个值的过程是两个步骤，流程如下：

第一步A：Proposer向系统所有的Acceptor节点发送一个prepare命令(携带提议编号n）

第一步B：Acceptor接收到prepare，若这个n是已经接收过的最大值，则承诺不会接受任何比n小的提议。如果m是之前已经accept的小于n的最大提议，则返回给Proposer相应m值。

第二步A：第一步汇总到的已经accepted的最新值，如果没有一个比n大的，那么向Acceptor发送accept请求[n,value],否则选择返回的提议中m最大的对应值作为提议值。

第二步B：如果编号不违反承诺，则接受该提议。

概念1：提案编号，相当于逻辑时钟，只增不减。
概念2：选中，当一个值被majority节点accept之后，这个值就是被选中的。
概念3：安全性，一个值被选中后，永远不会变化，后续提案选中的都是同样值。

核心：prepare阶段如果被majority接收，那么majority就不会再接收更老的逻辑时钟的请求了。比如说如果某个节点提交了一个提案编号为10的prepare请求，并且被majority的节点返回了prepare的response，那么在10之前的那些提案要么已经被chosen，要么永远再也不会被chosen了。如果10之前的提案已经被chosen的话，逻辑时钟为10的这个prepare过程一定可以学习到，然后再用学习到的这个值来进行第二个步骤，然后其他的majority来接受（注意第一步的majority和第二步的majority可以不是同一个集合），这样就保证了paxos算法的安全性(safety)。

三、paxos和FLP

概念：FLP定理
FLP定理是说在分布式异步网络环境下，协商确定一个值，没有算法既安全正确，又能正常终止。

在paxos中很容易构造一个场景，让paxos协商值的过程变成活锁，永远无法终止。比如说： 节点A用10的提案编号给所有的节点发prepare请求，然后节点B用11的提案编号给所有的节点发prepare请求，然后A再去发accept指令的时候，会发现当前系统的时钟已经到11了，没有节点响应他的请求了，因此他只能用12的提案编号重新开始paxos的流程，发送prepare请求，然后节点B要发accept的时候，也看到系统的整体时钟已经到了12，没有节点响应他的请求了，他因此把提案编号增大成13，然后继续paxos的流程，一直这些循环往复，导致paxos无法进行下去。

paxos算法在任何情况下都保证了safety安全性，但是不保证liveness。liveness的问题一般都是用随机化的方法来规避，通过随机化让冲突发生的概率很低很低，即使发生了冲突，再随机化重试即可规避。关于Liveness问题，导致这个问题出现的原因主要是由于节点可能会存在的传输延迟，导致诚实节点会锁在不同的区块上，导致没有足够的1/2的节点可以支持整个共识过程的进行。Tendermint共识算法针对这个问题的解决方案主要是用PoLC（Proof of Lock Change），而Istanbul-BFT并没有解锁过程，所以整个算法的Liveness是可能会存在问题的。目前应该还是没有找到一个特别合适的解决方案，具体可见前面的相关链接。

四、paxos协商一个序列的值

基础paxos仅协商了一个值，多副本状态机模型是要协商一个序列的值。一般做法是，先选一个主，由主来统一提交日志。

另外，可以把多个paxos实例的第一步的流程合并，比如说：第一步某个节点选取一个提案编号逻辑时钟，发给系统中的所有节点prepare，告诉他们不要再接收老的消息了，同时把过半槽位的accepted值返回；这样在一个步骤里面就可以prepare多个paxos实例，完成了多个paxos实例的第一步骤，然后这个节点后续收到client发的请求后，选择空闲的槽位，让所有节点accpet这个槽位的值就可以了。因为针对这个槽位来说，这个槽位的paxos实例的第一步已经完成过了。其实也就是过半同意算法。

从上面的流程可以看到，paxos算法只是从整体宏观上来讲，如何协商一个log entry，以及在此之上实现多副本状态机的大体流程，但其他部分都讲的很不详细，可以说paxos只是相当于一个项目的可行性分析，和工程实现差距非常大。

五、raft协议，一个非常好的网站去理解raft协议

http://thesecretlivesofdata.com/raft/

raft为了实现多副本状态机，对比paxos，采用了一种不同的方式：raft为了可理解性来设计。raft把实现多副本状态机这个问题拆成了多个子问题(decomposition)，分别是

• 选主(leader election)

  选主分为启动时选主和异常时选主

  • 启动时选主：节点启动时都是follower，自己有一个定时器，超时后就节点A变成candidate发起选举。发给其他节点要求投票给自己，其他节点发现在本term内还没投票过，就同意，同时那些节点的选举定时器被重置。A得到半数以上的投票，成为leader，其他节点与A进行心跳，收到心跳都会重置定时器。

  • 异常时选主：leader与follower正常工作时会不断发送心跳信息，来确保follower知道leader是好着的。一旦有follower在心跳超时时间过了后，将变身为candidate，将自己的term+=1，然后向其他的节点发起request vote.通过后将变成新的leader。

两个timeout：第一个为选举超时（election timeout）,这个时间是随机的，每个节点不一样，如果在选举超时时间内没收到leader消息，那么follower就变成candidate开始选举流程（在某个candidate发送给request vote给follower之后，follower的选举超时就刷新了），一般在150-300ms。心跳超时（heartbeat timeout），是leader每隔一段时间给follower发送的消息，一旦leader挂掉，使得follower收不到hb了，那么follower立即递增自己的term然后变身candidate，接受到心跳，就可以重置选举超时定时器。一般心跳超时会比选举超时小很多。

选举约束：raft要求拥有最新日志的节点才能成为leader，也就是request vote会带有日志最新的index和term信息；收到一个vote后，如果比自己新且term大于等于自己的term，则投yes否则投no。

raft选主有几个特点：每个term最多只有一个leader，有的term可能没有leader；为了应对split vote的问题，加快选主的速度，使用随机化的方法。

• 日志复制(log replication)

  日志复制的消息是写在心跳信息的，一旦有一条写操作的话，首先追加到leader的log中，在下次心跳信息中，将这次变化携带进去，分发给follower，得到过半数响应后，leader首先将自己的节点值修改，然后立即响应客户端告知“成功”，最后通知follower修改自己节点的值。

  • leader请求复制时，会带上自己的term，如果follower发现自己的term更大则返回失败。

  • 除了term还会检查preLogIndex，只要不与follower的匹配，都会返回失败。

  leader只会追加写自己的log，但是follower可能会被覆盖，以期望与leader匹配。

  除此之外，日志的写入还有几个特点：

  • 日志压缩，积累到一定程度后，保留一个快照，同时记录term和logIndex。

• 安全性(safety)

Election Safety（选举安全）: 一个term逻辑时钟里只会有一个leader，并且在选主的时候有限制，只有日志最长的节点才有可能被选成主，通过这种限制，其实是可以和paxos做对比，由于leader含有最长的日志，所以相当于paxos的第一个步骤就不需要；或者说paxos的第一个步骤就类似于raft的选主，只是raft限制主的数据最新，paxos则是通过学习通过数据拷贝的方式，来保证发起提案的节点有最新的数据。

Leader Append-Only: 所有的写入请求都是经过leader；

Log Matching: 日志从leader向follower单向流程，并且以leader的日志为准。

State Machine Safety是说如果一个log entry被applied，这个log entry就不会再变，这个safety其实和paxos的safety是一致的。

术语：
1.状态，follower、candidate、leader代表着
跟随者---集群里跟随着主的变化而变化；
竞选者---当主失效或刚启动时候用投票竞选自己为ledaer；
主节点---集群里维系与follower联系的节点，所有的写请求都会经过leader，每一个写请求都会先写一条log（是未提交状态的，uncommited，因此不会修改节点的值）；然后将这条变化日志复制给其余follower节点，当leader收到了过半同意后，就修改节点值，此时为commited状态，然后通知follower节点修改为日志值。
2、term，可以理解为选举轮次。
3、majority，可以理解为过半，比如3节点2为过半，5节点3为过半。
4、vote split，其实称之为平票更合适.指有多个candidate开始选举流程，会向其他的节点发送request vote，最终获得一样的票数，一般raft会等待一段随机时间后再次发起
5、network partitions,俗称的脑裂，网络分割。在分割后被分割出去的几个follower会选举出新的leader，这样多个客户端可能会连在不同的leader上面。假设两个客户端分别连到被分割的两个leader上面并修改了值，因为旧的leader无法通过过半相应来完成提交，那么这个修改在老leader总是未提交的，而在新leader中就能够完成修改，当网络恢复（结束分割）后，新leader拥有更大的term（因为分割后完成了一轮选举），那么旧leader及其follower就回滚掉未提交的修改，重新以新leader当leader。这样就完成了最终一致性。

五、对比

paxos比较宏观、raft比较细致。 paxos类似一个项目可行性设计、raft类似于详细设计。 paxos两个步骤，第一个步骤通过学习的方式来copy最新的数据，然后用自己的提案编号来提交、raft通过限制日志最长的节点才能 成为主，来保证数据最新，也是通过leader的term来提交所有的日志。

六、预投票

预投票是raft一种流程优化，如A、B、C三个节点组成的集群，如果发生了脑裂C于A、B不通的话，A、B两个节点可以正常提供对外的服务，而C由于不能收到集群leader的心跳，将进入candidate状态，增加term，然后开始选主，然后选不上，再增加term，重新开始选主。。。然后就这样term会一直增加，直到网络恢复。网络恢复的时候，由于节点C的term比较大，A、B节点比它大的term的时候，会把自己的term置成最新的，然后进入follower状态，然后等待election timeout。节点C由于日志比较短，不可能被选成主，主只能在A和B中产生。A和B的election timeout触发之后，开始选主。可以看到，一个网络异常的节点在重新加入集群之后，会导致集群的波动，影响集群的可用性。

为了解决这个问题，在选主的时候，增加prevote的流程，在prevote阶段，先预投票，看自己能否有可能被选成主，只有在可能被选成主的情况下，在真正增加term，开始真正的选主的流程。

七、日志提交流程优化

raft日志提交流程常见的有batching和pipeline两种优化方法。

batching: 一个常见的优化方式是batching，把client提交过来的请求攒一攒，一起走raft的流程，提升整体的吞吐。

pipeline: raft的提交日志的流程大体上分为如下的步骤： (a)、leader收到client的请求； (b)、leader追加请求的log entry到本地日志； (c)、leader把请求的log entry复制到followers，导致follower把log entry分别追加到他们的本地日志； (d)、leader等待所有的followers返回，如果majority的节点返回成功，leader提交这个日志，并且把日志应用到状态机里； (e)、leader把结果发给client，然后再继续处理后续的请求。

应用pipeline上述步骤可优化成：

(a)、leader收到client的请求； (b)、leader追加请求的log entry到本地日志，同时并行的给follower复制日志； (c)、leader继续接受新的请求，并重复(b)； (d)、leader收到follower的返回，满足majority的条件之后，commit这个log entry，然后异步的在另外的一个线程里面apply应用到状态机里面； (e)、leader把结果发给client。

八、线性一致性

线性一致性用一句话来概括就是：所有的事件可以按照时间的先后顺序连成一条线。

基于raft实现线性一致性常见的有如下几种方法： read index: leader收到读请求之后，记录当前的commit index为read index，然后给所有的follower发送心跳保证自己的权威，然后等待read index应用到状态机之后，读取状态机的内容返回给client。这种方法核心有下面几点：1、read index等于commit index，确保能读到最新commit的数据；2、要确保自己还是主(说明数据最新，不会返回老的状态数据)；3、状态机可能是异步apply的，要等待read commit都apply到状态机之后再返回。

lease read: lease租约是一个协议，大家约定好，在lease租约时间的范围内，保证leader不会发生变化。

follower read: follower收到client的请求后，向leader请求commit index，本地的apply index大于commit index就可以了。(本地的状态机可能不是最新的，但这没关系，不会违背线性一致性，只要状态机比这个请求的开始的时间新可以)。