聊一聊分布式锁的设计模型

一、什么是分布式锁？

什么是分布式锁？对于这个问题，相信很多同学是既熟悉又陌生。随着分布式系统的快速发展与广泛应用，针对共享资源的互斥访问也成为了很多业务必须要面对的需求，这个场景下人们通常会引入分布式锁来解决问题。我们通常会使用怎么样的分布锁服务呢？有开源的 MySQL，Redis，ZooKeeper，Etcd 等三方组件可供选择，当然也有集团内自研的 Tair，Nuwa 等分布式锁服务提供方。总的来看，我们对分布式锁的需求可以大体划分为以下两类应用场景: 

• 实现操作原子性：在单机环境中，为了实现多进程或多线程对共享资源操作过程的原子性，我们可以借助内核提供的 SpinLock 或 Mutex 机制，保证只有一个进程或线程操作共享资源。和单机环境对锁的需求类似，在分布式环境中，我们通常会用分布式锁控制多个机器上的节点并发操作，避免数据或状态被破坏。
• 实现系统高可用：为了服务的高可用，往往需要部署多个节点实现服务冗余，避免单点故障造成的服务不可用。借助分布式锁+服务发现实现的选主功能，节点根据抢锁成功与否决定是否成为主节点对外提供服务。当发生节点宕机时，其他备份节点可以通过争抢到分布式锁的所有权，继续提供访问服务。

 分布式锁的业务需求、场景看起来比较简单，但是事实上我们在使用分布式锁过程中，总还是会提出这样、那样的新需求，看起来找不到一个分布式锁场景的大一统的解决方案。那么，分布式锁内部究竟是怎么实现的？或者说应该怎么实现呢？这个是我们这篇文章希望探讨的，也希望我们的探讨能够让读者朋友对分布式锁的原理有一定了解，在做技术选型的时候，也能够有更多的指导。



二、设计模型

我们应该给分布式锁建立怎么样的设计模型呢？这个问题可以换个视角来看，我们应该建立怎么样的合理性质来打造出一个分布式锁模型？我们不妨参考一下来自业界的两个定义。首先是 Apache Helix（开源社区一个风头正劲的通用集群资源管理框架，它能被用作自动管理存在于集群节点上的分区的，有副本的分布式资源）对于分布式锁管理器的性质定义：a）均匀分布，不是先开始的节点获取所有的分布式锁；b）再调度的均衡性，需要妥善处理持有分布式锁的节点意外退出后的锁资源分配问题；c）再平衡，当有新的节点加入的时候，节点间的锁资源应该再分配以达到均衡。看得出来，Helix 对分布式锁模型的定义非常强调均衡性，考虑到它是负责集群内的分区资源调度的，这个侧重点并不让人意外。 

图1 Helix 提出的分布式锁管理器的性质

 我们再看另一个大名鼎鼎的 Redis 对分布式锁性质的定义，它提出了分布式锁模型必须要遵守的三个原则：a）绝对互斥，同一时刻，只有一个客户端能够持有分布式锁；b）最终可用，如果持有分布式锁的客户端意外退出了，那么相关的分布式锁资源要能够被重新再分配；c）服务容错，提供分布式锁的服务本身要具备容错能力，即使部分节点崩溃，也不影响整体的分布式锁服务。

图2 Redis 提出的分布式锁管理器的性质

 结合自身的经验，我们高度认同Redis对有关分布式锁模型的基本约束条件，这些其实也是实现一个分布式锁服务所必须要考虑的几个属性。并且，Redis相关的文章中也继续探讨了分布式锁的其它的特性约束。事实上，如下图3所示，我们从三个维度归纳总结一个分布式锁模型落地需要考虑的性质。第一个维度是最基本的约束条件，与Redis提出的完全一致，我们称之为：互斥性，可容错，最终可用；第二层提出的分布式锁管理器需要关注的一些锁的特性，譬如抢锁效率，分布式锁的均衡性，锁的切换精度，锁的可重入性质等等。在这个之上，还有一个分布式锁落地时候必须要考虑的事关数据一致性与正确性保证的约束，即可防护性以及应对好时钟漂移的影响。 

图3 分布式锁设计模型需要考虑的三个维度的性质

 关于分布式锁管理器实际落地需要考虑的数据一致性与正确性的话题，其中一个话题是墙上时间的不靠谱，这个可以引入非墙上时间MonoticTime来解决，本文就不在这个问题上做更多讨论。另一个话题，实际使用分布式锁服务来访问共享资源的时候一定要辅助以Fencing能力方可做到资源访问的绝对互斥性。大神Martin Kleppmann提供了一个非常好的案例说明，如下图4所示，Client1首先获取了分布式锁的所有权，在操作数据的时候发生了GC，在长时间的"Stop-The-World"的GC过程中丢失了锁的所有权，Client2争抢到了锁所有权，开始操作数据，结果等 Client1的GC完成之后，就会出现Client1，Client2同时操作数据的情形，造成数据不一致。 

