Redlock

RedLock的基本思路就是为锁准备多个副本，避免Redis主从切换的时候，数据丢失。

Redlock是分布式锁在利用Redis上的一种具体实现，RedLock 是利用了Redis实现了DLM (Distributed Lock Manager), 包含了首先获得多数选票，并设置一个租约(lease)时间的功能, 来保证分布式锁的正确性，和高效性。

假设有N个master节点，通常情况下为5个节点，而且这些节点完全独立，5个节点既保证了性能的同时，又增加了可靠的容错性。

• 客户端首先获取当前时间，单位为毫秒
• 客户端依次尝试在N个redis节点上获取锁，使用通用key和随机数。客户端请求redis的超时时间要远小于锁的释放时间，假如锁的有效时间为10s，则客户端请求的超时时间要设置5-50ms。这避免了当某个redis不可用时，客户端会hold住很长时间
• 客户端会计算请求锁时消耗的时间，当客户端获取超过半数成功，且流逝的时间小于锁的有效期时间，则说明客户端成功获取到锁
• 成功获得锁后，锁的有效期 = 原来锁的有效期(10s) - 流逝的时间
• 如果锁获取失败了，那么客户端应该立即向所有reids节点发起释放锁的操作

问题1

由于N个Redis节点中的大多数能正常功能就能保证Redlock正常工作，因此理论上它的可用性更高。单Redis节点的分布式锁在failover的时候锁失效的问题，在Redlock中不存在了，但如果有节点发生崩溃重启，还是会对锁的安全性有影响。具体的影响程度跟Redis对数据的持久化程度有关。

假设一共有5个Redis节点：A B C D E。设想发生了如下的事件序列：

1. 客户端1成功锁住了A B C，获取锁成功（但D和E没有锁住）
2. 节点C崩溃重启了，但客户端1在C上加的锁没有持久化下来，丢失了
3. 节点C重启后，客户端2锁住了C D E，获取锁成功
   这样，客户端1和客户端2同时获得了锁（针对同一资源）

在默认情况下，Redis的AOF持久化方式是每秒写一次磁盘（即执行fsync），因此最坏情况下可能丢失1秒的数据。为了尽可能不丢数据，Redis允许设置成每次修改数据都进行fsync，但这会降低性能。当然，即使执行了fsync也仍然有可能丢失数据（这取决于系统而不是Redis的实现）。所以上面分析的由于节点重启引发的锁失效问题，总是有可能出现的。为了应对这一问题，antirez又提出了延迟重启（delayed restarts）的概念。也就是说，一个节点崩溃后，先不立即重启它，而是等待一段时间再重启，这段时间应该大于锁的有效时间（lock validty time）。这样的话，这个节点在重启前所参与的锁都会过期，它在重启后就不会对现有的锁造成影响。

问题2

如上面的时序图所示，假设锁服务本身是没有问题的，它总是能保证任一时刻最多只有一个客户端获得锁。上图中出现的lease这个词可以暂且认为就等同于一个带有自动过期功能的锁。客户端1在获得锁之后发生了很长时间的GC pause，在此期间，它获得的锁过期了，而客户端2获得了锁。当客户端2获得了锁。当客户端1从GC pause中恢复过来的时候，它不知道自己持有的锁已经过期了，它依然向共享资源（上图中是一个存储服务）发起了写数据请求，而这时锁实际上被客户端2持有，因此两个客户端的写请求就有可能冲突（锁的互斥作用失效了）。

除了GC以外，有很多原因会导致进程的pause，比如需存造成的缺页故障(page falut)，再比如CPU资源的竞争。即使不考虑进程pause的情况，网络延迟也仍然会造成类似的结果。

总结起来就是说，即使锁服务本身是没有问题的，而仅仅是客户端有长时间的pause或网络延迟，仍然会造成两个客户端同时访问共享资源的冲突情况发生。

问题3

如下示例说明了Redlock对系统计时(timing)过分依赖，还是假设有5个Redis节点A B C D E：

1. 客户端1从Redis节点A B C成功获取了锁（多数节点）。由于网络问题，与D和E通信失败。
2. 节点C上的时钟发生了向前跳跃，导致它上面维护的锁快速过期。
3. 客户单2从Redis节点C D E成功获取了同一个资源的锁（多数节点）
4. 客户端1和客户端2现在都认为自己持有了锁

上面这种情况之所以有可能发生，本质上是因为Redlock的安全性(safety property)对系统的时钟有比较强的依赖，一旦系统的时钟变得不准确，算法的安全性也就保证不了。

好的分布式算法应该基于异步模型(asynchronous model)，算法的安全性不应该依赖于任何计时假设(timing assumption)。在异步模型中：进程可能pause任意上的时间，消息可能在网络中延迟任意长的时间，甚至丢失，系统时钟也可能以任意方式出错。一个好的分布式算法，这些因素不应该影响它的安全性(safety property)，只可能影响它的活性(liveness property)，也就是说，即使在非常极端的情况下(比如系统时钟严重错误)，算法顶多是不能再有限的时间内给出结果而已，而不应该给出错误的结果。这样的算法在现实中是存在的，像比较著名的Paxos或Raft。但显然按这个标准的话，Redlock的安全性级别是达不到的。

锁的用途可以分为以下两种：

• 为了效率(efficiency)。协调各个客户端避免做重复的工作。即使锁偶尔失效了，只是可能把某些操作多做一遍而已，不会产生其他的不良后果。比如重复发送一封同样的email。
• 为了正确性(correctness)。在任何情况下都不允许锁失效的情况发生，因为一旦发生，就可能意味着数据不一致(inconsistency)，数据丢失，文件损坏，或者其他严重的问题。

因此应该根据不同的场景选择不同的锁：

• 如果是为了效率(efficiency)而使用分布式锁，允许锁的偶尔失效，那么使用单Redis节点的锁方案就足够了，简单而且效率高。Redlock而是一个过重的实现
• 如果是为了正确性(correctness)在很严肃的场合使用分布式锁，那么不要使用Redlock。它不是建立在异步模型上的一个足够强的算法，它对于系统模型的假设中包含很多危险的成分(对于timing)。