Redis单实例锁和Redlock分布式锁算法

在实际使用中，Redis除了作为一个KEY-VALUE的内存数据库之外，还常常被用作分布式环境的锁服务。本文对Redis的锁从单机和分布式环境上做一个概述，关注实现原理和优缺点。

单实例实现

获取锁

由于Redis的线程模型是单线程的- 也就是说，对于多个客户端任一时刻只会有一个请求在被处理。所以，通过“对Redis中某个指定的Key在不存在的情况下设置某个值，而存在就是有其他线程已经设置了这个值”这个语义行保证，可以实现获取锁这么一个操作。对应到Redis命令，也就是:

1
2
3



SET resource_name my_random_value NX PX 30000

上面的参数NX表示仅在前面的 resource_name不存在的情况下才设置，这其实就是某种程度上的排它性。而后面的PX则表示过期时间，Redis会在这个时间过后自动删除这个key,所以这个时间隐含的意义是获取到锁过后的操作的最大时间，如果锁里面的操作超过这个时间，那么这个Redis锁的正确性就会存疑（后面介绍具体原因）

关于 value 的生成，官方推荐从/dev/urandom中取20位随机数，或者用RC4在/dev/urandom中得到一个seed,然后生成伪随机流，又或者直接用时间戳+客户端编号的方式都可以。

释放锁

上面写到，在Redis中设置一个指定的key其实就是获取一个锁，那么释放锁也只需要删除这个key即可。但是，如下方式:

1 2	DEL resource_name

有一个潜在的问题：如果客户端A获取到了锁并且由于Full GC或者网络阻塞等原因没有释放锁，此时Redis服务器上这个锁刚好超时，客户端B获取到了这个锁。那么当客户端A的释放锁请求到了Redis

后就会释放此时实际上是客户端B的锁。所以，释放锁这个操作需要判断Value是之前锁定的那一个。



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

这里是通过lua脚本释放锁，需要传入要释放的锁的key和value。这里为什么要通过脚本而不是直接在客户端用这种方式呢:


if(redis.get('key') == 'value'){

    redis.del('key')

}

这实际上是因为上面的代码里的查询和删除不是原子性的，完全有可能出现get方法返回的是正确的值，然后马上这个key过期而其他线程获取到锁，然后就会出现误删其他人的锁的情况。而

lua脚本则可以保证原子性。

问题

上述的单实例的锁实现有一个潜在的问题： Redis会在指定的超时时间后自动删除这个key, 也就是释放锁。考虑这种情况：

Client A先获得了锁
Client B在等待A释放锁
此时, Client A被阻塞在某些事上，比如GC, RPC调用, CPU不足等待，导致Client A的操作时间超过了指定的锁时间
Redis发现这个锁已经超时还没有被释放，于是自动释放了这个锁（担心遇到死锁）
Client B获得了锁并且更新了资源
Client A恢复过来，那么此时Client A和Client B都持有了锁。如果他们都会数据库做了某些操作，那么就可能出现一方覆盖另外一方结果的情况

上述的情况我在开发中实际遇到过，还是核心记账系统。HBase也有

比如我们更新数据的操作是这样的:


int amt = UserAmt.find(); //从数据库查出某个数据

amt = amt - crtAmt;  //经过计算

UserAmt.update(amt); //然后把这个值在数据库里通过 update xxx set val = ${val}来更新

上面这种方式的代码就可能会出现值被覆盖的问题。

要解决这个问题需要通过fence(栅栏)技术，其实也就是乐观锁机制。我们需要一个版本号来排它。

fence

也就是说:

锁服务需要一个单调递增的版本号
写数据的时候也需要版本号
数据库服务需要保存版本号，然后对请求做检查

对于数据库，我们还有一种简单的方式，就是在更新数据时用这种方式:


update table_name set xxx = #{xxx}, version = version+1 where version = #{version};

//或者

update table_name set xxx = xxx+#{xxx} where xxx = #{oldxxx};

PS：某种意义上，这其实就是CAS。

多实例实现

Redis官方提供了一种分布式环境下的锁算法: Redlock。该算法描述如下：

