好久没更新博客，主要是前段时间看了一点机器学习的东西，公式不好打字，后来准备面试又看了很多java的基础，过几天会把java的基础整理一下丢在博客上。

今天主题是zookeeper，bigdata课上老师讲了zookeeper的内容，再加上自己也试了一下，就放在这里整理了。整理只为了自己看，离精通或者熟悉还差着一万八千里呢！

Zookeeper简介

用途

zk是一个高扩展和高可用的服务，主要用来支持

• Distributed configuration
• Consensus
• Group Membership
• Leader Election
• Naming
• Coordination

基础架构

Zookeeper分布在不同的服务器上，每个节点是一个server，其中有一个会作为leader，如图：

具体来说，zk的架构有如下特点：

• 所有的server都有一份数据、logs、硬盘snipshots的拷贝，被存在内存数据库中（它并不存储真正的数据，所以上面空间通常只有几十M，仅用来存必要的一些配置等）
• 在启动时会选择一个作为leader
• client可以选择任何一个server链接
• 当大多数（超过一半）server完成了一个改变，那这个修改就被认为成功，并返回update response（可能造成读取旧数据）

ZK的数据模型

zk的service到底是什么呢？其实就是一个被全部server追踪的分布式文件系统（这个角度来看有点像hdfs），它也是层次命名空间（类似linux），上面的每个节点称为一个znode。每一个znode都存储着一定的数据，并且可能有子的znode。

Znode的主要特点：

• 基于Key对象来实现/维护分布式一致性信息
• 通过数据改变的版本信息、ACL改变和timestamp来维护一致性
• 每次改变版本号都会增加
• Znode不是用来存数据的，只是用来存储一些configuration和meta-data
• 每个znode可以存timestamp和version信息

Znode的类型：

1. Persist vs. Ephemeral
   • persist节点：一旦被创建不会轻易丢失，即使数据库重启也依然在，每个persist可以包含数据，也可以包含子节点
   • ephemeral节点：在session结束或过期后自动删除。服务器的重启也会导致ephemeral接触（可以用于做分布式锁）
2. Sequence vs. Non-sequence
   • sequence节点：创建出的节点名在指定名称后带有10位10进制数的序号。多克客户端创建同一名称的节点时，都能创建成功，只是序号不同
   • non-sequence节点：多客户端在同时创建同一non-sequence节点时，只有一个可创建成功，其他失败。创建出的节点与指定名称完全相同

Watch机制：

• 主动推送：当watch被触发时，zk服务器辉主动将更新推送给client，而不是靠client的轮询（观察者模式）
• 一次性触发：watch只会被触发一次，后续更新通知必须重新注册一个watch

Session的特点：

• session是每个client到server的连接，zk支持每个client在保存同个session的基础上切换到不同的server
• 内建超时机制
• 执行顺序的保证是基于同个session的（即会话一致性）

Zookeeper的一致性

数据一致性：

一致性是指多副本中数据的一致性，以下是个简单整理（程度由强到弱）：

1. 强一致性：有原子一致性、线性一致性，有两个要求：
   • 任何一次读都能读到某个数据最近一次写到数据
   • 系统中所有进程，看到的操作顺序都和全局时钟下看到的顺序一致
2. 顺序一致性：也有两个要求：
   • 任何一次读都能读到最近一次写的数据
   • 系统的所有进程顺序一致，但不一定和全局时钟下看到的数据一致
3. 弱一致性：指数据更新后，有些操作可能访问不到，最终一致性是一种弱一致性，是指任意时刻节点上同一份数据不一定相同，但一段时间后，数据总会达到一致。里面有根据访问分为：
   • 因果一致性：如果A通知B它更新了一个数据（A,B有因果关系），那么B后续访问只能看到更新过的值
   • 读写一致性：当进程A自己更新一个值后，它自己只能访问到更新过的值（会话一致性同理）
   • 单调一致性：当进程看到数据对象的某个值，它就不会再访问到那个值之前的值
4. 补充一点：paxos是共识（consensus）机制，而不是一致性协议

ZK保证的一致性原则

