一、引言
大型分布式系统需要不同形式的协调服务。配置是最基本的协调形式之一，在其最简单的形式中，配置只是系统流程的操作参数列表，而更复杂的系统具有动态配置参数。组成员和领导选举在分布式系统中也很常见:进程通常需要知道哪些其他进程是活动的，以及这些进程负责什么。
在设计协调服务时，zookeeper的设计者不再在服务器端实现特定的原语，而是选择公开一个API，使应用程序开发人员能够实现他们自己的原语。这样的设计需要一个可以被用来组成各种协调服务的内核，它支持开发者实现自己的原语，而不需要更改服务核心。这种方法支持适应于应用程序需求的多种形式的协调，而不是将开发人员限制在一组固定的原语集合中。
二、Zookeeper的服务
1.服务概览
ZooKeeper为其客户端提供了一组数据节点(znodes)的抽象，这些数据节点是根据层次命名空间组织的。这个层次结构中的znode是客户端通过ZooKeeper API操作的数据对象。层级命名空间通常用于文件系统。这是一种理想的数据对象组织方式，因为用户已经习惯了这种抽象，并且它能够更好地组织应用程序元数据。为了引用给定的znode，我们使用标准的UNIX符号表示文件系统路径。例如，我们使用/A/B/C来表示znode C的路径，其中C的父节点是B，而B的父节点是A。所有znode都存储数据，除了临时znode之外，所有znode都可以有子节点。
客户端可以创建两种类型的znode:
- Regular:客户端通过显式的创建和删除来操纵常规的znode。
- Ephemeral:客户端显式的创建，显式的删除或者session到期后系统自动删除。
此外，在创建新znode时，客户端可以设置一个顺序标志。使用顺序标志集创建的节点的名称后面附加了一个单调递增的计数器的值。如果n是新的znode, p是父znode，那么n的序列值永远不会小于在p下创建的任何其他顺序znode的名称中的值。
ZooKeeper实现了监控(watch)，允许客户端在不需要轮询的情况下及时接收更改通知。当客户端发出设置了watch标志的读操作时，操作将正常进行，但是服务端会承诺当该znode发生改变时通知客户端。watch是与session关联的一次性触发器;一旦触发或会话关闭，它们将被取消注册。watch只是通知客户端发生了更改但不提供更改后的内容。例如，如果客户端在“/foo”更改两次之前发出getData(" /foo"， true)，客户端只会获得一个watch事件，告诉客户端“/foo”的数据已经更改。
2.客户端API
- **create(path, data, flags): **创建一个具有路径名path的znode，在其中存储数据[]，并返回新znode的名称。标志使客户端能够选择znode的类型:常规、临时和设置顺序标志;
- **delete(path, version): **如果znode在预期版本中，则删除该znode路径;
- **exists(path, watch): **如果具有路径名path的znode存在，则返回true，否则返回false。监视标志允许客户端在znode上设置一个监视;
- getData(path, watch):返回与znode关联的数据和元数据，例如版本信息。watch标志的工作方式与exists()的工作方式相同，但如果znode不存在，ZooKeeper不设置watch;
- setData(path, data, version):如果版本号是znode的当前版本，则向znode路径写入数据;
- getChildren(path, watch):返回znode子节点的名称集;
- **sync(path): **等待在操作开始时挂起的所有更新传播到客户机连接的服务器。该路径当前被忽略。
所有方法都有一个同步和一个异步版本，可以通过API使用。当应用程序需要执行单个ZooKeeper操作且没有要执行的并发任务时，它会使用同步API，因此它会执行必要的ZooKeeper调用并阻塞。然而，异步API使应用程序能够同时执行多个ZooKeeper操作和其他任务。ZooKeeper客户端保证按顺序调用每个操作的相应回调。
3.ZooKeeper的保证
ZooKeeper有两个最基本的顺序保证：
- Linearizable writes: 所有更新ZooKeeper状态的请求都是串行化的，并且是优先级高的优先的;
- FIFO client order: 来自给定客户机的所有请求都是按照客户机发送请求的顺序执行的。
要查看这两个保证如何交互，请考虑以下场景。由多个进程组成的系统选出一个leader来指挥工作进程。当新的leader接管系统时，必须改变大量的配置参数，并在完成后通知其他进程。然后我们有两个重要的要求
- 当新leader开始进行更改时，我们不希望其他进程开始使用正在更改的配置;
- 如果新的leader在配置完全更新之前死亡，我们不希望工作进程使用这个残缺的配置。
使用ZooKeeper，新leader可以指定一条路径作为ready znode;其他进程仅在znode存在时才使用配置。新的leader通过删除ready、更新各种配置znodes和创建ready来更改配置。由于顺序保证，如果一个进程看到就绪的znode，它必定看到新leader所做的所有配置更改。如果新的leader在就绪的znode创建之前死亡，那么其他进程就知道配置还没有完成，所以不会使用它。
上面的方案仍然有一个问题:如果工作进程在新leader开始进行更改之前看到就绪，然后在更改过程中开始读取配置，那么会发生什么情况? 这个问题通过通知的顺序保证解决了:如果客户端正在监视更改，那么客户端将在更改后看到系统的新状态之前看到通知事件。因此，如果读取就绪znode的进程请求接收该znode的更改通知，那么它将在读取任何新配置之前看到通知客户端更改的通知。
当客户端除了ZooKeeper之外还有自己的通信渠道时，就会出现另一个问题。例如，考虑两个客户端A和B，它们在ZooKeeper中具有共享配置，并且通过共享通信通道进行通信。如果A更改了ZooKeeper中的共享配置，并通过共享通信通道将更改告知B，则B将在重新读取配置时看到更改。如果B的ZooKeeper副本稍微落后于A，则可能看不到新配置。使用上述保证，B可以在重新读取配置之前发出写操作，从而确保看到最新的信息。为了更有效地处理这个场景，ZooKeeper提供了sync请求:当后面跟着一个读操作时，就构成了一个慢读操作。sync会导致服务器在处理读之前应用所有挂起的写请求，而不会产生完全写的开销。
4.原语示例
- Configuration Management：可以使用ZooKeeper在分布式应用程序中实现动态配置。其最简单的形式是将配置存储在znode (zc)中。进程以zc的完整路径名启动。工作进程通过读取zc来获取配置，并且在读取配置的时候设置watch标志为true。如果zc中的配置被更新，进程将得到通知并读取新的配置，再次将watch标志设置为true。请注意，在这个方案中，与其他大多数使用监控的方案一样，使用watch是为了确保某个进程拥有最新的信息。
- Rendezvous：有时在分布式系统中，并不总是预先清楚最终的系统配置是什么样子的。例如,客户可能想要开始一个主进程和几个工作进程,但过程是通过一个调度程序开始,所以客户不知道提前信息,比如地址和端口,它可以给连接到主的工作进程。我们使用ZooKeeper来处理这个场景，它使用的是客户端创建的一个节点zr。客户机将zr的完整路径名作为主进程和辅助进程的启动参数传递。当主服务器启动时，它将使用有关地址和端口的信息填充zr。当工作进程开始工作时，他们将zr设置为真。如果zr还没有被填充，那么当zr被更新时，worker将等待被通知。如果zr是一个临时节点，主进程和工作进程可以监视要删除的zr，并在客户机结束时清理它们自己。
- **Group Membership: **我们利用临时节点来实现组成员关系。具体来说，我们使用临时节点来查看创建节点的会话的状态。我们首先指定一个znode, zg来代表这个组。当组中的某个进程成员启动时，它将在zg下创建一个临时的子znode。如果每个进程有唯一的名称或标识符，则该名称用作子znode的名称;否则，该进程将使用序列标志创建znode，以获得唯一的名称分配。进程可以将进程信息放入子znode的数据中，例如，进程使用的地址和端口。在zg下创建子znode之后，进程将正常启动。它不需要做任何其他事情。如果进程失败或结束，则在zg下表示它的znode将被自动删除。进程可以通过简单地列出zg的子进程来获得组信息。如果某个流程希望监视组成员关系中的更改，则可以在接收更改通知时将监视标志设置为true并刷新组信息(始终将监视标志设置为true)。
- **Simple Locks: **虽然ZooKeeper不是一个锁服务，但它可以用来实现锁。使用ZooKeeper的应用程序通常使用根据需要定制的同步原语，如上图所示。在这里，我们将展示如何使用ZooKeeper实现锁，以说明它可以实现各种各样的通用同步原语。最简单的锁实现使用“锁文件”。锁由znode表示。要获取锁，客户机尝试使用临时标记创建指定的znode。如果创建成功，客户端持有锁。否则，客户端可以读取znode，并将监视标志设置为在当前leader结束时得到通知。客户端在死锁或显式删除znode时释放锁。等待锁的其他客户端在观察到znode被删除后再次尝试获取锁。虽然这个简单的锁定协议可以工作，但它确实存在一些问题。首先，它受到羊群效应的影响。如果有许多客户端等待获得锁，那么当锁被释放时，他们都会争着获得锁，即使只有一个客户端可以获得锁。其次，它只实现排它锁定。下面两个原语展示了如何克服这两个问题。
- Simple Locks without Herd Effect：我们定义了一个锁znode l来实现这些锁。直观地，我们将所有请求锁的客户端排成一行，每个客户端按照请求到达的顺序获得锁。因此，客户希望获得锁做以下工作:
在锁的第1行中使用顺序标志，将客户机获取锁的尝试与所有其他尝试相比较。如果客户机的znode在第3行拥有最低的序列号，则客户机持有锁。否则，客户机将等待删除znode，该znode要么拥有锁，要么将在该客户机的znode之前接收锁。通过只观察客户机的znode之前的znode，我们可以避免羊群效应，在释放锁或放弃锁请求时只唤醒一个进程。一旦客户端监视的znode离开，客户端必须检查它现在是否持有锁。(先前的锁请求可能已经被放弃，并且有一个序列号较低的znode仍然在等待或持有锁。)释放锁与删除表示锁请求的znode n一样简单。通过使用
临时标记创建时，崩溃的进程将自动清除任何锁请求或释放它们可能拥有的任何锁。综上所述，该锁定方案具有以下优点:
1. 删除一个znode只会导致一个客户端醒来，因为每个znode都被另一个客户端监视，所以我们不存在羊群效应;
2. 没有轮询或超时;
3.由于我们实现锁定的方式，我们可以通过浏览ZooKeeper数据来查看锁争用、解锁和调试锁定问题的数量。
- Read/Write Locks：为了实现读/写锁，我们稍微改变了锁的过程，并有单独的读锁和写锁的过程。解锁过程与全局锁的情况相同。
这个锁过程与前面的锁略有不同。写锁只在命名上有所不同。因为读锁可以共享，所以第3行和第4行略有不同，因为只有更早的写锁znode才能防止客户机获得读锁。当有多个客户端等待读锁并在删除序列号较低的“写”znode时得到通知时，可能会出现“羊群效应”;事实上，这是一个需要的行为，所有那些读客户机都应该被释放，因为它们现在可能有锁了。
三、ZooKeeper实现
ZooKeeper通过在组成服务的每个服务器上复制ZooKeeper数据来提供高可用性。我们假设服务器由于崩溃而失败，而这些有问题的服务器稍后可能会恢复。图4显示了ZooKeeper服务的高层组件。在接收到请求后，服务器将其准备执行(请求处理器)。如果这样的请求需要服务器之间的协调(写请求)，那么它们将使用协议协议(原子广播的实现)，最后服务器将更改提交到整个集成的所有服务器上完全复制的ZooKeeper数据库。对于读请求，服务器只是读取本地数据库的状态并生成对请求的响应。
1.请求预处理器
因为消息层是原子的，所以我们保证本地副本不会发散，尽管在任何时候，一些服务器可能比其他服务器应用了更多的事务。与客户端发送的请求不同，事务是幂等的。当leader收到写请求时，它会计算应用写时系统的状态，并将其转换为捕获这个新状态的事务。必须计算将来的状态，因为可能有尚未应用到数据库的未完成事务。例如，如果客户端执行一个条件setData，并且请求中的版本号与正在更新的znode的未来版本号匹配，那么服务将生成一个setDataTXN，其中包含新数据、新版本号和更新的时间戳。如果发生错误，例如不匹配的版本号或要更新的znode不存在，则生成errorTXN。
2.原子广播
3.副本数据库
每个zookeeper实例在内存中都有一个zookeeper状态的副本。当ZooKeeper服务器从崩溃中恢复时，它需要恢复这个内部状态。在运行服务器一段时间后，重播所有已交付的消息以恢复状态的时间可能会非常长，因此ZooKeeper使用定期快照，并且只需要从快照开始重新交付消息即可。我们称ZooKeeper快照为fuzzy快照，因为我们没有锁定ZooKeeper状态来获取快照;相反，我们首先对树进行深度优先遍历，原子性地读取每个znode的数据和元数据，并将它们写入磁盘。由于产生的模糊快照可能应用了快照生成期间交付的状态更改的某个子集，因此结果可能在任何时间点都不对应于ZooKeeper的状态。但是，由于状态变化是幂等的，所以我们可以将它们应用到两倍于按顺序应用状态变化的时间。
例如，假设在一个ZooKeeper数据树中，两个节点/foo和/goo分别具有f1和g1值，当模糊快照开始时，这两个节点都处于版本1，状态更改的数据流形式<transactionType, path, value, new-version>如下：
<SetDataTXN, /foo, f2, 2>
<SetDataTXN, /goo, g2, 2>
<SetDataTXN, /foo, f3, 3>
在处理这些状态更改之后，/foo和/goo的值分别为f3和g2，版本分别为3和2。但是，模糊快照可能记录了/foo和/goo的值分别为f3和g1，版本分别为3和1，这不是ZooKeeper数据树的有效状态。如果服务器崩溃并使用此快照进行恢复，并且Zab重新提交状态更改，则结果状态对应于崩溃前的服务状态。
参考：
http://www.cs.cornell.edu/courses/cs6452/2012sp/papers/zookeeper-usenix10.pdf
