为什么 zookeeper 不满足线性一致性依然可以实现分布式锁？

在《为什么要使用zookeeper？》（以下简称前文）这篇文章中我们以分布式锁为例介绍了使用 zookeeper 的基本原理及适用场景。前文最后我们遗留了一个问题，分布式锁的实现需要线性一致性保证，而 zookeeper 并不满足线性一致性却依然可以实现分布式锁，本文将对这个问题进一步解答。文章分为两个部分，既然 zookeeper 不满足线性一致性保证，那么它提供了怎样的一致性保证。然后我们介绍 zookeeper 实现分布式的方法及背后原理。

zookeeper 一致性保证

因为一致性概念偏理论理解起来比较抽象，所以为了避免歧义本节参考 zookeeper 官方文档相关内容并加上自己的解读。

ZooKeeper is a high performance, scalable service. Both reads and write operations are designed to be fast, though reads are faster than writes. The reason for this is that in the case of reads, zooKeeper can serve older data, which in turn is due to ZooKeeper's consistency guarantees:

注意我标注下划线内容，根据这一点我们就可以断定 zookeeper 不满足线性一致性（线性一致性要求所有操作像操作一个副本，满足数据读取就近原则）。下文引用官方文档来进一步说明 zookeeper 提供的一致性保证。

• Sequential Consistency : Updates from a client will be applied in the order that they were sent.

这里明确了 zookeeper 对于写数据的顺序性的保证。像大多数共识算法一样，Zab 算法也是采用单一主节点来接收所客户端发送的数据写入请求，主节点收到的写入请求的顺序即为写操作顺序。

• Atomicity : Updates either succeed or fail -- there are no partial results.

此处的原子性和 ACID 中的原子性为同一概念，都是保证数据写入操作要么全部完成要么全部失败，不允许部分结果出现。原子性模型保证可以简化客户端故障处理流程，可以通过简单的重试完成故障恢复。这个原子性和前文中线性一致性中所要求的原子性不是一个概念，线性一致性的原子性强调操作不能交叉进行，也就是没有并发操作。

• Single System Image : A client will see the same view of the service regardless of the server that it connects to. i.e., a client will never see an older view of the system even if the client fails over to a different server with the same session.

单一系统视图并不能意味着读取到最新数据，只能保证了一个客户端读取数据的单调性：客户端一旦读取到最新的数据，它就不会再读取到旧数据了，即使它连接的 zookeeper 节点因为故障致使它不得不连接到另一个节点，它也不会读取到旧数据。

• Reliability : Once an update has been applied, it will persist from that time forward until a client overwrites the update. This guarantee has two corollaries:

• If a client gets a successful return code, the update will have been applied. On some failures (communication errors, timeouts, etc) the client will not know if the update has applied or not. We take steps to minimize the failures, but the guarantee is only present with successful return codes. (This is called the monotonicity condition in Paxos.)

• Any updates that are seen by the client, through a read request or successful update, will never be rolled back when recovering from server failures.

可靠性保证和 ACID 中的持久性保证类似，大家参照原文自行理解即可。

• Timeliness : The clients view of the system is guaranteed to be up-to-date within a certain time bound (on the order of tens of seconds). Either system changes will be seen by a client within this bound, or the client will detect a service outage.

及时性强调了在一个十秒为单位的时间窗口内客户端可以看到数据变更或者检测到系统中断，也就相当于给写入数据在 zookeeper 整个集群内完成复制拟定了一个时间范围。

Note:Sometimes developers mistakenly assume one other guarantee that ZooKeeper does not in fact make. This is: * Simultaneously Consistent Cross-Client Views* : ZooKeeper does not guarantee that at every instance in time, two different clients will have identical views of ZooKeeper data. Due to factors like network delays, one client may perform an update before another client gets notified of the change. Consider the scenario of two clients, A and B. If client A sets the value of a znode /a from 0 to 1, then tells client B to read /a, client B may read the old value of 0, depending on which server it is connected to. If it is important that Client A and Client B read the same value, Client B should call the sync() method from the ZooKeeper API method before it performs its read. So, ZooKeeper by itself doesn't guarantee that changes occur synchronously across all servers, but ZooKeeper primitives can be used to construct higher level functions that provide useful client synchronization.

zookeeper 官方文档还特意说明了 zookeeper 并不保证同步复制，所以不同的客户端可能在从节点上读取到旧数据，打消了 zookeeper 支持线性一致性读错误理解。

以上内容引自：https://zookeeper.apache.org/doc/r3.9.0/zookeeperProgrammers.html#ch_zkGuarantees

