分布式锁是有用的在多个程序以相互独享的方式访问共享资源时。

有很多的库和书籍介绍如何使用redis的分布式锁，每个库的实现方式不一样，很多以一个简单的方式实现。

我们试图去实现一个标准的redis分布式锁。我们实现了一个叫做Redlock的算法，它实现了一个比单个instance更加安全的方法。我们希望社区能够分析它的性能，提更多的反馈意见回来。

实现

在介绍算法之前这里有一些实现：

安全性和存活期的保证

我们修改设计中3方面的保证，以一个高效的方式来设计分布式锁。

1.安全性：互斥现象在。在任何时候都应该仅仅有一个client hold a lock。

2.存活性A：死锁的释放。很多时候可能获得一个锁，即使client锁住的资源挂了或者只得到资源的部分。

3.存活性B：容错能力。尽可能的redis核心的node是正常工作的，clients能够得到和释放锁。

为什么基于实现的容错是不够的？

为了理解我们想要提升的是什么，先看看大多数redis分布式锁库的情况。

简单的方法是使用redis锁住资源在redis instance上创建一个key。key在创建的时候通常有一个生存期，使用redis的expires机制，所以在最终它会被释放或者如上保证中的的第2个处理。当client需要释放资源的时候，将会删除key。

表面上它没什么问题，但这里有一个问题：这是一个单点的挂了。如果发生在redis master上呢？它挂了呢？OK,我们添加一个slave。如果master挂了就使用它。不幸的是，由于redis的写是异步的导致我们这样做将无法实现互斥时的安全属性。

使用这个模型一个明显的race condition：

1.client A 在master上获得锁。

2.master在数据写到slave之前挂了。

3.将slave提升为master

4.client B获得锁在A已经锁住的资源上，违反安全性。

有些时候特殊情况下表现正常的，可能在一次失败时大量的client同时hold the lock。这种情况下你可以使用你的数据复制方式。否则我们建议使用这个文档中介绍的实现方式。

正确实现一个instance

在应用程序中有时一个 race condition也是可以接受的，因为我们对一个单instance进行加锁的基础是我们使用了分布式算法。

获得锁，如下：

SET resource_name my_random_value NX PX 30000

命令仅仅设置key在它没有准备好exist(NX option)的时候，同时存在一个30000 milliseconds (PX option)的超时设置。key将会被设置值为“myrandomvalue”。这个值是特别跨所有的clients和所有的锁请求的。

由于使用了随机值所以在释放锁的时候是安全的，一个脚本来告诉redis：移除key如果它存在并且它保存的值是我所期望的，它将通过以下lua脚本来完成：

这样可以避免remove掉别的client创建的key。例如：一个client可能获取锁，一些操作用时可能比key的生存期上(key超时)，并且只会remove lock，此时锁已经被别的client所获得。上述脚本是的每个锁上使用一个随机的字符串来标记，这样锁将只有在client设置remove它的时候被移除。

这个随机的字符串怎么得到？我猜是来自/dev/urandom的20个字节，当然你也可以使用字节的方法来实现它唯一并且对你来说是够用的。例如：一个安全的方法是从/dev/urandom取随机种子出来作为一个伪随机字符串。

一种简单的解决方式是使用unix time 的 microseconds 来解决，将它和client ID相关联，这虽然不是足够的安全但是在大多数环境可以进行测试。

我们使用key的生存期叫做“lock validity time”，它能够在同时自动释放时间， client保存时间是为了形成操作请求在别的client可能再次获取锁之前。没有在技术上违反互斥的保证，它仅仅限制在获取锁时候给定一个窗口时间。

因此我们在获取和释放锁上有一个好的方式，在非分布式的单节点中总是没问题的，安全的。但是扩展到一个分布式系统中就没法保证了。

Redlock算法

我们假设有N个独立的masters节点，每个节点都是独立的不使用master-slave主从复制机制。我们已经描述了怎么在当个节点中安全的获取和释放锁，我们在不同的机器上跑5台独立的redis服务器，来确保挂了是由于不同的原因。

为了获取锁客户端在进行如下操作：

1.获取当前时间的微妙

2.使用相同的key name和随机值在所有的reids节点中试着获取锁。在第二步，当为每个节点设置锁时，客户端使用一个超时，这个时间是比较小的，它是所有的自动释放时间和这样做事为了获取它。例如，如果自动释放的时间是10s，超时时间可能在5-50s之间。这样避免client阻塞很长时间，尽力去尝试与redis node通信，如果一个node挂了，我们应该与下一个node通信ASAP。

3.client计算获取锁的时间，通过当前时间减去第一步的时间。只有当主的节点(至少3)可以获取锁时，总共用于获取锁的时间消耗比锁住的时间消耗小，那么这个锁是可获取的。

4.如果一个锁是可获取的那么它的合法时间初始化的时间减去时间消耗，正如第三步计算的那样。

