【迁移】用 Redlock 构建 Redis 分布式锁【译】

由于不同的进程都必须在排他的方式操作共享资源，分布式锁在很多环境中是非常有用的基础组件。



有很多库和博客都介绍了怎么用Redis来实现分布式锁管理器，但是每个库都有不同的设计理念，很多只是用了很小的一个方向，相比于略微复杂一点的设计都不能保证。



现在我尝试提供一个更权威的算法来实现Redis分布式锁。我们提出一个算法，名叫Redlock，我们相信它是比一般单例实现方式更加安全地实现了分布式锁管理器。我们希望Redis社区能够分析它，提供反馈，并且把它作为一个实现更加复杂和可供选择的设计的一个出发点。



尽管已经有了10个以上Redlock的独立实现，我们不知道哪个依赖这个算法，我还是认为把我的笔记分享出来是很有意义的。由于Redis已经在很多别的地方被多次提到了，所以我不准备在这里讨论他了。



在我准备详细讲述Redlock之前，我想说我十分喜欢Redis，而且之前也成功地在生产环境中应用了。我认为如果你想在服务器之间共享一些生命期比较短，相似并且快速变化的数据，而且对于偶尔不管什么原因的丢失数据不太敏感的话，那么我建议你使用他。比如，一个好的用法是保留每个IP地址的请求数，和不同IP的用户ID。



然而，Redis也开始向着需要保证强一致性和持久化需求的数据管理的领域进军。这一点困惑住我了，因为Redis起初是不是为了这个目的设计的。可以论证，分布式锁就是这些领域中的一种。让我们详细去检验。



你用那个锁来做什么？



锁的目的是保证在不同的节点间执行相同的任务，只有一个成功。这个任务可能是向一个共享的存储系统中写入数据，进行某些计算，调用一些外部的API接口，或者别的。在较高层次分析，在分布式应用中有两个原因是你想让锁去完成的：效率或者正确性。为了区别这些情况，你可以试着想象锁失败会导致什么后果：



效率：



加锁可以不用你去把一件事做两次（比如一些复杂计算）。如果锁失败了，两个节点最终做了同一件事，结果就会在花销上有略微的增加或者一些不适当的。



正确性：



加锁阻止了线程的不同步和系统状态的混乱。如果锁失败并且两个节点在同一份数据上同步工作，结果就将导致产生一个损坏的文件，数据丢失，永久不一致。一个病人服用了错误剂量的药物，或者其他一些比较严重的问题。



两者都是获取锁时会遇到的情形，但是你必须非常清楚地分辨出你正在处理的是哪种。



我认为如果你只是出于保证效率来使用锁，那么使用Redlock而带来的花销和复杂度会令你望而却步。运行五个Redis服务并且花费大量时间去检查是否获取到你的锁。你最好不要仅仅使用一个Redis实例，以确保在宕机情况下可以通过异步复制的方式将数据复制到从节点。



如果你使用了单个Redis实例，当这个节点突然断电或者其他什么故障发生的时候就会释放锁。但是如果你只是将锁用于优化效率的话，宕机也不会经常发生，那就没大毛病。这个“没多大毛病”的情景是Redis的一个亮点。至少如果你依赖单个Redis节点，每个进入系统的人都是看到相同的，这只用于极少数的情形。



另外一个方面，Redlock算法，重大选举和5个节点的复制，看起来更加适合正确性的选择。我认为在下面这些情形中都不大适合这个目的。本文的余下部分我们主要讨论你的锁在分布式事务中怎样保证正确性的，如果两个不同节点并发地持有同一个锁，这将是一个严重的bug。



使用锁保护资源



让我们先不讨论Redlock的特别之处，让我们先看下一个分布式锁通常是怎么用的吧。记住，分布式系统中的锁不同于多线程应用中的mutex（互斥锁）。他比那个要来的复杂，归因于不同的节点和网络会以不同的方式失败而产生的问题。



举个例子，假如说你有一个系统，他的客户端需要更新共享存储（如HDFS或S3）中的文件，不同之处在于，回写更改的文件，最终释放锁。锁同时阻止了会导致丢失更新的两个客户端读写循环。代码如下所示：



// THIS CODE IS BROKEN
function writeData(filename, data) {
    var lock = lockService.acquireLock(filename);
    if (!lock) {
        throw 'Failed to acquire lock';
    }

    try {
        var file = storage.readFile(filename);
        var updated = updateContents(file, data);
        storage.writeFile(filename, updated);
    } finally {
        lock.release();
    }
}



