1.简介
在许多环境中不同进程必须以互斥方式使用共享资源进行操作时，分布式锁是非常有用的原语。
有许多库和博客文章描述了如何使用Redis实现DLM(分布式锁管理器)，但是每个库都使用不同的方法，而且许多库使用简单的方法，与使用稍微复杂一点的设计相比，安全性更低。
该页面试图提供一种更规范的算法来实现Redis的分布式锁。 我们提出了一种称为Redlock的算法，该算法实现了DLM，我们认为它比普通的单实例方法更安全。 我们希望社区能够对其进行分析，提供反馈，并将其用作实现或更复杂或替代设计的起点。
2. 安全和活性保证
我们将用三个属性来建模我们的设计，从我们的角度来看，这三个属性是有效使用分布式锁所需的最小保证。
- 安全特性：互斥。 在任何给定时刻，只有一个客户端可以持有锁。
- 活性属性A:无死锁。最终，总是可以获得一个锁，即使锁定资源的客户机崩溃或被分区。
- 活性特性B:容错。只要大多数Redis节点启动，客户端就能够获取和释放锁。
3.为什么基于故障转移的实现还不够
为了理解我们想要改进的地方，让我们分析一下大多数基于redis的分布式锁库的现状。
使用Redis锁定资源的最简单方法是在实例中创建key。 使用Redis过期功能，通常会在有限的生存时间内创建key，以便最终将其释放（我们列表中的属性2）。 当客户端需要释放资源时，它将删除key。
从表面上看，这工作得很好，但是有一个问题:这是我们架构中的一个单点故障。如果Redis master倒下了怎么办?那么，让我们添加一个slave!如果主服务器不可用，则使用它。不幸的是，这是不可行的。这样我们就不能实现互斥的安全特性，因为Redis复制是异步的。
该模型存在明显的竞态条件：
- 客户端A获得主服务器中的锁。
- 在将key写入传输到从机之前，主机崩溃。
- slave被提升为主服务器。
- 客户端B获取对相同资源A的锁定，而该资源A已经为其持有了锁定。 安全违规！
有时候，在特殊情况下（例如在故障期间），多个客户端可以同时持有锁是完全可以的。 在这种情况下，您可以使用基于复制的解决方案。 否则，我们建议实施本文档中描述的解决方案。
4.使用单个实例的正确实现
在尝试克服上述单实例设置的局限性之前，让我们检查一下在这种简单情况下如何正确执行此设置，因为这在不时存在竞争条件的应用程序中实际上是一种可行的解决方案，并且因为 单个实例是我们将用于此处描述的分布式算法的基础。
获取锁的方法如下：
SET resource_name my_random_value NX PX 30000
该命令仅在键不存在时才设置键(NX选项)，其过期时间为30000毫秒(PX选项)。键被设置为my_random_value值。该值在所有客户端和所有锁请求中必须是唯一的。基本上，使用random值是为了以一种安全的方式释放锁，其中有一个脚本告诉Redis:只有当键存在且存储在键中的值正是我所期望的值时，才删除该键。这是通过下面的Lua脚本完成的:
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else
return 0
end
为了避免删除由另一个客户端创建的锁，这一点非常重要。例如，客户端可能获取了该锁，在某些操作中被阻塞的时间超过了该锁的有效时间（键将过期的时间），然后又删除了某个其他客户端已经获取的锁。 仅使用DEL是不安全的，因为一个客户端可能会删除另一个客户端的锁。使用上述脚本时，每个锁都由一个随机字符串“签名”，因此仅当该锁仍是客户端尝试将其删除的设置时，该锁才会被删除。
这个随机字符串应该是什么？ 我假设它是来自/dev/urandom的20个字节，但是您可以找到更简单便捷的方法来使其足够独特以完成您的任务。 例如，一个安全的选择是使用/dev/urandom为RC4设置种子，并从中生成伪随机流。一个更简单的解决方案是结合使用unix时间和微秒级分辨率，并将其与客户端ID串联在一起，它不那么安全，但在大多数环境中可能可以完成任务。
我们当作键的存活时间锁使用的时间值，被称为“锁的有效时间值”。它既是自动释放锁的时间值，又是执行另一操作之前客户端可以再次获取锁而技术上不违反互斥保证的时间，该时间仅限于给定的时间范围 从获得锁的那一刻起的时间。
因此，现在我们有了获取和释放锁的好方法。 该系统基于由一个始终可用的单个实例组成的非分布式系统的推理是安全的。 让我们将概念扩展到我们没有此类保证的分布式系统。
5.Redlock算法
在分布式版本的算法中，我们假设有N个Redis master。这些节点是完全独立的，因此我们不使用复制或任何其他隐式协调系统。我们已经描述了如何在单个实例中安全地获取和释放锁。我们认为该算法将使用此方法在单个实例中获取和释放锁，这是理所当然的。在我们的示例中，我们将N = 5设置为一个合理的值，因此我们需要在不同的计算机或虚拟机上运行5个Redis主服务器，以确保它们以独立的方式发生故障。
为了获取锁，客户端执行以下操作：
- 它获取当前时间(以毫秒为单位)。
- 它尝试在所有N个实例中顺序获取锁，在所有实例中使用相同的键名和随机值。在步骤2中，当在每个实例中设置锁时，客户端使用一个超时，这个超时与自动释放锁的总时间相比很小，以便获取锁。例如，如果自动释放时间为10秒，则超时时间可能在5到50毫秒之间。 这样可以防止客户端长时间与处于故障状态的Redis节点进行通信：如果某个实例不可用，我们应该尝试与下一个实例尽快进行通信。
- 客户端通过从当前时间中减去在步骤1中获得的时间戳，来计算获取锁所需的时间。当且仅当客户端能够在大多数实例（至少3个）中获取锁，并且获取锁所花费的总时间少于锁有效时间时，才视为已获取锁。
- 如果获取了锁，则将其有效时间视为初始有效时间减去经过的时间，如步骤3中所计算。
- 如果客户端由于某种原因（无法锁定N / 2 + 1个实例或有效时间为负）而未能获得该锁，它将尝试解锁所有实例（即使是它认为无法锁定的实例）。
6.算法是异步的吗？
该算法基于这样的假设：尽管各进程之间没有同步时钟，但每个进程中的本地时间仍以近似相同的速率流动，并且与锁的自动释放时间相比，误差较小。这个假设与现实世界的计算机非常相似:每台计算机都有一个本地时钟，我们通常可以依靠不同的计算机来获得一个很小的时钟漂移。
在这一点上，我们需要更好地指定我们的互斥规则：只有在拥有锁的客户端将在锁有效时间内（如步骤3中获得的）减去一段时间（仅几毫秒）的情况下终止工作，才能保证 以补偿进程之间的时钟漂移）。
7.失败重试
当一个客户端无法获得锁时，它应该在一个随机延迟之后再次尝试，以便尝试去同步多个客户端试图在同一时间获取同一资源的锁(这可能会导致没有人获胜的分裂大脑状态)。同样，客户端在大多数Redis实例中尝试获取锁定的速度越快，出现裂脑情况（以及需要重试）的窗口就越小，因此理想情况下，客户端应尝试将SET命令发送到N个实例 同时使用多路复用。
值得强调的是，对于未能获取大多数锁的客户端，尽快释放（部分）获取的锁有多么重要，这样就不必等待key期满才能再次获取锁（ 但是，如果发生了网络分区，并且客户端不再能够与Redis实例进行通信，则在等待key到期时需要支付可用性损失）。
8.释放锁
释放锁很简单，只需在所有实例中释放锁，无论客户端是否认为它能够成功锁定给定的实例。
9.安全论点
该算法安全吗？ 我们可以尝试了解在不同情况下会发生什么。
首先，假设客户端在大多数情况下都能获得锁。所有实例都将包含一个具有相同生存时间的key。**但是，key是在不同的时间设置的，所以key也将在不同的时间过期。**但是，如果第一个key在时间T1（在与第一台服务器联系之前进行采样的时间）设置为最差，而最后一个key在时间T2（从最后一台服务器获得答复的时间）设置为最坏的话， 该集合中第一个到期的key至少存在MIN_VALIDITY = TTL-（T2-T1）-CLOCK_DRIFT。 所有其他键都将在稍后过期，因此我们确信这些键至少在这次将同时被设置。
在设置大多数键的过程中，另一个客户端将无法获取锁，因为如果已经存在N / 2 + 1个键，则N / 2 + 1 SET NX操作将无法成功。因此，如果获得了锁，就不可能同时重新获得它(违反互斥特性)。
但是，我们也要确保多个试图同时获取锁的客户端不能同时成功。
如果一个客户端锁定大多数实例使用最近定一个时间，或更大定时间值，然后，锁将获得最大定有效时间（基本上是我们设置的TTL），这将认为锁是无效的，并释放掉实例上获得的锁，所以，我们仅需要考虑客户端使用一个小于有效时间锁定大多数实例的情况。 在这种情况下，对于上面已经说明的参数，对于MIN_VALIDITY，没有客户端应该能够重新获取该锁。因此，只有当大多数锁定时间大于TTL时间时，多个客户端才能同时锁定N / 2 + 1个实例（“时间”为步骤2的结尾），从而使锁定无效。
10.活性参数
系统活性基于三个主要特征：
- 锁的自动释放(因为key过期):最终，key可以再次被锁定。
- 事实是，客户端通常会在锁未被获取或锁已被获取且工作终止时协作删除锁，这使得我们不必等待key过期才能重新获取锁。
- 事实是，当客户端需要重试一个锁时，它等待的时间要比获取大多数锁所需的时间要长，以便在资源争用期间不太可能出现分裂大脑的情况。
但是，我们在网络分区上付出的可用性代价等于TTL时间，因此如果存在连续分区，我们可以无限期地付出这个代价。每次客户端获得锁并在能够删除锁之前被分区时都会发生这种情况。
基本上，如果有无限个连续的网络分区，系统可能在无限长的时间内不可用。
11.性能，崩溃恢复和fsync
使用Redis作为锁定服务器的许多用户在获取和释放锁的延迟以及每秒可能执行的获取/释放操作数方面都需要高性能。为了满足此要求，与N个Redis服务器进行通信以减少延迟的策略肯定是多路复用（或穷人的多路复用，即将套接字置于非阻塞模式，发送所有命令，并读取所有命令） 之后，假设客户端和每个实例之间的RTT相似）。
然而，如果我们想要以崩溃恢复系统模型为目标，还需要考虑持久性。
基本上要看到这里的问题，让我们假设我们配置的Redis根本没有持久性。 客户端在5个实例中的3个实例中获取了锁。 客户端能够获取锁的一个实例被重新启动，此时，我们又可以为同一资源锁定3个实例，而另一个客户端可以再次锁定它，这违反了锁的排他性的安全性。
如果启用AOF持久性，则情况将会大大改善。 例如，我们可以通过发送SHUTDOWN并重新启动它来升级服务器。因为Redis expires是语义实现的，所以当服务器关闭时，实际上时间仍然在流逝，所以我们所有的需求都是好的。但是，只要正常关闭，一切都很好。 停电呢？如果将Redis默认配置为每秒在磁盘上进行fsync，则重启后可能会丢失我们的key。从理论上讲，如果我们想要在任何类型的实例重新启动时保证锁的安全性，我们需要在持久性设置中启用fsync=always。这反过来又会完全破坏传统上用于以安全方式实现分布式锁的相同级别的CP系统的性能。然而，事情比第一眼看上去要好。 基本算法安全是保留,只要当一个实例在崩溃之后重新启动时,它不再参与任何当前活动锁,所以当前活动的集合锁重新启动实例时,都是通过锁定实例以外的一个重新加入系统。为了保证这一点，我们只需要使一个实例在崩溃后至少不可用超过我们使用的最大TTL（即实例崩溃时存在的所有锁的所有键）所需的时间即可。 无效并自动释放。
使用延迟重启基本上可以实现安全性，即使没有任何可用的Redis持久性，但是请注意，这可能会导致可用性损失。例如，如果大多数实例崩溃，TTL系统将变得全局不可用(这里全局意味着在这段时间内没有任何资源是可锁定的)。
12.使算法更可靠：扩展锁
如果客户端执行的工作由小的步骤组成，则默认情况下可以使用较小的锁有效时间，并扩展实现锁扩展机制的算法。基本上，如果在计算的中间，而锁的有效性接近较低的值，则客户端可以通过向所有扩展键的TTL的实例发送Lua脚本来扩展锁，如果该键存在并且其值仍然是 获取锁时客户端分配的随机值。 The client should only consider the lock re-acquired if it was able to extend the lock into the majority of instances, and within the validity time 客户端应仅考虑重新获取锁如果它能够有效时间内容，在大多数实例上扩展锁（基本上，所使用的算法与获取锁时所使用的算法非常相似）。
但是，这并没有从技术上改变算法，因此应该限制锁重获尝试的最大次数，否则将违反活性属性之一。