ZooKeeper 配方和解决方案

• 使用 ZooKeeper 创建更高级别结构的指南
  • 有关错误处理的重要说明
  • 开箱即用的应用程序：名称服务、配置、组成员身份
  • 屏障
    • 双重屏障
  • 队列
    • 优先级队列
  • 锁
    • 可恢复错误和 GUID
    • 共享锁
    • 可撤销共享锁
  • 两阶段提交
  • 领导者选举

使用 ZooKeeper 创建更高级别结构的指南

在本文中，您将找到使用 ZooKeeper 实现高阶函数的指南。所有这些都是客户端实现的约定，不需要 ZooKeeper 的特殊支持。希望社区能在客户端库中捕获这些约定，以简化其使用并鼓励标准化。

关于 ZooKeeper 最有趣的事情之一是，即使 ZooKeeper 使用异步通知，您也可以使用它来构建同步一致性基元，例如队列和锁。正如您将看到的，这是可能的，因为 ZooKeeper 对更新施加了总体顺序，并具有公开此排序的机制。

请注意，以下配方尝试采用最佳实践。特别是，它们避免轮询、计时器或任何会导致“羊群效应”、造成流量突发并限制可扩展性的其他内容。

可以想象有很多有用的函数未包含在此处 - 例如，可撤销的读写优先级锁。此处提到的某些结构（尤其是锁）说明了某些要点，即使您可能会发现其他结构（例如事件句柄或队列）是执行相同功能的更实用方法。通常，本节中的示例旨在激发思考。

有关错误处理的重要说明

在实现配方时，您必须处理可恢复异常（请参阅 常见问题解答）。特别是，一些配方采用了顺序临时节点。在创建顺序临时节点时，会出现一种错误情况，即 create() 在服务器上成功，但服务器在将节点名称返回给客户端之前崩溃。当客户端重新连接时，其会话仍然有效，因此不会删除该节点。这意味着客户端难以知道其节点是否已创建。以下配方包括处理此问题的措施。

开箱即用的应用程序：名称服务、配置、组成员身份

名称服务和配置是 ZooKeeper 的两个主要应用程序。这两个函数由 ZooKeeper API 直接提供。

ZooKeeper 直接提供的另一个函数是组成员资格。该组由一个节点表示。组成员在组节点下创建临时节点。当成员节点异常失败时，ZooKeeper 检测到故障后会自动将其删除。

屏障

分布式系统使用屏障来阻止一组节点处理，直到满足条件，此时允许所有节点继续进行。屏障是通过指定屏障节点在 ZooKeeper 中实现的。如果屏障节点存在，则屏障就存在。以下是伪代码

1. 客户端在屏障节点上调用 ZooKeeper API 的exists() 函数，并将watch 设置为 true。
2. 如果exists() 返回 false，则屏障消失，客户端继续进行
3. 否则，如果exists() 返回 true，则客户端等待屏障节点的 ZooKeeper 监视事件。
4. 当触发监视事件时，客户端重新发出exists( ) 调用，再次等待，直到删除屏障节点。

双重屏障

双重障碍使客户端能够同步计算的开始和结束。当足够多的进程加入障碍时，进程开始其计算并在完成计算后离开障碍。本教程展示如何使用 ZooKeeper 节点作为障碍。

本教程中的伪代码将障碍节点表示为b。每个客户端进程p在进入时向障碍节点注册，并在准备离开时注销。节点通过以下Enter过程向障碍节点注册，它等待x个客户端进程注册，然后才继续计算。（此处的x由您决定。）

在进入时，所有进程都在就绪节点上进行监视，并创建一个临时节点作为障碍节点的子项。每个进程（最后一个进程除外）都进入障碍并等待在第 5 行出现就绪节点。创建第 x 个节点（最后一个进程）的进程将在子项列表中看到 x 个节点，并创建就绪节点，唤醒其他进程。请注意，等待进程仅在需要退出时才会唤醒，因此等待是有效的。

在退出时，您不能使用诸如ready之类的标记，因为您正在监视进程节点的消失。通过使用临时节点，在进入障碍后失败的进程不会阻止正确的进程完成。当进程准备离开时，它们需要删除其进程节点并等待所有其他进程执行相同操作。

当b的子项中没有进程节点时，进程退出。但是，为了提高效率，您可以将最低进程节点用作就绪标记。所有其他准备退出的进程都会监视最低现有进程节点的消失，而最低进程的所有者则会监视任何其他进程节点（为简单起见，选择最高节点）的消失。这意味着除了最后一个节点（在删除时唤醒所有人）之外，只有单个进程在每个节点删除时唤醒。

