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