技术科普｜深入理解分布式锁的原理与实现 part 1

一、Distributed Lock

在单机多线程环境下，我们可以通过以下方式进行同步：

• 互斥锁 mutex
• 信号量 semaphore
• 用户态互斥锁 futex

那如果在分布式环境下，需要处理资源抢占问题时，我们经常想到的就是分布式锁和一致性共识协议。事实上，分布式锁就是一个简化版的共识协议，我们可以从一个分布式锁需要保证的几个性质来理解这一点：

熟悉分布式系统的同学很快就能联想到，其实上面的三点本质上就是在描述两个重要性质：safety 和 liveness. 其中 safety 对应第一点，liveness 对应后两点。

简单来说，safety 是系统的 invariant，无论何时系统都需要保证 invariant 成立。而 liveness 则是强调系统无论什么环境下，都要能最终保证其工作最终能够完成。

举个例子，著名的哲学家进餐的解决方法和分布式锁需要保证的 safety 和 liveness 性质如出一辙：

• safety: 因为叉子不能共享，一个正在吃饭的哲学家两侧的哲学家不能在同时吃饭。
• liveness: 没有哲学家会挨饿，也就是有限时间内饿了的哲学家都能吃上饭。

其实用 TLA+ 来验证很多分布式算法时，验证的条件就是 safety 和 liveness. 我们后面会试着用 TLA+ 来描述一个分布式锁的实现。 

如果一个分布式锁能够保证 safety 和 liveness，本质上就是一致性共识协议，也就是所有客户端通过分布式锁服务要能对当前谁持有锁达成共识。那为什么不直接用一致性共识协议呢？原因有以下几点：

分布式锁有几种常见的实现方式：

• 基于数据库的实现：不管是不是内存型数据库，都是往数据库中写入一条携带 uuid 或者自增 id 的记录。通过检查这条记录中的 id 信息是否和客户端匹配，进而获知自己是否上锁成功。
• 借助分布式应用程序协调服务：比如前面提到的 ZooKeeper 或者 etcd，它们的客户端都提供了能够实现分布式锁的接口。

不同分布式协调服务的实现原理不尽相同，不在本文描述范围之内。本文重点还是关注基于数据库的实现，主要以 Redis 为例，整体思想大同小异。

选择 Redis 为例的一个重要原因是，关于 Redis 分布式锁在几年前有两个大牛也下场进行了一波争论。

二、基于单机数据库的实现方式

一种最简单的方式就是所有客户端，通过往数据库中写入一条记录表示获取锁，而删除掉这条记录就代表释放锁。当然获取锁的时候需要检查记录是否存在，比如通过IF NOT EXISTS这样的关键词。比如在 Redis 中就可以通过这样一条命令来完成，其中SETNX代表SET if Not eXists.

SETNX lock 1    // 1是客户端id

上面的方案非常直观，但有一个明显的问题，如果客户端上锁成功之后没有释放，此后其他客户端都无法获取锁，违背了 liveness 性质。

没有释放的情况很多：

想要解决这个问题，一个通常的做法就是对这个数据增加一个过期时间 TTL(Time to Live)。当这个数据存活时间达到 TTL 之后，数据库就会自动将其删除，也就是锁自动释放。这个过期时间设置长短，需要考虑操作共享资源需要多长时间。比如在 Redis 中，我们可以对 lock 这条数据设置 10 秒的过期时间。

SETNX lock 1
EXPIRE lock 10

那么 Redis 能否保证这两个命令能原子完成呢？答案是否定的，也就会出现第一个命令成功，而第二个命令失败的情况，仍然会出现无法上锁成功的情况。 Redis 后来提供了原子的命令，保证两个操作能够原子执行。

// 下面的两个命令都等价于SETNX lock 1和EXPIRE lock 10
// 但能保证原子执行
SET lock 1 NX EX 10        // EX代表秒
SET lock 1 NX PX 10000     // PX代表毫秒

（二）如何避免释放掉其他客户端上的锁

增加了 TTL，就可能出现另一种问题：客户端 1 操作共享资源期间，由于各种原因，时间超过了 TTL，此时 Redis 就会把客户端 1 上的锁释放。进而客户端 2 就会获取到锁，如果此时客户端 1 刚好操作完共享资源，开始释放锁，不就把客户端 2 的锁给释放了吗？

解决这个问题的关键就在于判断当前持有锁的客户端是不是自己。回顾以下我们获取锁的命令是SET lock 1 NX EX 10，其中1是客户端的 id. 之所以要把自身 id 写入到锁之中，就是为了在释放锁时检查持有锁的 id.  这是一个典型的 read-modify-write 操作，实际上就是要原子的执行如下伪代码：

If get(lock) == $id
    del(lock)

然而 Redis 没有提供这样原子执行的命令，而是通过调用 Lua 脚本的形式可以保证原子性。

if redis.call("GET", KEYS[1]) == ARGV[1]
then
    return redis.call("DEL", KEYS[1])
else
    return 0
end

如果get和del不是原子执行的，也会出现违反 safety 的现象。到这里，一个基于单机数据库的分布式锁服务基本就完成了。

然而，如果这个单机数据库发生了单点故障呢？这时候我们就只能将分布式锁服务替换成一个分布式服务了。