队列

分布式队列是一种常见的数据结构。要在 ZooKeeper 中实现分布式队列，首先指定一个 znode 来保存队列，即队列节点。分布式客户端通过调用 create() 将某些内容放入队列，其中路径名以“queue-”结尾，create() 调用中将序列和临时标志设置为 true。由于设置了序列标志，因此新路径名将采用以下形式：path-to-queue-node/queue-X，其中 X 是单调递增的数字。想要从队列中删除的客户端将调用 ZooKeeper 的 getChildren( ) 函数，其中 watch 在队列节点上设置为 true，并开始处理具有最低数字的节点。客户端无需发出另一个 getChildren( )，直到它用尽从第一个 getChildren( ) 调用中获取的列表。如果队列节点中没有子项，则读取器将等待观察通知以再次检查队列。

注意

现在 ZooKeeper 配方目录中存在队列实现。这与版本一起分发——版本工件的 zookeeper-recipes/zookeeper-recipes-queue 目录。

优先级队列

要实现优先级队列，您只需要对通用 队列配方 进行两个简单的更改。首先，要添加到队列，路径名以“queue-YY”结尾，其中 YY 是元素的优先级，较小的数字表示较高的优先级（就像 UNIX 一样）。其次，在从队列中删除时，客户端使用最新的子项列表，这意味着如果队列节点触发观察通知，客户端将使先前获取的子项列表无效。

锁

完全分布式锁，全局同步，这意味着在任何时间快照中，没有两个客户端认为它们持有相同的锁。这些可以使用 ZooKeeper 实现。与优先级队列一样，首先定义一个锁节点。

注意

现在 ZooKeeper 配方目录中存在锁实现。这与版本一起分发——版本工件的 zookeeper-recipes/zookeeper-recipes-lock 目录。

希望获取锁的客户端执行以下操作

1. 使用“locknode/guid-lock-”的路径名和设置的序列和临时标志调用 create( )。如果错过了 create() 结果，则需要 guid。请参见下面的注释。
2. 在锁节点上调用 getChildren( )，而不设置 watch 标志（这一点很重要，可以避免羊群效应）。
3. 如果步骤 1 中创建的路径名具有最低序列号后缀，则客户端具有锁，并且客户端退出协议。
4. 客户端使用 watch 标志调用 exists( )，该标志设置在具有下一个最低序列号的锁目录中的路径上。
5. 如果 exists( ) 返回 null，则转到步骤 2。否则，在转到步骤 2 之前，等待来自上一步的路径名的通知。

解锁协议非常简单：希望释放锁定的客户端只需删除在步骤 1 中创建的节点。

以下是一些需要注意的事项

• 删除节点只会唤醒一个客户端，因为每个节点都恰好由一个客户端监视。通过这种方式，可以避免羊群效应。

• 没有轮询或超时。

• 由于锁定实现的方式，很容易看到锁定争用的数量、中断锁定、调试锁定问题等。

可恢复错误和 GUID

• 如果在调用 create() 时发生可恢复错误，客户端应调用 getChildren() 并检查是否存在包含路径名称中使用的 guid 的节点。这处理了 create() 在服务器上成功但服务器在返回新节点的名称之前崩溃的情况（如 上文 所述）。

共享锁

通过对锁定协议进行一些更改，可以实现共享锁定

注释

• 似乎此配方会产生羊群效应：当一大群客户端等待读锁定时，并且当序列号最低的“write-”节点被删除时，所有客户端几乎同时收到通知。事实上，这是有效行为：因为所有等待的读取器客户端都应该被释放，因为它们已锁定。羊群效应是指在事实上只有一台或少数机器可以继续时释放“羊群”。

• 请参阅 锁定注释，了解如何在节点中使用 guid。

可撤销共享锁

通过对共享锁定协议进行轻微修改，可以通过修改共享锁定协议使共享锁定可撤销

在步骤1中，在获取读写锁协议的1中，在调用create( )后立即调用getData( )，并设置watch。如果客户端随后收到它在步骤1中创建的节点的通知，它将对该节点执行另一个getData( )，并设置watch并查找字符串“unlock”，这向客户端发出信号，表明它必须释放锁。这是因为，根据此共享锁协议，您可以通过在锁节点上调用setData()并向该节点写入“unlock”来请求带有锁的客户端放弃锁。