5.如果一个client获取失败了，那么它将设置解锁所有的redis节点。(当然它也不行锁住N/2+1的节点， node的表现是不能被锁住的)。

算法处理是异步的？

算法的实现依赖于在processs之间没有异步锁，每个process的本地时间大致相同，当比自动释放锁的时间小时会有一个错误。这个假设非常想一个真实世界的计算机。每个计算机有一个本地时间并且我们可以根据不同的计算机有一个时间的偏移(它比较小)。

我们需要更好的互斥规则：事实证明只要client hold锁尽可能的长将会终止它的工作，减去一些时间（仅仅有几微妙用来补偿进程间的时间偏移）。

关于更多相似系统请求一个有范围的clock偏移，可以查询这个： Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.

失败重试

当一个client不能获取锁时，它将会在一个时间之后再次尝试，这样做的目的是为了打算多个clients在同时请求相同的资源(这可能会导致大脑分裂而没有一个人赢)。一个比较快的client将会尽可能的获取redis node的锁，因此client应该使用多路技术在同时向多个nodes发起SET命令。

值得强调的是clients请求锁失败后，会释放ASAP锁部分。因此这里不需要等待超时，锁可能会被再次请求(然而如果网络部分有问题并且client连接redis服务器处理问题，这里可能会等待超时)。

释放锁

释放锁是比较简单的并且设计释放所有redis节点的锁，无论如何事实上client相信能够成功地一个给定的redis节点上加锁。

安全参 数

算法是安全的？我们在多种环境下去思考。

我们假设client是可以获取锁的，所有的redis节点都会包含一个具有相同生存期的key。但是如果key是在不同的时间被设定了那么也会有不同的到期时间。

如果第一个key的时间设置错了，那么之后的也将会发生错误。

第一个key的超时时间至少被设置为MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT。其他的key将在之后超时。在这其间主要的key将会被设置，在这个设置其间，其他的client不能获取lock，

如果N/2+1已经存在了那么N/2+1 SET NX将不能被设置成功。

因此如果一个锁被获取了，那么它将不能在同时被别人获取。但是有些时候我们也会有多个client同时请求锁，可能会考虑合法的锁和解锁节点，因此，我们需要考虑，一个client能够锁住redis节点此时时间可能少于合法时间。这样对于 MIN_VALIDITY 命令没有client能够重新获取锁。

因此多个clients能够同时lock N/2+1个redis节点当锁住主节点的时间大于TTL时间使得这个锁不可用的时候。

如果你能对现在的算法发现bugs或者安全方面的问题，非常感谢。

存活期参数

系统的存活期是基于以下3点的：

1.当key超时自动被释放，并且能够再次被加锁。

2.当锁不课获取时client协助移除它，或者锁可以被获取但是工作结束了，我们不必等待超时来重新获取锁。

3.当client需要重新加锁时，它等待的时间应该比获取主锁的时间长。

然而我们在网络部分需要付出相当于TTL的时间，因此这里如果有持续的字段，这个时间是不确定的。这个发生在client每次获取一个lock，并且在移除锁之前

得到部分。

如果这里有不确定的网络延迟，那么系统可能变得不可服务在不确定的时间内。

性能 挂了回复 同步

在锁的请求和释放方面许多使用者把redis作为一个需要高性能的服务器在延迟方面也是如此,每秒可能会有大量锁的释放和请求.为了达到这个要求,策略是与多个redis node通信来减少延迟,这样做是比较复杂的.(或者使用poor’s man multiplexing， 它使用socket的非阻塞模式，发送所有命令后，之后读取所有的命令，在每个redis借点的RTT时间都是相同的。)

然而这里也会有数据持久性方面的考虑，如果我们想把它作为一个挂了回恢复的系统。我们假设我们没用配置redis的数据持久性。一个client会请求3到5个redis节点的锁。client能够获取锁的一个redis节点如果重启了，这个时候可能会有3个redis节点请求相同的资源锁，别的client可能也会再次获取锁，这样违背了就不是独占锁了，违背了安全属性。

如果能够AOF文件持久化，事情将会有所改进。例如，我们可以发送SHUTDOWN命令来更新服务器和重启它。因为redis的定时器是语义上实现的所以当服务器off的时候定时器也会消逝。如果正常关闭的话没什么问题。但是如果发生电源供应中断这些呢？如果redis使用了默认的配置，对于每秒执行的同步写入到磁盘，在我们重启后key可能会发生错误。事实上，如果我们想要证实在redis重启后锁安全，我们需要设置数据持久化。反过来，这个与相同级别的CP系统没法比，传统的实现了安全的分布式锁。在redis挂了重启后，RLL时间会变长由于需要将那些加锁的key重新变得的可利用和自动释放之前的锁。

使用 delayed restarts可能是安全的架构即使没有任何redis的数据持久化是可用的，然而这里也可能有一个问题。例如如果主的redis节点挂了，整个系统都将瘫痪。(globally 以为着在这个时间段内没有资源被锁住)

---