使用Redis实现分布式锁

使用Redis的分布式锁模式

分布式锁在许多环境中是非常有用的原语，在这些环境中，不同的进程必须以互斥的方式操作共享资源。

有许多库和博客文章描述了如何使用Redis实现DLM（分布式锁管理器），但每个库都使用不同的方法，许多库使用的方法比较简单，与稍微复杂一些的设计相比，提供的保证较低。

本页描述了一种更规范的算法，用于使用Redis实现分布式锁。我们提出了一种名为Redlock的算法，它实现了一个我们认为比普通的单实例方法更安全的DLM。我们希望社区能够分析它，提供反馈，并将其作为实现或更复杂或替代设计的起点。

实现

在描述算法之前，这里有一些已经可用的实现链接，可以用作参考。

安全性和活性保证

我们将用仅三个属性来建模我们的设计，从我们的角度来看，这些是有效使用分布式锁所需的最低保证。

  1. 安全属性：互斥性。在任何给定时刻，只有一个客户端可以持有锁。
  2. 活性属性 A：无死锁。即使锁定资源的客户端崩溃或被分区，最终总是可以获取锁。
  3. 活性属性 B：容错性。只要大多数 Redis 节点正常运行，客户端就能够获取和释放锁。

为什么基于故障转移的实现还不够

为了理解我们想要改进的内容，让我们分析一下大多数基于Redis的分布式锁库的现状。

使用Redis锁定资源的最简单方法是在实例中创建一个键。该键通常使用Redis的过期功能创建，具有有限的生存时间，以便最终它会被释放（我们列表中的属性2）。当客户端需要释放资源时，它会删除该键。

表面上这工作得很好，但有一个问题：这是我们架构中的一个单点故障。如果Redis主服务器宕机了会发生什么？ 好吧，让我们添加一个副本！并在主服务器不可用时使用它。不幸的是，这是不可行的。这样做我们无法实现互斥的安全属性，因为Redis复制是异步的。

这个模型存在一个竞态条件：

  1. 客户端A在主节点获取锁。
  2. 主节点在将键的写入传输到副本之前崩溃。
  3. 副本被提升为主节点。
  4. 客户端B获取了资源A的锁，而资源A已经被另一个客户端持有锁。安全违规！

在某些特殊情况下，例如在故障期间，多个客户端可以同时持有锁，这是完全可以接受的。 如果是这种情况，您可以使用基于复制的解决方案。否则，我们建议实施本文档中描述的解决方案。

正确实现单例模式

在尝试克服上述单实例设置的局限性之前，让我们先检查一下如何在这个简单的情况下正确执行，因为这实际上是在某些应用中可行的解决方案，其中偶尔的竞争条件是可以接受的，而且锁定到单个实例是我们将用于此处描述的分布式算法的基础。

要获取锁，可以按照以下方式进行：

    SET resource_name my_random_value NX PX 30000

该命令仅在键不存在时设置键（NX 选项），并设置过期时间为30000毫秒（PX 选项）。 键被设置为值“my_random_value”。该值在所有客户端和所有锁定请求中必须是唯一的。

基本上，随机值用于以安全的方式释放锁，通过一个脚本告诉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连接起来。虽然这不如前者安全，但对于大多数环境来说可能已经足够。

"锁的有效时间"是我们用作键的生存时间的时间。它既是自动释放时间，也是客户端在另一个客户端可能再次获取锁之前执行所需操作的时间，而不会在技术上违反互斥保证，该保证仅限制在从获取锁的那一刻起的给定时间窗口内。

所以现在我们有了一个很好的方法来获取和释放锁。有了这个系统，对于一个由单个、始终可用的实例组成的非分布式系统进行推理是安全的。让我们将这个概念扩展到分布式系统，在那里我们没有这样的保证。

红锁算法

在算法的分布式版本中，我们假设有N个Redis主节点。这些节点是完全独立的，因此我们不使用复制或任何其他隐式协调系统。我们已经描述了如何在单个实例中安全地获取和释放锁。我们理所当然地认为算法将使用这种方法在单个实例中获取和释放锁。在我们的示例中，我们设置N=5，这是一个合理的值，因此我们需要在不同的计算机或虚拟机上运行5个Redis主节点，以确保它们以基本独立的方式失败。

