分布式锁

分布式锁用来锁什么?

  1. 效率(efficiency),避免不必要的重复昂贵计算。如果锁失败了,我们可能会面临两个节点执行相同的任务,会造成提升成本(为aws多支付5美分)或者一些小麻烦(比如给用户发送重复的邮件等)
  2. 正确性(correctness),防止并发问题和保证系统正确状态。如果失败了,两个节点使用相同的数据并行工作,会造成文件损坏,数据丢失,数据不一致,例如给病人服用错误的药量、奖品超发等一系列严重问题

分布式锁需要满足哪些?

安全属性:相互排斥。任何时候,只有1个client可以持有
可用属性A:死锁释放。在客户端锁住资源之后发生宕机或网络不通时,锁应该可以达到被获取的状态
可用属性B:容错性。只要大多数redis节点存活,客户端应该可以申请、释放锁。

redis单实例/单集群实现

申请锁:

1
SET resource_name my_random_value NX PX 30000

释放锁:

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

redis单实例/单集群的问题

  1. 单实例时会有单点故障
  2. 主从时,redis主从采用异步复制数据
    1. client A 从master获取锁
    2. master宕机,锁数据未同步到slave
    3. slave 升级为master
    4. client B 获取锁,此时A还未释放,此时违反了相互排斥原则

The Redlock algorithm

我们假设有N个redis master节点,这些节点是独立的,他们之间不存在数据复制或其他任何隐式系统的协调。假设N=5。

client获取锁有以下操作:

  1. 获取当前时间毫秒值
  2. 使用相同的key,随机的value,尝试在所有实例上连续的获取锁,在第二步为了获取锁,client超时时间小于锁自动释放时间,例如自动释放时间为10秒,超时时间应该在5-50ms之间。防止客户端与宕机节点阻塞很长时间,如果一台实例不可用,我们应该尽快的与下一个实例交互。
  3. client根据第一步获取的时间,计算消耗的时间,以重新获取锁,仅当client在多数实例获取锁成功(至少3个),并且消耗时间小于锁的过期时间,锁才会被认为获取成功。
  4. 如果锁获取了锁,锁的有效时间是第三步计算时间与初始化有效时间的较小值。
  5. 如果client因为某些原因获取失败(没有达到N/2+1个实例或超过有效期),那么将在所有实例释放锁(即使实例被认为未能获取锁)

redlock的问题

在上面的时序图中,假设锁服务本身是没有问题的,它总是能保证任一时刻最多只有一个客户端获得锁。上图中出现的lease这个词可以暂且认为就等同于一个带有自动过期功能的锁。客户端1在获得锁之后发生了很长时间的GC pause,在此期间,它获得的锁过期了,而客户端2获得了锁。当客户端1从GC pause中恢复过来的时候,它不知道自己持有的锁已经过期了,它依然向共享资源(上图中是一个存储服务)发起了写数据请求,而这时锁实际上被客户端2持有,因此两个客户端的写请求就有可能冲突(锁的互斥作用失效了)。

初看上去,有人可能会说,既然客户端1从GC pause中恢复过来以后不知道自己持有的锁已经过期了,那么它可以在访问共享资源之前先判断一下锁是否过期。但仔细想想,这丝毫也没有帮助。因为GC pause可能发生在任意时刻,也许恰好在判断完之后。

也有人会说,如果客户端使用没有GC的语言来实现,是不是就没有这个问题呢?Martin指出,系统环境太复杂,仍然有很多原因导致进程的pause,比如虚存造成的缺页故障(page fault),再比如CPU资源的竞争。即使不考虑进程pause的情况,网络延迟也仍然会造成类似的结果。

总结起来就是说,即使锁服务本身是没有问题的,而仅仅是客户端有长时间的pause或网络延迟,仍然会造成两个客户端同时访问共享资源的冲突情况发生。

Redlock对系统计时(timing)的过分依赖