图4 缺乏Fencing保护的分布式锁可能导致数据不一致

 针对上述问题，解决方案是引入共享资源访问的IO Fence能力，如下图5所示，全局锁服务提供全局自增的 Token，Client1拿到锁返回的Token是33，并带入存储系统，发生 GC，当Client2 抢锁成功返回 Token 34，带入存储系统，存储系统会拒绝后续Token小于34的请求，那么经过了长时间GC重新恢复后的 Client 1再次写入数据的时候，因为底层存储系统记录的Token已经更新，携带Token 值为33的请求会被直接拒绝，从而达到了数据保护的效果。 

图5 基于 Fencing 的数据一致性保障

 回到文章的主旨，如何实现一个高效的分布式锁管理器呢？首先，抛出一个观点，分布式锁管理器也可以按照控制平面与数据平面进行切分。图3中提到的分布式锁性质可以划分到不同的平面分别负责。我们的这个观点其实并非首创，事实上在OSDI'20的Best Paper -《Virtual Consensus in Delos》一文，Facebook的研究团队针对一致性协议的设计做了深入探讨，非常的精彩。文章里面提到了类似Raft这类分布式一致性协议，里面也同样可以分拆出管控平面与数据平面，前者负责容错、成员变更、角色调整，后者负责定序与持久化。通过解耦两个平面，一下子让共识协议变得很灵活。

图6 Delos 中 Virtual Consensus 对管控数据平面的观点

 我们分布式锁模型的实现是否也可以参考类似的思路呢？将容错、成员变更等负责的逻辑转移至管控平面，而数据平面负责分布式锁的其它譬如互斥，最终可用，抢锁效率等等功能。答案是肯定的，好吧，即使这样的思路也并非我们首创，在数据库领域，一直有这么个流派来演进这类的分布式锁系统，它们被统称为 DLM（Distributed Lock Manager），典型的有 Oracle RAC，GFS2，OCFS2，GPFS，我们接下来好好说道说道DLM。

三、何谓DLM？

DLM 的思想来自《The VAX/VMS Distributed Lock Manager》，在1984年首次应用于 VAX/VMS V4.0。接下来，我们以 Oracle RAC 为例，来说明下 DLM 的设计思路。 Oracle RAC 运行于集群之上，基于内存融合技术，使得 Oracle 数据库具备高可用性和极致性能。如果集群内的一个节点发生故障，Oracle 可以继续在其余的节点上运行。为了保证多个节点写入内存 Page 过程的一致性，使用分布式锁管理器(DLM)处理分布式锁资源的分配和释放。

如图7所示，DLM 是一个去中心化的设计，集群中的所有节点都是对等的，每个节点都维护了部分锁信息。那么申请锁时，应该由谁来决定锁的分配呢 ? 在 DLM 中，每把锁都有 Master 的概念，由 Master 统一协调、授权，决定是否允许加锁或解锁，每个节点都有可能成为锁的 Master。每个节点管理这些锁资源时，将这些锁资源通过树状结构进行组织，通过对树节点的父子继承关系可以优化锁的粒度，提升加解锁的效率。 

图7 DLM的分布式锁角色关系

 在加锁或解锁过程中，涉及到以下几类节点: a）Requester: 发起加锁或解锁的节点；b）DirectoryNode: 锁的目录节点，存放着锁的 Master 被哪个节点锁持有这类信息；d）Master: 锁的持有者，实际管理者，负责锁的分配，释放。下面我们用具体示例来描述分布锁的分配、释放的具体过程，例子里面存在A， B， C 3个节点，其中A 为 Requester，B 为 DirectoryNode, C 为 Master 节点。

3.1 加锁过程

图 8 是需要到其他节点上加锁的过程，是所有加锁情况中最耗时的情况，最多需要 2 轮交互。当资源在本地建立后，后续对于具有继承关系的资源在本地加锁就可以了，无需和其他节点进行交互： 1. 节点 A 对资源 R1 加锁，首先在本地构造该锁对象，也称为锁的 shadow，但此时 A 节点并未加锁成功； 2. 节点 A，对资源 R1 通过哈希计算出 R1 对应的目录管理者为节点 B； 3. 节点 A 请求节点 B，节点 B 的记录上显示 R1 的锁的 Master 在 C 上； 4. 节点 A 向节点 C 发起对 R1 加锁请求； 5. 节点 C 维护 R1 的锁请求队列，如果允许 A 加锁，则返回成功;