最后我们来总结一下，通过对官方文档一致性保证内容的解读，zookeeper 支持对于写操作的线性一致性——所有客户端的写操作都按照主节点的顺序操作。而对于读操作并不保证线性一致性，在一个客户端视角保证单调性读——既一个客户端一旦读取到最新值就不会读取到旧值，但是在多个客户端视角更像最终一致性——一个客户端读取到新值，而另一个客户端可能读取到旧值，但是一段时间后也会读取到新值。

使用 zookeeper 实现分布式锁

简单实现

回顾一下前文中使用 zookeeper 实现分布式的示例。我们利用“同一级节点 key 名称是唯一的”这个特性，让不同的多个客户端使用 create()方法创造了一个永久节点（create /lock 0），客户端通过判断请求是否成功来判断自己是否加锁成功。释放锁的方法很简单，就是使用 delete 命令删除节点即可（delete /lock）。但是这样有两个问题：

• 一个客户端释放锁后，其他客户端无法感知这个操作。所以只能通过定期轮询的方式再次请求加锁。

• 客户端进程崩溃、网路故障等原因都可能造成未能调用 unlock 方法（或者调用失败），此时锁不能被正确被释放阻塞后续其他客户端操作。

所以我们对分布式锁又提出了两个新的要求：

• 锁释放后其他等待锁的客户端可以收到通知并再次请求锁，无需客户端自己轮序操作。

• 无论出现任何异常情况，锁都能被正确的释放。

改进版实现

要满足以上两点新的要求，需要用到 zookeeper 两个特性，第一个是临时节点，第二个是 watch 机制。watch 机制类似于观察者模式，watch 流程是客户端向服务端某个节点路径上注册一个 watcher，同时客户端也会存储特定的 watcher，当节点数据或子节点发生变化时，服务端通知客户端，客户端进行回调处理。通过 watch 机制其他待加锁客户端可以监听节点变化以获取锁的信息，避免无效的轮序操作。zookeeper 创建节点的时候可以选择临时节点，临时节点的特点就是一旦 session 关闭，临时节点清除。这样一旦加锁的客户端发生故障（或网络异常）造成客户端和 zookeeper 间 session 关闭，临时节点就会被释放，规避了锁长期占有的情况。使用两个新的特性后新的加锁操作步骤如下：

1. 使用 create 命令创建一个临时节点（create -e /lock 0），客户端通过命令的返回结果判断自己是否获得了锁

2. 所有没有获取锁的客户端使用 exists 命令判断节点是否存在并监听节点变化（exists -w /lock）。如果节点不存在重新执行步骤 1。（节点不存在有两种情况，一种是创建节点的数据复制延时读取到旧的数据，一种是节点被另一个客户端释放锁的行为删除了）

3. 如果节点存在客户端等待节点的删除通知，一旦收到节点删除的通知重新执行步骤 1。（节点存在也有两种情况，一种是节点依然被另一个客户端作为锁持有。一种是节点已经被另一个客户端释放锁而删除，但是此处因为复制延时而读取到了旧数据）

通过以上步骤我们发现，exists 命令也有可能读取到旧数据。这样是否会影响到加锁逻辑的正确性，我们详细分析一下。在步骤 2 中如果客户端读取到了旧数据，也就是添加节点行为的复制延时让客户端误认为节点暂不存在，通过再次执行步骤 1 就可以避免此问题。而在步骤 3 中如果客户端读取到了过期数据，误以为此时锁还没有被释放而进入了等待通知状态，是不是就会一直等待下去呢？答案是否定的，此处就用到了 zookeeper 中关于 watch 机制的相关保证：

With regard to watches, ZooKeeper maintains these guarantees:

• Watches are ordered with respect to other events, other watches, and asynchronous replies. The ZooKeeper client libraries ensures that everything is dispatched in order.

• ++A client will see a watch event for a znode it is watching before seeing the new data that corresponds to that znode.++

• The order of watch events from ZooKeeper corresponds to the order of the updates as seen by the ZooKeeper service.以上内容引自：https://zookeeper.apache.org/doc/r3.9.0/zookeeperProgrammers.html#sc_WatchGuarantees
  

注意我标注的文字，表明了一个客户端应该先收到它所观察的节点的事件通知然后才会看到这个节点的变化。具体到上面的问题就是即使步骤 3 中客户端因为读取旧的数据误以为锁未被释放进入了等待通知状态，客户端也一定可以收到节点删除的事件，从等待中被唤醒。因为根据 watch 机制的保证，如果读取到过期的数据，那么也一定还没有接收到导致数据变化的事件通知。

