Redis分布式锁实现

2018-09-10 本文已影响0人一剑光寒十九洲

前置知识

最低保证的分布式锁特性

互斥安全：能够保护临界代码区被互斥的访问。（这是锁的要求）
不会死锁：当持有锁的客户端崩溃或者无法访问到redis，该锁能够被释放，使得其它客户端仍然可以获取这个锁。
可用：只要大部分redis节点还活着，客户端就可以获取和释放这个锁（单实例的redis不需要考虑这个特性，在下面我们暂时不考虑这个特性，我们暂时只考虑多客户端访问单实例redis）。

事实上，要想同时满足所有这三个特性是非常难的。

使用到的命令

命令	含义	返回值
SETNX key value	当 key 不存在，将 key 的值设为 value	设置成功返回1，否则返回0
PEXPIRE/EXPIRE key milliseconds	为给定 key 设置生存时间	设置成功返回 1，否则返回0
SET key value [EX seconds] [PX milliseconds] [NX\|XX]	将字符串值 value 关联到 key	设置完成返回OK，如果设置了 NX 或者 XX ，但因为条件没达到而造成设置操作未执行，那么命令返回空批量回复（NULL Bulk Reply）
DEL key [key ...]	删除给定的一个或多个 key	被删除 key 的数量
EVAL script numkeys key [key ...] arg [arg ...]	通过内置的 Lua 解释器，可以使用 EVAL 命令对 Lua 脚本进行求值	Lua 脚本的返回值也会被转换成 Redis 协议(protocol)，然后由 EVAL 将值返回给客户端

分布式系统中可能遇到的情况

进程崩溃：分布式系统中某一个进程的崩溃，可能会使得其持有的资源无法释放或者其它需要依赖于该进程的进程们无法正常进程，等等。
网络分区：网络分区可能是的一部分进程无法访问另外一部分进程。
网络延时：网络延时可能会使得一个数据包在经历了一段比较长的时间之后才到的对端，而这时可能对端的状态已经出现了比较大的改变。
网络丢包：某些数据包可能在传输的过程中丢失。（如果是在一条tcp连接上，tcp本身会保证不会丢包，udp则不会保证）
网络包乱序：后发送的数据包可能比其它数据包提前到达。（如果是在一条tcp连接上传输数据，tcp本身会保证不会产生数据包乱序，udp则不会保证）

分布式系统中错误的假设

The network is reliable.
网络总是可靠的。
Latency is zero.
网罗延迟总是零。
Bandwidth is infinite.
带宽是无限的。
The network is secure.
网络是安全的。
Topology doesn't change.
网络拓扑关系从不改变。
There is one administrator.
有一个管理员能够处理出现的问题。
Transport cost is zero.
传输成本为零。
The network is homogeneous.
网络是同构的。

实现

分布式系统程序设计目标

分布式设计要为重启而设计

我们开发的程序的可靠性只需要略高于硬件和操作系统即可：连续运行数个星期。
某些资源不足的错误，直接重启进程就好
通过软件手段来提高系统的整体可用性。

下面我们来看看设计一个分布式锁来保护临界区方法doSomething的过程。

先来看一个最简单的锁

    t, err = SETNX lock "locked"    // p1
    if err == nil && t == 1 :       // p2
        doSomething()               // p3
        del lock                    // p4

对这个算法各个阶段失败的探索，有助于我们理解分布式程序和单机程序的不同之处：

