原创文章,转载请务必将下面这段话置于文章开头处。 本文转发自技术世界,原文链接 http://www.jasongj.com/zookeeper/distributedlock/
如上文《Zookeeper架构及FastLeaderElection机制》所述,Zookeeper 提供了一个类似于 Linux 文件系统的树形结构。该树形结构中每个节点被称为 znode ,可按如下两个维度分类
Zookeeper 简单高效,同时提供如下语义保证,从而使得我们可以利用这些特性提供复杂的服务。
所有对 Zookeeper 的读操作,都可附带一个 Watch 。一旦相应的数据有变化,该 Watch 即被触发。Watch 有如下特点
对于分布式锁(这里特指排它锁)而言,任意时刻,最多只有一个进程(对于单进程内的锁而言是单线程)可以获得锁。
对于领导选举而言,任意时间,最多只有一个成功当选为Leader。否则即出现脑裂(Split brain)
对于分布式锁,需要保证获得锁的进程在释放锁之前可再次获得锁,即锁的可重入性。
对于领导选举,Leader需要能够确认自己已经获得领导权,即确认自己是Leader。
锁的获得者应该能够正确释放已经获得的锁,并且当获得锁的进程宕机时,锁应该自动释放,从而使得其它竞争方可以获得该锁,从而避免出现死锁的状态。
领导应该可以主动放弃领导权,并且当领导所在进程宕机时,领导权应该自动释放,从而使得其它参与者可重新竞争领导而避免进入无主状态。
当获得锁的一方释放锁时,其它对于锁的竞争方需要能够感知到锁的释放,并再次尝试获取锁。
原来的Leader放弃领导权时,其它参与方应该能够感知该事件,并重新发起选举流程。
从上面几个方面可见,分布式锁与领导选举的技术要点非常相似,实际上其实现机制也相近。本章就以领导选举为例来说明二者的实现原理,分布式锁的实现原理也几乎一致。
假设有三个Zookeeper的客户端,如下图所示,同时竞争Leader。这三个客户端同时向Zookeeper集群注册Ephemeral且Non-sequence类型的节点,路径都为/zkroot/leader
(工程实践中,路径名可自定义)。
如上图所示,由于是Non-sequence节点,这三个客户端只会有一个创建成功,其它节点均创建失败。此时,创建成功的客户端(即上图中的Client 1
)即成功竞选为 Leader 。其它客户端(即上图中的Client 2
和Client 3
)此时匀为 Follower。
如果 Leader 打算主动放弃领导权,直接删除/zkroot/leader
节点即可。
如果 Leader 进程意外宕机,其与 Zookeeper 间的 Session 也结束,该节点由于是Ephemeral类型的节点,因此也会自动被删除。
此时/zkroot/leader
节点不复存在,对于其它参与竞选的客户端而言,之前的 Leader 已经放弃了领导权。
由上图可见,创建节点失败的节点,除了成为 Follower 以外,还会向/zkroot/leader
注册一个 Watch ,一旦 Leader 放弃领导权,也即该节点被删除,所有的 Follower 会收到通知。
感知到旧 Leader 放弃领导权后,所有的 Follower 可以再次发起新一轮的领导选举,如下图所示。
从上图中可见
非公平模式
的原因如下图所示,公平领导选举中,各客户端均创建/zkroot/leader
节点,且其类型为Ephemeral与Sequence。
由于是Sequence类型节点,故上图中三个客户端均创建成功,只是序号不一样。此时,每个客户端都会判断自己创建成功的节点的序号是不是当前最小的。如果是,则该客户端为 Leader,否则即为 Follower。
在上图中,Client 1
创建的节点序号为 1 ,Client 2
创建的节点序号为 2,Client 3
创建的节点序号为3。由于最小序号为 1 ,且该节点由Client 1
创建,故Client 1
为 Leader 。
Leader 如果主动放弃领导权,直接删除其创建的节点即可。
如果 Leader 所在进程意外宕机,其与 Zookeeper 间的 Session 结束,由于其创建的节点为Ephemeral类型,故该节点自动被删除。
与非公平模式不同,每个 Follower 并非都 Watch 由 Leader 创建出来的节点,而是 Watch 序号刚好比自己序号小的节点。
在上图中,总共有 1、2、3 共三个节点,因此Client 2
Watch /zkroot/leader1
,Client 3
Watch /zkroot/leader2
。(注:序号应该是10位数字,而非一位数字,这里为了方便,以一位数字代替)
一旦 Leader 宕机,/zkroot/leader1
被删除,Client 2
可得到通知。此时Client 3
由于 Watch 的是/zkroot/leader2
,故不会得到通知。
Client 2
得到/zkroot/leader1
被删除的通知后,不会立即成为新的 Leader 。而是先判断自己的序号 2 是不是当前最小的序号。在该场景下,其序号确为最小。因此Client 2
成为新的 Leader 。
这里要注意,如果在Client 1
放弃领导权之前,Client 2
就宕机了,Client 3
会收到通知。此时Client 3
不会立即成为Leader,而是要先判断自己的序号 3 是否为当前最小序号。很显然,由于Client 1
创建的/zkroot/leader1
还在,因此Client 3
不会成为新的 Leader ,并向Client 2
序号 2 前面的序号,也即 1 创建 Watch。该过程如下图所示。
公平模式
的由来基于 Zookeeper 的领导选举或者分布式锁的实现均基于 Zookeeper 节点的特性及通知机制。充分利用这些特性,还可以开发出适用于其它场景的分布式应用。