至此我们已经说明了，无论 exists 命令读取到了新增节点的延时数据还是删除节点的延时数据，均不影响加锁的正确性。但是如果你详细阅读过 zookeeper 的官方文档或者 Curator 等 zookeeper 客户端的源码，你就会发现上面的方法并不是 zookeeper 推荐的方案，而是在这个方案上更近一步规避了“羊群效应”。什么是“羊群效应”呢？以上加锁方法所有客户端都新建一个节点并监听节点变化，一旦这个节点删除所有客户端都会收到通知并同时并发新建这个节点，但依然只有一个节点可以添加成功，客户端少的情况下还好，一旦客户端较多，这种周期性、大量的并发访问加重了集群的负担，也降低了分布式锁的执行效率。zookeeper 为我们提供了一种更好的实现方式。

zookeeper 官方文档实现

zookeeper 官方推荐的分布式锁的实现步骤如下：

1. 客户端调用 create 命令创建一个临时顺序节点（create -s -e locks/lock-）

2. 客户端通过 getChildren 方法查看 locks 节点下子节点情况

3. 如果 locks 节点下所有子节点的最小序号节点等于步骤 1 中创建操作返回的临时顺序节点的序号，说明获取锁成功。

4. 否则就用 exists 命令判断小于自己创建节点序号的上一个节点是否存在，并 watch 此节点变化。

5. 如果节点存在，等待节点删除时间的通知，受到通知后跳转到步骤 2 重新执行。如果节点不存在直接跳转到步骤 2 执行。

以上内容引自：https://zookeeper.apache.org/doc/r3.9.0/recipes.html#sc_recipes_Locks

有序节点会在创建节点的时候为自动为节点添加序号后缀，三个客户端执行步骤 1 后目录示例如下：

+/locks++lock-01++lock-02++lock-03

其中，01、02、03 由 zookeeper 写入数据的顺序一致性保证，可产生一个全局唯一的单调递增的编号，这就是加锁的核心逻辑，我们不再通过 create 命令唯一性保证加锁操作的排他性，而是通过判断哪个客户端创建了最小序号的有序节点来判断加锁行为。这样就带来了两个显而易见的好处，第一，未获得锁的客户端重新争抢锁的时候不需要重新创建节点，只需要判断自己已经创建的节点是不是变成了当前最小的节点即可。第二，所有未获取到锁的客户端无需只都监听一个节点的状态来获取锁释放的消息，而是监听比自身序号小的上一个节点状态变化。这样就按照加锁操作的先后顺序形成了一个释放通知队列，避免了所有未获取锁的客户端在锁释放后一拥而上重新争抢锁的羊群效应。这两点好处可以显著提高 zookeeper 分布式锁执行效率。

加锁步骤中的 getChildren 和 exists 这两个读操作也会出现读取到过期数据的问题，读者可以根据上文中对 exists 命令的分析方式划分为两种情况（一种是没有读取已经新建的节点数据，另一种是读取到了已被删除的节点数据。）展开分析以确定读取到过期数据的行为不会对加锁逻辑造成影响。

总结

接下来我们总结一下本文内容。文章开头我们介绍了 zookeeper 的一致性模型，zookeeper 仅对写操作提供线性一致性保证，无论多少个客户端的写操作在 zookeeper 集群全局有序。而对于跨客户端的读操作，zookeeper 仅能提供类似于最终一致性的保证。接下来我们介绍了三种锁的实现方式，首先介绍了最简单的实现方式，仅仅使用 create 命令不能创建同名节点的特性实现加锁逻辑，本质上也是利用 zookeeper 写线性一致性保证。然后我们引入临时节点和事件监听概念，改进了加锁逻辑以解决释放锁后通知及异常未释放锁这两个问题，并且为了处理 exists 命令读取到延时数据问题，依赖了 zookeeper 事件监听机制顺序性保证。最后我们又引入有序节点的概念，规避“羊群效应”。为了正确高效的使用 zookeeper 实现一个分布式锁，我们依赖于的写数据线性一致性保证、临时节点、有序节点、节点监听机制、监听事件顺序性保证等诸多 zookeeper 功能及特性，正是依赖于以上众多功能和特性才能保证 zookeeper 即使并不满足读数据的线性一致性保证，依然可以实现一个分布式锁。但是这也也增加了具体代码的实现难度和复杂度。zookeeper 本身定位是一个底层服务，直接使用起来比较困难，在实际应用场景下我们可以使用 Curator 这类 zookeeper 客户端来简化使用难度。以上就是本文全部内容，如果你有疑问或建议欢迎给我留言，我们大家一起探讨。