Martin在文中构造了一些事件序列,能够让Redlock失效(两个客户端同时持有锁),假设有5个Redis节点A, B, C, D, E:

  1. 客户端1从Redis节点A, B, C成功获取了锁(多数节点)。由于网络问题,与D和E通信失败。
  2. 节点C上的时钟发生了向前跳跃,导致它上面维护的锁快速过期。
  3. 客户端2从Redis节点C, D, E成功获取了同一个资源的锁(多数节点)。
  4. 客户端1和客户端2现在都认为自己持有了锁。

上面这种情况之所以有可能发生,本质上是因为Redlock的安全性(safety property)对系统的时钟有比较强的依赖,一旦系统的时钟变得不准确,算法的安全性也就保证不了了。Martin在这里其实是要指出分布式算法研究中的一些基础性问题,或者说一些常识问题,即好的分布式算法应该基于异步模型(asynchronous model),算法的安全性不应该依赖于任何记时假设(timing assumption)。在异步模型中:进程可能pause任意长的时间,消息可能在网络中延迟任意长的时间,甚至丢失,系统时钟也可能以任意方式出错。一个好的分布式算法,这些因素不应该影响它的安全性(safety property),只可能影响到它的活性(liveness property),也就是说,即使在非常极端的情况下(比如系统时钟严重错误),算法顶多是不能在有限的时间内给出结果而已,而不应该给出错误的结果。这样的算法在现实中是存在的,像比较著名的Paxos,或Raft。但显然按这个标准的话,Redlock的安全性级别是达不到的。

客户端GC pause引发Redlock失效

  1. 客户端1向Redis节点A, B, C, D, E发起锁请求。
  2. 各个Redis节点已经把请求结果返回给了客户端1,但客户端1在收到请求结果之后进入了长时间的GC pause。
  3. 在所有的Redis节点上,锁过期了。
  4. 客户端2在A, B, C, D, E上获取到了锁。
  5. 客户端1从GC pause从恢复,客户端1认为自己成功获取到了锁,继续处理业务
  6. 客户端1和客户端2现在都认为自己持有了锁。

Martin给出的这个例子其实有点小问题。在Redlock算法中,客户端在完成向各个Redis节点的获取锁的请求之后,会计算这个过程消耗的时间,然后检查是不是超过了锁的有效时间(lock validity time)。也就是上面的例子中第5步,客户端1从GC pause中恢复过来以后,它会通过这个检查发现锁已经过期了,不会再认为自己成功获取到锁了。我对Martin的例子做了简单的调整:gc pause节点,由收到回复之前,改到确认加锁成功之后、执行业务之前。antirez在他的反驳文章中就指出来了这个问题,但Martin认为这个细节对Redlock整体的安全性没有本质的影响。

Martin构造这里的这个例子,是为了强调在一个分布式的异步环境下,长时间的GC pause或消息延迟(上面这个例子中,把GC pause换成Redis节点和客户端1之间的消息延迟,逻辑不变),会让客户端获得一个已经过期的锁。从客户端1的角度看,Redlock的安全性被打破了,因为客户端1收到锁的时候,这个锁已经失效了,而Redlock同时还把这个锁分配给了客户端2。换句话说,Redis服务器在把锁分发给客户端的途中,锁就过期了,但又没有有效的机制让客户端明确知道这个问题。而在之前的那个例子中,客户端1收到锁的时候锁还是有效的,锁服务本身的安全性可以认为没有被打破,后面虽然也出了问题,但问题是出在客户端1和共享资源服务器之间的交互上。

zookeeper实现

  1. 客户端尝试创建一个znode节点,比如/lock。那么第一个客户端就创建成功了,相当于拿到了锁;而其它的客户端会创建失败(znode已存在),获取锁失败。
  2. 持有锁的客户端访问共享资源完成后,将znode删掉,这样其它客户端接下来就能来获取锁了。
  3. znode应该被创建成ephemeral的。这是znode的一个特性,它保证如果创建znode的那个客户端崩溃了,那么相应的znode会被自动删除。这保证了锁一定会被释放。

