本文是读ZooKeeper: Wait-free coordination for Internet-scale systems的笔记，从第一手资料了解zookeeper
概述
什么是zookeeper？
a service for coordinating(协调) processes of distributed applications，是一个重要的基础服务，目标是从更底层提供一个简单、高性能的服务，用来按需构建同步服务
zookeeper（动物管理员），为什么叫这个名字？
zookeeper是Hadoop和Hbase的重要组件，hadoop里面各种组件都是以动物命名的，而zookeeper相当于这动物园的管理员了
zookeeper特点是什么？
提供了一组通用（generic）的，无等待的（wait-free）api，同时提供了两个重要的特性：
保证每个客户端请求FIFO
所有写请求串行进行
结果是读请求能够读本地，从而能够满足可扩展性
介绍
大的分布式系统对coordination提出了各种各样的需求:
Configuration：包括静态的操作数组和动态的配置参数
Group membership：哪些server还存活着
leader election：每个server都负责什么
解决上述coordination需求的一种方案是：为每种coordination需求都开发专门的服务。但是我们要知道一个道理：更powerful primitives的实现可以用于less powerful primitives，所以基于这个假设我们在设计coordination的服务上：我们不在实现具体的primitives，而是提供通用（generic）的API来实现满足个性化的primitives，一旦作出这种决策，带来的好处有两点：
coordination kernel帮助我们在不改变服务核心的情况下实现新的primitives
根据应用需求提供更多样化的primitives
在设计ZooKeeper的API的时候，我们移除了阻塞primitives，如锁，基于的考虑有如下两点：
阻塞primitives会导致处理慢的客户端影响相对较快的客户端
由于请求在处理上依赖于其他客户端的响应和失败的检查，那ZooKeeper本身实现上也会更复杂
ZooKeeper由于实现了wait-free的数据对象，从而和其他基于阻塞语义（blocking primitives）有了显著的区别，ZooKeeper在组织wait-free的数据对象借鉴了文件系统的思路，将wait-free的数据对象按层级组织起来，不同只是移除了open和close这种阻塞方法。
仅仅靠wait-free来实现coordination是不够的，还需要提供操作的有序保证（order guarantees）：每个客户端FIFO，所有写请求linearizable。
ZooKeeper实现了pipelined architecture，提高了系统的吞吐。客户端可以同时发出多个请求，异步执行，同时保证请求的FIFO。
为了实现写请求linearizable，实现了Zab协议，一个leader-based atomic broadcast protocol，但是对于读请求，我们不适用Zab，只是本地读，这样能很方便的扩展系统。
在客户端缓存数据可以有效的提高系统性能，但是缓存的数据怎么更新呢？ZooKeeper使用watch机制，不直接操作客户端缓存，这是因为：由于Chubby直接管理客户端缓存，一旦某个客户端处理慢了（可能是挂了），会导致阻塞数据更新。针对这个问题，Chubby使用租期来解决，一旦某个客户端有错误，不会影响更新操作太长时间，但这也只是确定了影响的上限，无法避免，而ZooKeeper的watches可以彻底解决改问题。
总结起来，本篇论文的主要内容是：
Coordination kernel：基础设施，提出了wait-free的方案
Coordination recipes：应用，个性化primitives的实现
Experience with Coordination：心得，具体案例和评测
Zookeeper服务
ZooKeeper提供了client library来访问服务，client library主要做两件事：
管理client和ZooKeeper之间的网络连接
提供ZooKeeper的api
术语：
client：a user of the ZooKeeper service
server：a process providing the ZooKeeper service
znode：an in-memory data node in the ZooKeeper data
data tree：像文件系统一样按层级组织的命名空间
update，write：改变data tree状态的操作
session：client和ZooKeeper之间的网络连接
Service overview
ZooKeeper给客户端提供了znode的抽象，客户端通过api来操作znode中存储的数据，znode的地址类似文件系统中的path，像上图中节点p_1就通过路径/app1/p_1来访问，客户端可以创建两种znode：
Regular: 需要客户端显式的创建和删除
ephemeral: 客户端创建，也可以删除，也可以当会话终止时候让系统自动删除
除此之外，创建的时候可以带sequential的flag，此时创建znode p，则会自动带上一个下标n，n是一个单调递增的数，并且满足seq(parent)>= max(children)，意思是新建的node，其下标总是大于其父节点下面创建过的所有node的最大n。
watches怎么创建？
读请求上设置watch参数
watches作用？
客户端不必轮询服务器获取数据，当数据发生改变的时候，通知客户端
watches什么时候失效？
当数据发生改变通知客户端后
session关闭
watches通知了什么？
watches通知只是告知状态改变了，但是不提供改变的数据
数据模型
如图一所示：类似于文件系统，但是znodes不是用来做数据存储的，而是用来跟实际的应用映射的，像图1中，有两个应用app1,app2，app1下面实现了个简单的group membership protocol。
虽然znode设计之初不是为了存储数据，但是也可以存储一些meta-data或者configuration信息，同时znode本身会存储time stamps 和 version counters等元信息
会话（sessions）
代表client和ZooKeeper之间的网络连接，作用有：
server端可以通过sessions超时来判断客户端是否健在
客户端可以通过sessions观察其操作的一连串变化
sessions使得client的连接可以从一个server透明的转移到另一个server，因此可以持续的提供client服务
Client API
create(path, data, flags)
delete(path, version) //if znode.version = version, then delete
exists(path, watch)
getData(path, watch)
setData(path, data, version) //if znode.version = version, then update
getChildren(path, watch)
sync()
以上所有操作有syn和asyn两个版本。ZooKeeper的客户端保证所有写操作是完全有序的，写操作后其他client的写能看到。
在访问的znode的时候都是通过完整的path来访问的，而不是像文件系统那样通过open,close来操作文件句柄，大大简化了servers端的复杂度，不需要保存额外的信息了。
ZooKeeper guarantees
Linearizable writes：所有写请求有序
FIFO client order：每个客户端请求FIFO
考虑场景：leader election
当新的leader产生的时候，需要改变大量的配置后，通知其他processes，需要满足两个要求：
新leader改变配置的时候，其他processes不能读取不完整的配置
新leader在改变配置过程中挂了，其他processes不能使用这个不完整的配置
通过锁能满足第一个需求，zookeeper的实现：
新leader改变前删除 ready znode
改变配置（通过pipeline加速）
新建 ready znode
因为写顺序的保证，其他客户端能看到ready的时候，肯定新配置也生效了，如果在更改配置中leader挂了，就不会有ready。
上面仍然有一个问题：如果process先是看到了ready，此时在读取之前，leader删除了ready，开始更改配置，那process会读取到不完整的配置了，怎么解决呢？
这是通过对通知的顺序性保证解决的：
if a client is watching for a change, the client will see the notification event before it sees the new state of the system after the change is made.Consequently, if the process that reads the ready znode requests to be notified of changes to that znode, it will see a notification informing the client of the change before it can read any of the new configuration.
客户端将会在看到改变后的状态之前收到通知事件，因此，当process可以读取ready新状态之前，会先收到状态改变的通知
另一个可能的问题是：客户端之间除了ZooKeeper之外，还有别的通信通道，场景是：
A和B在ZooKeeper上有共享数据，A改变数据后，通过其他通信手段告诉B数据改变了，此时B去读取数据，可能会读取不到改变的数据，因为ZooKeeper集群可能存在的主从延迟，解决方案是：B读之前先发个sync请求，类似于文件系统中的flush操作，让数据同步给各个server。
除此之外，ZooKeeper还有两个保证：
高可用，只要大多数机器还存活，就能提供服务
数据可靠：只要ZooKeeper回复写成功，则数据最终一定会存在在服务器上
Examples of primitives
配置管理
约定
群管理（Group Membership）
锁
最简单的锁就是在特定path里检测有没有znode，没有则acquire lock，新建ephemeral znode。release的时候删除该znode。但这么做会有问题，如果有很多个client在等待锁，那么当锁释放的时候会产生惊群效应(herd effect)。第二点是这只能实现排他锁（exclusive locking）
Lock
1 n = create(l + “/lock-”, EPHEMERAL|SEQUENTIAL)
2 C = getChildren(l, false)
3 if n is lowest znode in C, exit
4 p = znode in C ordered just before n
5 if exists(p, true) wait for watch event
6 goto 2
Unlock
1 delete(n)
只有seq numeber最低的znode能够acuqire锁，不然就等待，每次只通知一个client
- 读写锁
Write Lock
1 n = create(l + “/write-”, EPHEMERAL|SEQUENTIAL)
2 C = getChildren(l, false)
3 if n is lowest znode in C, exit
4 p = znode in C ordered just before n
5 if exists(p, true) wait for event
6 goto 2
Read Lock
1 n = create(l + “/read-”, EPHEMERAL|SEQUENTIAL)
2 C = getChildren(l, false)
3 if no write znodes lower than n in C, exit
4 p = write znode in C ordered just before n
5 if exists(p, true) wait for event
6 goto 3
写锁和前面的一样
读锁需要等待seq num小的znode里没有写操作，读可以并发
ZooKeeper Applications
The Fetching Service
Katta
Yahoo! Message Broker
ZooKeeper Implementation
图4是Zookeeper的组件，如果用raft来理解的话，就包括下面几部分
一致性协议（Zab）
状态机（Database）
Log（日志持久化）