请注意，此协议要求锁持有者同意释放锁。这种同意很重要，尤其是在锁持有者在释放锁之前需要进行一些处理时。当然，您始终可以通过在协议中规定撤销者允许在锁持有者未在一段时间内删除锁的情况下删除锁节点来实现带激光束的可撤销共享锁。

两阶段提交

两阶段提交协议是一种算法，它允许分布式系统中的所有客户端同意提交事务或中止事务。

在 ZooKeeper 中，您可以通过让协调器创建事务节点（例如“/app/Tx”）和每个参与站点的一个子节点（例如“/app/Tx/s_i”）来实现两阶段提交。当协调器创建子节点时，它将内容保留为未定义。一旦参与事务的每个站点从协调器收到事务，该站点就会读取每个子节点并设置监视。然后，每个站点处理查询，并通过写入其各自的节点来投票“提交”或“中止”。一旦写入完成，其他站点就会收到通知，并且一旦所有站点都拥有所有投票，它们就可以决定“中止”或“提交”。请注意，如果某个站点投票“中止”，则节点可以更早地决定“中止”。

此实现的一个有趣方面是协调器的唯一作用是决定站点组，创建 ZooKeeper 节点，并将事务传播到相应的站点。事实上，即使通过在事务节点中写入事务，也可以通过 ZooKeeper 传播事务。

上面描述的方法有两个重要的缺点。一个是消息复杂度，即 O(n²)。第二个是无法通过临时节点检测站点故障。要使用临时节点检测站点故障，该站点必须创建该节点。

要解决第一个问题，您可以仅让协调器通知事务节点的更改，然后在协调器做出决定后通知站点。请注意，此方法具有可扩展性，但它也较慢，因为它要求所有通信都通过协调器进行。

要解决第二个问题，您可以让协调器将事务传播到站点，并让每个站点创建自己的临时节点。

领导者选举

使用 ZooKeeper 进行领导者选举的一种简单方法是在创建表示客户端“建议”的 z 节点时使用 SEQUENCE|EPHEMERAL 标志。其思想是拥有一个 z 节点，例如“/election”，每个 z 节点都使用 SEQUENCE|EPHEMERAL 标志创建一个子 z 节点“/election/guid-n_”。使用序列标志，ZooKeeper 会自动追加一个序列号，该序列号大于先前追加到“/election”的任何子序列号。创建具有最小追加序列号的 z 节点的进程是领导者。

但这还不是全部。重要的是要注意领导者的故障，以便在当前领导者故障的情况下，新客户端作为新领导者出现。一个简单的解决方案是让所有应用程序进程监视当前最小的 z 节点，并在最小的 z 节点消失时检查它们是否是新领导者（请注意，如果领导者故障，最小的 z 节点将消失，因为该节点是临时性的）。但这会导致羊群效应：在当前领导者发生故障时，所有其他进程都会收到通知，并在“/election”上执行 getChildren 以获取“/election”的当前子节点列表。如果客户端数量很大，它会导致 ZooKeeper 服务器必须处理的操作数量激增。为了避免羊群效应，只需监视 z 节点序列中的下一个 z 节点即可。如果客户端收到其正在监视的 z 节点已消失的通知，那么在没有更小的 z 节点的情况下，它将成为新领导者。请注意，这避免了羊群效应，因为没有所有客户端都监视同一个 z 节点。

以下是伪代码

让 ELECTION 成为应用程序选择的路径。要自愿成为领导者

1. 使用 SEQUENCE 和 EPHEMERAL 标志创建路径为“ELECTION/guid-n_”的 z 节点 z；
2. 让 C 是“ELECTION”的子项，而我是 z 的序列号；
3. 监视“ELECTION/guid-n_j”上的更改，其中 j 是最大的序列号，使得 j < i 且 n_j 是 C 中的 z 节点；

在收到 z 节点删除通知时

1. 让 C 是 ELECTION 的新子项集；
2. 如果 z 是 C 中最小的节点，则执行领导者程序；
3. 否则，监视“ELECTION/guid-n_j”上的更改，其中 j 是最大的序列号，使得 j < i 且 n_j 是 C 中的 z 节点；

注释

• 请注意，子节点列表中没有前置子节点并不意味着此子节点的创建者知道它是当前领导者。应用程序可以考虑创建单独的子节点以确认领导者已执行领导者程序。

• 请参阅 锁定注释，了解如何在节点中使用 guid。