分布式锁是一个在很多环境中非常有用的原语，它是不同进程互斥操作共享资源的唯一方法。有很多的开发库和博客描述如何使用Redis实现DLM（Distributed Lock Manager），但是每个开发库使用不同的方式，而且相比更复杂的设计与实现，很多库使用一些简单低可靠的方式来实现。
这篇文章尝试提供更标准的算法来使用Redis实现分布式锁。我们提出一种算法，叫做Relock，它实现了我们认为比vanilla单一实例方式更安全的DLM（分布式锁管理）。我们希望社区分析它并提供反馈，以做为更加复杂或替代设计的一个实现。
实现
在说具体算法之前，下面有一些具体的实现可供参考.
- Redlock-rb (Ruby实现).
- Redlock-php (PHP 实现).
- Redsync.go (Go 实现).
- Redisson (Java 实现).
安全和活跃性保证
从有效分布式锁的最小保证粒度来说，我们的模型里面只用了3个属性，具体如下：
1. 属性安全: 互斥行.在任何时候，只有一个客户端可以获得锁.
2. 活跃属性A: 死锁自由. 即使一个客户端已经拥用了已损坏或已被分割资源的锁，但它也有可能请求其他的锁.
3. 活跃属性B:容错. 只要大部分Redis节点可用, 客户端就可以获得和释放锁.
为何基于容错的实现还不够
要理解我们所做的改进，就要先分析下当前基于Redis的分布式锁的做法。
使用Redis锁住资源的最简单的方法是创建一对key-value值。利用Redis的超时机制，key被创建为有一定的生存期，因此它最终会被释放。而当客户端想要释放时，直接删除key就行了。
一般来说这工作得很好，但有个问题: 这是系统的一个单点。如果Redis主节点挂了呢？当然，我们可以加个子节点，主节点出问题时可以切换过来。不过很可惜，这种方案不可行，因为Redis的主-从复制是异步的，我们无法用其实现互斥的安全特性。
这明显是该模型的一种竞态条件：
- 客户端A在主节点获得了一个锁。
- 主节点挂了，而到从节点的写同步还没完成。
- 从节点被提升为主节点。
- 客户端B获得和A相同的锁。注意，锁安全性被破坏了！
有时候，在某些情况下这反而工作得很好，例如在出错时，多个客户端可以获得同一个锁。如果这正好是你想要的，那就可以使用主-从复制的方案。否则，我们建议使用这篇文章中描述的方法。
单实例的正确实现方案
在尝试解决上文描述的单实例方案的缺陷之前，先让我们确保针对这种简单的情况，怎么做才是无误的，因为这种方案对某些程序而言也是可以接受的，而且这也是我们即将描述的分布式方案的基础。
为了获取锁，方法是这样的：
复制代码 代码如下:
SET resource_name my_random_value NX PX 30000
这条指令将设置key的值，仅当其不存在时生效(NX选项), 且设置其生存期为30000毫秒(PX选项)。和key关联的value值是"my_random_value"。这个值在所有客户端和所有加锁请求中是必须是唯一的。
使用随机值主要是为了能够安全地释放锁，这要同时结合这么个处理逻辑：删除key值当且仅当其已存在并且其value值是我们所期待的。看看以下lua代码：
复制代码 代码如下:
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else
return 0
end
这么做很重要，可以避免误删其他客户端创建的锁。例如某个客户端获得了一个锁，但它的处理时长超过了锁的有效时长，之后它删除了这个锁，而此时这个锁可能又被其他客户端给获得了。仅仅做删除是不够安全的，很可能会把其他客户端的锁给删了。结合上面的代码，每个锁都有个唯一的随机值，因此仅当这个值依旧是客户端所设置的值时，才会去删除它。
那么应该怎样生成这个随机值呢？我们使用的是从/dev/urandom读取的20个字节，但你也可以找个更简单的方法，只要能满足任务就行。例如，可以使用/dev/urandom初始化RC4算法，然后用其产生随机数流。更简单的方法是组合unix时间戳和客户端ID, 这并不安全，但对很多环境而言也够用了。
我们所说的key的时间，是指”锁的有效时长“. 它代表两种情况，一种是指锁的自动释放时长，另一种是指在另一个客户端获取锁之前某个客户端占用这个锁的时长，这被限制在从锁获取后开始的一段时间窗口内。
现在我们已经有好的办法获取和释放锁了。在单实例非分布式系统中，只要保证节点没挂掉，这个方法就是安全的。那么让我们把这个概念扩展到分布式的系统中吧，那里可没有这种保证。
Redlock 算法
在此算法的分布式版本中，我们假设有N个Redis主节点。这些节点是相互独立的，因此我们不使用复制或其他隐式同步机制。我们已经描述过在单实例情况下如何安全地获取锁。我们也指出此算法将使用这种方法从单实例获取和释放锁。在以下示例中，我们设置N=5（这是个比较适中的值），这样我们需要在不同物理机或虚拟机上运行5个Redis主节点，以确保它们的出错是尽可能独立的。
为了获取锁，客户端执行以下操作：
- 获取当前时间，以毫秒为单位。
- 以串行的方式尝试从所有的N个实例中获取锁，使用的是相同的key值和相同的随机value值。在从每个实例获取锁时，客户端会设置一个连接超时，其时长相比锁的自动释放时间要短得多。例如，若锁的自动释放时间是10秒，那么连接超时大概设在5到50毫秒之间。这可以避免当Redis节点挂掉时，会长时间堵住客户端：如果某个节点没及时响应，就应该尽快转到下个节点。
- 客户端计算获取所有锁耗费的时长，方法是使用当前时间减去步骤1中的时间戳。当且仅当客户端能从多数节点（至少3个）中获得锁，并且耗费的时长小于锁的有效期时，可认为锁已经获得了。
- 如果锁获得了，它的最终有效时长将重新计算为其原时长减去步骤3中获取锁耗费的时长。
- 如果锁获取失败了（要么是没有锁住N/2+1个节点，要么是锁的最终有效时长为负数），客户端会对所有实例进行解锁操作（即使对那些没有加锁成功的实例也一样）。
算法是异步的"TTL"时间的可用性代价，如果网络持续割裂，我们就得无限的付出这个代价。这发生于当客户端获取了一个锁，而在删除锁之前网络断开了。
基本上，如果网络无限期地持续割裂，那系统将无限期地不可用。
性能、故障恢复和文件同步
许多用户使用Redis作为一个需要高性能的加锁服务器，可以根据延迟动态的获取和释放锁，每秒可以成功执行大量的获取/释放锁操作。为了满足这些需求，一种多路复用策略是协同N台 Redis服务器减少延迟（或者叫做穷人的互助，也就是说，将端口置为non-blocking模式，发送所有的命令，延迟读出所有的命令，假定客户端和每个Redis实例的往返时间是相似的）。
然而，如果我们旨在实现一种故障系统的恢复模式，这里有另一种与持久性相关的思路。
考虑这个基本问题，假定我们完全没有配置Redis的持久性。一个客户端需要锁定5个实例中的3个。其中一个允许客户端获取的锁重新启动，虽然我们可以再次为一些资源锁定3个实例，但其它的客户端同样可以锁定它，违反了排他锁安全性。
如果我们启用AOF持久性，情况就会得到相当的改善。例如我们可以通过发送 SHUTDOWN升级一个服务器并且重启它。因为Redis的期限是通过语义设置的，所以服务器关闭的情况下虚拟时间仍然会流逝，我们所有的需求都得到了满足。不管怎样所有事务都会正常运转只要服务器完全关闭。如果电源中断会怎样？如果Redis进行了相关配置，默认情况下每秒文件都会同步写入磁盘，很有可能在重启后我们的数据会丢失。理论上，如果我们想在任何一种实例重启后保证锁的安全性，我们需要确保在持久性配置中设置fsync=always。这将会在同等级别的CP系统上损失性能，传统上这种方式用来更安全的分配锁。
不管怎样事情比我们初次瞥见他们看起来好些。基本上算法的安全性得到保留，就算是当一个实例在故障后重启，它也将不再参与任何当前活跃的锁的分配。因此当实例重启时，当前所有活动锁的设置将从锁定的实例中获取除它重新加入系统。
为了保证这一点，我们只需要做一个实例，在超过最大TTL后，崩溃，不可用，那么就需要时间去获取所有存在着的锁的钥匙，当实例崩溃时，其就会变得无效，会被自动释放。
使用延时重启可以基本上实现安全，甚至不需要利用任何Redis的持久化特性，但是这存在着另外的副作用。举例来说，如果大量的实例崩溃，系统变得全局不可用，那么TTL（这里的全局意味着根本就没有资源可用，在这个时间内所有的资源都会被锁定）。
让算法更可靠: 扩展锁
如果客户工作的执行是由小步骤组成，那么它就可以在默认时间里默认使用更小的锁，并扩展了算法去实现的一个锁的扩展机制。当锁的有效性接近于一个低值，那么通常是客户端在运算中处于居中位置。当锁被取得时，可能扩展的锁通过发送一个Lua脚本到所有的实例，这个实例是扩展TTL的钥匙，如果钥匙存在，那么它的值就是客户端复制的随机值。
客户端应该仅考虑锁的重新取得，如果它可以被扩展，锁就会在有效时间内进入大量实例（基本的算法使用非常类似于获取锁的使用）。
虽然这不是从技术上去改变算法，但是无论如何尝试获取锁的最大次数是需要限制的，否则的话会违反活跃性中的一个属性。