Redlock - Distributed locks with Redis

Redlock - 基于Redis的分布式锁。

除了自己的思考以外，内容来源如下：

Distributed locks with Redis
How to do distributed locking
Is Redlock safe?

SETNX & SET NX

通常，大家利用Redis实现分布式锁最简单的方案是命令SETNX。

SETNX全称为SET IF NOT EXIST，也就是说如果不存在则设置该值。

那为什么SETNX可以实现分布式锁的功能呢？

由于Redis的单线程（无锁化的命令执行）特性，可以保证不会出现多个客户端同时执行SETNX的情况。

Implements

在Redlock之前，Redis分布式锁大体包含以下四种实现方式，

不过仔细考量下这种实现方式就会发现一些问题，具体如下：

① 加锁成功后没有释放锁，导致死锁，

1
2
3
4
5
6
// 加锁
SETNX LOCK_KEY 1
// 业务逻辑
do somethind ...
// 释放锁
EXPIRE LOCK_KEY 0

在上面的业务逻辑中如果出现业务异常导致无法触发释放锁的操作，从而导致LOCK_KEY无法释放，

此时，其他业务线程就会一致等待LOCK_KEY的释放，从而造成死锁。

② 为解决死锁的问题，加锁后立即设置超时时间，降低死锁可能性，

1
2
3
4
5
6
7
8
// 加锁
SETNX LOCK_KEY 1
// 设置过期时间
EXPIRE LOCK_KEY 5s
// 业务逻辑
do somethind ...
// 释放锁
EXPIRE LOCK_KEY 0

与①中不同之处在于新增了[设置默认时间]，避免了业务逻辑异常导致无法执行释放锁的操作，

但仍然存在执行加锁成功但设置默认时间失败的情况，可理解为加锁与过期设置操作的非原子性，也会造成死锁。

③ 利用时间特性来生成特定的LOCK_KEY来解决非原子性操作，

1
2
3
4
5
6
7
8
// 生成特定的时间锁
LOCK_KEY = FUNC(LOCK_KEY, TIME)
// 加锁
SETNX LOCK_KEY 1
// 业务逻辑
do somethind ...
// 释放锁
EXPIRE LOCK_KEY 0

利用时间来生成特定的时间锁来解决死锁问题，但是会生成大量无效KEY。

由于与时间相关，业务逻辑的处理时间可能大于锁的有效期，就会造成业务逻辑还没有处理完的同时其他线程就可以竞争『同一把锁』。

『同一把锁』是指原始锁是同样的，也就是未执行FUNC(LOCK_KEY, TIME)之前的LOCK_KEY。

当执行完LOCK_KEY = FUNC(LOCK_KEY, TIME)后，LOCK_KEY将与TIME相关，也就是说不同时段使用不同的逻辑锁。

④ 使用SET EX NX来解决SETNX与EXPIRE非原子性的问题，

>= 2.6.12: Added the EX, PX, NX and XX options.

此方法需要Redis版本大于等于v2.6.12，如下，

1
2
3
4
5
6
// 加锁并设置过期时间
SET LOCK_KEY 1 EX 5s NX
// 业务逻辑
do somethind ...
// 释放锁
EXPIRE LOCK_KEY 0

通过该命令很好的解决了方法②中的不足，也不许引入③中的复杂逻辑，实现了设置与过期的原子性操作，

但其仍然没有解决业务逻辑超长的执行时间导致的锁自动过期的问题。

上面讨论的实际上都是如何解决互斥，那么如何保证分布式锁的容错性并没有讨论。

假设线程锁定的默认时间 > Master节点宕机恢复时间，考虑以下主备场景，

  • A线程尝试加锁并加锁成功；
  • B线程尝试加锁并加锁失败；
  • Master节点宕机；
  • 尝试切换Slave为Master提供服务；
  • C线程尝试加锁并加锁成功；

以上步骤中，Master节点宕机是关键，再主备场景下主从存在延时，