如果p1调用失败了（即err!=nil），失败的原因可能有哪些呢？有可能是请求打到redis服务器前，主机崩溃了或者网络永久性不可达了，在这种情况下，这次请求没有被redis服务端接受的，返回了错误，客户端不会获得锁，算法没有毛病。如果请求打到了redis服务器之后，在redis执行了相关操作但是响应打到客户端之前，主机崩溃了或者网络永久性不可达了，将会导致这样的一种状况：客户端得到了err!=nil，认为自己没有拿到锁，自然之后也就不会有释放锁的操作；但是在redis那边，键lock已经被创建了，锁已经分配出去了，其它的客户端将再也无法获取到这个锁。如此就造成了一种死锁现象。这是算法就无法正常工作了。请注意：一次网络调用实际上起码是分三个操作来完成的：客户端发送请求，服务端执行操作，服务端返回响应，这三个不是原子操作，它们可能因为进程崩溃或者网络断开而中断，在分布式环境下，我们必须要对这种情形进行容错处理。
和上面的分析一样，我们还可以看到，在客户端获得锁（redis设置了lock同时客户端获取到了err!=nil&&t==1的响应）之后，在接下来执行p2和p3和p4的时候，仍然有可能出错，考虑一下，在客户端持有锁直到del lock请求发送到服务端之前，一旦客户端崩溃或者和redis服务器之间的网络永久性断开，客户端将再也无法通知redis服务器释放锁。而这个锁也就再也不能被其他客户端获取。注意：客户端的崩溃有可能使得某些资源再也无法被释放。
上面的2种情形的都会出现redis再也无法释放锁从而造成死锁的现象，只不过在情形1中客户端并不知道自己持有锁，而在情形2中，客户端则是知道自己持有锁的。向上翻一下，这肯定是违背了分布式锁最低要求的特性2的。接下来我们需要想出一种办法来避免这种情形下的死锁的发生。

这个实现可以满足特性1：互斥安全的要求，但是无法满足特性2:互斥安全

带有过期时间的锁

我们必须提供一个机制，使得当持有锁的客户端（不管该客户端知道不知道它持有这个锁）崩溃或者和redis服务器之间的网络不可达的时候，仍然能够释放该客户端持有的锁。
我们可以使用redis的超时机制通过redis服务器自身来释放这个锁。

    t, err = SET lock "locked" NX EX 10 // p1
    if err == nil && t == 1:            // p2
        doSomething()                   // p3
        del lock                        // p4

我们为锁lock设置了一个超时时间，这样当持有锁的客户端失效（崩溃或者和redis服务器网络永久性不可达）后，redis在键lock过期之后，会主动的把该键删除从而释放这个锁，从而使得其它的客户端可以获取到这个锁。
但是，这个算法仍然是有问题的。为什么呢？因为加入了过期时间的问题，这意味着客户端持有的锁的时间是有限的，它必须在锁过期时间之内完成临界区代码，否则，一旦锁过期了，该锁就可能被其它的客户端获取到，从而使得两个客户端代码同时进入了临界区，而这违背了分布式锁的特性1的要求。
我们继续对上述的情形进行分析，看看两个客户端同时进入了临界区代码之后会发生的情况，在首先获取锁的客户端1的锁过期后，客户端2获取了锁但是还没有退出临界区代码的时候，客户端1率先完成了临界区代码，然后它执行del语句，而这会将客户端2持有的锁删除，这也是不合理的，客户端2持有的锁应该只能由它自己释放。

这个实现可以满足特性2:不会死锁，但是削弱了特性1:互斥安全的特性

带有识别客户端和超时时间的锁

对于上面的那个实现，我们首先看怎么解决情形3中的问题，即一个客户端可能会释放另外一个客户端的锁，造成这种情况的原因在于，该redis服务器并不能区分释放锁的客户端是否就是获取到锁的客户端。所以我们自己来实现这样的需求。
第一个问题是，我们该怎样去区分不同的客户端呢？一种比较好的方式是使用客户端的ip-port串去标示，你还可以在加上当前获取锁的时间戳，就像这样：ip-port-unixstamp。我们需要在获取锁的时候把这个标识保存到redis服务器上，我们可以把它作为锁的value值，我们可以使用这样的语句来获取锁：

SET lock "192.168.0.108-8888-1536512839" NX EX 10

