ylock: A Framework for Distributed ReentrantReadWriteLock
1 Lock in Distributed Environment
锁作为也许是最常见的同步手段,在各种场景和环境中被广泛使用。
我们平常使用的语言往往自带有官方的锁实现,例如 Java 中常用的 ReentrantReadWriteLock
,Go 中的 RWMutex
等等,使用起来非常方便。
但是,这些锁仅仅作用在同一进程中。在分布式环境中,不同进程之间需要进行同步的需求并不少见。这时候就需要使用到分布式锁。
在分布式环境中各种各样的故障时常发生,参与锁交互的进程有可能会丢失数据、无法通信,因此要实现一个像单进程锁一样可靠高效的分布式锁是非常困难的。我们往往需要根据自己的使用场景做出取舍,例如,是要更高的服务可用性还是更严格的互斥性。
说到如何实现分布式锁,一篇比较具有影响力的文章是:How to do distributed locking,作者是 Martin Kleppmann,讲述了分布式锁的使用场景以及可能会出现的误区。
总的来说,要衡量一个锁的特性,我们主要关注这几个方面:
Exclusiveness
锁的排他性,表现在能够在哪些场景保证严格的互斥性,举例来说,服务端或客户端发生的网络故障、机器宕机、由于垃圾回收等导致的进程无响应等。
Liveness
锁的活性。在分布式场景中故障是家常便饭,如果某个进程获取了锁之后发生故障,导致整个流程完全阻塞往往是不可接受的。锁的活性衡量这个锁在面对故障时的可恢复性,例如,在发生故障后能够自动释放,让其他进程能够获取锁。liveness 和 exclusiveness 往往是互相冲突的。
Reentrancy
锁的可重入性。具备可重入性的锁可以由已经获取了锁的线程重复获取,便于函数的递归或嵌套调用,减少开发者的心智负担以及冗余代码。
Fairness
锁的公平性,表现在更早开始等待锁是否意味着能够更早获得锁。公平的锁能够避免饥饿的发生,非公平的锁在效率上往往更高。
锁的使用场景则大体可以分为以下两种:
Efficiency
通过使用分布式锁来避免一些重复无必要的工作。例如考虑用户连续点击两次发送验证码的场景。在这种场景中,对互斥性的要求不是那么严格 (如果没有成功保证互斥性,最后也只是重复发送了一条短信),而对活性和锁的效率的要求会更高。
Correctness
通过使用分布式锁来保证系统状态不会被并发修改,以保证正确性。例如考虑银行提款的场景。在这种场景中,需要保证严格的互斥性,锁的活性和效率相比起来就没有那么重要。
在简单梳理了分布式锁的一些要求和特性之后,我们来看下现在市面上比较主流的一些分布式锁实现。
2 Available Distributed Locks
市面上的一些现有的分布式锁根据实现方式分类,可以分为以下几种:
2.1 Dedicated Lock Service
专门设计并实现锁的管理维护服务,锁的维护和管理逻辑通常位于服务端,如 Google 的 Chubby。
通常来说,这些 Lock Service 会运行分布式共识算法例如 Paxos,Raft 等。Google 的 Chubby 使用 Paxos。
这种做法的优势是有较高的自由度来定制锁的行为和保证,另外可以把复杂度隐藏在服务端,只需要给用户提供简单的 API 进行调用。
缺陷则是实现难度较大 (客户端连接管理,Fail over 流程,状态监听等等),使用成本较高 (需要部署多个 Lock Service 实例)。另外,通常用来实现 Lock Service 的共识算法例如 Paxos、Raft 等由于较强的一致性保证,性能会比较差。在 Google,主要是用于选主这样的偶发且长时间持有锁的场景,并不适用于高频率获取,短时间持有的场景,而这些场景往往是业务系统中比较常见的。
2.2 Lock Service on Common Middleware
依托较为常见的能够提供一致性、原子性的中间件,通过在客户端编写锁的维护和管理逻辑实现锁服务。通常用来提供锁服务的中间件有 Redis、Zookeeper、etcd 等。
通过这些中间件提供的服务以及额外编写在客户端的一些逻辑实现分布式锁,可以说是比较常见的方式。在 Apache Curator Recipes 中,有现成的 ReentrantReadWriteLock 实现,在 Redis 官网也有官方推荐的单实例以及多实例分布式锁实践。
这种做法的优势是较低的部署成本 (如果已具备对应的中间件)和相对较低的实现难度。开发者只需要利用中间件客户端提供的 api,在此之上构建锁的管理和维护逻辑即可。
2.3 Self as Lock Service
所有参与分布式锁的进程运行分布式共识协议如 Paxos、Raft,不依赖外部的服务。
本质上来说,分布式锁也是一种多进程间达成的共识。因此,也能够在多进程间运行 Paxos 等共识算法来实现一定程度的分布式锁。这种方式不需要任何的服务端,或者说锁的使用者本身就是锁的服务端的一部分。
然而,这种方式也是非常受限的。首先,对于某个要使用分布式锁的服务,必须在一开始就部署多台实例,尽管负载和可用性上来说并没有这样的需要。另外,不但服务大部分宕机就无法进行上锁,与集群发生网络隔离的小部分服务也会无法进行上锁。一般来说这种方式在业务系统中使用得比较少。
3 What We Need
在瓴岳的使用场景中,对于要求强互斥性的场景,通常会使用带事务保证的数据库来实现,例如使用 InnoDB 引擎的 MySQL。除此之外的使用场景,比较多的是为 Efficiency 而使用的锁,或者对 Correctness 的要求不是特别高。
比起保证强互斥性而导致活性和性能较低的分布式锁,我们更多情况下需要的是具备活性、高效、在多数场景下能够保证互斥性的分布式锁。这个锁最好能够具备一些其他的特性,例如可重入性、公平性、共享 / 互斥模式等。
在这之前,公司内部也有一个使用 Redis 简单实现的分布式锁库。这个库能够满足日常的使用需求,但是也存在一些缺陷。
- 以扩展抽象类作为主要的使用入口,用户如果需要使用分布式锁,需要额外创建一个类来使用,不够简单直接。
- 不支持可重入性、公平性、互斥 / 共享模式等,功能性上有所欠缺。
- 缺少相应的监控,开发者对持有锁的时间没有直观的了解。
考虑到 Redis 提供的互斥性保证在一些场景可能不足,因此可能也会需要一个以 Zookeeper 作为锁服务的分布式锁。
结合以上的需求,我们开发了 ylock。
4 ylock: What & Why & How
一句话来说,ylock 是一个分布式锁框架,可以通过基本 0 代码注入支持不同底层实现的支持可重入、公平 / 非公平、互斥 / 共享、活性、统一接口的分布式锁。
ylock 在不同的中间件如 Redis 和 Zookeeper 上实现了 ReentrantReadWriteLock 的功能,并支持以统一的接口进行调用,使具体的实现细节对用户透明。在此之上,提供了开箱即用的监控功能,用户在 Grafana 等可视化监控系统稍作配置就可以看到具体的监控信息。
在 ylock 中,基于某个中间件实现锁接口的模块,被称为 engine。目前 ylock 提供了 RedisEngine
和 ZookeeperEngine
。
大体上 ylock 的结构如下:
4.1 Uniform Facade
ylock 提供两种接口,Lock
和 Locks
。
其中,Lock
主要作为粗粒度的锁来使用,而 Locks
作为细粒度的锁来使用 (例如,用户粒度)。
具体接口定义如下:
1 | public interface Lock { |
1 | public interface Locks { |
每个锁都由 group
和 name
唯一标记,group
主要代表这个锁的业务用途区分,类似前缀;name
则是锁在 group
下的具体划分,例如用户名等。
Lock
和 Locks
的接口设计主要参考了 Go 中的 RWMutex
。Java 中的 ReentrantReadWriteLock
下还有 ReadLock
和 WriteLock
的抽象,使用起来不够方便而且实现起来也会增加一些没有必要的限制。
4.2 Lock Engines
目前 ylock 提供分别基于 Redis 和 Zookeeper 的 LockEngine
实现。其中,RedisEngine
提供的锁性能和吞吐量要更优,ZookeeperEngine
提供的锁互斥性要则更胜一筹。
4.2.1 RedisLockEngine
4.2.1.1 Drawbacks of Existing Redis Locks
RedisLockEngine 使用 Redis 作为底层支持提供 ReentrantReadWriteLock 的功能。
Redis 作为比较常用的一种用于实现分布式锁的中间件,市面上现成的实现并不少。
例如,Redis 官网提供的简易单实例锁实现:
1 | ====== lock ====== |
这种锁的缺陷是缺少可重入性、无公平性、无互斥/共享锁的选项,并且由于设置一个固定的过期时间,对持有锁的时间有限制。
Redlock 在这里将略过不提,如 Martin Kleppmann 的文章中指出的,Redlock 作为保障 Correctness 的锁来说不够严格,作为保障 Effciency 的锁来说不太必要。
除此之外,Redisson是比较常提到的 Redis 锁实现。Redisson 提供 Lock、FairLock、ReadWriteLock、SpinLock 等实现,具备 WatchDog 自动续期以及可重入性。然而它把不同的特性分配到了不同的锁实现上,例如,FairLock 和 ReadWriteLock 是不同的两个实现,不是很理想。另外,Redisson 的公平锁实现依赖客户端的本地时间戳进行超时验证,相当于是对多个进程的时间做了一致的假设,这在分布式算法中并不是理想的做法。这也是 Martin Kleppmann 反对 RedLock 的主要一点:
In particular, the algorithm makes dangerous assumptions about timing and system clocks (essentially assuming a synchronous system with bounded network delay and bounded execution time for operations), and it violates safety properties if those assumptions are not met.
既然主流的实现都不是很理想,我们是否可以自己在 Redis 上实现一个 ReentrantReadWriteLock 呢?
4.2.1.2 Data Structure: an AQS-like Redis Lock
回顾 Java 中的 ReentrantReadWriteLock
,它的核心逻辑是基于 Doug Lea 开发的 AbstractQueuedSynchronizer
(以下 简称 AQS) 以及在其子类 Sync
的基础上实现的。那么同理,如果我们能够在 Redis 提供的数据结构以及功能上实现 AQS 或者 Sync
, 那么我们就可以顺理成章地实现 ReentrantReadWriteLock
。
为了避免本文变为介绍 AQS
和 ReentrantReadWriteLock
的文章,这里仅简单介绍下 AQS
和 Sync
的原理和结构,对此感兴趣的同学可以自行阅读源码或查阅相关资料。AQS
的核心为一个可以原子更新的 32 位整数 state
以及一个 CLH (Craig, Landin, and Hagersten) 队列 变体。尝试获取锁的线程会在锁空闲的时候直接获取锁 (通过 CAS 原子操作修改 state
),如果锁已被占用,则将自身线程、获取模式 (互斥 / 共享) 记录并组成一个等待节点入队并等待。在上一个节点释放锁后,唤醒下一个节点获取锁。ReentrantReadWriteLock
的内部类 Sync
则是在 AQS 的基础上添加了锁的获取逻辑和记录共享锁和互斥锁的获取次数等。
它们合起来的大致示意图如下:
对上图的数据结构进行一些调整,我们可以在 Redis 中实现类似的结构:
Queue
利用 Redis 中的队列实现,ThreadId 和 Mode 可以组合为单一字符串存储。
State
State 的作用主要是记录锁的占用状态以及获取次数。考虑到可重入次数只是单一进程内单个线程的概念,可以仅记录在本地而不是中心化的 Redis 存储中,可以忽略。那么此时的锁的获取次数就相当于 ExclusiveOwnerThread 和 SharedOwnerThread 的数量,锁的占用状态也同样可以通过检查这两个字段来获取。因此,这个字段的作用可以被下面的 ExclusiveOwnerThread 和 SharedOwnerThreads 替代。
ExclusiveOwnerThread
ExclusiveOwnerThread 的作用是记录互斥获取了锁的线程名称,可以简单地用 Redis 中的字符串 Key-Value 实现。当该值为空或不存在时,说明锁没有被互斥获取。需要注意的是,在分布式锁的场景中,ThreadId 需要是分布式环境中唯一的,一个比较简单的方式是给 ThreadId 前面添加一个 UUID。
ThreadLocal
在
Sync
中,使用ThreadLocal
来记录共享获取锁的线程以及获取的次数。和前面同理,忽略可重入获取的次数,那么需要记录的就是共享获取锁的线程,相当于一个集合。而 Redis 中同样有 Set 这种数据结构,因此使用 Set 来代替。
根据上述,勾勒出 Redis 中锁的结构如下图:
waiter_queue
为等待者队列,以先入先出的模式存放正在等待锁的节点。exclusive_owner
记录当前锁的互斥占有者,也是用来判断锁是否被互斥占用的依据。shared_owners
记录当前锁的共享占有者。由于共享占有者可能具备多个,因此使用一个 Set 来存储。pending_readers
是一个用于读锁获取的辅助字段,后续会另外说明。
一个锁相关的 key 通过使用相同 HashTag 的方式可以保证分到同一个 Redis 实例中,结合 Lua Script 可以保证锁相关操作的原子性。
4.2.1.3 Lock Notification: pub-sub or polling?
锁的数据结构大致确定后,我们仍需要考虑通知机制的问题。AQS 使用 park/unpark 线程的方式来通知等待节点,时效性和可靠性都有保证。在 Redis 中,行为比较相似的是 pub-sub 通知机制,但是如果使用 pub-sub 又会衍生出几个问题:
pub-sub 的粒度问题。
如果做一个粗粒度的 pub-sub,也就是说锁在释放的时候向一个当前锁粒度的 channel 发送消息,并且所有的等待节点都订阅这个 channel。这时候会导致惊群效应 (herd-effect),这个锁所有的等待节点都在此时调用 Redis,造成短暂的峰值调用。
而如果做一个细粒度的 pub-sub,也就是每个等待节点对应一个自己的 pub-sub channel。这种实现首先是比较复杂,其次是需要另外解决某个等待节点对应的进程发生故障导致节点不响应的问题,此时通知已经发送,而当前节点故障,后续的节点没有收到通知。
锁被动释放时的通知问题。
在 AQS 的使用场景中,所有的锁都是由持有者主动释放。而在分布式环境中,需要考虑到活性,当持有者发生故障后,锁可能会被被动释放。此时如何通知下一个等待节点获取锁是值得思考的问题。
pub-sub 在 Redis Cluster 中的性能问题。
Redis Cluster 保证在集群中的每个节点都可以发布以及消费所有消息,在带来使用上的便利性的同时,由于每一条消息都需要广播到所有的节点,性能问题随之而来。对单个节点的视角来看,发布消息的性能随着集群中节点数量的上升而下降。Redisson 也同样因为此原因添加了 基于轮询的 SpinLock。
综合以上考虑,我们决定使用轮询的方式,并借鉴了 Redisson 中的 SpinLock,设置了可配置的轮询策略,如常数间隔轮询 (constant polling) 和级数间隔轮询 (exponential polling) 的方式,可以根据不同的场景使用不同的设置。使用轮询一方面保证了性能和吞吐的扩展性,另一方面降低了复杂度。
值得一提的是,尽管面临上述的问题,Redisson 的 FairLock 实现中仍然使用了 pub-sub 机制来实现,付出的代价则是当碰到不响应的节点时,锁会等待 5 秒才能继续执行:
Fair lock guarantees that threads will acquire it in is same order they requested it. All waiting threads are queued and if some thread has died then Redisson waits its return for 5 seconds. For example, if 5 threads are died for some reason then delay will be 25 seconds.
然而,当发生类似机房断电之类的大规模故障时,这样的行为很可能会导致锁需要等待非常久的时间才能正常工作,是比较难以接受的。
当然,轮询也有其对应的缺点,在 Redis 锁场景中,比较突出的是感知锁的状态改变的即时性。如果使用 pub-sub 这种通知机制,下一个等待节点在锁释放后,在较低网络延迟的环境下能够很快接收到推送消息进而获取锁,可能在毫秒内就能完成。而轮询则需要等待下一次轮询发起,可能需要几十毫秒。当然,通过缩短轮询周期能够缩小这个时间,但是这样也会增大对 Redis 的压力。
考虑到业务逻辑的自身耗时,且用户可以根据平均持有锁的时间来调节锁的轮询时间,实际上真正受此影响的场景是在读多写少的环境中,连续多个读锁等待节点排队获取锁的情况。默认情况下,一个等待节点要在轮询中判断自己为队头时才会尝试获取锁,这样就导致在多个连续读锁的情况下,等全部读锁都获取到锁会比较耗时 (最后一个读锁等待节点需要等待前面所有的读锁等待节点都获取锁后才能获取)。做个粗略的计算,如果轮询周期为 T,那么等 N 个连续的读锁等待节点获取锁大概会需要 NT / 2 的时间。当 T 为 100ms,N 为 30 时,需要 1.5s 的时间。实际上,它们之间并没有严格的先后顺序关系,只要满足条件都可以获取锁,不需要必须等待前面的节点都获取了锁才获取。pending_readers
就是为了解决这个问题而存在的。pending_readers
是一个集合,在多个共享锁等待节点相连的情况下,第一个获取共享锁的节点可以把后面连续的所有共享锁等待节点加入到 pending_readers
中,这样后面的节点在轮询时就可以直接获取读锁,而不需要等待自己成为队头,提高获取锁的效率。
4.2.1.4 Fault Tolerance: Liveness of Redis Lock
由于单机、基于内存通信的环境和分布式、基于网络通信的环境有着很大的差别,在分布式锁的使用过程中,可能会碰到机器宕机、网路分区、进程不响应等故障,因此锁算法需要具备容错性,在面对故障时能够继续进行。然而,分布式锁的活性通常需要利用超时进行保证,但是分布式系统中各个机器的时间并没有保证,我们需要避免对时间做出不实际的假设。
这两个问题可以依赖 Redis 的相对时间过期机制来解决。
获取锁成功的进程发生故障
面对已经成功获取了锁的客户端发生故障的情况,可以通过设置锁状态对应的 key 的超时时间,并使用进程内部的 watch dog 后台线程周期性更新的方式来保障活性。如果持有锁的进程宕机、网络故障、长时间不响应等,shared_owners 以及 exclusive_owner 这两个 key 会过期被删除,从而锁会被释放,其他进程能够获取锁。
排队获取锁的进程发生故障
面对正在排队的进程发生故障,可以通过为每个节点设置带超时时间的 string key 来保证。设想如果队头节点发生故障,一直不获取锁,而后面的节点没有将其强行踢出的机制,此时锁的活性就无法保证了。因此,当进程作为等待节点入队时,同时创建一个对应的 string key-value 对,用于表示自己尚存活且还在队列中,并设置一个较短的超时时间。每个节点在轮询锁状态判断自己能否获取锁的同时,如果等待队列的队头不是自己,会通过查看队头的 string key 来判断队头是否还存活。如果 string key 不存在,说明队头节点代表的进程发生故障,则将其踢出,并继续查看新的队头是否存活。最后在结束之前,再刷新 string key 的过期时间。
无论是等待节点的 string key 还是锁状态的超时时间都是相对时间,这样能够避免对多进程的时间做出不实际的假设,转为依赖于 Redis 单节点的时间或者说真实时间 (在 Redis 节点的时间不偏移的情况下)的同时保证了锁的活性。
4.2.1.5 Reentrancy
由于 WatchDog 续期机制,我们并不需要在重入的时候显式延长锁的超时时间。因此,可重入功能可以做在本地内存中,在本地维护锁的重入次数。比起每次重入都调用 Redis 的方式来说,这种方式的优点是效率更高,也不会因为 Redis Server 的 fail over 导致重入次数计算错误。缺点则是难以在故障后锁被夺取的第一时间发现自己已经不再持有锁。不过,如果是需要长期持有锁,并对互斥性要求更高的话,可以使用 ZookeeperEngine 提供的锁。
4.2.2 ZookeeperLockEngine
Zookeeper 的抽象天然地适合用来实现 ReentrantReadWriteLock。
因此,正如 Martin Kleppmann 所建议的,Apache Curator Recipes 已经提供现成可用的 ReentrantReadWriteLock 实现。秉承着不重复造轮的原则,ylock 使用了该实现作为 ZookeeperLockEngine 的主要部分。
然而由于 Locks
接口的存在,除了粗粒度的锁之外,我们还需要细粒度的锁,如用户粒度。这种锁通常来说生命周期比较短,不同于那些在代码中显式声明后一直使用的锁。不过 Apache 提供的锁在本地内存中有维护状态,也就是说,在获取锁的时候初始化锁实例上锁,解锁的时候用同样的参数重新初始化锁实例解锁是行不通的。
因此,我们在 Apache 提供的实现基础上实现了在内存中维护锁状态的 LockKeeper
,用来保存获取过的锁实例并统计重入次数,在重入次数归 0 并一段时间内没有使用之后清除,并实现底层存储的缩容机制。
具体的 Apache Curator Recipes 提供的锁实现在这里就不细说了,有兴趣的同学可以看看源码。
4.2.3 Lock Engine Guarantees
下表统计了目前 ylock 自带的 2 种 Lock Engine 提供的活性和互斥性的保证:
4.3 Metrics
除了基本的锁功能之外,ylock 还提供了开箱即用的监控功能。
得益于统一的接口,所有 Lock Engine 提供的锁都能够通过 AOP 进行透明的监控。
监控的 Metrics 分为两种: Event 和 Span。顾名思义,Event 统计的是诸如上锁、解锁之类的事件,而 Span 则是统计上锁、持有锁、解锁耗费的时间。所有的 Metrics 都可以通过锁的 group 进行分组查看。
ylock 的监控实现思路参考了 Netflix Hystrix 的实现方式。AOP 层在上锁、解锁操作时将对应的 Event 和 Span 发布到基于 RxJava 的订阅流中,下游则可以由用户自定义的 Metrics Exporter 进行消费。在 ylock 的 Spring Boot 客户端中,在项目中有 Influxdb bean 的情况下,默认提供导出到 Influxdb 的 Metrics Exporter 实现。
AOP 层解耦了各种 Lock Engine 实现以及监控逻辑;发布订阅的模式则解耦了数据监控和导出的实现,并把过程转为异步,不会因为数据导出流程故障阻塞锁的基础功能。
值得一提的是,可重入锁在使用上会比较方便,在监控上却相反比较困难。例如,监控一个多层重入的锁的持有时间,用户希望获得的是整个锁的持有时间,而不是第一次获取到第一次释放的时间。这种情况下,可以实现一个同样可重入的 Timer,同样统计锁的重入次数,在归 0 时统计锁的持有时间。
下图为在 Grafana 上查看的 ylock 导入到 Influxdb 的样本数据:
4.4 Built-in Spring Support
瓴岳的大部分服务都基于 Spring Boot 实现。为了用起来更方便透明,ylock 提供支持 Spring Boot 的客户端,支持以下特性:
开箱即用:
引入依赖后无需其他配置即可直接使用,如
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18<dependencies>
<dependency>
<groupId>com.yqg.infra</groupId>
<artifactId>ylock-spring-starter</artifactId>
<version>1.0.0</version>
</dependency>
<!-- engine 依赖按需引入, 例如只使用到 REDIS 引擎可以不引入 ZOOKEEPER 引擎 -->
<dependency>
<groupId>com.yqg.infra</groupId>
<artifactId>ylock-engine-redis</artifactId>
<version>1.0.0</version>
</dependency>
<dependency>
<groupId>com.yqg.infra</groupId>
<artifactId>ylock-engine-zookeeper</artifactId>
<version>1.0.0</version>
</dependency>
</dependencies>注解注入:
1
2
3
4
5
6
7
8
9
10// 注解注入
private Locks testLocks;
// 注入的同时指定锁的配置。大多数情况下使用默认配置即可
private Lock testLock;默认监控:
当项目中存在 InfluxDB bean 的情况下,自动收集锁的使用数据并导出到 Influxdb。用户只需要在 Grafana 上略加配置即可直观地看到监控数据。
5 Conclusion
本文讲述了我们在实现适合日常业务场景下具备 ReentrantReadWriteLock 特性,保证活性,提供 Best-Effort 的互斥性,同时具备直观数据统计的分布式锁的实践。
在实现上,严格的 Correctness 和 liveness 往往是冲突的。在需要保证严格正确性的业务场景中,可能使用基于版本号的乐观锁和具备 ACID 事务保证的数据库锁会是更合适的选择。