Redis红锁

在算法的分布式版本中，我们假设我们有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：分布式文件缓存一致性的高效容错机制。

失败时重试

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

值得强调的是，对于未能获取大多数锁的客户端来说，尽快释放（部分）获取的锁是多么重要，这样就不需要等待密钥到期才能再次获取锁（但是，如果发生网络分区并且客户端不再能够与 Redis 实例通信， 在等待密钥过期时需要支付可用性罚款）。

释放锁

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

安全论据

算法安全吗？让我们来看看在不同场景中会发生什么。

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

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

但是，我们还希望确保尝试同时获取锁的多个客户端无法同时成功。

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

活泼性参数

系统活动性基于三个主要功能：

1. 自动释放锁（因为钥匙过期）：最终钥匙再次可供锁定。
2. 事实上，通常，当未获取锁或获取锁并终止工作时，客户端将合作移除锁，因此我们可能不必等待密钥过期即可重新获取锁。
3. 事实上，当客户端需要重试锁时，它等待的时间比获取大多数锁所需的时间要长得多，以便从概率上使资源争用期间的裂脑条件变得不太可能。

但是，我们支付的可用性损失等于网络分区上的TTL时间，因此，如果有连续分区，我们可以无限期地支付此罚款。每次客户端获取锁并在能够删除锁之前进行分区时，都会发生这种情况。

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

性能、崩溃恢复和同步

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

但是，如果我们想以崩溃恢复系统模型为目标，则关于持久性还有另一个考虑因素。

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

如果我们启用AOF持久性，事情将会有所改善。例如，我们可以通过向服务器发送 SHUTDOWN 命令并重新启动它来升级服务器。由于 Redis 过期在语义上是实现的，因此当服务器关闭时，时间仍然会过去，因此我们所有的要求都很好。但是，只要它是干净关闭，一切都很好。停电怎么办？如果 Redis 配置为（默认情况下）每秒在磁盘上同步一次，则重新启动后，我们的密钥可能会丢失。从理论上讲，如果我们想在面对任何类型的实例重启时保证锁定安全，我们需要在持久性设置中启用。由于额外的同步开销，这将影响性能。fsync=always

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

为了保证这一点，我们只需要在崩溃后使一个实例不可用，至少比我们使用的最大TTL多一点。这是实例崩溃时存在的有关锁的所有密钥变得无效并自动释放所需的时间。

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

使算法更可靠：扩展锁

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

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

但是，这在技术上不会更改算法，因此应限制锁定重新获取尝试的最大次数，否则会违反其中一个活动属性。