为了获取锁，客户端执行以下操作：

  1. 它获取当前时间的毫秒数。
  2. 它尝试在所有N个实例中依次获取锁，使用相同的键名和随机值。在步骤2中，当在每个实例中设置锁时，客户端使用一个相对于锁自动释放总时间较短的超时时间来获取锁。例如，如果自动释放时间为10秒，超时时间可能在~5-50毫秒范围内。这可以防止客户端在尝试与一个已下线的Redis节点通信时长时间阻塞：如果一个实例不可用，我们应该尽快尝试与下一个实例通信。
  3. 客户端通过从当前时间减去步骤1中获得的时间戳来计算获取锁所花费的时间。当且仅当客户端能够在大多数实例（至少3个）中获取锁，并且获取锁所花费的总时间小于锁的有效时间时，锁才被认为是被成功获取的。
  4. 如果锁被获取，其有效时间被认为是初始有效时间减去经过的时间，如步骤3中所计算。
  5. 如果客户端由于某种原因未能获取锁（无论是无法锁定N/2+1个实例还是有效时间为负），它将尝试解锁所有实例（即使是它认为无法锁定的实例）。

算法是异步的吗？

该算法依赖于一个假设，即尽管进程之间没有同步的时钟，但每个进程中的本地时间以大致相同的速率更新，与锁的自动释放时间相比，误差较小。这个假设非常类似于现实世界中的计算机：每台计算机都有一个本地时钟，我们通常可以依赖不同计算机之间的时钟漂移较小。

此时，我们需要更好地指定我们的互斥规则：只有在持有锁的客户端在锁的有效时间内（如步骤3中所获得的）完成其工作的情况下，才能保证互斥，减去一些时间（仅几毫秒以补偿进程之间的时钟漂移）。

本文包含更多关于需要绑定时钟漂移的类似系统的信息：Leases: an efficient fault-tolerant mechanism for distributed file cache consistency。

失败时重试

当客户端无法获取锁时，它应该在随机延迟后再次尝试，以尝试使多个客户端在同一时间尝试获取同一资源的锁时不同步（这可能导致分裂脑情况，即没有人获胜）。此外，客户端尝试在大多数Redis实例中获取锁的速度越快，分裂脑情况的窗口（以及重试的需要）就越小，因此理想情况下，客户端应尝试使用多路复用同时向N个实例发送SET命令。

值得强调的是，对于未能获取大多数锁的客户端来说，尽快释放（部分）已获取的锁是非常重要的，这样就不需要等待键过期才能再次获取锁（然而，如果发生网络分区并且客户端不再能够与Redis实例通信，那么在等待键过期时会有可用性损失）。

释放锁

释放锁很简单，无论客户端是否认为它能够成功锁定给定的实例，都可以执行。

安全参数

算法安全吗？让我们看看在不同情况下会发生什么。

首先，我们假设客户端能够在大多数实例中获取锁。所有实例都将包含一个具有相同生存时间的键。然而，键是在不同时间设置的，因此键也会在不同时间过期。但是，如果第一个键在最坏的情况下是在时间T1（我们在联系第一个服务器之前采样的时间）设置的，而最后一个键在最坏的情况下是在时间T2（我们从最后一个服务器获得回复的时间）设置的，我们可以确定集合中第一个过期的键将至少存在MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT。所有其他键将在稍后过期，因此我们可以确定这些键将至少在这段时间内同时设置。

在大多数键被设置的时间内，另一个客户端将无法获取锁，因为如果N/2+1个键已经存在，N/2+1个SET NX操作将无法成功。因此，如果已经获取了锁，就不可能同时重新获取它（违反了互斥属性）。

然而，我们还想确保多个客户端同时尝试获取锁时不能同时成功。

如果客户端使用接近或超过锁定最大有效时间（我们基本上用于SET的TTL）的时间锁定了大多数实例，它将认为锁定无效并解锁实例，因此我们只需要考虑客户端能够在小于有效时间的时间内锁定大多数实例的情况。在这种情况下，对于上述已经表达的论点，对于MIN_VALIDITY，任何客户端都不应该能够重新获取锁定。因此，只有当锁定大多数实例的时间大于TTL时间时，多个客户端才能同时锁定N/2+1个实例（“时间”为步骤2的结束），从而使锁定无效。

活跃性论证

系统的活跃性基于三个主要特性：

  1. 锁的自动释放（由于键过期）：最终键再次可用以被锁定。
  2. 通常情况下，客户端会在未获得锁时或获得锁并完成工作后合作移除锁，这使得我们很可能不需要等待键过期就可以重新获得锁。
  3. 当客户端需要重试锁时，它会等待一个相对较长的时间，这个时间比获取大多数锁所需的时间要长，以便在资源争用期间概率性地减少脑裂条件的发生。