• FIFO一致性：对于同一个客户端，执行一个请求（get、delete这类操作）应该按照他们被发送的顺序；保证该客户端对于notification和状态改变的顺序一致
• 顺序一致性：所以客户端看到的并行写入操作的结果的顺序是一样的，ZAB实现，有点类似paxos
• 原子性：update操作要不成功要不失败，不会有中间结果
• 单系统镜像：同一个client不论连接那个server，看到的数据都应该是完全一致的。对于不同的client则可能看到不同的（因为有延迟）的数据
• 持续性（单调一致性）：当一个更新完成后，他会一直保持直到它被再次更新
• 高可用性：2F+1个服务器可以最多容忍F台服务器崩溃
• 最终一致性：数据在一段时间后最终辉达成一致

ZAB(zookeeper atomic broadcat)协议：

目标

可靠投递：如果一个事务被提交到一个服务器，那它最终会被提交到所有服务器
全局有序：如果一台服务器上事务A在事务B之前提交，那么在所有服务器上事务A一定都在B之前提交
因果有序：如果事务A在事务B之前发生（A,B有因果关系），如果一起被提交，一定是A在B之前执行

协议内容——广播

为了保证一致性，所有写操作都要经过leader完成，由leader进行广播。广播是个简化的二阶段提交过程：

1. leader收到消息请求后，给消息赋予一个全局唯一的64位自增id，叫zxid（类似于rdbms的事务id），通过zxid比较可以实现因果有序
2. leader通过fifo队列将带有zxid的proposal分发给所有follwer
3. 当follwer收到proposal，先存下来，然后返回leader一个ack
4. 当leader收到过半ack后，leader会向所有follwer发送commit命令，同时在本地执行该请求
5. follwer收到commit命令后，执行该请求

值得一提的是，写请求是通过leader广播完成的，但读请求leader或者follwer都可以直接处理，只要从本地内存中读取数据返回client即可

协议内容——恢复

已经proposal的命令应该被备份。例如一些服务器在收到commit之前leader就挂掉了，这个时候就无法执行该请求。当它重启后应该重新执行（client如果挂掉也需要和server重新同步一下）

领导选举

基于TCP的FastLeaderElection

每个zookeeper的服务器都需要在数据文件夹下创建一个名为myid的文件（里面只有一个整数），用来唯一标识该服务器。而在配置文件必须与其一致，选票包括：

• logicClock：表示服务器发起投票轮数，自增整数
• state：当前服务器状态
• self_id：当前服务器myid
• self_zxid：当前服务器最大zxid
• vote_id：推举的服务器myid
• vote_zxid：被推举服务器上最大zxid

具体投票流程为：

1. 初始化选票：清空票箱（票箱中记录了每个服务器最后一次投票）
2. 发送初始化选票：每个服务器都通过广播票投给自己
3. 接受外部投票：尝试从其他服务器获得选票，并计入自己票箱。
4. 判断选举轮数（logicClock）：如果外部logicClock大于自己，则说明自己选举落后于其他服务器，立即清空票箱并将自己logicClock更新为收到的logicClock。再对比自己之前的投票和收到投票logicClock，确认是否需要更新；如果外部logicClock小于自己，则忽略这次投票；相等则进行下一步选票PK
5. 选票PK：是基于myid和zxid的比较，即先选zxid大的，如果zxid相同再选myid比较大的
6. 统计投票：如果半数服务器认可了自己的投票，则终止，否则继续
7. 更新服务器状态：每个服务器根据投票结果更新服务器状态为leading或following

应用

分布式一致性锁

利用名称唯一性，枷锁操作时，只需要所有客户端创建/test/lock节点，只有一个创建成功，即可以获得锁。而解锁时，只要删除/test/lock节点，其他客户端通过watch机制可以继续进入竞争创建节点。如下图：

并发的惊群效应

以上的实现非常简单，但会产生惊群效应，即当锁释放时，所以客户端都会被唤醒，但只有一个客户端可以获得锁。这个可以通过改良分布式锁实现的方式解决。

让所有客户端都在/lock下创建临时顺序节点，如果创建客户端自身节点编号是/lock下最小的节点，则获得锁。其他节点只监视比自己小的的最大节点（如创建节点1、2、5，1获得锁，2只监视1，5只监视2），只有当自己监视的节点释放锁自己才可以获得锁。这种其实是一种按照创建顺序排队的实现。