假设Master节点宕机前未将A线程的加锁数据同步至Slave节点，

那么，此时Slave切换为Master后中缺少A线程的加锁数据，从而C线程获取了锁造成了资源的竞争。

最近由于所谓的政治舆论压力，作者将master-slave改为了master-replica。

Redlock

Redlock主要就是解决分布式场景下互斥、死锁以及容错这三个关键问题。

Redlock核心思想：基于Quorum机制，采用大于一半的投票方式来实现分布式锁。

Redlock具体步骤如下：

① 采用N(奇数)台相互独立的Redis实例参与投票；

② Client随机生成random_val，向实例发送set(key, random_val, nx=True, px=TTL)命令的方式获取投票结果；

每次循环调用Redis实例与上面讲到的单实例情况下分布式锁的实现大体相同，其中，TTL是业务方来控制的，不设置的话有可能导致死锁。

③ 由于①中说明存在多个实例，则Client端通过顺序请求的方式来获取多个实例的投票。

为了避免某个实例问题导致的阻塞情况，增加一个默认的超时时间以防止长时间的阻塞。

④ 完成③中的投票后，统计投票结果以及投票过程的耗时，当通过半数(N/2+1)的(设置)成功投票以及超时校验后则认为成功加锁；

不仅仅需要过半的成功投票，还需要校验整个加锁过程的耗时是否超时，其中锁默认的有效期(defaultValidityTime)是业务相关的。

当④中成功获取锁后，锁的有效期需要减去投票过程的耗时：validityTime = TTL - elapsedTime。

⑤ Client加锁失败的话需要释放掉已经设置成功的实例。

加锁失败的原因有加锁超时、投票未过半两种情况，无论那种情况都需要释放掉已经设置的锁（这里会尝试释放所有实例的锁）。

Safety

原文Safety arguments中讨论了Redlock是如何保证加锁的安全性。

锁定策略

通过半数投票机制来实现锁定策略，具体实现如下，

1
2
3
4
5
# N为实例数量，m为投票数量
if m > N/2 + 1:
    successed
else:
    failed

锁定时间

锁的实际有效期计算公式如下，

1
2
# TTL为锁的过期时间，T1为开始加锁时间，T2为结束加锁时间，CLOCK_DRIFT为时钟偏移
MIN_VALIDITY = TTL - (T2 - T1) - CLOCK_DRIFT,

可以理解为：在尝试加锁的开始已经属于锁定时间的一部分，锁的具体锁定时间与加锁过程耗时有关。

此外，如果任务优先执行完会立即释放锁，从而实际锁定时间可能会小于MIN_VALIDITY。

Liveness

锁的释放

锁的释放也包括两种情况：主动释放与自动释放。

自动释放是利用Redis自动过期实现的，而主动释放是基于Client主动触发来实现的，具体如下，

1
2
3
4
if processTime < MIN_VALIDITY:
    for server in servers:
        if server.get(LOCK_KEY) == current_val;
            server.del LOCK_KEY

在Client删除实例的LOCK_KEY时会去判断VAL值是否是该节点之前设置过的。

Unsafety

STW

Garbage Collector（垃圾回收器）是用于帮助应用自动回收已过期的内存空间的一种辅助工具。

如何衡量一个垃圾回收器的性能的好坏，大多体现在如何保证更小Stop The World的。

先看下面这个场景，当STW时间大于持有锁的有效时间时，就会造成分布式锁的异常。

STW unsafe lock

如图所示，Stop The World导致了线程执行时延，

线程从暂停中恢复时已经超过了锁的有效期，从而导致锁失效，此时另外一个线程尝试并成功获取锁，造成资源竞争。

原文提到：STW恢复后再次验证锁的有效性来避免锁定超时的情况。

但这里其实存在一个问题：如果进程执行了一部分逻辑怎么办？

在MySQL中，基于undolog与redview的MVCC实现了事务的功能。