第二个问题是，在我们的客户端释放锁的时候，如何让redis对比持有锁的客户端标示和当前发送释放锁指令的客户端，以决定是否删除锁呢？我们需要类似于这样的原子指令：

    if (get lock) == "192.168.0.108-8888-1536512839":
        del lock

翻查一下redis命令手册，没有找到这样的判断-删除的原子指令（也许有人会想到事务，遗憾的是，事务只能保证指令执行间不被插入其它指令，但是redis没有为我们提供判断lock的值是否为"192.168.0.108-8888-1536512839"的指令：如果我们使用redis事务，下面的命令序列应该是大家能想到的：multi, exists, del, exec，遗憾的是在执行del前我们无法获取到exists的值），不过我们不用绝望，因为我们还有redis-lua来自己实现这样的功能，redis保证了一个redis—lua脚本会在redis服务器中被原子性的执行，所以我们可以利用redis-lua脚本来实现这个功能：

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

其中ARGV[1]的参数值为客户端要释放lock时发送的自身客户端标识，KEYS[1]为锁的key名lock，脚本的功能是判断该标识是否和lock中保存的创建lock的客户端标识一致，如果一致，则删除锁lock。
完整的代码如下：

    $do_del_lock$ = `if redis.call("get",KEYS[1]) == ARGV[1] then
        return redis.call("del",KEYS[1])
    else
        return 0
    end`
    if t, err = SET lock $ip-port-unixstamp$ NX EX 10 // p1
    if err == nil && t == 1:            // p2
        doSomething()                   // p3
        eval $do_del_lock$ 1 lock $ip-port-unixstamp$ // p4

这样我们就解决了上个实现中一个客户端可能会释放掉其它客户端的锁的问题。

现在我们还有一个问题，即情形2中的问题，事实上，我们可以看到，如果情形2不会出问题的话，即如果可以保证互斥的话，那么是不可能存在一个客户端释放掉另外一个客户端持有的锁的问题的，也就是情形3永远也不会发生。那么我们为什么不直接解决情形2的问题呢？
我们来考虑一下，情形2的问题的关键在哪里。原因在于，这个锁会自动的过期，而它过期的时候，可能持有锁的客户端正在执行临界区代码，还没有完成（标注1）。而为什么我们选择了一个带有过期时间的锁呢，因为我们持有锁的客户端可能会失效，使得该锁永远无法被释放（标注2）。
如果我们决定使用带有过期时间的锁，可能会发生标注1中的情形，如果我们决定使用没有过期时间的锁，那么可能会发生标注2中的情形。但是只要我们解决了其中任何一种情形，我们就可以实现一个同时满足特性1:互斥安全和特性2:不会死锁的redis锁。（标注1满足2不满足1，而标注2满足1不满足2）
那么我们有没有办法解决这个问题呢？
对于标注1，很显然的一种想法是在该锁即将过期时我们进行续租，redis服务期并没有提供一种某个键即将过期的机制，但是我们的客户端请求锁的时候是知道自己对该锁的租约时间的，我们可以在即将到达的时候发送一个expire指令来延长我们的租约时间。这个想法很好，那么客户端在还剩下多久租约时间时发送这个续租命令，该续租命令能不能在剩余租约到达前被redis服务器执行，执行的结果能不能成功的返回（考虑我们之前说过的网络延时和网络故障的情形），如果续租失败，怎么办。关于这个模型，我之后还会进行思考，看看其可能性，我还会有更新的。
对于标注2，问题的关键是redis服务器无法感知到客户端是否是失效的，以及这个失效是永久性失效还是暂时性的失效。也就是说，在客户端和redis之间没有一种心跳机制，redis服务器是个请求-响应的服务器模型，暂时还没有心跳机制，所以这条路走不通。

可以看到，仅仅是实现redis分布式锁的两个特性就已经非常困难了，要实现全部三个特性那真是难如登天啊。

这个问题我还会关注的，如果我有了什么新的想法我会继续更新这篇文章的。