Redis中的分布式锁
Redis的分布式锁模式
分布式锁作为原语，在多个进程必须以互斥的方式去操作某些共享资源的环境下十分有用。
有很多的库和博客文章描述了如何在Redis中实现分布式锁管理器(DLM:Distributed Lock Manager)，但大部分都采用了简单的方法。这些方法比起那些稍微复杂一点的设计保障更低。
本文描述了通过一种更典型的算法来在Redis中实现分布式锁。我们提出了一种相较于常见的单实例方法，更安全去实现DLM的红锁(Redlock)算法。我们希望社区能分析该算法并提供反馈，并将该算法作为分布式锁或者其他更复杂或更多变设计的起点。
安全性与活性保障
我们将用三种属性来对我们的设计建模。这三种属性是以更加高效实现分布式锁所需的最基本的属性。
1.安全性：互斥。即在任何时候都只有一个客户端能拥有锁。
2.活性 A：无死锁。即使锁定资源的客户端崩溃或被分区，最终它也总能获取到锁。
3.活性 B：容错。只要Redis的大部分节点存活，客户端就能获得和释放锁。
为什么基于故障切换的实现还不够
在讨论这个问题之前，我们先说说当前大多数基于Redis的分布式锁库的事务现状。
在Redis中，锁住某资源的最简单的方法为实例创建一个key。该键通常会设置一个基于Redis过期机制创建的过期时间，所以最后这个键一定会被释放（上述三种属性的第二条：无死锁）。当客户端需要释放资源时便删除key。
从表面上看这种方法不错，但有个漏洞：在分布式系统中出现了一个单点故障。
写者注
单点故障，指的是当系统中某一点故障，整个系统都会跟着故障。比如在分布式系统中，主节点分发任务，子节点处理任务。如果主节点出现故障那么整个系统都会故障。
如果Redis的主机崩溃了会发生什么？我们可以提前复制主机，当主机不可用时用这个“从机”。但实际上这种方法是不可用的。由于Redis的复制是异步的(asynchronous)，所以这种实现方法无法保证互斥的安全性（上述三种属性的第一条：互斥）。
以下是该模型的一种竞争情况：
1.A客户端获取了主机中的锁。
2.主机在向从机传输写入的key之前就崩溃了。
3.从机被提升为主机。
4.B客户端此时获取到同一个资源的锁，而A客户端已经获取了这个锁。这违反了安全规定。
在某些特殊情况下这个方法没啥问题，比如在故障期间多个客户端可以同时获得锁。在这种情况下可以用复制主机的方法解决。不然我们建议通过本文描述的方法实现。
单实例的正确实现
在尝试解决上面提到的单实例设置的限制之前，让我们先看看在简单的情景下如何正确地实现，不仅因为这是对于那些时不时发生竞争情况下应用的一种可行方案，同时也是因为锁定单个实例是我们在此描述的算法的基础。
用以下方式可以获得锁：
SET resource_name my_random_value NX PX 30000这条指令会在该key不存在(NX option)的时候SET一个key，并设置30000毫秒的过期时间(PX option)。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这对于避免移除其他客户端创建的锁十分重要。比如一个客户端获得了锁，它执行某些操作因为所耗时间要大于锁的存在时间（即锁的过期时间）而被阻止执行，导致在此之后它移除了其他客户端的锁。因为客户端可能会其他客户端的锁，所以仅使用DEL指令是不安全的。而通过上面的脚本，为每个锁都带上一个随机的字符串；只有该锁是其对应的客户端创建，同时该客户端试图移除时，锁才会被移除。
那么这个随机的字符串应该如何设置呢？比如你可以让字符串中有20bytes通过/dev/urandom生成，但实际上不需要这么做就能让字符串足够“独特”。比如其中一种安全的方法就是
写者注
没学过密码学和加密算法，不知道对不对。
将/dev/urandom作为RC4加密算法的种子，并从中生成一个伪随机流。还有一种更简单的方法计算用UNIX微秒精度的时间戳，将时间戳和客户端的ID相连。当然这并不那么安全，但它仍然能在大部分环境下胜任。
“锁的有效周期”指的是我们能在锁TTL内进行操作的这段时间。同时这即是锁自动释放前的时间，也是A客户端B客户端再次获得锁前执行的相关操作的时间，并且从技术层面上不会违反互斥保证，而互斥保证只在锁被获取的那一刻起给定的时间窗内生效。
综上，这是一种获取和释放锁的好方法。对于这个系统，将其推理到由单个总是可用的实例组成的非分布式系统上是可行的。现在让我们将这个概念拓展到没有相应保证的分布式系统上看看。
The Redlock Algorithm
在分布式版本中的红锁算法中，我们假设有n个redis主机。这些节点之间相互独立，所以我们不需要用到复制主机和其他内含的协调系统。我们之前已经描述果了如果在单实例的情况下安全的获取和释放锁。由此我们理应认为红锁算法也使用同一方法在单实例的情况下获取和释放锁。我们取一个比较合理的值，如n=5，表明我们需要在5台不同的电脑或虚拟机上运行redis主机，并确保它们停止工作时基本上不会影响到其他主机。
客户端为了获得锁，需要执行以下一系列的操作：
1.获取当前时间，该时间以毫秒为单位。
2.客户端尝试在全部N个实例中顺序获取锁，在所有实例中都用相同名称的键名和随机值。同时客户端在为每个实例设置锁时，会用一个远小于锁的释放时间的timeout去获取锁。比如锁自动释放的时间是10秒，那么timeout的值可能是5-50毫秒。这可以避免客户端在尝试访问Redis的挂掉的节点时被阻塞太长时间：如果实例不可用，那么应该尽快访问下一个实例。
3.客户端通过减去步骤1中时间戳的当前时间，来计算获得锁需要耗费多长时间。只有锁能在大部分实例中（至少3个）获取锁，并且获取锁的总耗费时间要小于锁的有效时间，锁才算被真正的获取到。
4.锁被获取后，其有效时间变为它的初始的有效时间期减去步骤3中计算的耗费时间。
5.如果客户端因为某些原因（比如无法锁住N/2+1个实例，或锁的有效时间的值为负数）无法获取锁，客户端会试着解锁所有的实例（包括客户端认为无法锁住的实例）。
该算法是异步的吗？
该算法假设进程中没有同步钟，各个进程的时间以同样的速率更新，且于锁自动释放时间的误差幅度很小的情况。这一假设非常接近现实中的实际运用：每台电脑都有各自的本地钟，并且一般来说即使计算机有较小的时钟漂移也并无大碍。
写者注
计算机的本地钟一般靠晶振计时，但晶振材料会受到环境影响。这导致不同计算机的本地钟不一致，如果分布式系统都靠节点的本地钟，若本地钟的误差逐渐扩大，就会导致原本事件的顺序发生变换，从而导致不可预期的错误。
基于这点我们需要明确规定互斥规则：需要保证持有锁的客户端在锁的有效时间（步骤3计算得到的），在此基础上再减去一些时间（通常是几毫秒，来补偿进程间的时钟漂移）内停止工作。
失败重试
当一个客户端无法获取锁时，它应该在随机设置的延迟时间后重试，以便于使同时尝试获取同一资源锁的多个客户端失去同步（这可能会导致“脑裂”情况）。同时，若客户端获取大多数Redis实例锁的速度越快，”脑裂“情况和需要重试的窗口就越小，因此在理想情况下客户端应该采用多路复用的方式来向N个实例发送SET指令。
写者注
“脑裂”(split brain)。当活动节点故障或者停止相应时，备用节点会接管服务。在任何一个节点现在都不能与另一个节点通信的情况下，备用节点可能会认为活动节点无法工作，从而将自己提升为活动节点。这导致系统中出现了两个活动节点，两个节点上的数据都会发生变化，导致数据完整性和一致性受到损害。
强调客户端在获取大多数锁失败后，尽可能快的释放（部分）以获取的锁是非常重要的，以便不需要为了锁能再次被获取而一直等到key过期（但是如果发生了网络分区，并且客户端无法再于Redis实例通信，那么就只能等到锁自动释放）。
释放锁
释放锁比较简单，无论客户端是否认为能锁上给定的实例都可以被执行。
安全性讨论
该算法安全吗？让我们看下在不同情况下会发生什么。
我们假设客户端能获取大部分实例的锁。所有实例都有着一个相同TTL的key。但是，这些key是不同时设置的，所以最后这些key将会不同时失效。但如果第一个key在最坏情况下在T1时刻创建（在与第一台服务器通信前采样的时间），最后一个key最坏在T2时刻创建（从最后一个服务器获得回复的时间），我们可以确保集合中第一个key的过期时间至少为MIN_VALIDITY=TTL -(T2-T1)-CLOCK_DRIFT。其他所有key都会在该时间后过期，所以我们可以确保key将会在该时间后同时设立。
在设置大部分key的时候，由于已经存在N/2+1个key，导致N/2+1 SET NX的操作执行失败，使得另一个客户端无法获取锁。那么如果一个锁被获取了，那么就不能同时再获取这个锁（与互斥属性冲突）。
但我们想确保多个客户端可以同时尝试获取锁，不过不能同时成功。
如果一个客户端在非常接近或者大于锁的最大有效时间（基本上指的就是SET指令设定的TTL）锁住了大部分的实例，那么就可以认为该锁是无效的并且会解锁实例，所以我们只需要考虑客户端能够在小于有效时间内锁定实例的情况。而这种情况已经在上面讨论过了，通过MIN_VALIDITY就没有其他客户端可以重新获得锁。这样一来多个客户端仅在锁定大多数实例的时间要大于锁的TTL的情况下才能同时锁住N/2+1个实例，从而使锁定无效。
活性讨论
这个系统的活性基于以下三个主要特征：
1.因为key过期而自动释放锁：无论如何key最后都能被再次锁住。
2.客户端在未获取锁，或者在获取锁后停止工作时会以合作的方式去移除锁，这样就不需要等到key过期再重新获取锁。
3.当客户端需要重试锁时，它会等到一段时间。该时间应该比获取大部分锁的时间要更长，以便在在争夺资源时不会出现“脑裂”的情况。
但是，在网络分区的情况下需要付出和TTL时间相等的可用性惩罚，所以当出现连续分区的情况，我们可以无限期的进行惩罚。这发生在每次当客户端在能获取锁并在移除锁前就被分区的情况。
写者注
Redis有着Sentinel哨兵机制。当检测到节点故障时，会对节点进行惩罚，从而避免访问不可用的节点。惩罚措施有断开主从节点的链接等。
基本上如果有发生了无限次的持续网络分区，那么该系统可能会在无限长的时间内不可用。
性能，崩溃恢复，文件同步（fsync）
有很多用户在将Redis作为锁服务器时，对于获取和释放锁的延迟，和每秒可执行的获取/释放锁的数量，要求有足够高的性能。为了解决这种需求,与N个Redis服务器通信并减少延迟的方法只能是多路复用（假设客户端和每个实例之间的RTT接近，将套接字置于非阻塞模式，发送所有指令并再稍后读取所有指令）
写者注
RTT（round-trip time）。指的是客户端到服务器往返花费的时间。从发送端发送数据开始，到发送端收到来自接收端的确认结束。
但是，如果我们以崩溃恢复的系统模型为目标，那么还有另一个关于持久性的考虑因素。
该问题如下：我们假设在没有持久性的情况下配置Redis。一个客户端能获取5个实例里其中3个的锁。若此时其中一个客户端能获取锁的实例重启了，那么对于此资源，又会出现3个能锁住的实例，同时其他客户端能再次锁上它。这与锁互斥的安全性相冲突。
如果我们使用AOF持久化，情况就不一样了。比如我们可以通过向服务器发送SHUTDOWN指令并重启来升级服务器。由于Redis的过期是语义实现的，所以当服务器关闭时，即使过去很长一段时间，我们的需求也不会出现问题。然而，仅在正常关机下需求才不会出现问题，那如果突然停电导致的关机该怎么办？如果Redis的默认配置为每秒都进行fsync将数据写入硬盘，那么在服务器重新开机后我们为锁设置的key可能就会丢失。理论上讲，如果我们想保证在任何类型的实例重启时锁的安全，我们需要在持久化设置中启用fsync=always。由于这会导致额外的同步开销，所以会在一定程度上影响性能。
不过实际运用之后会发现这种方法比设想的还要好。基本上只要实例在崩溃后重启，它就不再参与任何当前活动的锁，也保证了算法的安全性。这就意味着：当实例重新启动时，当前活动的锁集，都是通过锁定实例而不是重新加入系统的实例来获得的。
为了保证这一点，我们只需要在崩溃后使一个实例不可用，不可用的时间至少要比我们所用的最大TTL多一点。同时这也是实例崩溃时存在的锁的所有key变为无效并自动释放所需的时间。
使用延迟重启的方法，即使没有任何可用的Redis持久性，基本上也可以实现安全。但这可能会转化为可用性惩罚。如果大多数实例崩溃，系统中全部的TTL都将不可用（这里的“全部”意味着在此期间根本没有资源可锁定）。
让该算法变得更可靠：拓展锁
如果客户端执行的操作由很多个步骤组成，那么可以使用初始的更小的锁有效时间，并在此基础上拓展实现”锁的拓展机制“的算法。基本上如果客户端在计算过程中，锁的有效性接近一个比较低的值时，那么客户端可以通过向所有实例发送一个Lua脚本来拓展锁，如果key已经存在，其值仍然是一开始获取锁时客户端分配的随机值。
只有当客户端在有效期内能够将锁扩展到大多数实例中，（所使用的算法与获取锁时使用的算法非常相似），客户端才能重新获取锁。
然而从技术层面讲这没有改变算法本身，所以应该限制锁重新获取尝试的最大次数，否则会违反活性属性。
关于一致性的免责声明
请考虑仔细阅读本页末尾的“Analysis of Redlock”部分。Martin Kleppman的文章和antirez对此的回答非常重要。如果你担心一致性和正确性，你应该注意以下问题：
1.您应该实现fencing tokens。这对于可能花费大量时间并适用于任何分布式锁定系统的进程来说尤其重要。当然延长锁的TTL也是一种选择，但不要认为只要获取锁的进程是活动的，锁就会被保留。
2.Redis没有使用单调时钟作为TTL过期机制。这意味着墙上时钟偏移可能会导致一个锁被多个进程获取。尽管可以通过阻止管理员手动设置服务器的时间和正确设置NTP来缓解这个问题，但这个问题在现实生活中仍然有可能发生并影响一致性。
写者注
NTP（Network Time Protocal），即网络时间协议。计算机中通常有单调时钟和墙上时钟。墙上时钟可以与NTP服务器同步，返回UTC的时间戳。单调时钟指的是计算机从启动开始往后的纳秒数。其中墙上时钟可以回拨，导致发生“时光倒流”的情况，而单调时钟不会回拨。