不幸的是，尽管你有个表现不错的锁服务，这段代码依旧是有问题的。下面的图标展示了你是怎样导致数据混乱的：



在这个例子中，获得锁的客户端当持有锁的时候停止了一大段时间——可能由于GC在进行。锁有一个延迟，或许也总是一个不错的主意。然而，如果GC持续的时间超过释放的过期时间，客户端不会认为它过期了，它会继续运行，并产生不安全的状态更改。



这个bug不仅仅停留在理论：HBase经常有这种问题。通常GC是很短的。但是“stop the world”GC有时候会持续几分钟——当然要比释放过期长的多。甚至所谓的线程垃圾收集器，比如HotSpot JVM的CMS不能完全运行在并行条件下。甚至她们需要反复地stop the world。



你不能够在将数据写回到存储之前在锁过期期间加入检查来修复这个问题。记住GC可以在任何时候阻断一个运行中的线程，包括回最大限度造成不便的点。



如果你会因为自己的程序在运行阶段不会发生长时间的GC停留而沾沾自喜，别高兴太早，因为仍然会有别的原因导致停止。可能你的进程想要去读取一个尚未写入内存的地址数据，它就会得到一个错误的页面，停下来直到页面从磁盘中加载出来。如果你的磁盘确实是EBS（快存储），读取一个无意而可变的数据导致Amazon的同步网络请求阻塞。可能有很多进程抢占CPU，你命中了你的任务树中的一个黑色节点（算法基于红黑树）。可能一些时间发送给进程SIGSTOP。这样的话你的进程游可能会挂掉。



假如你仍旧不相信进程会停止的事实，请换位思考下，文件写请求在到达存储服务之前会在网络中会发生延迟。报文类似广域网和IP都会果断延迟发送包，在GitHub的设计中，网络包延迟大约是90秒。这意味着一个应用进程会发生写请求，它会在当释放过期一分钟之后到达存储服务器。



甚至在一个管理良好的网络中，这种事情也会发生。你没法对延迟做一些假设，也是为什么上面的代码基本上是不安全的，不管你用了怎样的锁服务。



使用栅栏让锁变得安全



这个问题解决起来也比较简单：你需要在每个向存储服务的写请求中加入栅栏token。在这篇文章中，一个栅栏token既是当客户端请求锁时递增的数字。下面这张图说明了这点：



client1需要释放和获取编号为33的token，但是之后它进入了一个长时间的停滞，然后释放超期。Client2需要释放锁，获取了编号为34的token，然后发送它的写请求道存储服务商，包括34token。然后，client1恢复活跃并且发送它的写请求到存储服务商，包括33token。然而，存储服务器记录了34token，所以拒绝了33token。



注意到这样需要存储服务器做一个动态的检查tokens的操作，阻止往回写的token。但是当你知道了这个套路之后就觉得不是特别的难。提供的锁服务产生了严格递增的tokens，这样使得锁变的安全。比如说，如果你把ZooKeeper当作锁服务来用，你可以使用zxid或者znode版本号当作栅栏token，这样你就做的很好了。



然而，这样导致你用Redlock时遇到一个大问题：它没有产生栅栏tokens的能力。这个算法不能产生确保每时每刻提供给客户端锁的数组。这意味着尽管这个算法时非常不错的，但是使用它不是很安全，因为你不能阻止客户端之间的运行条件。当一个客户端停滞或者包延迟的情形。



如果某人修改Redlock算法来产生栅栏tokens我也不会感到很稀奇。这个唯一的随机数值不能提供需要的单调性。仅仅保证在Redis节点上计数器是不充分的，因为这个节点有可能挂掉。保证在不同节点上的计数器都正常表明他们可能不是同步的。所以你可能需要一个一致性算法来产生栅栏tokens。



花时间去解决一致性



事实上Redlock在产生栅栏tokens的时候总是失败也称为它不应该应用在对锁的正确性要求很高的业务场景中。但是有更需要讨论的问题存在着。



在学术文献中，这种算法最具实践系统模型时不可靠失败检测的异步模型。英文字面上讲，就是这个算法对时间不敏感：进程可能会随意停止一段时间，包也会随机性地发生网络延时，锁会失败——尽管如此这个算法还是希望去做正确的事。基于我们上面所述，还是有非常有理由的证据的。