6. A 更新本地 R1 锁 shadow 相关信息，加锁完成。 

图8 DLM的加锁过程 

3.2 解锁过程

图 9 展示了解锁的过程，也比较直观，如下三个步骤： 1. 节点 A 对资源 R1 解锁，删除本地构造该锁对象； 2. 节点 A 请求节点 C，请求将 A 的锁释放； 3. 若 A 是队列中最后一个请求者，则节点 C 将发送请求给 B，将  R1 从目录中摘除，以便后续其他节点能够成为锁的 Master ，否则，C 节点仅仅将 A 从 R1 的加锁队列移除。

图9 DLM的解锁过程

3.3 成员变更

上述的加锁和解锁过程，仅仅是普通的一次加解锁过程。那么集群出现节点故障、集群增删节点，如何控制分布式锁能够被正常路由和分配呢？在 DLM 中，存在 Connection Manager 角色，除了负责各个节点的网络通信，还有一个重要功能是在集群节点发生增删时，节点间首先选举出 leader 节点进行协调，每个节点均有可能成为 leader 节点。在发生节点增加或删除时会下述过程:

• 重建节点拓补：leader 节点通过两阶段投票方式向集群其他节点发起通告，告知当前集群节点拓扑情况，其他节点有权利接受或拒绝该信息。若对该拓扑图未达成一致( 其他节点拒绝该拓扑信息 )，leader 会休眠一段时间，其他节点执行 leader 选举，新 leader 会向其他节点发出通告。通过该方式，实现集群中所有节点对全局拓扑图以及锁资源的路由算法达成一致。在成员变更期间，仍可以发起抢锁请求，但这些请求会在请求队列中，并不能抢锁成功。成员变更完后，这些请求按照发起顺序被重新发出。
• 重建节点锁信息：leader 会通知其他节点对锁信息进行重建，重建过程拆分为多个阶段，当所有节点完成一个阶段后，leader 会通知集群所有节点进入下一个阶段。在重建过程中，任一节点发生故障，均需要重新发起选举和重建流程。重建分为以下阶段: 1) 节点清空目录信息(锁的路由表)以及节点持有的锁，这是因为锁资源信息需要重新路由；2) 对于之前节点持有的锁，按照原来的路由策略和顺序重新发起加锁，这个过程会将整个集群的锁的目录信息重新建立起来，锁的 Master 重新确定。由于每个节点对仅对自身重新加锁，那么对于发生故障被删除节点而言，它之前持有的锁 Master 会被新节点替代；3) 所有节点完成重新加锁流程后，就可以执行正常的加解锁流程了。

 从上述过程，我们可以看到集群发生节点成员变更时，恢复过程是非常复杂的。为了减少这种情况的发生，当一个节点通信失败后，会等待一定时间，超过该间隔后仍无法正常通信，才会执行删除节点的流程。一个节点如果仅是发生重启，没有达到需要触发成员变更的阈值，那么只需要恢复这个节点就可以了。在这个过程中，仅仅该节点的锁相关信息丢失了，对于集群的其他节点没有影响。重启过程中，发往该节点的请求将会被 Pending 住，直到该节点恢复。 发生重启的节点，上面大部分锁仍能恢复。节点上的锁由两部分组成，一部分为Local Lock，表示发起加锁的为节点自身。另一部分为 Remote Lock，表示由其他节点发起的加锁。对于Local Lock，其他节点没有信息无法恢复，但不存在竞争，也无需恢复；对于 RemoteLock，可以从其他节点的 shadow 信息中进行恢复。

3.4 些许思考

从成员变更过程，我们可以看到，Connection Manager 在DLM中承担了极其关键的角色，这个也是整个设计中最为复杂的地方，当出现节点故障时，由 Connection Manager 统一协调锁的重新分配，事实上承担了我们所谓的分布式锁管控平面的工作。DLM的优点是什么？负责分布式锁资源分配的数据平面不用考虑整个系统的容错，可以很均衡地让更多机器参与到资源分配，并且锁资源信息不需要落盘，不需要走共识协议做容错，只需要关注抢锁的互斥性和抢锁效率问题，这个抢锁效率，服务水平扩展能力都将非常有优势。 通过上述对 DLM 的加锁，解锁及成员变更过程进行剖析，这个里面还是有比较清晰的管控平面与数据平面的解耦设计，当然，实现过程很复杂，特别是failover这块恢复逻辑。但这种思想还是非常好的，值得我们做架构设计时候借鉴。尤其要提到一点，不同于 DLM 起源的 1980 年代，后期业界有了 Paxos/Raft/EPaxos 等共识协议，我们也有了类似 ZooKeeper/Etcd 等基于共识协议的一致性协议，我们的分布式锁管理器的管控平面完全可以用起来这些成熟的三方组件。