获取当前时间
对N个实例顺序进行获取锁的操作。对单实例的操作同上。要求是对一个Redis实例的操作时间要远远小于锁的超时时间，这样可以保证在少数Redis节点挂掉的时候仍可快速对下一个节点进行操作
客户端记录所有实例返回加锁成功的时间，当且仅当客户端获取到多半实例(N/2+1)的锁且获取锁的时间小于锁超时时间，锁才认为是成功获取
如果锁获取成功，锁的有效时间就是初始时间减去上面所说的获取锁花费时间
如果因为任何原因获取锁失败，则尝试在所有节点删除这个锁（即使这个节点没有获取成功）

一些细节问题

时钟摇摆问题

由于使用的各个Redis实例之间没有同步的时钟，并且每个机器时间可能不准，最简单的做法是在上面步骤3中的时间再减去一小段时间。关于这个有个讨论.

不过实际使用时，这个变量很难确定，所以大部分实现库也没有对这个做特殊处理。但是必须注意这个是事实存在的问题

失败重试

当一个客户端获取锁失败时，应该随机延迟一会儿再次尝试获取锁，已避免多个客户端同时获取锁的竞争情况（最坏时大家都获取不到锁）。理想情况下，应该使用IO多路复用对多个实例执行SET。

如果获取多半实例(N/2+1)锁失败，最好的方式是立即释放所获取到的锁，而不用等待锁超时了再次尝试重新获取。

释放锁

释放锁则只需要简单的遍历所有实例，然后删除key即可，而不用管某个实例上是否成功获取到锁。

故障恢复

使用Redis做分布式锁的大部分用户都是因为它的低延迟、高性能。而在出现故障的情况下，Redis会有一些问题。

对于Redis出现故障重启过后的逻辑，分为两种情况：

关闭持久化

当关闭持久化后，如果某个客户端获取到了锁（也就是多半实例），在Redis因为任何问题重启过后这个客户端获取到的所有锁就失效了，其他客户端可以再次获得锁。

开启持久化

如果开启了AOF持久化（rsync，每隔1秒终保存一次数据），重启会导致丢失1秒左右的数据，也会导致锁的互斥性问题。而如果关闭rsync（保证锁可以被安全的保存），就对性能有了较大了影响（每次更改都会持久化），与传统的CP系统实现也差不多了。

上述问题都是因为系统重启过后锁依然是有效，而其他客户在此时有可能再次获得锁。如果我们让所有的锁在重启过后都已经超时，则上述问题都可以很容易的解决。所以，在Redis系统崩溃过后，我们在Redis锁的最大的有效时长的延迟过后再重启，则不会出现类似的问题。

安全性的相关讨论

假设客户端可以获取大部分实例上的锁，而所有实例均有一个相同的锁合法时间，由于初始设置的时间不一定相同，所以各个实例上的键不一定同时过期。假设 T1 为请求第一个实例的时间，T2 为从最后一个服务器得到回复的时间。在客户端认为获得到分布式锁后，第一个实例上的键会在 MIN_VALIDITY = TTL - (T2 - T1) - CLOCK_DRIFT 后过期，之后其他的键也会过期，所以确定在 MIN_VALIDITY 内，所有键都还未过期。

在过半实例都被设置的情况下，若一个客户端请求获取锁，因为无法在过半的实例上设置键，所以会失败。如果一个客户端占有锁的时间接近或大于 MIN_VALIDITY，部分实例上的锁才会失效。MIN_VALIDITY 内是不可能存在过半实例可以被设置键的情况，故在 MIN_VALIDITY 内分布式锁是安全的。

作者关于安全性的一篇文章有关于Redlock安全性的一篇讨论。Martin 认为Redlock算法是一个asynchronous model with unreliable failure detectors，依赖了不可靠的元素来保证其一致性，容错性有一定限度，超过限度则无法保证其正确性。GC 的 stop-the-world、网络的阻塞、CPU切片等等都会影响 Redlock 的效率或者正确性，而作者的答案是:

对于锁内超时，分布式锁并不能提供强一致性，只在没有其他办法控制共享资源时才会使用，Redlock算法是为了找到单节点或者主备锁的替代品，并且在复杂度和效率上取得平衡

如果对于一致性有强烈的需求，zookeeper或者fencing token或者说CAS都是不错的选择

陈硕在极客时间专栏上对这个问题也有描述。如果我们需要的是修改共享资源，CAS/乐观锁等方式都可以实现，如果我们需要的是进程或者实例之间的互斥，则需要分布式锁。而对于强一致性的需求，则决定了是否要使用Redis作为工具，zookeeper是一个不错的替代品。