算法使用锁的唯一愿望事产生延迟，避免节点宕机导致的无限时的等待。但是延迟事不精确的：只是因为一个请求延迟，不意味着其他节点会挂掉——在网络中产生大的延迟倒还好，也许是本地时钟出问题了。当用来做失败检测的时候，延迟是判定出错的。



记得Redis使用getTimeOfDay api，而不是monotonic clock，去检查过期的keys。getTimeOfDay的帮助页明确说明了它返回给在系统时间上是不连续跳跃的——意味着，他会时隔几分钟突然跳跃变化，或者及时地跳回来。如此，如果系统时钟在做奇怪的事情，他会比想象更快或者更慢更容易发生Redis的key的延迟。



异步模型中的算法不是一个大问题：这些算法通畅证明他们的安全属性经常维持住，没有产生时间假定。只有存活的属性依赖延迟或者其他失败检测。用英文直译的话就是如果系统延迟随时发生，算法的表现就会很差，但是算法永远不会造成错误的论断。



然而，Redlock不是这样的。他依赖于大量的时间假定：他却包所有Redis节点能够在过期前维持keys很长一段时间；在过期延迟面前网络延迟是个小case；进程的停止时长也比过期持续的时间要短的多。



通过坏的延迟摧毁Redlock



让我们看一些表明了Redlock是依赖于时间假设的例子。假设系统有5个Redis节点和两个客户端。如果在一个Redis节点上的时钟跳过了会发生什么？



1  client 1在节点A、B、C上加了锁。由于网络原因，D和E没有能够到达。



2  在C节点上的时钟跳过了，造成锁过期。



3  Client 2在节点C、D、E上加了锁。由于网络原因，A和B不能到达。



4  Client 1和2都认为他们获取了锁。



一个类似的问题也会发生。当C在持久化锁道磁盘之前发生宕机，然后立刻重启。由于这个原因，Redlock官方文档推荐崩溃节点至少在长期持有锁的过程中延迟启动。但是当一个理所当然的计算时间时候发生了延迟重启，如果时钟跳过久失败。



好的，你可能认为时钟抖动是不可思议的。因为你肯定非常确信正确地配置了NTP去调节是种。这种情形下，让我们看下一个进程的停止是怎么样造成这个算法失败的例子：



1  Client 1请求了节点A，B，C，D，E上的锁



2  当Client 1上的响应在争夺资源，client 1将进行stop-the-world GC。



3  锁在所有的Redis节点上过期。



4  Client 2在A，B，C，D，E上获取锁。



5  Client 1完成GC，收到来自Redis节点上的响应表明他获取锁成功了。



6  Client 1和2现在都确信他们获取了锁。



注意尽管Redis是用C写的，这样就没有GC，任何客户端发生GC停留的系统都会有这个问题。你只有组织Client 1在Client 2获取锁之后去做任何事情才能保证线程安全。比如使用上述的栅栏方法。



一个很长的网络延迟会产生和进程停止一样的效果。他可能受限于你的TCP用户延迟-如果你让延迟比Redis的带宽还算。可能延迟的网络包可以忽略，但是我们不得不仔细研究和思考TCP是怎么样实现来确保正确发送包的。当然，因为有延迟我们回归到时间精确性的问题上来。



Redlock同步假定



这些例子展示了Redlock只有在你确定一个同步系统模型的时候才能正确地工作-就是有下面这些属性的系统：



绑定的网路延迟



绑定的进程停止



绑定的时钟错误



注意同步模型不意味着绝对同步的时钟：他表明你嘉定一个周知的，已经解决了网络延迟绑定，停止和时钟抖动。Redlock嘉定延迟，停止和抖动都是小问题；如果时间问题和时间的持久性一样规模的话，算法就失效了。



当然在数据中心环境下，时间嘉定将适合很多场合-这被叫做半同步系统。但是他有足够的好吗？时间嘉定一旦失败，Redlock就会将他的安全的属性透明化，比如，允许在另一个之前发布到一个客户端的节点就过期了。如果你认为你的时钟是可靠的，“大多数时间”不充分-你需要让她总是正确的。



为大多数版系统环境制定一个同步系统模型是不安全的。保证提醒你自己关于Github的90秒包延迟时间。



另一个方面，一个为半同步系统设计的一致性算法有机会工作。Raft，Viewstamped复制，Zab和Paxos在策略中都落实了。这样的算法是用来远离所有的时间假定的。这是困难的：保证网络是临时的，进程和时钟比他们自己还要确信。但是关于分布式系统的凌乱的认知，你不得不特别关心你的假定。