zookeeper实现的问题

ZooKeeper是怎么检测出某个客户端已经崩溃了呢?实际上,每个客户端都与ZooKeeper的某台服务器维护着一个Session,这个Session依赖定期的心跳(heartbeat)来维持。如果ZooKeeper长时间收不到客户端的心跳(这个时间称为Sesion的过期时间),那么它就认为Session过期了,通过这个Session所创建的所有的ephemeral类型的znode节点都会被自动删除。

设想如下的执行序列:

  1. 客户端1创建了znode节点/lock,获得了锁。
  2. 客户端1进入了长时间的GC pause。
  3. 客户端1连接到ZooKeeper的Session过期了。znode节点/lock被自动删除。
  4. 客户端2创建了znode节点/lock,从而获得了锁。
  5. 客户端1从GC pause中恢复过来,它仍然认为自己持有锁。

最后,客户端1和客户端2都认为自己持有了锁,冲突了。看起来,用ZooKeeper实现的分布式锁也不一定就是安全的。该有的问题它还是有。但是,ZooKeeper作为一个专门为分布式应用提供方案的框架,它提供了一些非常好的特性,是Redis之类的方案所没有的。像前面提到的ephemeral类型的znode自动删除的功能就是一个例子。

还有一个很有用的特性是ZooKeeper的watch机制。这个机制可以这样来使用,比如当客户端试图创建/lock的时候,发现它已经存在了,这时候创建失败,但客户端不一定就此对外宣告获取锁失败。客户端可以进入一种等待状态,等待当/lock节点被删除的时候,ZooKeeper通过watch机制通知它,这样它就可以继续完成创建操作(获取锁)。这可以让分布式锁在客户端用起来就像一个本地的锁一样:加锁失败就阻塞住,直到获取到锁为止。这样的特性Redlock就无法实现。

顺便提一下,如上所述的基于ZooKeeper的分布式锁的实现,并不是最优的。它会引发“herd effect”(羊群效应),降低获取锁的性能。一个更好的实现参见下面链接:

如何解决?

Martin给出了一种方法,称为fencing token。fencing token是一个单调递增的数字,当客户端成功获取锁的时候它随同锁一起返回给客户端。而客户端访问共享资源的时候带着这个fencing token,这样提供共享资源的服务就能根据它进行检查,拒绝掉延迟到来的访问请求(避免了冲突)。如下图:

fencing token

基于random token的“Check and Set”

  1. 先设置X.currlock = token。
  2. 读出资源X(包括它的值和附带的X.currlock)。
  3. 按照”write-if-currlock == token”的逻辑,修改资源X的值。意思是说,如果对X进行修改的时候,X.currlock仍然和当初设置进去的token相等,那么才进行修改;如果这时X.currlock已经是其它值了,那么说明有另外一方也在试图进行修改操作,那么放弃当前的修改,从而避免冲突。

antirez举了一个“将名字加入列表”的操作的例子:

  1. T0: Client A receives new name to add from web.
  2. T0: Client B is idle
  3. T1: Client A is experiencing pauses.
  4. T1: Client B receives new name to add from web.
  5. T2: Client A is experiencing pauses.
  6. T2: Client B receives a lock with ID 1
  7. T3: Client A receives a lock with ID 2
  • “Check and Set”对于写操作要分成两步来完成(设置token、判断-写回),而递增的fencing token机制只需要一步(带着token向资源服务器发起写请求)。
  • 递增的fencing token机制能保证最终操作共享资源的顺序,那些延迟时间太长的操作就无法操作共享资源了。但是基于random token的“Check and Set”操作不会保证这个顺序,那些延迟时间太长的操作如果后到达了,它仍然有可能操作共享资源(当然是以互斥的方式)。

fencing token 实现

Chubby的分布式锁是怎样做fencing的?