四、最佳实践

阿里云存储部门拥有着从块存储到文件存储，对象存储，日志存储，以及表格存储等全球最完整的存储产品体系。图 10 展示了当前存储产品采用的非常通用的基于分区调度模型的系统架构。整个业务系统按照管控平面与数据平面来划分，其中数据平面将用户的存储空间按照一定规则分割成若干分区，在运行时一个分区会被分配至某个服务器提供服务，一个服务器可以同时加载多个分区。分区不使用本机文件系统存储持久化数据，其拥有的全部数据均会存储在盘古分布式文件系统中的特定目录。基于如此的分区调度模型，当某个服务器发生宕机的时候，它承载的分区需要被重新调度，快速迁移至其它健康的服务器继续提供服务。 

图10 云存储基于盘古+女娲的通用的分区调度设计框架

 在云存储的分区调度模型中，有关分区资源的互斥访问（即任何时刻任一个分区必须至多为某一台服务器所加载并提供读写访问服务）是存储系统提供数据一致性的基石，必须得到保障。事实上，云存储的最佳实践中有着类似 DLM 的设计哲学，将分布式锁管理器的容错问题抽离出来，借助女娲-飞天分布式协同基础服务提供的选主功能来实现，进而可以专注在分布式锁资源的调度策略：

1）管控调度器负责具体分区资源的互斥分配，这里结合不同存储业务的特殊需要，可以演进出不同的调度策略，从分布式锁的均衡性，分布式锁的抢锁效率，分布式锁的切换精度等不同维度做专项优化； 2）分布式锁管理器中最复杂的容错能力，通过依赖女娲选主功能实现，并且通过女娲的服务发现能力实现管控节点平滑上下线； 3）存储系统的数据最终均存放在盘古-飞天分布式存储文件系统，从具体的分区数据，到管控调度的元数据，这些信息都会放入盘古。盘古提供了高可靠高性能的存储服务以及 Fencing 保护能力，保障数据一致性；

图11 基于盘古分布式文件系统提供的 Fencing 保护

 分布式锁提供 Fencing 保护的核心点是在访问共享资源的时候带上 Token 检查。盘古作为存储的统一的基座，通过引入特殊的 InlineFile 文件类型，配合 SealFile 操作，实现了类似的 IO Fence 保护能力：a）SealFile 操作用来关闭已经打开的文件，防止分布式锁旧的占有者继续写数据；b）为每个分区引入 InlineFile，针对盘古文件的元数据操作关联 InlineFile 相关的 CAS 判断，进而可以防止分布式锁旧的占有者打开新的文件。如图 11 所示，这两块功能结合起来事实上也是提供了存储系统中的写数据 Token 检查支持。

我们看到，就云存储的 DLM 实现中，有一个通用的基于分区的调度器，有女娲提供容错保障，由盘古提供资源的 Fencing 保护，这个就是云存储的最佳实践。

五、总结

分布式锁提供了分布式环境下共享资源的互斥访问，在分布式系统中应用十分广泛。这篇文章从分布式锁的性质出发，探讨了分布式锁的模型设计。就分布式锁系统，我们探讨了控制平面与数据平面解耦的架构设计，并介绍了阿里云存储场景下分布式锁的最佳实践。期望我们的分享对于读者朋友有所帮助。 

参考文献

1.  How to do distributed locking -- Martin Kleppmann：https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html 2. Distributed Lock Manager -- Apache Helix：https://helix.apache.org/1.0.2-docs/recipes/lock_manager.html 3. Distributed Locks with Redis -- Redis：https://redis.io/docs/reference/patterns/distributed-locks/ 4. The VAX/VMS Distributed Lock Manager -- VMS Software：https://wiki.vmssoftware.com/Distributed_Lock_Manager 5. Cache Fusion: Extending Shared-Disk Clusters with Shared Caches -- Oracle RAC：http://www.dia.uniroma3.it/~vldbproc/086_683.pdf

往期推荐

1. 阿里云块存储团队软件工程实践

2. 地图作业平台低代码实战（搭建能力提升）