前言
在分布式架构中因为节点之间存在共享资源的竞争，所以在并发的情况下会带来的数据不一致的问题，而分布式锁则成为了一种解决方案。分布式锁的实现一般分为四种:
- 基于数据库实现
- 基于Zookeeper实现
- 基于Etc实现
- 基于Redis实现
不同的实现各有优劣，具体采用哪种还得结合项目实际情况。
下面的文章内容是Redis作者提出的关于采用Redis实现分布式锁RedLock的算法讲解，受限于个人理解和翻译水平，译文与原文可能存在些许出入，请海纳！
阅读原文(Distributed locks with Redis)始终是最好的选择。
译文内容
在许多不同进程必须相互独占地操作共享的资源的环境中，分布式锁是一种非常有用的艺术。
有很多库和博客讲述了如何使用Redis实现DLM（分布式锁管理器），但每个库使用了不同的方式，与使用稍微复杂一点的设计实现相比，很多库使用了一个更低保障的简单方式实现。
这篇文章尝试提供一种更经典的算法来使用Redis实现分布式锁。我们建议用来实现DLM的算法称之为Redlock，我们相信它相比毫无特色的单例方案更加安全。我们希望社区能够分析它，提供反馈，并且将其视为实现Redis分布式锁或者更复杂或者可替代设计的一个起点。
实现
在讲述Redlock算法前，这里有一些已经可以使用的实现链接用于资料参考：
- Redlock-rb (Ruby) 同样有一个Redlock-rb的fork添加了gem管理用于简单发布或者更多
- Redlock-py (Python)
- Aioredlock (Asyncio Python)
- Redlock-php (PHP)
- PHPRedisMutex (PHP)
- cheprasov/php-redis-lock (PHP)
- Redsync (Go)
- Redisson (Java)
- Redis::DistLock (Perl)
- Redlock-cpp (C++)
- Redlock-cs (C#/.NET)
- RedLock.net (C#/.NET)
- ScarletLock (C# .NET)
- Redlock4Net (C# .NET)
- node-redlock (NodeJS)
安全性和存活保障
我们将我们的设计模型化为三点性质，这三点性质从我们的视角看，是高效地使用分布式锁的最低保障：
- 安全性：互斥锁。在给定的任何时刻，只有一个客户端可以持有该锁。
- 存活性A：避免死锁。最终总是可能获取到锁，即使持有锁的客户端crash了或者被分离了。
- 存活性B：容错性。只要Redis的大多数节点在运行，客户端就能够获得和释放锁。
为什么基于故障转移的实现是不够的
为了理解我们想要改善的地方，让我们分析一下当前大多数基于Redis的分布式锁的现状。
使用Redis给一个资源上锁的最简单的方法是在一个实例中创建一个key。通过Redis的expire功能，这个key通常伴随着有效期被创建，所以最终它将会被释放(在我们列表中的性质2)。当客户端需要释放资源的时候，直接删除该key。
从表面上看，这运行正常，但是有一个问题：在我们的架构中这是一个单点故障。如果主redis停机了会发生什么？让我们添加一个从redis，当主redis不可用的时候使用它，不幸的是这是不可用的，这样做我们不能实现互斥锁的安全性，因为redis的复制是异步的。
在这种模式下有一个明显的竞争条件：
- 客户端A在主redis中获得锁
- 在key被传送到从redis前，主redis crash了
- 从redis晋升为主redis
- 客户端B获得相同资源的锁，但是该锁早已被客户端A持有了。安全性问题
多个客户端可以同时持有锁有时在特殊条件下是非常好的，比如故障期间。如果是这种情况，你可以使用基于复制的解决方案。否则我们建议实现我们在这篇文档里讲述的方案。
单实例的正确实现
在试图克服上面讲述的单实例的局限性之前，让我们先检查一下在这种简单情况下如何正确完成它，因为这对于可接受偶尔的竞争条件的应用来说这实际上在是一个可实施的方案，也是因为单实例中的锁是我们这里讲述的分布式算法的基础。
为了获得锁，需要做的如下：
SET resource_name my_random_value NX PX 30000
这个命令只有当key不存在的时候才会设置（NX选项），并且过期时间为30000毫秒（PX选项），设置key的值为"my_random_value"，这个值在所有客户端和所有的锁请求中必须是唯一的。随机的值是为了以一种安全的方式释放锁，通过脚本告诉redis：只有当key存在并且key存储的值是所期望的值的时候才移除该key。这是由下面的Lua脚本实现的：
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else
return 0
end
这对于为了避免移除其他客户端创建的锁是很重要的。例如一个客户端可能获得锁，然后在某些操作中被阻塞了超过锁的有效期时间（在该时间key将会过期），并且在稍后移除锁，而该锁早已被其他客户端获得。仅仅使用DEL是不安全的，因为一个客户端也许会移除其他客户端的锁。通过上面的脚本替代，每个锁被一个随机字符串所"签名"，所以锁只有当仍然是被设置自己的客户端移除的时候才会被移除。
这样的随机字符串应该是什么？我假设它是20字节，来自/dev/urandom，但是对于你的任务来说，你可以找到让它变得足够唯一的更简单的方式，例如一个安全的选择是用/dev/urandom作为RC4的种子，并且利用它生成一个伪随机的stream。一个更简单的方案是使用精确到微秒的unix时间戳与客户端ID拼接，虽然这不够安全，但是也许能胜任大多数环境中的任务。我们用作key生命周期的时间，被称之为锁的有效期。它既是客户端自动释放锁的时间，也是在其他客户端可以再次获得锁之前该客户端用于执行操作所需要的时间，从获得锁的时刻开始，在给定的时间窗口内，没有违背互斥锁保障。
所以现在我们有了一个获得和释放锁的好方法。这个方法在一个由单个的、总是可用的实例组成的非分布式系统是安全的，让我们将概念扩展到一个没有这种保障的分布式系统中去。
Redlock算法
在分布式版本的算法中，我们假设我们有N个主redis，所有这些节点都是独立的，所以我们不使用复制或者任何其他内部的系统。我们已经讲述过在一个单实例系统中如何安全的获得或者释放锁，在单实例中，我们认为Redlock算法将会使用这个方法获得和释放锁是理所当然的。在我们的实例中我们将N设置为5，这是一个合理的值，所以为了保证所有redis以基本独立的方式失败，我们需要在不同的计算机或者虚拟机中运行5个主redis。
为了获得锁，客户端需要执行下面的操作：
- 获得当前的时间，精确到毫秒。
- 在N个实例中相继使用相同的key和不同的随机值获得锁，在步骤2中，当在每个实例中设置锁的时候，客户端使用比锁自动释放时间少的超时时间来获得锁。例如，如果锁自动释放时间是10s，则超时时间可以设置为5-50毫秒之间，这防止了客户端长时间阻塞在与挂了的redis节点的交互中：如果一个实例不可用，我们应该尝试尽快与下一个实例交互。
- 客户端通过当前时间减去步骤1获得的时间来评估为了获得锁耗费来多少时间，当且只有当客户端可以从大多数实例（这里是至少3个）中获得锁，并且获得锁所需时间比锁的有效期少时，才会被考虑获得锁。
- 如果获得了锁，它的有效期为初始有效时间减去如步骤3那样计算出的获得锁所消耗的时间。
- 如果因为一些原因获得锁失败（要么大多数实例少于N/2+1要么有效期为负），将会试图解锁所有的实例（即使实例被认为不能上锁）。
Redlock算法是异步的吗？
Redlock算法基于这样一个假设，即当进程之间没有同步时钟时，每个进程中的本地时间仍然以相同的速率流动，与锁的自动释放时间相比，误差较小。这个假设与现实世界中的计算机非常相似：每台计算机都有一个本地时钟，我们通常可以依赖不同的计算机来获得一个很小的时钟漂移。
在这一点上我们需要更精确的定义我们的互斥锁规则：它保证只要客户端持有锁，那么在锁有效期（步骤3中获得）减去一些时间（只有几毫秒，为了补偿进程之间的时钟飘移）内客户端将会结束它的工作。与需要限制时钟飘移的相似系统的更多信息，这篇论文是一个有趣的参考：Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.。
失败重试
当一个客户端无法获得锁的时候，为了取消在同一时刻针对相同资源尝试获得锁的客户端之间的同步，该客户端应该在一个随机延时后再一次尝试获得锁（这可能会导致没有赢家的大脑分裂局面）。同样，客户端尝试在大多数redis实例中获得锁越快，出现分裂的窗口越小（重试的需要也越少），所以理想情况下，客户端应该多路复用地同时向N个实例发送SET命令。
值得强调的是，如果获取大部分锁失败，客户端应该尽可能快的释放（部分）已经获得了的锁，这很重要。所以为了让锁能够再次被获得就没有必要等待key过期（然而如果发生了网络断开并且客户端无法再与redis实例交互，在等待key过期时，有一个可用的惩罚需要支付）。
释放锁
释放锁很简单，只涉及在所有实例中释放锁，无论客户端是否相信它能够成功地锁定给定实例。
安全性讨论
Redlock算法是安全的吗？我们尝试在不同情况下会发生什么。
在开始之前我们先假设客户端能够在大多数实例中获得锁。所有实例会包含一个有相同生命周期的key。然而key是在不同的时间设置的，所以所有的key也会在不同的时间过期。但是如果第一个key在T1时刻（我们在与第一个服务器联系前采样的时刻）被设置为最坏的状态，最后一个key在T2时刻（我们从最后一个服务器获得回复的时间）被设置为最坏的状态，我们确定第一个过期的key将会存活至少最短有效期=TTL - (T2 - T1) - 时钟飘移。所有其他的key将会在稍后过期，所以我们确定至少这次key将会被同时设置。
在大多数key被设置期间，另一个客户端将不能获得锁，因为如果N/2+1个key已经存在则N/2+1个SET NX操作不会成功。所以如果一个锁被获得了，在同一时刻该锁不可能被再次获得（违背互斥锁性质）。
然而我们同样要确保多个客户端在同一时刻尝试获得锁时不会成功。
如果一个客户端使用接近或者大于锁最大的有效期（我们用于SET的有效期）的时间锁住了大多数实例，那么该锁将会被认为是非法的并且会解锁所有的实例，所以我们只需要考虑客户端可以用少于有效期的时间锁住大多数实例的情形，在这种情形下对于上面早已表达过的论点，在最短有效期内应该没有客户端能够重复获得锁。所以多个客户端将能够同时锁住N/2+1个实例（用步骤2结尾的时间），只有当锁住大多数实例的时间大于TTL的时候，锁才会无效。
你能提供一个正式的安全性证明，指出现有的相似算法或者发现bug吗？非常感激！
存活讨论
系统存活基于三个主要功能：
- 锁自动释放（因为key过期）：最终key可再次用于上锁。
- 事实上，客户端通常会在没有获得锁时，或者在获得锁后工作终止时，合作地移除锁，这使得我们不必等待key过期来重新获得锁。
- 事实上，当客户端需要重试锁时，它等待的时间比获取大多数锁所需的时间要长得多，以便在资源竞争期间不太可能出现分裂大脑的情况。
然而，在网络分区时我们支付一个与TTL时间对等的可用惩罚，所以如果有连续的分区，我们可以无限期的支付这个惩罚，这发生在每当一个客户端获得锁并且在可以移除锁之前被分割开的时候。
基本上，如果有无限连续的网络分区，系统可能在很长的时间内不可用。
性能、崩溃恢复和同步
就获得和释放锁两方面的延迟以及每秒获得/释放锁操作次数，许多用户使用redis作为锁服务器需要高性能。为了满足这个需求，用以降低与N个redis实例对话的延迟的策略无疑是多路复用（或者管道复用：让socket进入非阻塞模式，发送和读取所有的命令，假设在客户端和每个实例之间的RTT是相似的）。
然而如果我们想要达成一个崩溃-恢复的系统模式，仍然有另一个关于持久化的考虑。这里为了明白问题，我们假设我们没有给redis配置持久化，一个客户端在5个实例中的3个获得锁，能够获得锁的实例中有一个实例被重启了，此时我们可以为同一资源锁定3个实例，另一个客户端可以再次锁定，这违反了锁的独占性的安全属性。
如果我们配置了AOF持久化，情况将会改善很多。比如我们可以通过发送SHUTDOWN更新一个和重启它。因为redis的过期机制是语义实现的，所以当服务器关闭的时候时间仍然在流逝，我们所有的请求都正常。然而，只要彻底关闭，所有事情都是正常的。如果停电了怎么办？如果redis被配置了默认每秒同步数据到硬盘，重启之后有可能我们的key会丢失，理论上，如果我们想要保证面对任何实例重启锁都安全的情况，我们需要在持久化配置中设置fsync=always。反过来这又会破坏传统意义上用来以安全的方式实现分布式锁的同级别CP系统的性能。然而，情况实际上比它们第一眼看起来更好。基本上，只要崩溃后重启，算法继续持有安全性，它不在参与任何当前活动的锁，所以当实例重启时，当前所有活动的锁被正在请求锁的实例获得，而不是重新加入系统的实例。
为了保证这一点，我们只需要让一个崩溃时间、不可用时间（实例崩溃后存在的锁的所有key所需的时间）比最大TTL还要长的实例变成非法和自动释放的。
即使没有任何类型的redis持久化可用，使用延迟重启是基本可能实现安全性的，但是注意这有可能转移成一个惩罚。比如，如果大多数实例崩溃了，对于TTL来说系统将会变成全局不可用的（这里的全局指期间不在有资源是可上锁的）。
让算法更可靠: 扩展锁
如果客户端执行的工作是由小步骤组成的，则可以默认使用较小的锁有效期，并且扩展实现锁扩展机制的算法。在计算执行到一半当锁有效期快到的时候，基本上客户端可以通过发送一个扩展Lua脚本给所有的实例来扩展锁，该脚本用于扩展key的TTL，而对应的key必须仍然存在并且持有的随机指仍然是上锁时的值。
客户端应该只在key有效期内并且能够在大多数实例中扩展锁的时候才认为锁是可以重新获得的（基本上使用的算法与刚开始获取锁的算法相似）。
然而这不能在技术上改变算法，所以重新获得锁的尝试次数应该限制最大值，否则违背了存活性质。
想要帮忙？
如果你在分布式系统中使用了，拥有你的意见和分析将会是非常好的，用其他语言实现的参考文献同样棒极了。
提前感谢！
Redlock分析
- Martin Kleppmann在这里分析了Redlock，我不同意该分析结果并且在这里发表了我对他的分析结果的回应。
最后
译文原址
Thanks!