提到分布式锁,就不能不提Google的Chubby。

Chubby是Google内部使用的分布式锁服务,有点类似于ZooKeeper,但也存在很多差异。Chubby对外公开的资料,主要是一篇论文,叫做“The Chubby lock service for loosely-coupled distributed systems”,下载地址如下:

另外,YouTube上有一个的讲Chubby的talk,也很不错,播放地址:

Chubby自然也考虑到了延迟造成的锁失效的问题。论文里有一段描述如下:

a process holding a lock L may issue a request R, but then fail. Another process may ac- quire L and perform some action before R arrives at its destination. If R later arrives, it may be acted on without the protection of L, and potentially on inconsistent data.
(译文: 一个进程持有锁L,发起了请求R,但是请求失败了。另一个进程获得了锁L并在请求R到达目的方之前执行了一些动作。如果后来请求R到达了,它就有可能在没有锁L保护的情况下进行操作,带来数据不一致的潜在风险。)

Chubby给出的用于解决(缓解)这一问题的机制称为sequencer,类似于fencing token机制。锁的持有者可以随时请求一个sequencer,这是一个字节串,它由三部分组成:

锁的名字。
锁的获取模式(排他锁还是共享锁)。
lock generation number(一个64bit的单调递增数字)。作用相当于fencing token或epoch number。
客户端拿到sequencer之后,在操作资源的时候把它传给资源服务器。然后,资源服务器负责对sequencer的有效性进行检查。检查可以有两种方式:

调用Chubby提供的API,CheckSequencer(),将整个sequencer传进去进行检查。这个检查是为了保证客户端持有的锁在进行资源访问的时候仍然有效。
将客户端传来的sequencer与资源服务器当前观察到的最新的sequencer进行对比检查。可以理解为与Martin描述的对于fencing token的检查类似。
当然,如果由于兼容的原因,资源服务本身不容易修改,那么Chubby还提供了一种机制:

lock-delay。Chubby允许客户端为持有的锁指定一个lock-delay的时间值(默认是1分钟)。当Chubby发现客户端被动失去联系的时候,并不会立即释放锁,而是会在lock-delay指定的时间内阻止其它客户端获得这个锁。这是为了在把锁分配给新的客户端之前,让之前持有锁的客户端有充分的时间把请求队列排空(draining the queue),尽量防止出现延迟到达的未处理请求。
可见,为了应对锁失效问题,Chubby提供的三种处理方式:CheckSequencer()检查、与上次最新的sequencer对比、lock-delay,它们对于安全性的保证是从强到弱的。而且,这些处理方式本身都没有保证提供绝对的正确性(correctness)。但是,Chubby确实提供了单调递增的lock generation number,这就允许资源服务器在需要的时候,利用它提供更强的安全性保障。

总结

无论redis还是zookeeper实现的分布式锁,都是在客户端实现,此时我们把获取锁的线程当作客户端,访问的资源作为服务端。

多个或同一个客户端做一件事,比如扫码支付/抢一个商品/提交同一个form表单,最终只能有一个可以成功,在客户端我们只能做一些辅助性的拦截(防止重复提交,库存校验等),无论客户端做不做这些,我们服务端都要再次校验。

在分布式环境下,会有网络,时钟,gc各种原因会造成客户端的到达服务端的顺序不一致,所以,无论有没有分布式锁,我们都要在资源(服务端)进行校验,从而保证系统正确性。

我觉得,分布式锁有两个作用:

  • 限流,降低访问共享资源的并发
  • 分配访问共享资源的ticket

至于这个ticket是有效还是无效,最终要靠共享资源(服务端)决定。

参考

Distributed locks with Redis
How to do distributed locking
针对Martin的blog的讨论
针对antirez的blog的讨论
Note on fencing and distributed locks
The Chubby lock service for loosely-coupled distributed systems
基于Redis的分布式锁到底安全吗(上)?
基于Redis的分布式锁到底安全吗(下)?