用ZooKeeper构建高级结构

　　这节中讲述使用ZooKeeper构建高级功能的方法，都是一些传统的，不需要ZooKeeper特殊支持的功能。希望社区能够在client端的库中考虑这些传统来简化使用和促进标准化。

　　有意思的是虽然ZooKeeper使用异步通知，却可以用它来构造一致同步的基元，比如队列和锁。这是因为ZooKeeper实现了更新的整体有序，并有向外展示这种有序的机制。

　　所有设计遵循实用原则，特别避免了轮询，计时和任何导致“羊群效应”的事情，避免网络暴发和扩容受限。

　　还有很多可以想象的有用功能这里没有提到，比如可撤销读写优先级锁。列举的功能也可以以其它方式实现，总之本文只是为了刺激大家的想象力。

原装可用的功能

　　目录服务和配置是两大ZooKeeper直接提供的功能，另一个是组员管理，组由znode表示，成员由之下的瞬时node表示，掉线的成员被服务检测到后会自动删除。

Barrier

　　分布式系统使用Barrier来阻塞一组进程直到某条件满足。ZooKeeper设计一个barrier node来实现Barrier功能。node存在代表Barrier存在。伪代码如下：

client调用exists并设置watch

如果exists返回假，barrier不存在，进程继续

如果exists返回真，有barrier，进程阻塞等待watch事件

收到watch事件时重新调用exists……直到barrier移除

双Barrier

　　双Barrier用来同步一次计算的开始和结束，当足够多的进程加入barrier，计算开始，完成后离开Barrier。这个前面已经有过实例就不细说了。

　　为提高效率，可以在进程中选出一个lowest进程，其它进程设置watch它，而loweset设置watch任意node，这样每次删除操作最多只通知一个进程，队了lowest删除会通知所有进程。

队列

　　分布式队列是一种常见的数据结构，首先指定一个znode为队列节点，client调用create在此节点上创建以queue-开头的节点，同时设置ephemeral和sequence标识，这样node的path末就会自动添加一个递增的数字。需要从队列中取元素的进程调用getChildren并设置watch，从数字最小的node开始处理，直到队列为空，再次设置watch并等待。

优先级队列

　　稍加改动即可，首先在节点命名改为queue-xx-的形式，xx代表优先级，其次就是每次收到通知都要重新获取子node列表。

锁

　　完全分布式的同步锁，意味着在任意时间点都不会有两个client认为自己获得了同一个锁。

　　首先定义一个锁znode，想获取锁的client执行以下操作：

1. 在锁znode下创建瞬时、序列节点

2. getChildren，不watch（避免羊群效应）

3. 如果1中的节点序列号最小，获得锁，结束流程;

4. 调用exists，watch序列号小于自己的最近的子node，设置watch

5. 如果返回为假，转到2,如果真，等待watch事件后转到2

　　释放锁则只需要删除上述1中创建的znode即可。

　　注意事项：

子znode删除只会唤醒一个进程，因为每个znode只被一个进程watch，从而避免了羊群效应

没有polling超时

这种实现方式便于查看锁的竞争，break和debug相关问题

共享锁

　　共享锁（S锁）：共享 (S) 用于不更改或不更新数据的操作（只读操作），如 SELECT 语句。

　　如果事务T对数据A加上共享锁后，则其他事务只能对A再加共享锁，不能加排他锁。获准共享锁的事务只能读数据，不能修改数据。

　　对上述实现进行一定修改可以实现共享锁：

获取读共享锁

1. create以read-开头的瞬时序列znode

2. getChildren，无watch

3. 如果无以write-开头的znode，有较小的read- znode，获取锁，结束算法

4. exists watch最近的较小的write- znode  

5. 如果返回为假，回到2

6. 等待watch事件后回到2

获取写共享锁

1. create以write-开头的瞬时序列znode

2. getChildren，无watch

3. 如果无较小的znode，获取锁，结束算法

4. exists watch最近的较小znode  

5. 如果返回为假，回到2

6. 等待watch事件后回到2

以上方法看起来似乎可能导致羊群效应，当很多read进程等待一个write进程的时候。实际上这样是合理的，因为上述read进程将被一起释放。羊群效应指的是实际只有一个（或少量）进程能继续时，大量进程被唤醒。

可回收锁

　　以上述算法稍作修改可实现可回收共享锁。步骤1中，create之后马上getData并watch。收到相应事件后再次getData并查找“unlock”字串，表示它必须释放锁。这是因为根据这个共享锁算法，你可以通过对加锁的znode执行setData（“unlock”）来请求拥有锁的进程释放。

　　这个算法要求持有锁的进程同意释放锁，这很重要，特别是如果持有者需要在释放之前执行一些操作。当然你也可以强制实现可回收锁，如果持有者在一定时间后没有释放锁（删除znode），允许请求者删除该znode。

二阶段提交

　　一种允许分布式系统中的所有client同意要么提交事务，要么退出的算法。

　　协调者先创建一个事务znode，例如/app/tx, 再为每个参与者创建相应的子znode，例如/app/tx/s-i，内容未定义。当参与者从协调者处收到事务时，参与者read所有子znode并设置watch，之后执行具体的事务逻辑，完成之后通过write各自投票commit or abort到各自对应的znode, 完成之后其它参与者会收到通知，所有参与者投票后，就可以决定最终结果了。注意在有部分参与都投abort的情况下，有些参与都可以更早决定abort。（类似逻辑运算的提前结束）

　　协调者的职责是创建znode，根据znode决定结果，传播事务到参与者（可以通过写znode实现）。以上实现有两个缺点，第一上消息复杂性，为O(n^2)；二是无法通过ephemeral方式侦测参与者的失效，因为znode不是参与者创建的。

　　要解决第一个问题，可以在事务znode更改时只通知协调者，在作出决定后再通知参与者。这种方式可扩容，但较慢，因为所有的通信要通过协调者。

　　关于第二个问题，可以让协调者通知参与者自己创建相应的znode。

领袖选举 leader election

　　可以通过SEQUENCE|EPHEMERA标签来简单实现，每个进程都在如/election的路径下创建自己的znode，然后znode最小的进程即为leader。

　　当然还需要watch leader的失效，以方便重新选出新的最小znode的leader。比较繁琐的方式是让所有的进程watch leader，这将导致羊群效应：一旦leader失效要向所有的进程发送通告，每个进程都要执行getChildren选出最小znode，如果进程数量巨大将导致ZooKeeper瞬间的大量操作。为了这种情况，避免watch相邻的较小znode即可。