那么在分布式的场景下业务如何保证锁失效导致的资源竞争的问题，是支持业务回滚？还是支持垃圾数据的容错？

实际上，无论进程在做什么都应该有一个耗时的上限，而这个上限是由具体的业务场景决定的（甚至需要考虑STW的时间）。

Blocking

除了垃圾回收造成的长时间STW，进程运行过程中会遇到资源抢占等一系列造成阻塞的问题。

例如，磁盘容量不足、内存容量不足、IO阻塞、CPU的异常抢占策略等等，都有可能造成进程长时间的Blocking。

Safety with fencing token

fencing-tokens

Martin提出fencing token来解决上面延时导致的过期问题。

fencing token可以理解为zookeeper中自增的zxid或znode的版本号。

zookeeper中，zxid是用于实现事务的全局有序，而znode的版本号是用来解决资源竞争的新老问题（也就是fancing token）。

fencing token是用于解决新老版本的问题，在分布式锁场景下用于解决锁异常情况下的有效性问题。

fencing token一定是全局唯一且全局有序，

  • 全局唯一是为了保证锁的唯一性，不允许存在两个进程获取到同一把锁；
  • 全局有序是为了保证锁的有效性，总会认为最后持有的锁有效，也就是所谓的ID最大的有效。

Antirez并不认为Redlock存在这个问题，由于Redlock实现了随机数的VAL机制保证了唯一性，已经满足了锁竞争的场景。

如果进程获取锁当前的VAL与本地设置的VAL不同，那么自然可以认为锁已经被抢占了。

Safety with timing assumptions

Martin提出Redlock锁的有效期与Redis实例的时钟强依赖，而Redis实例的时钟是不可靠的。

假设一种场景，假设共五个Redis实例1~5，两个客户端A与B参与投票：

  • 客户端A 在 1、2、3 三个节点抢占成功；
  • 此时，节点3时钟前跳，导致客户端A的抢占失效（客户端A并无感知）；
  • 客户端B 在 3、4、5 两个节点抢占成功；

因此，当时钟发生异常的情况下，客户端A与客户端B均成功获取锁，导致分布式锁失效。

time forward

此外，linux提供了两种获取系统时间：CLOCK_REALTIME与CLOCK_MONOTONIC参考，

  • CLOCK_REALTIME：会发生向前或向后的时钟跳跃，包括认为修改与NTP的影响；
  • CLOCK_MONOTONIC：只会收到NTP的影响，合理的运维可以尽量避免此问题。

Redis使用CLOCK_REALTIME，存在时钟跳跃的风险。

Is Redlock safe

Redis作者antirez对Martin提出的不安全问题给出了自己的理由。

Redlock是一种基于客户端实现分布式锁的思路，不仅仅适用于redis。

Redlock的目标用于是哪些使用原本使用Redis作为分布式锁的用户，提高原有分布式锁的容错性。

类似于Zookeeper，只要满足半数投票就可以认为加锁成功，允许部分机器出现异常情况。

Redlock无法保证绝对的安全性，这也是它可以实现高性能的关键。

常见的共识系统为了避免时钟问题，使用fencing token来的全局有序来保证绝对的安全性，而如何保证全局有序又将成为为系统性能的瓶颈。

Thoughts

虽然很久之前就有打算对这块内容整理一下，不过一拖再拖。

微服务场景下通常会涉及到分布式锁的问题，常用的实现有：

  • MySQL
  • Redis
  • Zookeeper
  • Etcd

其中，基于数据库来实现可以解决了大部分的场景，ZK/ETCD提供了强一致性的保证，Redis提供了更好的性能。

如何选择还是要看业务场景，分布式锁对于微服务来说等同于JVM的STW、PYTHON中的GIL，无锁话设计才是性能提升的关键。

Reading

https://zhuanlan.zhihu.com/p/151436396
https://dbaplus.cn/news-159-3080-1.html
https://zhuanlan.zhihu.com/p/76294773