RedLock算法

安全性和可用性保证

• 安全特性：互斥访问，即永远只有一个 client 能拿到锁
• 避免死锁：即使原本锁住某资源的 client crash 了或者出现了网络分区,最终 client 都可能拿到锁，不会出现死锁的情况，
• 容错性：只要大部分 Redis 节点存活就可以正常提供服务

单节点分布式锁实现

加锁

SET resource_name my_random_value NX PX 30000

关于 my_random_value 说明

• 为了标记加锁的客户端
• 必须全局唯一

NX 作用

• 保证加锁的安全

PX 作用

• 保证锁最终可以被释放

解锁

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

单结点问题

• 可用性不高

RedLock 算法

1. 获取当前时间戳,微妙单位
2. 使用相同的key 和random_value,顺序对N个redis实例加锁,
   1. 获取锁耗时要远小于锁的生存时间 比如锁的存活时间是10s,对每个redis 实例加锁的耗时在 5-50ms, 超时后尽快访问下一个redis 实例
3. 客户端计算加锁是否成功, 两个条件
   1. 成功获取 N/2+1 个redis 实例的锁
   2. 获取锁的时间远小于锁的生存时间
4. 锁的实际生存时间计算
   1. 生存时间-获取锁消耗的时间-时钟漂移
5. 如果当前客户端获取锁失败,就尝试解锁所有的redis 实例

RedLock 算法生效的前提条件

• 时钟漂移足够小

失败重试

• 获取锁失败后,过一段随机时间后再重试,避免竞争加剧

锁续期

RedLock是否安全

参考 HowToDoDistributionLock

分布式系统下的NPC问题

• N：Network Delay，网络延迟
• P：Process Pause，进程暂停（如Java中的GC线程，GC在运行过程中会导致应用程序停顿这就是 Stop The World）
• C：Clock Drift，时钟漂移（指两个电脑间时间流速基本相同的情况下，两个电脑或者两个进程间，时间的差值，Martin指出时钟漂移出现的场景有运维人员手动调整系统时间或同步NTP时间出现跳跃）

GC导致锁不安全

Making the lock safe with fencing

GC 导致RedLock 不安全

参考文献

• RedLock
• Is redLock safe
• HowToDoDistributionLock