（三）基于主从数据库的实现方式

如果我们基于主从数据库来实现一个分布式锁服务，最大的困难就在于主从复制是异步完成的。

一种违背 safety 性质的情况如下：

（四）基于数据库 Quorum 的实现方式

主从数据库作为分布式锁服务的最大问题在于，客户端每次只和其中一个数据库节点进行通信，而主从数据库之间是异步复制，导致主库和从库之间有可能没有对哪个客户端获取成功锁达成共识，进而导致违背互斥。

想要解决这个问题，首先我们仍然需要多个数据库节点，但客户端在上锁时要么直接和多个数据库同时通信，并获取其中大多数的授权。要么多个数据库之间有一个一致性共识协议，客户端每次只和 leader 节点通信，由 leader 节点负责确保大多数节点达成了共识，并告知客户端上锁成功。后一种方法，其实已经和 ZooKeeper 和 Etcd 非常接近了。

三、Redlock

Redis 的作者后来基于 Qruorum 提出了 Redlock 这种分布式锁解决方案，这个方案有 2 个前提：

Redlock 的主要流程如下：

我们可以结合 Redlock 是如何保证 safety 和 liveness 性质来理解这个方案。

（一）Safety Arguments

分几种情况来看：

• 如果客户端用大于等于 TTL 的时间来对所有 Redis 节点进行上锁，此时第 3 步会检查失败，并开始向所有节点释放锁。此时客户端并没有获取锁成功，可能有其他客户端获取锁成功，不违背 safety. 
• 如果客户端用小于 TTL 的时间对所有 Redis 节点进行上锁，此时第 3 步会检查成功，认为该客户端获取分布式锁成功。此时是如何保证 safety 成立呢？

由于客户端至少向大多数的 Redis 节点成功写入了记录，因此成功写入的这些 Redis 节点保存的这条记录 TTL 相同（客户端上锁时指定的过期时间相同），而这些节点中这条记录的过期时间不尽相同（客户端往不同节点写入这条记录的时间不同）。

这里需要注意，客户端是从大多数 Redis 节点获取锁成功，有小部分 Redis 节点是可能超时或者获取锁失败的，我们也无需考虑。

在这些成功写入的节点中，最早写入成功的时间Tmin一定大于T1（因为从T1之后才发送了请求），而最晚写入的时间Tmax一定小于T2（因为T2时刻已经获取到了所有节点加锁结果）。那么这个分布式锁最早失效的时间就是最早成功写入记录这个节点的失效时间（因为这个节点过期，可能就会导致不满足 Quorum）。


由于我们无法精确知道Tmin，我们可以转而使用T1来进行如下推导：

  第一个写入成功的Redis节点这条记录的过期时间
= TTL + Tmin
> TTL + T1
> TTL - (T2 - T1)
> TTL - (T2 - T1) - CLOCK_DRIFT
= MIN_VALIDITY

由此得到分布式锁的最早失效时间MIN_VALIDITY = TTL - (T2 - T1) - CLOCK_DRIFT。在[T2, MIN_VALIDITY]这段时间之内，大多数节点的这条记录都没有过期。换句话说，其他客户端是不可能在这段时间之内往大多数节点写入这条记录，即不可能获取分布式锁。因此 Redlock 能够保证 safety.

推导过程中要引入 T2 和时钟漂移的原因在于，客户端往所有节点写入记录的时间也需要记录在内。

（二）Liveness Arguments

Liveness 成立主要依赖以下三方面：

由于有这几种清理和重试的机制，保证了多个 Redis 组成的分布式锁服务不会出现时钟无法获取分布式锁的情况。

不过 Redis 自己的官方文档中，描述了这样一种场景：如果每次客户端获取到分布式锁之后，在客户端向 Redis 发送释放锁的命令之前，客户端被网络隔离，在锁过期时间 TTL 之前，其他节点无法获取到分布式锁。如果网络时断时续这种情况一直出现，也就会导致整个分布式锁的可用性大大降低。

（三 ）What if Redis crashed?

如果 Redis 没有开启任何持久化，当节点 crash 时，Redlock 是否能满足 safety 呢？答案是否定的。比如一个客户端在 ABCDE 这 5 个节点中的 ABCDE 上锁成功，成功获取了分布式锁。如果此时 A 进程 crash 并重启，那么其他客户端就可以从 ADE 获取到同一个分布式锁。

想要完全避免这个问题，一种办法是每次 Redis 都需要把记录落盘，即开启fsync=always，性能肯定会大打折扣。

另一种办法就是当 Redis 节点重启之后，只有经过一个 TTL 时间，才能对外服务。这样也就避免了 A 重启之后再次上锁成功的问题（因为之前的锁一定已经过期）。这个办法的缺点在于如果节点频繁重启，也会大大影响可用性。

然而，当 Redlock 提出之后，DDIA 的作者 Martin Kleppman 就质疑了这个算法，后来 Redis 的作者 Antirez 也下场进行了反驳。两个人都是大牛，到底谁说的更有道理呢？我们下一期「分布式锁」技术科普再继续讨论～

Reference

[1]万字长文说透分布式锁：https://zhuanlan.zhihu.com/p/403282013