然而，我们在网络分区上付出了等于TTL时间的可用性代价，因此如果存在连续的分区，我们可能会无限期地付出这个代价。 这种情况每次发生在客户端获取锁并在能够移除锁之前被分区隔离时。

基本上，如果有无限连续的网络分区，系统可能会在无限长的时间内不可用。

性能、崩溃恢复和fsync

许多使用Redis作为锁服务器的用户需要在获取和释放锁的延迟以及每秒可以执行的获取/释放操作数量方面具有高性能。为了满足这一要求，与N个Redis服务器通信以减少延迟的策略肯定是多路复用（将套接字置于非阻塞模式，发送所有命令，稍后读取所有命令，假设客户端与每个实例之间的RTT相似）。

然而，如果我们想要针对崩溃恢复系统模型，还需要考虑持久性的问题。

基本上，为了看到这里的问题，让我们假设我们配置的Redis完全没有持久性。一个客户端在5个实例中的3个实例中获取了锁。客户端能够获取锁的其中一个实例被重启，此时又有3个实例可以为同一资源加锁，另一个客户端可以再次加锁，违反了锁的独占性安全属性。

如果我们启用AOF持久化，情况会有所改善。例如，我们可以通过发送SHUTDOWN命令并重新启动来升级服务器。因为Redis的过期时间在语义上是实现的，所以即使服务器关闭，时间仍然会流逝，我们的所有需求都得到了满足。 然而，只要它是干净的关闭，一切都很好。那么停电呢？如果Redis配置为默认情况下每秒将数据同步到磁盘，那么在重新启动后，我们的键可能会丢失。理论上，如果我们想要在任何类型的实例重启情况下保证锁的安全性，我们需要在持久化设置中启用fsync=always。这将由于额外的同步开销而影响性能。

然而，情况比乍一看要好。基本上，只要一个实例在崩溃后重新启动时不再参与任何当前活动的锁，算法的安全性就得以保留。这意味着当实例重新启动时，所有当前活动的锁都是由锁定实例获得的，而不是重新加入系统的那个实例。

为了保证这一点，我们只需要在崩溃后使实例不可用，时间稍微超过我们使用的最大TTL。这是实例崩溃时存在的所有锁的键失效并自动释放所需的时间。

使用延迟重启基本上可以在没有任何Redis持久化的情况下实现安全性，但请注意，这可能会转化为可用性损失。例如，如果大多数实例崩溃，系统将在TTL期间全局不可用（这里的全局意味着在此期间没有任何资源可以被锁定）。

使算法更可靠：扩展锁

如果客户端执行的工作由小步骤组成，可以默认使用较短的锁有效期，并通过实现锁扩展机制来扩展算法。基本上，如果客户端在计算过程中锁的有效期接近较低值，可以通过向所有实例发送Lua脚本来扩展锁，如果键存在且其值仍然是客户端获取锁时分配的随机值，则延长键的TTL。

客户端只有在能够将锁扩展到大多数实例中，并且在有效时间内（基本上使用的算法与获取锁时使用的算法非常相似）时，才应认为锁已重新获取。

然而，这从技术上讲并没有改变算法，因此应该限制锁重新获取尝试的最大次数，否则会违反其中一个活性属性。

关于一致性的免责声明

请仔细考虑彻底审查本页末尾的Redlock分析部分。 Martin Kleppman的文章和antirez的回应非常相关。 如果您关心一致性和正确性，您应该注意以下主题：

  1. 你应该实现防护令牌。 这对于可能需要大量时间的进程尤其重要，并且适用于任何分布式锁定系统。 延长锁的生命周期也是一种选择，但不要假设只要获取锁的进程存活，锁就会一直保持。
  2. Redis 没有使用单调时钟来实现 TTL 过期机制。 这意味着，如果系统时间发生偏移，可能会导致多个进程获取到同一个锁。 尽管可以通过禁止管理员手动设置服务器时间并正确配置 NTP 来缓解这个问题，但在实际应用中，仍然有可能发生这种情况，从而影响一致性。

想要帮忙吗？

如果你对分布式系统感兴趣，你的意见/分析将非常有价值。此外，其他语言的参考实现也会很有帮助。

提前感谢！

Redlock分析

  1. Martin Kleppmann 在这里分析了Redlock。对此分析的反驳可以在这里找到。
RATE THIS PAGE
Back to top ↑